hboy
BAN USER- 0of 0 votes
AnswersArrayList A, B, C are sorted int arraylists.
- hboy in United States
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.| Report Duplicate | Flag | PURGE
Ebay Software Engineer / Developer Arrays
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--;
}
}
}
}
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 :)
Here is C# solution.
- hboy January 12, 2013