Google Interview Question for Software Engineers


Country: Switzerland




Comment hidden because of low score. Click to expand.
9
of 9 vote

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:

private static int findDuplicated(int[] array) {
        if (array == null || array.length < 1) {
            return -1;
        }
        int result = -1;
        for (int i = 0; i < array.length; i++) {
            if (Math.abs(array[i]) < 1 || array.length - 1 < Math.abs(array[i])) {
                result = -1;
                break;
            }
            if (array[Math.abs(array[i])] >= 0) {
                array[Math.abs(array[i])] = -array[Math.abs(array[i])];
            } else {
                result = Math.abs(array[i]);
            }
        }
        // Undo
        for (int i = 0; i < array.length; i++) {
            array[i] = Math.abs(array[i]);
        }
        return result;
    }

- tested.candidate July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- damluar July 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's really a nice solution, same with me. But it cannot handle uint32t, I think.

- malinbupt September 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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;
	}

- smarthbehl July 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- JoyZombie August 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- dark_horse August 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- dark_horse August 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

int temp=0;

while(true)
{
int next=a[temp];
if(next==-1)
return temp;
a[temp]=-1;
temp=next;
}

- Anonymous August 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- asdf1234qwertyzxcvbn August 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- asdf1234qwertyzxcvbn August 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- FullRetard August 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Sum of n positive integers = n(n+1)/2
In this case, we have to find it for n-1 since there are n-1 unique values.
Hence, for all unique values, sum will be (n-1)(n)/2.
Next, iterate through all elements in array and sum up, say sumVal.
Now duplicateVal = sumVal - (n-1)(n)/2 ;

- dada August 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- puneet.sohi July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- puneet.sohi July 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- puneet.sohi July 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 vote

Xor each number ofthe array, then XOR them with all the numbers from 1 to n-1. the result is your answer.

- sonesh July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Won't work if a value is duplicated more than twice. ie:
[1, 2, 2, 2, 4]

Would return 6.

- zortlord July 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ;

}

- Scott July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this question has an answer with o(1) memory and o(n) run time.
you could think on an index i as pointing on index a[i]. in this graph there is a circle and atlist one index out of the circle pointing in to the circle.

- lior July 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
                }              
            }
            
        }

- billu July 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
                }              
            }
            
        }

- billu July 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
                }              
            }
            
        }

- billu July 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int function(int arr[], int size)
{
    int actual;
    int num;
    
    for(int i=0;i<=size;i++)
    {
        int actual = arr[i] - (arr[i]/(size+1))*(size+1);
        arr[actual-1] = arr[actual-1]+(size+1);
    }
    
    for(int i=0;i<=size;i++)
        if(arr[i]/(size+1) > 1)
              return (i+1);
    return -1;
}

- skum July 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int function2(int arr[], int size)
{
    for(int i=0;i<=size;i++)
    {
        if(arr[i] < 0)
        {
            if(arr[-1*arr[i]] < 0)
                return -1*arr[i];
            arr[-1*arr[i]] =  -1*arr[-1*arr[i]];
        }
        else
        {
            if(arr[arr[i]] < 0)
                return arr[i];
            arr[arr[i]] =  -1*arr[arr[i]];
        }
            
    }
    return -1;
}

- skum July 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My approach would be simple:
Enter each element in a BST. Obviously, when you have a duplicate element, you can realize and add it to another array.

This would be a maximum of O(N), where N is the number of elements in the array.

- Tejas July 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)))

- Naman July 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- drake August 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This assumes there is only one duplicate pair, all other nums are unique.

- a August 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If there is only one duplicate in the array we do:
add all numbers between 1 to n = x
add all numbers in the array = y
subtract y from x : x-y = z;
The duplicated value will be n-z.

- Eugen Hotaj November 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

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;
}

- hnatsu July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- puneet.sohi July 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- caohongfei July 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hnatsu July 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi caohongfei, by far your answer is the best I love it, I checked your math and I think the formula is: array sum minus (N+1)N/2. I was thinking to improve my answer with a binary search but after this no way that is tunnel vision. Thanks for your comment.

- hnatsu July 15, 2015 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More