Google Interview Question for Interns


Country: United States
Interview Type: Phone Interview




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

Not sure if negative elements are also considered here. But, if we don't have them, then we can use 'negative sign' to keep track of the elements in the array.

consider A = [1, 2, 3, 1, 4]

for i = 0:
abs(A[0]) = 1, Now we will change sign of A[1] to -A[1]. Making A = [1, -2, 3, 1, 4]

Moving forward, if we encounter any element which already has negative sign, that is our repeated element. 

at i = 3, we will have abs[A[3]] = 1, but at this point A[abs[A[3]]] = A[1] is negative which means we have other element as 1.

for the case where element is 0, we can add a logic such that we will write 0 in A[0] if we encounter zero at all .

- amitexam November 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 vote

int repeatedArray(int *arr,int len)
{
    int i=0;
    for(i=0;i<len;i++)
    {
        int k = abs(arr[i]);
        arr[k] = -1 * arr[k];
    }
    for(i=0;i<len;i++)
    {
        if(arr[i]>0)
            return i;
    }
}

- rsingh November 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_duplicate(arr):
    for i in range(len(arr)):
        while arr[i] != i:
            if arr[arr[i]] == arr[i]:
                return arr[i]
            else:
                buf = arr[i]
                arr[i] = arr[arr[i]]
                arr[buf] = buf

    return None

- glebstepanov1992 November 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ce genre de question est de besoin d'un unique identifiant.

def return_dulicate(array):
	aux = []
	index = 1
	for c in array:
		if(index & (1<<c)>0):
			aux.append(c)
		index|=(1<<c)
	return aux

- Marouane BENALLA November 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If all values are positive integers then we can do this

public static void printDuplicates(int[] a) {
        for (int i = 0; i < a.length; i++) {
            if (a[Math.abs(a[i])-1] < 0) {
                System.out.print(Math.abs(a[i]) + " ");
            } else {
                a[Math.abs(a[i])-1] *= -1;
            }
        }
    }

- OctA November 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

If the array has size N, are all the numbers between 1 and N? Is the array read-only?

- wefgef November 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is an Objective-C solution in O(n) time and O(1) space, since the integers in the array are not greater than the size of the array we can use them as an index of the same array and mark each number in index as negative and then if we found that X number is already negative that is a duplicate number

-(void)findDuplicatesInArray:(NSMutableArray *)array{
    
    for(int i = 0; i < [array count]; i++){
        
        int temp = abs([array[i] intValue]);
        
        if([array[temp] intValue] >= 0){
            
            array[temp] = [NSNumber numberWithInt:-abs([array[temp] intValue])];
        }
        else{
            
            NSLog(@"%i", abs([array[i] intValue]));
        }
        
    }
}

- oscarsanchez1937 November 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Let a[i] be the value of an element in the array: 0 <= a[i] <= n and n be the #elements in a
2. k = #bits to represent 0..n: k = ceiling(log2(N))
3. m = #bits of the datatype, e.g. 32
4. if k < m: we have at least n bits we can use to store some information
5. let value(i) be the value of a[i] that only uses k bits: value(i): a[i]&((1<<k)-1)

so we can iterate over the array and extract the value of a[i] = value(i)
if a[i] != value(i) that is a dublicate we have found a dublicate
if not store in a[value(i)] = value(i) + (1<<(k+1)) (or value(i) + n, or anything like this...)

following thoughts are important:
1) this is theoretically not O(1) space but practically it is O(1) space: why, it uses bits that are allocated but not used
2) since the array is modified, it might be a good idea to revert the change in the array after finding a dublicate, especially if the function name does not imply modifications of the array
3) even if you do redo the changes, the array will temporarily be changed, so in production, this
will have side effects if concurrent access to the array happens.

this given we can do:

// returns -1 if no dublicate was found
int getAnyDublicate(vector<int>& a)
{
	int result = -1;
	if(a.size() <= 1) return result; 
	int k = static_cast<int>(log2(a.size() - 1) + 1.0);
	assert(k < numeric_limits<unsigned int>::digits);
	unsigned int datamask = (1 << k) - 1;
	unsigned int seenmask = (1 << (k + 1));
	for(int e : a)
	{
	 	int v = e & datamask;
		if(a[v] & seenmask != 0) { result = v; break; }
		a[v] |= seenmask;
	}
	for(int& e : a) e &= datamask; // revert all changes
	return result;
}

- Chris November 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] findDuplicates(int[] intArray){
		int arrLength = intArray.length;
		byte[] duplArr = new byte[arrLength];
		int dupCount = 0;
		for(int index=0; index<arrLength; index++ ){
			if( duplArr[intArray[index]-1] == 1) {
				duplArr[intArray[index]-1] = 2;
				dupCount++;
			}
			else if( duplArr[intArray[index]-1] == 0){
				duplArr[intArray[index]-1] = 1 ;
			}
		}
		int[] dupOutputArr = new int[dupCount];
		int outputArrIndex = 0;
		for(int index=0; index<arrLength; index++ ){
			if(duplArr[index] == 2){
				dupOutputArr[outputArrIndex] = index+1;
				outputArrIndex++;
			}
		}
		return dupOutputArr;
	}

- Sathish Kumar November 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] findDuplicates(int[] intArray){
		int arrLength = intArray.length;
		byte[] duplArr = new byte[arrLength];
		int dupCount = 0;
		for(int index=0; index<arrLength; index++ ){
			if( duplArr[intArray[index]-1] == 1) {
				duplArr[intArray[index]-1] = 2;
				dupCount++;
			}
			else if( duplArr[intArray[index]-1] == 0){
				duplArr[intArray[index]-1] = 1 ;
			}
		}
		int[] dupOutputArr = new int[dupCount];
		int outputArrIndex = 0;
		for(int index=0; index<arrLength; index++ ){
			if(duplArr[index] == 2){
				dupOutputArr[outputArrIndex] = index+1;
				outputArrIndex++;
			}
		}
		return dupOutputArr;
	}

- Sathish Kumar November 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] findDuplicates(int[] intArray){
		int arrLength = intArray.length;
		byte[] duplArr = new byte[arrLength];
		int dupCount = 0;
		for(int index=0; index<arrLength; index++ ){
			if( duplArr[intArray[index]-1] == 1) {
				duplArr[intArray[index]-1] = 2;
				dupCount++;
			}
			else if( duplArr[intArray[index]-1] == 0){
				duplArr[intArray[index]-1] = 1 ;
			}
		}
		int[] dupOutputArr = new int[dupCount];
		int outputArrIndex = 0;
		for(int index=0; index<arrLength; index++ ){
			if(duplArr[index] == 2){
				dupOutputArr[outputArrIndex] = index+1;
				outputArrIndex++;
			}
		}
		return dupOutputArr;
	}

- Sathish Kumar November 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Time: O(n)
// Space: O(1)
std::vector<int> arrayDuplicates(std::vector<int> &A)
{
std::vector<int> ret;
int processedMarker = A.size();

for (int i=0; i<A.size(); i++) {
if ( A[i] != i ) {
int newIndex;

while( A[i] != i ) {
if (A[i] == processedMarker || A[newIndex] == processedMarker )
break;

if (A[newIndex] == A[i]) {
ret.push_back(A[i]);
A[newIndex] = processedMarker;
A[i] = processedMarker;
break;
}

swap(A[i], A[newIndex]);
}
}
}
return ret;
}

- EmilFlater November 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Time: O(n)
// Space: O(1)
// It will not work if there are values in array < 0
// 0 case is handled fine
std::vector<int> arrayDuplicates(std::vector<int> &A)
{
    std::vector<int> ret;
    int processedMarker = A.size();
    
    for (int i=0; i<A.size(); i++) {
        if ( A[i] != i ) {
            int newIndex;
            
            while( A[i] != i ) {
                newIndex = A[i];
                if (A[i] == processedMarker || A[newIndex] == processedMarker )
                    break;
                
                if (A[newIndex] == A[i]) {
                    ret.push_back(A[i]);
                    A[newIndex] = processedMarker;
                    A[i] = processedMarker;
                    break;
                }
                
                swap(A[i], A[newIndex]);
            }
        }
    }
    return ret;
}

int main()
{
    vector<int> A{0,2,1,1,1,1,0,2};
    auto V = arrayDuplicates(A);
    for (auto v : V) {
        cout << v << endl;
    }
    return 0;
}

- EmilFlater November 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int missing(int[] arr){
	if(arr == null || arr.length == 0){
		throw new IllegalArgumentException();
	}
	
	for(int i = 0; i < arr.length; i++){
	
		while(arr[i] != i){
		
			int dest = arr[i];
			if( dest < arr.length && arr[dest] != dest){
				swap(i,dest,arr);
			}else{
				break;
			}
		}
	}
	for(int i = 0; i < arr.length; i++){
	
		if(arr[i] != i){
			return i;
		}
	}
}

private void swap(int a, int b, int[] arr){
	int tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}

- divm01986 November 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findDuplicates(int[] input)
	{
		if(input == null)
			return;
			
		for(int i = 0; i < input.length; ++i)
		{
			int s = Math.abs(input[i]);
			if(input[s] < 0)	//we have been here before...
			{
				System.out.println(s);
			}
			input[s] = -input[s];
		}
	}

- ohadr.developer November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not to consider sorting? In c# Sort is in-place.
1. Sort
2. Iterate through sorted array and return first duplicate.
Will handle 0 negative cases

public class Duplicate
    {
        public int? GetDuplicate(int[] arr)
        {
            Array.Sort(arr);
            int el_prev = arr[0];
            for (int i=1; i< arr.Length; i++)
            {
                if (el_prev == arr[i]) return el_prev;
                el_prev = arr[i];
            }

            return null;
        }
    }

- Anna December 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Minimal Coding.

def find_duplicate(x):
    index = -1
    for i in range(len(x)):
        if x[abs(x[i])] > 0: 
            x[abs(x[i])] = -1*x[abs(x[i])]
        else:
            index = i
    return index

x = [2,1,2,4,3]
print (find_duplicate(x))

- vishal.gupta4081 December 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a=[1,2,3,4,5,4,3,2,1,2,3,4,5]
b=[]
for i in range(0,len(a)):
    if (a[i] in a[:i-1]) and (a[i] not in b):
        b.append(a[i])
print b

- Samkit Patira October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a=[1,2,3,4,5,4,3,2,1,2,3,4,5]
b=[]
for i in range(0,len(a)):
if (a[i] in a[:i-1]) and (a[i] not in b):
b.append(a[i])
print b

- Samkit Patira October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int duplicate(vector<int>& integers) {
  unordered_map<int, int> visited_elements;
  unordered_map<int, int>::const_iterator locate;
  for(register size_t i = 0; i < integers.size(); ++i) {
    if((locate = visited_elements.find(integers[i])) == visited_elements.end()) {
      visited_elements[integers[i]] = i;
    } else {
      return integers[i];
    }
  }
}

int main() {
  vector<int> my_vec = {1, 2, 3, 2, 4};
  int repeated_integer = duplicate(my_vec);
  cout << "Repeated integer: " << repeated_integer << endl;
  return 0;
}

- Oleg Silkin May 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int duplicate(vector<int>& integers) {
  unordered_map<int, int> visited_elements;
  unordered_map<int, int>::const_iterator locate;
  for(register size_t i = 0; i < integers.size(); ++i) {
    if((locate = visited_elements.find(integers[i])) == visited_elements.end()) {
      visited_elements[integers[i]] = i;
    } else {
      return integers[i];
    }
  }
}

int main() {
  vector<int> my_vec = {1, 2, 3, 2, 4};
  int repeated_integer = duplicate(my_vec);
  cout << "Repeated integer: " << repeated_integer << endl;
  return 0;
}

- Oleg Silkin May 03, 2018 | Flag Reply


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