## Ebay Interview Question Software Engineer / Developers

• 0

ArrayList A, B, C are sorted int arraylists.

When A[i] + B[j] = C[k], you need to remove C[k] from ArrayList C.

Please implement code with O(N^2). Note that you are not allowed to use additional data structures such as arrays, hash tables, etc.

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 5 vote

``````For each index k in C :
Find index alim in A such that A[alim] <= C[k]
Find index blim in B such that B[blim] <= C[k]

left = 0
right = blim

-------while left <= alim and right >= 0 :
if A[left] + B[right] == C[k] :
Remove C[k] and break
else if A[left] + B[right] < C[k] :
left++
else :
right--``````

Complexity( O( (sizeA + sizeB)*sizeC ) ~ O*(n^2) )

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

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

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

It works fine. There was some indentation problem, now it's correct.

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

@Cerberuz: Thanks for that one.

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

@Cerberuz
Is this assignment correct
left = A[0]
right = B[blim]

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

No, thanks for pointing it out. Made the correction.

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

Nice.

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

what if arrays have negative values ?

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

can we use implicit functions of ArrayList like Contains() and Remove().....?

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

We can use ArrayList.Remove() only.

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

For each k in c
For each l in a
Use binary search to find k-l in b

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

order N^2 Log N

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

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

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

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

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

It seems like your solution would not remove any elements from C array. Also what is for nextMin?

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

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

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

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

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

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

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

@bdKeano You are not allowed to use an additional space in the question. :)

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

Oh shoot !! Just reread the question again. Sorry.

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

No solution in this post is correct!

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

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

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

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

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

O(n^3)

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

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

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

Hi MI,

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

@hboy this is the same solution written by some other people where u commented code is not working for some cases.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````//lenA,LenB,LenC are length of A,B,C
for(int k=0;k<lenC;k++)
int i=0,j=lenB-1;
while(i<lenA&&j>=0){
if(A[i]+B[j]==C[k])
remove(C[k]);
else if(A[i]+B[j]>C[k])
j--;
else i++;
}
}``````

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

Your solution is the exactly same with mine. But I found that our solutions will not solve the following input data. :)

List<int> A = new List<int> { 1, 2, 4, 6 };
List<int> B = new List<int> { 1, 3, 5, 8 };
List<int> C = new List<int> { 2, 3, 5, 8 };

Name:

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

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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