Interview Question for Interns


Country: India
Interview Type: In-Person




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

Let's say |A| = n+2 and |B| = n, and element to find are x,y
x+y = sum(A)-sum(B);
x*y = mul(A)/mul(B);

(x+y)^2 = x^2 + y^2 +2xy
Then find x,y

- RG February 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice idea, some modification:

x + y = Sum(A) - Sum(B)
   x^2 + y^2 = Sum(A[i]^2) - Sum(B[i]^2)

   Solve the equations to find x and y.

- Westlake February 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Plz give an example brother.. I am not getting this

- Anonymous February 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Instead of doing sum(a)-sum(b) ou can do sum(a[i]-b[i]) for i:0>n. The same for mul/mul. This way you avoid (in general)having a too large sum/mul number

- ryan.fly67 February 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It wont work when B has element(s) of value zero.

- Anonymous February 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question said elements not numbers or integers....

- Vineet August 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

For small integers array and small number of elements, sum/mul solution works pretty good.
But:
1) what if the you have lots of elements and the numbers are big, we will get overflow error
2) what if we canot apply sum/mul operations to the elements in the input arrays? For example, the array has some file names instead of integers.

proposed solution:
1) sort both array, and scan through to compare two arrays.
O(nlogn) time complexity.

- samuel February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Solution using difference of sum is nice but as pointed by samuel: what if the you have lots of elements and the numbers are big, we will get overflow error

proposed solution is:

1) Create a HashMap<K, V> where K = number and V = count occurences of number
2) loop through both arrays at the same time adding values and counts to Map
3) iterate over HashMap and print those elements where count = 1

Implementation in Java:

import java.util.HashMap;
import java.util.Map;

public class Solution {

public static void printMissingElems(int[] a, int[] b) {

    Map<Integer, Integer> mapCount = new HashMap<Integer, Integer>();    
    int i = 0;    
    int aLen = a.length;
    int bLen = b.length;
    int lenBiggest = aLen > bLen ? aLen : bLen;
    
    while (i < lenBiggest) {    
        if (i < aLen) {            
            addNum(mapCount, a[i]);            
        }
        if (i < bLen) {            
            addNum(mapCount, b[i]);            
        }        
       i++;
    }
    
    printDiffNums(mapCount);
}

public static void printDiffNums(Map<Integer, Integer> mapCount) {    
    for(Map.Entry<Integer, Integer> entry : mapCount.entrySet()){        
        if (entry.getValue() == 1) {
            System.out.println(entry.getKey());        
        }    
    }
}
     
public static void addNum(Map<Integer, Integer> mapCount, int num) {
    if (!mapCount.containsKey(num)) {
        mapCount.put(num, 1);
    } else {
        int count = mapCount.get(num);
        mapCount.put(num, count + 1);
    }
}

public static void runSampleTests() {
    int[] a = {1, 4, 8, 3, 15, 33, 92, 145, 25, 22, 29, 38, 73, 66, 71};
    int[] b = {1, 4, 8, 3, 15, 19, 33, 92, 145, 25, 22, 29, 38, 44, 73, 66, 71};
    
    printMissingElems(a, b);
}

    public static void main(String args[]) {
    	runSampleTests();
    }    
}

- guilhebl February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The solution seems good but will not work in case the extra two numbers are the same.

- Akshay February 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ashkay

How about if first array's members are ADDED to the HashMap while the second array's members are SUBTRACTED, then non-zero frequencies are the required output.

- Uwais August 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) time and O(N) space solution.

Let s1 has n+2 elements and s2 has n elements. We want to find two missing elements in s2.
[Step 1] Compute sum(s1) and sum(s2); while computing sum(s2) simultaneously build up a set(s2) from the elements in s2.
[Step 2] Compute sum_diff = sum(s1) - sum(s2)
[Step 3] Go through each element in s1, see if that number appears in the set(s2). If not, that element and sum_diff-element are the missing pair

void find_missing_pair(vector<int>& s1, vector<int>& s2)
{
	int sum_s1=0, sum_s2=0, sum_diff=0;	

	for(int i=0; i<s1.size(); i++)
		sum_s1 += s1[i];
	
	unordered_set<int> set_s2;	
	for(int i=0; i<s2.size(); i++) {
		set_s2.insert(s2[i]);
		sum_s2 += s2[i];
	}

	sum_diff = sum_s1 - sum_s2;
	for(int i=0; i<s1.size(); i++) {
		if( set_s2.find(s1[i])==set_s2.end() ) {
			printf("%d and %d missing!\n", s1[i], sum_diff-s1[i]);
			return;
		}
	}
}

- Anonymous February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think that the time complexity of this solution is O(n^2) as set_s2.find() method takes O(n) time to search the element.

- Akshay February 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Searching for each no. of S1 in setS2 itself takes the time complexity O(n)*n = O(n^2)

- lokesh6spark March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let Array A contain n elements
Let Array B contain n+2 elements
1. Find Sum(A) ==> O(N)
2. Find Sum(B) ==> O(N)
3. Sum(B) - Sum(A) ==> Gives u sum of the two missing numbers
4. Sort Array B ==> O(NlogN)
5. Use the algorithm to find pair of integers from sorted Array B that add up to difference in step 3 ==> O(N)

Complexity 3N + NlogN

- Amit February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How could you know there is only one pair resulting the same sum?

- Anonymous February 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes.. u r right.. my solution is incorrect.. thanks for pointing tht out friend

- Amit February 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in C++ (linear time) :

void printElements(vector<int> L1, vector<int> L2) {
    // Assumes L1 is the list with two additional elements
    int xored1 = 0, xored2 = 0,
        summed1 = 0, summed2 = 0;
    vector<int>::iterator it;
    for (it = L1.begin(); it != L1.end(); ++it) {
        xored1 ^= *it;
        summed1 += *it;
    }
    for (it = L2.begin(); it != L2.end(); ++it) {
        xored2 ^= *it;
        summed2 += *it;
    }
    int a, b;
    if ((xored1 ^ xored2) == 0) {
        a = (summed1 - summed2) / 2;
        b = a;
    } else {
        int i = 0;
        while ((xored1 ^ xored2) >> (i + 1)) {
            ++i;
        }
        xored1 = 0;
        xored2 = 0;
        for (it = L1.begin(); it != L1.end(); ++it) {
            if (*it & (1 << i))
                xored1 ^= *it;
        }
        for (it = L2.begin(); it != L2.end(); ++it) {
            if (*it & (1 << i))
                xored2 ^= *it;
        }
        a = xored1 ^ xored2;
        b = summed1 - summed2 - a;
    }
    cout << a << "," << b << endl;
}

- Thomas February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain the logic

- RG February 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sure, it uses the fact that a^(a^b) = b.

We have xored1 which is the xor of all the elements in first list (with the 2 extra elements) and xored2 the same for the second list. We also have both sums of the lists.

Then xored1 ^ xored2 = x1^x2 where x1,x2 are the extra elements. If this equals zero, it means that the two extra elements are the same, hence are equal to the difference between the two sums divided by 2.

Otherwise, it means that the 2 elements are different in a least one bit. We compute position i of the first different bit. We then take all elements in both list where the bit at position i is 1. There is exactly one element different between those two sublists which we can find easily. We deduce the other element from that and we are done.

- Thomas March 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindTwoExtraNumbers {

    public static void findExtras(int[] a, int[] b) {
        int xor = 0;
        for (int i : a) {
            xor ^= i;
        }
        for (int i : b) {
            xor ^= i;
        }

        // Let x and y be the two extras
        int x = 0, y = 0;
		
        // Create a mask containing one of orx's 1 bit. For convenience, 
	// the right most 1 bit is used here.
        int mask = xor & ~(xor - 1);

        // Go through all elements of the two arrays, and xor them to
        // either x or y, depending on their corresponding bit's value.
        for (int i : a) {
            if ((i & mask) != 0)
                x ^= i;
            else
                y ^= i;
        }
        for (int i : b) {
            if ((i & mask) != 0)
                x ^= i;
            else
                y ^= i;
        }
        System.out.println(x + " and " + y);
    }

    public static void main(String[] args) {
        int[] a = { 3, 25, 27, 54, 55, 62, 68, 85, 94, 95 };
        int[] b = { 3, 8, 25, 27, 54, 55, 61, 62, 68, 85, 94, 95 };
        findExtras(a, b);
    }
}

- Anonymous February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindTwoExtraNumbers {

	public static void findExtras(int[] a, int[] b) {
		int xor = 0;
		for (int i : a) {
			xor ^= i;
		}
		for (int i : b) {
			xor ^= i;
		}

		int x = 0, y = 0;
		
		// mask containing the right most set bit in the xor.
		int mask = xor & ~(xor - 1);

		// Go through all elements of the two arrays, and xor them to
		// either x or y, depending on their corresponding bit's value.
		for (int i : a) {
			if ((i & mask) != 0)
				x ^= i;
			else
				y ^= i;
		}
		for (int i : b) {
			if ((i & mask) != 0)
				x ^= i;
			else
				y ^= i;
		}
		System.out.println(x + " and " + y);
	}

	public static void main(String[] args) {
		int[] a = { 3, 25, 27, 54, 55, 62, 68, 85, 94, 95 };
		int[] b = { 3, 8, 25, 27, 54, 55, 61, 62, 68, 85, 94, 95 };
		findExtras(a, b);
	}
}

- Anonymous February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Use Hashset and all all values from A and B to it in a way:
a) If already present: delete
b) else add
2) If Hashset is non-empty, it will essentially contain two numbers. These are the two numbers that we are looking for.
2) If Hashset is empty, this means that the two numbers are the same. We can find out these numbers by subtracting the sums of the two arrays A and B and dividing the difference by 2.

- Abhinav February 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Java(N log N)

public class FindMissingElements {
	private static void swap(int a[], int i, int j)
	{
	    int t = a[i];
	    a[i] = a[j];
	    a[j] = t;
	}
	 
	/* This function takes last element as pivot, places the pivot element at its
	   correct position in sorted array, and places all smaller (smaller than pivot)
	   to left of pivot and all greater elements to right of pivot */
	private static int partition (int arr[], int l, int h)
	{
	    int x = arr[h];    // pivot
	    int i = (l - 1);  // Index of smaller element
	 
	    for (int j = l; j <= h- 1; j++)
	    {
	        // If current element is smaller than or equal to pivot 
	        if (arr[j] <= x)
	        {
	            i++;    // increment index of smaller element
	            swap(arr, i , j);  // Swap current element with index
	        }
	    }
	    swap(arr, i+1, h);  
	    return (i + 1);
	}
	 
	/* arr[] --> Array to be sorted, l  --> Starting index, h  --> Ending index */
	private static void quickSort(int arr[], int l, int h)
	{
	    if (l < h)
	    {
	        int p = partition(arr, l, h); /* Partitioning index */
	        quickSort(arr, l, p - 1);
	        quickSort(arr, p + 1, h);
	    }
	}
	private static int findOneNumber(int[] a, int[] b) {
		int x = 0;
		int len = 0;
		int i = 0;
		if(a.length > b.length) {
			len = b.length;			
			while(len > i) {
				if(a[i] != b[i])
					return a[i];
				i++;
			}
			if(len == i) return a[len];
		} else {
			len = a.length;			
			while(len > i) {
				if(a[i] != b[i])
					return b[i];
				i++;
			}
			if(len == i) return b[len];
		}
		return x;
	}
	private static int findOtherNumber(int[] a, int[] b, int oneNumber) {
		int sumA = 0, sumB = 0, diff = 0;
		for(int i = 0 ; i < a.length ; i++)
			sumA += a[i];
		for(int i = 0 ; i < b.length ; i++)
			sumB += b[i];
		diff = sumA - sumB;
		if(diff > 0) {
			return diff - oneNumber;
		} else {
			return -1 * diff - oneNumber;
		}
	}
	public static void main(String[] args) {
		int[] a = {1, 6, 8, 3, 16, 33, 192, 145, 25, 28, 29, 38, 73, 66, 71};
	    int[] b = {1, 6, 8, 3, 16, 19, 33, 192, 145, 25, 28, 29, 38, 44, 73, 66, 71};
	    int lenA = a.length;
	    int lenB = b.length;
	    quickSort(a, 0, lenA - 1);
	    quickSort(b, 0, lenB - 1);
	    int oneNumber = findOneNumber(a, b);
	    int otherNumber = findOtherNumber(a, b, oneNumber);
	    System.out.println(oneNumber + ", " + otherNumber);
	}

}

If there are any error or improvement, please let me know.

- RiponCoder March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this could also be an answer:
#include <stdio.h>
#include<conio.h>
#include<stdlib.h>
main()
{
//a[5], b[3];
int c,x,d,z,k[2],n1,n2,a[10],b[12];


printf("\nsize of array1\n");
scanf("%d",&n1);
printf("\nsize of array2\n");
scanf("%d",&n2);
printf("\nenter array 1\n");
for(c=0;c<n1;c++)
{
scanf("%d",&a[c]);

}
printf("\nenter array 2\n");
for(c=0;c<n2;c++)
{
scanf("%d",&b[c]);

}
for(c=0;c<n1;c++)
{
d=a[c];
for(x=0;x<n2;x++)
{
z=-1;
if(b[x]==d)
{
z=0;
break;
//continue;

}

else
{
z=d;
//printf("\n%d\n",z);
}

}
if(z!=0)
printf("\n%d\n",a[c]);



}
getch();
}

- Anonymous September 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Xor all the numbers (let call it xorSum)
2) If xorSum == 0 then val = (sum(A) - sum(B)) / 2
3) If xorSum != 0 then xor all the numbers that have 1 bit at the same position as xorSum. In that case we will xor only one of two missed numbers. And as a result we get the answer

- grtkachenko October 14, 2014 | 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