Google Interview Question
Software EngineersCountry: Switzerland
really nice solution, which leaves array as it was. I also came up with O(n) time, O(1) space solution, but I rely on swapping elements, which changes the array.
In an array of length N you have numbers in range 1 to n-1 , there will always be a duplicate by pigeonhole principle.
Now if you have to find one duplicate it is easy.
1.) Start with temp = 0; and do a while true loop
2.) If value at array[i]=-1 then i is the duplicate number and return.
3.) else
set temp = array[array[i]];
array[array[i]] = -1;
int temp=0;
//there will always be a duplicate by pigeonhole
while(true){
if(arr[temp]==-1) return temp;
temp = arr[arr[temp]];
arr[arr[temp]] = -1;
}
Its very difficult to understand to your logic considering the code, you've provided. Lets say we've 5 stored at 0th index
so arr[0] will give us 5
lets say, we've 10 stored at 5th index
so, temp = arr[arr[temp]] = 10
then, you are setting -1 as :-
arr[arr[temp]] = -1 , which will write -1 at index by two more levels of indirection, which doesn't help in anyway, I guess.
But I somewhat understood what you were trying to say, but actually couldn't come up with right algo using that approach,
Can you repost the correct version of what you were trying to do in first place?
I think the code posted above doesn't work as expected. Here's what it should look like:
int temp=true;
while(true)
{
int next=a[temp];
if(next==-1)
return temp;
a[temp]=-1;
temp=next;
}
I don't think the code posted here will work as expected. Here's what it should look like:
int temp=0;
while(true)
{
int next=a[temp];
if(next==-1)
return temp;
a[temp]=-1;
temp=next;
}
int temp=0;
while(true)
{
int next=a[temp];
if(next==-1)
return temp;
a[temp]=-1;
temp=next;
}
I don't think the solution posted above works as expected. Here's what it should look like:
int temp=0;
while(true)
{
int next=a[temp];
if(next==-1)
return temp;
a[temp]=-1;
temp=next;
}
I don't think the solution posted above works as expected. Here's what it should look like:
int temp=0;
while(true)
{
int next=a[temp];
if(next==-1)
return temp;
a[temp]=-1;
temp=next;
}
We can have two solution, one will use extra space for faster run time O(n), the other will not use extra space but take longer O(nlogn).
Say we have array A of numbers in range 0 - n-1
Soln 1: If we're allowed extra space. Create an binary array B of size n-1 and set all elements to false. Iterate through the array.
For each element in array A, use it to index into array B. If the element at arr B is false, set it to true. If it is true, means we
have a duplicate.
E.g. for elemnt 30 at index 27 in A, if B[30] == true, this means element 30 at index 27 is duplicate
Run time O(n)
Soln 2: If we're not allowed extra space: Sort the array.
Now iterate through the array and for each element, check its neighbors.
If a duplicate found, mark it and check the next neighbor and so on till you find a non duplicate number and repeat
Run time O(nlong n for sorting + n for subsequent iteration) = (nlongn)
Xor each number ofthe array, then XOR them with all the numbers from 1 to n-1. the result is your answer.
this could be achieved by O(n) using index sort
public int findDUP (int [] array){
for (int i = 0 ; i < array.length ;++i) {
int m = array[i];
while (m != array[m - 1]) {
swap (array, i , m - 1);
m = array[i] ;
}
}
for (int i = 0 ; i < array.length ;++i) {
if (array[i] - 1 != i) {
return array[i] ;
}
}
return 0 ;
}
First sort the array then perform modified version of Binary Search to look for a condition where current element is same as it's index and it's left side element is greater than 1 by it's index. TimeComplexity is N(Log(n)) + log(n)
class Program
{
static void Main(string[] args)
{
int[] myarry = {1,2,2,3};
Array.Sort(myarry);
printDuplidate(myarry,0,myarry.Length-1);
Console.ReadLine();
}
private static void printDuplidate(int[] myarry, int low, int high)
{
if(low > high)
{
Console.WriteLine("This array doesn't have any duplicate");
}
else
{
int mid = (low + high) / 2;
if(myarry[mid]==mid) //it can be on left side
{
if (mid - 1 >= 0 && (mid ) == myarry[mid - 1])
{
Console.WriteLine("Duplicate is "+myarry[mid]);
}
else
{
printDuplidate(myarry,low,mid-1);
}
}
else if(myarry[mid]==mid+1)
{
printDuplidate(myarry,mid+1,high);
}
}
}
class Program
{
static void Main(string[] args)
{
int[] myarry = {1,2,2,3};
Array.Sort(myarry);
printDuplidate(myarry,0,myarry.Length-1);
Console.ReadLine();
}
private static void printDuplidate(int[] myarry, int low, int high)
{
if(low > high)
{
Console.WriteLine("This array doesn't have any duplicate");
}
else
{
int mid = (low + high) / 2;
if(myarry[mid]==mid) //it can be on left side
{
if (mid - 1 >= 0 && (mid ) == myarry[mid - 1])
{
Console.WriteLine("Duplicate is "+myarry[mid]);
}
else
{
printDuplidate(myarry,low,mid-1);
}
}
else if(myarry[mid]==mid+1)
{
printDuplidate(myarry,mid+1,high);
}
}
}
class Program
{
static void Main(string[] args)
{
int[] myarry = {1,2,2,3};
Array.Sort(myarry);
printDuplidate(myarry,0,myarry.Length-1);
Console.ReadLine();
}
private static void printDuplidate(int[] myarry, int low, int high)
{
if(low > high)
{
Console.WriteLine("This array doesn't have any duplicate");
}
else
{
int mid = (low + high) / 2;
if(myarry[mid]==mid) //it can be on left side
{
if (mid - 1 >= 0 && (mid ) == myarry[mid - 1])
{
Console.WriteLine("Duplicate is "+myarry[mid]);
}
else
{
printDuplidate(myarry,low,mid-1);
}
}
else if(myarry[mid]==mid+1)
{
printDuplidate(myarry,mid+1,high);
}
}
}
We can create a new blank list for unique numbers of the list. While iterating the input list, check if the number found in the uninque_list then it must be duplicate, else unique and should be added to unique_list.
def find_duplicate(list_num):
unque_list,duplicate_list = [],[]
for number in list_num:
if number in unque_list:
print "duplicate number found - %s" % number
duplicate_list.append(number)
else:
unque_list.append(number)
return (unque_list,list(set(duplicate_list)))
Sample solution in C++
#include <vector>
#include <iostream>
using namespace std;
int findDuplicate(const vector<int>& v) {
double sum = 0;
for (const int num: v) {
sum += num;
}
double n = v.size();
sum -= ((n-1) * n) / 2;
return (int)sum;
}
int main() {
vector<int> v {1,2,3,3,4};
int duplicate = findDuplicate(v);
cout << duplicate << endl;
return 0;
}
I know there are N values and the values are from 1 to N-1 and there is a duplicate
After sorting the array I should expect:
1 is in index 0
2 is in index 1
3 is in index 2
And so on.
if N = 10 with no duplicate
1, 2, 3, 4, 5, 6, 7, 8, 9, _
if N = 10 with duplicate
1, 2, 3, 4, 5, 5, 6, 7, 8, 9
So the duplicate is the one that not correspond/match with the index
Like is a sort O(nlog(n))
public int FindDuplicate(int[] a)
{
Array.Sort(a);
for(int i=0; i < a.Length; i++)
{
if (a[i] != (i + 1))
return a[i];
}
return -1;
}
Ingenious solution hnatsu.
My only doubt about it is what if the numbers are not increasing linearly?
For instance: Range is 0 - 9, Numbers are {1,2,5,7,7,9} will your algorithm work?
If there is only one duplicate, the value will be the sum of the array minus (N-1)N/2. You don't have to sort the array in this case.
Hi puneet.sohi in that scenario this code will not work. What I understood from the problem the incoming data is in that way. maybe I understood wrong
Because all integers are positive and the array is long enough we can exploit the sign of the integer to mark which integer was encountered before:
- tested.candidate July 14, 2015