Ebay Interview Question Software Engineer / Developers

  • ebay-interview-questions
    0
    of 0 votes
    34
    Answers

    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.

    - hboy on December 29, 2012 in United States Report Duplicate | Flag
    Ebay Software Engineer / Developer Arrays

Country: United States
Interview Type: Phone Interview


Comment hidden because of low score. Click to expand.
2
of 6 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) )

- Cerberuz on December 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hboy on December 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Cerberuz on December 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Cerberuz: Thanks for that one.

- Piotrek on December 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on January 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Cerberuz on January 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice.

- Zagoritt on January 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if arrays have negative values ?

- mozh on November 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- cutie on December 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can use ArrayList.Remove() only.

- hboy on December 29, 2012 | Flag
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

- alex on December 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

order N^2 Log N

- MI on December 29, 2012 | Flag
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] .....

- Mr X on December 29, 2012 | Flag Reply
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;
}
}

- Mr X on December 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hboy on December 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Mr X on January 01, 2013 | Flag
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--;
            }
        }
    }
}

- hboy on December 30, 2012 | Flag Reply
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

- bdKeano on January 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hboy on January 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- bdKeano on January 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

No solution in this post is correct!

- Kevin on March 09, 2013 | Flag Reply
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+" ");
		}
	}

- Kevin on March 09, 2013 | Flag Reply
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));}
			}
		}
	}

- bling! on March 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n^3)

- sjp on March 26, 2013 | Flag
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;
	}

- Mani Kiran on September 27, 2013 | Flag Reply
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 };

- gleong on November 08, 2013 | Flag Reply
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.

- Sachin on December 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hboy on December 29, 2012 | Flag
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--

- MI on December 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hboy on December 30, 2012 | Flag
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--;
        }
    }
}

- hboy on December 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on December 30, 2012 | Flag
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++;
     }
}

- Anonymous on December 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hboy on December 30, 2012 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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