Amazon Interview Question Software Engineer / Developers
@gevorgk
Your logic is correct if we have an array of size n where n is the largest element in array.
But this is not the case, as novice has already given an example where size of array is 5 but the largest element is 7. when you will swap the elements your array will go out of bound.
Very nice..
What he is trying to achieve is to place number k in the k-1 of the array.
So, first check what the number in the 0 position. Move it to its right place and move the number in that position to 0 position. Repeat until you find a number that is < 1 or > N. Assume 1 is not there. in which case the zero position in the array will be -1.
This code will not work if there any duplicates in the array. It assumes that all the elements in the array are distinct. Atleast in the range 1 to n
@tito: it will work, there is check in the code for this case. In case if element value is larger than array size, I put -1
@Ravi: You got it man !!! :)
What is the problem with duplicates ? Every duplicate element goes to it's origin index, no problem.
@ALL: Please, don't be lazy and compile and try the code with your examples before commenting :)
Your code will not work. For example:
if I have an array , A[] = {7}
size of array is 1. Missing elements are 1 to 6.
output of your program is 1 is missing.
@tito: In your example size of array A[]={7} is 1. How in array of size 1 could be 1..6 missing elements ??????
How do you decided that there should be 6 elements and not 1274 for example ????
the same reason you are saying 1 and 4 are missing in array A[]={3,2,6,5,7}.
run your code of A[]={3,2,4,5,7}. Ideally it should give you 1 and 6 are missing. but you get 1 is missing.
@gevorgk
My bad I was thinking the range of natural number is between
1 and max number in array. If the range is between the 1 and size of array then your code is absolutely correct..
a small doubt ...
consider an array like { 5, 6, 3, 2,9,10,11,13,7}
The length of the array is 9. according to the solution given above if value is greater than n ( here say 9) we just mark that position as -1. Thus positions corresponding to missing numbers will be -1. Since array length is 9, numbers missing till 9 can be detected. But in the above array even 12 is missing. Dont we need to detect this missing number? Or i missed something?
gevorgk's logic and code runs very well, but pls shed some light on the APPROACH,the cases considered,and the CONSTRUCTION OF ALGO
The logic is pretty simple - I'm putting every element to corresponding index, e.g. put 3 to index 3, 5 to index 5 e.t.c. If element is greater than the size of array - put -1. And finally just check array for elements equal to "-1".
@gevogrk i am not able to understand a[k] = a[a[k]-1]
a[k]= -1
if array is {5,2,3,1,5} range-1-5
a[0]=5;
a[0]-1=4
a[4]=5
a[0]=a[4] then a[0] = -1
but 1 is not missing
are the K elements consecutive ?
eg.
from unsorted array of 1,2...15
elements 4,5,6 are missing
Need not be always,Missing K elements could be spread across the N elements. An array of size 5 ideally can contain natural elements 1 to 5 in index pos 0 to 4. But in this case some elements are missing and in those positions natural numbers higher than 5 are occupied. Like A[]={3,2,6,5,7}
Answer for this case should be like 1,4.
Definitely a nice algorithm gevorgk !! the original Question doesn't speak about duplicates. Hence i think this algo gives the right solution! :-)
How can you say that, please test it by this example:
4572186, the missing one is 3, but your method gets 6
Write a simpler Version
Here i am assuming numbers between 0 and n-1 [to avoid zero based index confusion]
Written in c#
public static void findMissing(int[] num,int n)
{
for (int i = 0; i < n; i++)
{
while (num[i] != i)
{
int cur = num[i];
if (cur == num[cur])
break;
num[i] = num[cur];
num[cur] = cur;
}
}
for (int i = 0; i < n; i++)
{
if(i!=num[i])
Console.Write(i);
}
}
Writen a simpler Version
Here i am assuming numbers between 0 and n-1 [to avoid zero based index confusion]
Written in c#
public static void findMissing(int[] num,int n)
{
for (int i = 0; i < n; i++)
{
while (num[i] != i)
{
int cur = num[i];
if (cur == num[cur])
break;
num[i] = num[cur];
num[cur] = cur;
}
}
for (int i = 0; i < n; i++)
{
if(i!=num[i])
Console.Write(i);
}
}
<pre lang="java" line="1" title="CodeMonkey41137" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Hashtable;
import java.util.List;
import java.util.Scanner;
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
Main m= new Main();
ArrayList<Integer> mn=m.findMissingConsecutiveNumbers(new int[]{11,7,6,0,9,0,5});
for(Integer i: mn)
System.out.println(i);
}
//To find the missing numbers in a sequence of numbers
//Assuming that min is present and 0 as a sentinal element(the sequence will never have zero)
//Also that the array has enough space for missing elements
//eg: 10,8,9,5 are the numbers I am assuming there is empty space for 2 elems (6 and 7) at the end
//If I dont make this assumption I can't do it in place and in O(n) time
public ArrayList<Integer> findMissingConsecutiveNumbers(int[] numbers)
{
//Idea is to first find the minimum element and use it at the lowest index
int min=numbers[0],index=0;
ArrayList<Integer> missingNumbers=new ArrayList<Integer>();
//Find min element
for(int i=1;i<numbers.length;i++)
{
if(numbers[i]!=0&& min>numbers[i]){
min=numbers[i];
index=i;
}
}
//Put the min element at first
swap(numbers,0,index);
//Put the elements in their correct positions
for(int i=1;i<numbers.length;i++)
{
if(numbers[i]!=0 && numbers[i] != min+i){
swap(numbers, i,numbers[i]-min);
i--;
}
}
//Find the missing elements and add them to a list
for(int i=1;i<numbers.length;i++)
{
if(numbers[i]==0)
missingNumbers.add(i+min);
}
return missingNumbers;
}
private void swap(int[] ar, int i, int j) {
int temp=ar[i];
ar[i]=ar[j];
ar[j]=temp;
}
}</pre><pre title="CodeMonkey41137" input="yes">1
2
10
42
11
</pre>
// i have used extra space but have ensured tat TC: O(n)
// but it has a couple of limitations, i have set d size of d Dynamivally allocated block to 100..
#include<stdlib.h>
#include<stdio.h>
void abc(int a[],int n)
{
int *count = (int *)calloc(sizeof(int),100 );
int i;
for(i=0;i<n;i++)
{
count[a[i]]=a[i];
}
for(i=1;i<=n;i++)
{
if(count[i]==0)
printf("%d\t",i);
}
}
int main()
{
int a[] = {10,1,4,2,7,6,9,15,20,60};
abc(a,10);
return 0;
}
O(n) solution with using just 2 extra variables. Uses similar logic like @gevorgk
void FindMissing(int a[], int n)
{
int i, k;
i = 0;
while( i < 7 )
{
if (a[i] != (i + 1))
{
if (a[i] >= n)
{
a[i] = -1;
}
else
{
k = a[a[i] - 1];
a[a[i] - 1] = a[i];
a[i] = k;
}
}
if (a[i] == (i + 1) || a[i] == -1)
{
++i;
}
}
for (i = 0; i < n; ++i)
{
if (a[i] != (i + 1))
{
printf("%d,", i + 1);
}
}
}
The following is the easiest perfectly working code
class Missing
{
static void findMissing(int a[],int N)
{
for(int i=0;i<a.length;i++)
a[(a[i]-1)%(N+1)]+=N+1; //array modified
for(int i=0;i<a.length;i++)
{
if(a[i]<N+1)
System.out.println((i+1)+" is missing");
a[i]=a[i]%(N+1); //array restored
}
}
public static void main(String args[])
{
java.util.Scanner sc=new java.util.Scanner(System.in);
int x;
System.out.println("Enter the array size");
x=sc.nextInt();
int[] arr=new int[x];
for(int i=0;i<x;i++)
{
System.out.println("Enter the values");
arr[i]=sc.nextInt();
}
findMissing(arr,arr.length);
}
}
Please tell me if I am wrong. This work o(n) complexity. It needs a hash table for storing the missing elements.
This will print all missing numbers and all repeated numbers.
class Program
{
public static int[] arr;
public static Hashtable missingKArr=new Hashtable();
static void Main(string[] args)
{
arr = new int[30] { 29,29,29,8, 3, 1, 9, 10, 8, 9, 12, 2, 13, 13, 14, 11, 12, 0, 15, 16, 19, 21, 25, 26, 2, 13, 14, 11, 12, 0 };
//missing numbers 4,5,6,7,17,18,20,22,23,24,27,28,
MissingKElements(30);
Console.Read();
}
public static void MissingKElements(int n)
{
for (int i = 0; i < n; ++i)
{
if (arr[i] != i)
{
Swap(i);
}
}
for (int i = 0; i < n; ++i)
{
if (arr[i] != i)
{
//if the missing number found, then replace it to the position.
//then remove from hashtable
if (missingKArr.ContainsKey(i))
{
arr[i] = i;
missingKArr.Remove(i);
}
else
{
//this is missing
missingKArr.Add(i, 1);
}
if (arr[arr[i]] != arr[i])
{
Swap(i);
if (missingKArr.ContainsKey(i))
{
arr[arr[i]] = arr[i];
missingKArr.Remove(i);
}
}
}
}
//here prints all missing numbers and repeated numbers
for (int i = 0; i < n; ++i)
{
if (arr[i] != i)
{
Console.Write(i+" "+'\n');
Console.Write(" repeated number " + arr[i]);
}
Console.WriteLine();
}
}
private static void Swap(int i)
{
int temp1 = arr[i];
int temp2 = arr[temp1];
arr[temp1] = temp1;
arr[i] = temp2;
}
}
}
Here is the code that takes care of duplicates as well. Complexity O(n). If swap() is done inline, it will take only 1 extra space (int tmp). Plus 1 for 'int i' and plus 1 for 'int size'. So not more than 3 variable used. :-)
#include <stdio.h>
void swap(int *a, int *b)
{
int tmp = *a; *a = *b; *b = tmp;
}
void find_missing(int *a, int size)
{
int i = 0;
for (i=1; i<=size; i++) {
while (a[i-1] != -1 && a[i-1] != i && a[a[i-1]-1] != a[i-1]) {
swap(&a[i-1], &a[a[i-1]-1]);
}
}
for (i=0; i<size; i++)
if (a[i] != i+1)
printf("%d ", i+1);
}
int main()
{
#define SIZE 12
/* array with enough space for n elements
extra space padded with -1*/
int a[SIZE] = {6,4,9,4,5,8,3,11,-1,-1,-1,-1};
find_missing(a, SIZE);
}
You can find out the cycle or loop in a single linked list by using two pointer approach.
Below link can be useful to find out the algorithm to find cycle or loop in linked list
<a href="newtechnobuzzz.blogspot.in/2014/07/how-to-find-loops-or-cycles-in-linked.html">Find out loop or cycle in linked list in java</a>
newtechnobuzzz.blogspot.in/2014/07/how-to-find-loops-or-cycles-in-linked.html
- gevorgk June 08, 2010void printMissing(int arr[], int n) { for (int i = 0; i < n; ++i) { int k = i; while(arr[k] != (k+1)) { if( arr[k] < 1 || arr[k] > n || arr[k] == arr[arr[k] - 1] ) { arr[k] = -1; break; } std::swap(arr[k], arr[arr[k] - 1]); } } for (int i = 0; i < n; ++i) { if(arr[i] < 0 ) std::cout << i+1 << " is missing" << std::endl; } }