This is very important pattern for Amazon, Google and facebook
import java.util.Arrays;
public class Cycle {
public static void main(String[] args) {
int[] arr = { 3, 2, 1, 4 };
cycle(arr);
System.out.println(Arrays.toString(arr));
}
static void cycle(int[] arr) {
int i = 0;
while (i < arr.length) {
int correct = arr[i] - 1;
if (arr[i] != arr[correct])
swap(arr, i, correct);
else
i++;
}
}
static void swap(int[] arr, int first, int second) {
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
}
Asked in Amazon, Google and Mircosoft
class Solution {
public int missingNumber(int[] nums) {
int i = 0;
while(i<nums.length){
int correct = nums[i];
if(nums[i] <<nums.length && nums[i]!= nums[correct]){
int temp = nums[i];
nums[i] = nums[correct];
nums[correct] = temp;
}
else
i++;
}
// search for first missing number
i=0;
while(i<nums.length){
if(nums[i]!=i){
return i;
}
i++;
}
return nums.length;
}
}
Q → 448. Find all numbers disappeared in an array
google question
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
int i = 0;
while (i < nums.length) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct]) {
swap(nums, i, correct);
} else {
i++;
}
}
// just find missing numbers
List<Integer> ans = new ArrayList<>();
for (int index = 0; index < nums.length; index++) {
if (nums[index] != index + 1) {
ans.add(index + 1);
}
}
return ans;
}
static void swap(int[] arr, int first, int second) {
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
}
Q → Find the Duplicate Number
asked in mircosoft and amazon
class Solution {
public int findDuplicate(int[] nums) {
int i = 0;
while (i < nums.length) {
if (nums[i] != i + 1) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct]) {
swap(nums, i, correct);
} else {
return nums[i];
}
} else
i++;
}
// just find missing numbers
for (int index = 0; index < nums.length; index++) {
if (nums[index] != index + 1) {
return nums[index];
}
}
return -1;
}
static void swap(int[] arr, int first, int second) {
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
}
Q → Find all duplicates in an array
class Solution {
public List<Integer> findDuplicates(int[] nums) {
int i = 0;
while (i < nums.length) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct]) {
swap(nums, i, correct);
} else {
i++;
}
}
// just find missing numbers
List<Integer> ans = new ArrayList<>();
for (int index = 0; index < nums.length; index++) {
if (nums[index] != index + 1) {
ans.add(nums[index]);
}
}
return ans;
}
static void swap(int[] arr, int first, int second) {
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
}
class Solution {
public int[] findErrorNums(int[] nums) {
int i = 0;
while (i < nums.length) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct]) {
swap(nums, i, correct);
} else {
i++;
}
}
// just find missing numbers
for (int index = 0; index < nums.length; index++) {
if (nums[index] != index + 1) {
return new int[] {nums[index], index+1};
}
}
return new int[] {-1, -1};
}
static void swap(int[] arr, int first, int second) {
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
}
Q → 41. First Missing Positive
asked in amazon
class Solution {
public int firstMissingPositive(int[] nums) {
int i = 0;
while (i < nums.length) {
int correct = nums[i] - 1;
if (nums[i]>0 && nums[i] <= nums.length && nums[i] != nums[correct]) {
swap(nums, i, correct);
} else {
i++;
}
}
// just find missing numbers
for (int index = 0; index < nums.length; index++) {
if(nums[index] != index+1)
return index + 1;
}
return nums.length+1;
}
static void swap(int[] arr, int first, int second) {
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
}