## Interview Question for Interns

• 0

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

Comment hidden because of low score. Click to expand.
0

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.``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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.

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) {
}
if (i < bLen) {
}
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();
}
}``````

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.

Comment hidden because of low score. Click to expand.
0

@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.

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

Can you explain the logic

Comment hidden because of low score. Click to expand.
0

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.

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

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

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:
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.

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.

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

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

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.

### 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.