Ebay Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Hi Cerberuz,
It seems like your solution cannot remove 3 element in C.
A = { 1, 3, 4, 6 };
B = { 1, 2, 5, 8 };
C = { 2, 3, 5, 8 };
Since all three lists are sorted, I'll assume they are in ascending order, we can traverse A and B from minimum sum possible to the maximum possible sum. For each value of sum we can check the value in C for a possible match . For eg:
A = 1, 4, 6, 8
B = -2, -1, 0, 1
min sum = A[0] + B[0] match this with C[0],if sum is grater then C[0] the we will match with C[1] and so on till sum < c[x]
next min = A[1] + B[0] or A[0] + B[1] int this case A[0] + B[1] match this with C[x] if sum is larger the increase x.
next min = A[1] + B[0] or A[0] + B[2] .....
Pseudo Code to traverse from min sum to max sum, assuming all three lists are of size N
int a = 0, x = 0, b = 0, y = 0;
while( itr < N*N)
{
if(A[a] + B[x] <= A[y] + B[b])
{
x++;
nextMin = A[a] + B[x]; // Match this with next min in C
}
else
{
y++;
nextMin = A[y] + B[b]; // Match this with next min in C;
if(a ==y)
{
y++;
}
if(b==x)
{
x++;
}
if(x == N)
{
x = 0;
}
if(y == N)
{
y = 0;
}
}
It seems like your solution would not remove any elements from C array. Also what is for nextMin?
This is just the pseudo code to traverse arrays A and B from their minimum possible sum to maximum possible sum.I have left out the code to remove elements from C since it's straight forward in the manner I described in my previous comment.
If we asssume A and B are of size N then there would be total of N*N possible sums. Each iteration of above pseudo code will calculate one such sum such that it is grater then the sum calculated in previous iteration. The variable to store the sum calculated in each iteration is named as nextMin
Here is my solution! Note that we need a reverse loop for C array.
// Find the sum A[i] + B[j] and compare it with K
// - if A[i] + B[j] == K we have found the pair A[i] and B[j]
// - if A[i] + B[j] < K, we need to increase the sum, so increment i.
// - if A[i] + B[j] > K, we need to decrease the sum, so decrement j.
public static void Remove(List<int> A, List<int> B, ref List<int> C)
{
for (int k = C.Count-1; k >= 0; k--) // Reverse loop for removing elements in array correctly.
{
int i = 0, j = B.Count - 1;
while (i < A.Count && j >= 0)
{
if (A[i] + B[j] == C[k])
{
C.RemoveAt(k);
break;
}
else if (A[i] + B[j] < C[k])
{
i++;
}
else
{
j--;
}
}
}
}
how bout entering all the values of C in a hashset. it will remove all the duplicates but that should not be a problem. Then run 2 for loops and for every A[i] + B[j] .. try adding it to the hash set ... if it returns false remove it from the array ... this solution might only work with java
public static void remove(int[] A, int[] B, LinkedList<Integer> C) {
if (A == null || B == null || C == null) {
return;
}
for (int i = 0; i < C.size(); i++) {
boolean flag = false;
int ptrA = 0;
int ptrB = B.length - 1;
while (ptrA < A.length && ptrB >= 0) {
if (A[ptrA] + B[ptrB] == C.get(i)) {
C.remove(i);
flag = true;
i--;
break;
} else if (A[ptrA] + B[ptrB] < C.get(i)) {
ptrA++;
} else {
ptrB--;
}
}
if (flag == false) {
ptrA = A.length - 1;
ptrB = 0;
while (ptrB <B.length && ptrA >= 0) {
if (A[ptrA] + B[ptrB] == C.get(i)) {
C.remove(i);
i--;
break;
} else if (A[ptrA] + B[ptrB] < C.get(i)) {
ptrB++;
} else {
ptrA--;
}
}
}
}
for(Integer i:C){
System.out.print(i+" ");
}
}
static void foo(ArrayList<Integer> a,ArrayList<Integer> b,ArrayList<Integer> c)
{
for (Integer x:a)
{
for (Integer y:b)
{
if (c.contains(x+y))
{c.remove(c.indexOf(x+y));}
}
}
}
Actually you can solve the problem in O(N). by taking care of the sorted property. This program loops through each of the arrays exactly once. thus total cost = O(3N) = O(N)
i am going to use C# here
int i=0, j=0, k=0;
List<int> newArray = new List<int>();
while((i<N || j<N)&&k<N)
{
if(A[i] + A[j] < A[k])
{
if(i = N-1)
{
j++;
}
else if(j == N-1)
{
i++;
}
else if(A[i+1]+B[j] < A[i]+B[j+1])
{
i++;
}
else
{
j++;
}
}
else if(A[i]+B[j] == C[k])
{
// dont make a copy - equivalent to delete
k++;
}
else
{
newArray.Push(C[k]);
k++;
}
return newArray;
}
while (i < A.size() && j < B.size()&& k < C.size())
{
if (A.get(i)+ B.get(j) == C.get(k))
{
C.remove(k);
}
else if (A.get(i)+ B.get(j) > C.get(k))
{
k++;
}
else
{
if (A.get(i)< B.get(j))
{
i++;
}
else if (A.get(i) > B.get(j))
{
j++;
}
else
{
//when A[i] == B[i], compare A[i+1] and B[j+1]
if ((i <= A.size()-2) && (j <= B.size()-2) )
{
if (A.get(i+1) < B.get(j+1))
{
i++;
}
else
{
j++;
}
}
else if (i <= A.size()-2)
{
i++;
}
else
{
j++;
}
}
}
}
Based on the value of A[i] and B[j], we increase i or j depending on which value is smaller. It will address of issue:
A = { 1, 2, 4, 6 };
B = { 1, 3, 5, 8 };
C = { 2, 3, 5, 8 };
A solution if we are allowed to merge the lists A and B together.
If we can merge A and B into a single sorted arrayList in linear time. (using the merge function of the merge sort). Once done, there is a standard algorithm to find if there are 2 elements in a sorted array whose sum is a number 'x', again in linear time. By maintaining pointers to the first and last elements in the sorted array, move the left pointer forward if sortedArray[left] + sortedArray[right] < x, else move the right pointer backward.
So this would consume linear space, and do the removal in linear time. Doing it for all elements in C would take quadratic time.
If we merge A and B into a single sorted array, we can't calculate sum of A and B using the single sorted array. For example,
A = { 1, 2 }
B = { 4 }
C = { 3, 5, 6 }
In this case, C arraylist should be { 3 } because 1 + 4 = 5 and 2 + 4 = 6.
But with your mergerd single array { 1, 2, 4 }, your C arraylist will be null. Also, you are not allowed to use additional arrays :)
For Each element i in C.
First ptr to first element of A
Second Ptr to last element of B
if(ptrA + PtrB) == i
print value
else if sum < i;
ptrA++
else
PtrB--
I wrote solution with C#.
for (int k = 0; k < C.Count; k++)
{
int i = 0, j = B.Count - 1;
while (i <= A.Count - 1 && j >= 0)
{
if (A[i] + B[j] == C[k])
{
C.RemoveAt(k);
break;
}
else if (A[i] + B[j] < C[k])
{
i++;
}
else
{
j--;
}
}
}
Complexity( O( (sizeA + sizeB)*sizeC ) ~ O*(n^2) )
- Cerberuz December 29, 2012