Google Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
Approach:
1). QuickSort the list
2). Find out the max position (say p) where it's just less than or equal to K
3). Loop through the list starting at (P) backward. Find the difference between the current indexed number and K (say q). Use binary search to find the max (say t) position of q. Then combine everything below t and p to add to the answer set.
Sample data:
List: 1, 3, 5, 9, 20, 28, 30, 37, 60, 100
K: 50
So, the max position of p is at 37. Now, we loop through the list backward, 37 +30 <= 50? No. 37 + 28 <= 50? No. 37 + 20 <= 50? No. 37 + 9 <= 50? Yes. Then combine everything below 9 and 37.
pseudo code:
quicksort(list)
int p = binarysearch_max_position(k, list.length)
// p is the max position where it's just less than or equal to k in the list
for (i=p; i>=0; i--) [
x = list(i);
d = k - x;
// d is the difference in between k and x
j = binarysearch_max_position_helper(d,i)
// find the max position where j can exist
// since everything below j is less than j
// that it means position [0 to j] can be
// added to x and still be less than or equal
// to k
(if j != -1) {
all_combination_generator(j,i);
}
}
private void all_combination_generator(int i, int j) {
for (int x = i; x>=0; x--) {
answerset.add(j,list[x]);
}
}
Is this o(nlogn)?
I don't get it. What do you mean by "combine everything below 9 and 37" in the example? You mean (9, 37), (5, 37)... ? But (20, 28) also is an answer.
And why do you need quicksort if you want numbers less than K? It needs just one pass of the array. Pick the number if it is less than or equal to K. Otherwise, not.
It is O(n).
Sorry that my statement caused some confusion. When I say "combine everything below 9 and 37", I should have said combine (everything below 9) and 37. In that example, 50 - 37 => 13. In the sorted array, we can find that 9 is max number below 13. With that, we know for sure that everything below 9 can be combined with 37 and be the answer, and everything above 9 isn't an answer with 37. The logic is to do a binary search to determine which set can be combined with this number.
As for your second question, the quicksort is just to put the list into a sorted order. For the second part, sorry that I am not sure if I get your solution. It sounds like you are just picking one number, but the question is asking for a pair of number. If you don't sort it, you can not do binary search. Again, apologize if I don't quick get your suggestion.
Hope this helps.
I just re-read my solution. Just to clarify (which I think that's what your question is at)
1). QuickSort the list
2). Find out the max position (say p) where it's just less than or equal to K
This is done so that we know where we should begin the loop backward.
In my example. (We need #1 to do this sorting because the question doesn't mention that the list is sorted)
List: 1, 3, 5, 9, 20, 28, 30, 37, 60, 100
K: 50
#2 is to find out the index at 37. With that, we can eliminate whatever that's on the right hand side of 37 since they are bigger than K by itself.
Actually, this is a good point as I typed it. The question didn't say that the number is all positive. My solution would work with assumption of all integers in the list being positive, but if it can be negative, then it's more complicated...
The question said it is a list, how can we quick sort a list? And how to random access the list?
Ha, good catch. Not sure if the interviewer's question was meant for linked list, arraylist or just a generic term for a loose data structure. If we don't have space constraint and this is really a "list", we can first convert this list to an array first which is o(n) and it doesn't affect the overall running time. I guess it's one of those assumptions can be cleared in the interview (same goes for if these integers are all positive).
If Sample data:
List: 1, 3, 5, 9, 20, 28, 30, 37, 45, 60, 100
K: 50
Then what will be the max position of p?
Ripon, the P would be at index of 45 since that's the max number in the list less than K (50).
Jeremy, I think the question didn't specify this, so it's definitely one of the assumptions that should be asked and clarified. It would be an added on requirement which can be asked once you have a solution for positive number. If negatives are allowed, then it's more complicated problem (with constraint of doing less than O(n^2))
I came up with same solution as @alex.
For negative numbers just change the pointer to be the first value <= k-min value in list.
Say k is 5, Sorted list: -2, -1, 2, 4, 6, 7, 8
Start pointer at first value <= (5--2=7) , and generate pairs moving left starting at second pointer (-1)
so (7, -2),
(6,-1)
and so on
Instead of carrying binary search every time (in a list where we cant jump to a node directly) and reverse traversing the sorted list, you can :
a. Sort list
b. Say first node is min. Find maximum node, max,. s.t. min + max <= K. Push each and every node including it on to a stack.
c. start traversing from first node. Say cur val is cur and it is the ath node (starting from 0th as the first node). Pop stack until cur + popped value <= K. pairCount += no. of stacked element - a (No. of pairs cur makes that are <= K).
1) Scan all elements and store all elements <= k in an array A O(n)
2) Sort this array. Let the total elements be e O(e*loge) in descending order
3) For i from 1 to e/2
d = k-A[i]
Do a binary search in this array to find the position of d. Output pairs A[i] and all A[j<=d]
Total complexity O(n) + O(e*loge)
doesn't print out pairs A[i] and all A[j<=d] O(d)?
therefore your last step would be O(e*d)
how about a modified version of a count sort where n is the number of records, and a is the array, if we assume that 0 <= a[0:n] <= m, we allocate a new array b of size m that stores the sorted array, and a Hash Set of capacity m that stores an ADT called Solution,
The Solution ADT is a pair of integers, a and b, the idea is that a + b <= k, and more solutions can be from the fact that all Solution(a, 0...b) and Solution(0...b) are also solutions
At the end we will have a Set of Solutions
pseudocode:
for i in 0...n {
b[a[i]] += 1;
if(b[a[i]]) > 0 {
solutions.add(new Solution(b[a[i]], k - b[a[i]]));
}
}
solutions = expandSolutions(solutions);
space complexity would be O(2m)
time complexity would be O(n + expandSolutions) = O(n + k^2)
if k is <<< n then the whole thing could run in O(n)
Can we use hashmap here?
like we can scan the list for numbers less than or equal to k and store it in hashmap (n, k-n). After putting all the elements we can just scan through the hash map and for each key, we will just have to check if the value is present in the key set. If yes then consider that to be the pair and continue with other keys.
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[] = {3, 1, 4, 2, 9, 10, 33, 42, 2, 0, 6};
int N = sizeof(a) / sizeof(*a);
sort(a, a + N);
for(int x=0 ;x<N;x++)
{
cout<< a[x]<<" , ";
}
cout<<endl;
int K = 12;
int i = 0;
int *t = std::upper_bound(a, a + N, K - a[0]);
int j = t-a-1;
cout<< *t << " "<< *a<<" "<<j<<" "<<endl;
while (i < j) {
for (int k = i + 1; k <= j; k++)
cout << "(" << a[i] << ", " <<a[k] << ") ";
i++;
while (a[i] + a[j] > K && i < j) {
j--;
}
}system("pause"); }
I would approach it that way:
1. Sort the list in ascending order with nLogn (e.g. QuickSort)
2. Allocate two indexes––smaller and bigger (at the beginning smaller points to the first element of the list and bigger points at the last element)
3. Make a while loop with a termination condition smaller != bigger. Now compute the sum list(smaller)+list(bigger). If it is greater than k, there's no need to find the sums of the rest elements with bigger, so decrement bigger by 1 and continue to the beginning of the loop.
Else if the sum is smaller or equal to k, print out smaller paired with each of the rest of the elements. Increment smaller by 1 and continue to the beginning of the loop.
I have a simple solution in O(nlogn). First sort the list of numbers. Then iterating from starting (i=1 to n). Do a modified binary search for the remaining n-i+1 elements with l=i ,r=n and find the element of index with floor (k-a[i]). No_of_pairs+= g-i+1.
Please comment if there's any error with the logic.
Why do we need O(n^2log(n)) to solve this ??
Even the brute force solution, where we simply produce all the pairs and check if their sum is <k or not is O(n^2)
I don't believe that we can solve this problem in anything less than O(n^2) because in worst case sum of elements for all the pairs will be <k and there are O(n^2) pairs.
int a[] = {3, 1, 4, 2, 9, 10, 33, 42, 2, 0, 6};
int N = sizeof(a) / sizeof(*a);
sort(a, a + N);
int K = 12;
int i = 0;
int *t = std::upper_bound(a, a + N, K - a[0]);
int j = t - a - 1;
while (i < j) {
for (int k = i + 1; k <= j; k++)
cout << "(" << a[i] << ", " <<a[k] << ") ";
i++;
while (a[i] + a[j] > K && i < j) {
j--;
}
}
My algorithm is as follows:
First of all, I assume the integers in the array and K are nonnegative numbers.
I use a hash table to store numbers as a key and the count of that number as a value.
PseudoCode
for(Integer i : arr) {
for(int j=K-i; K>=i && j>=0; j--) {
if(HashMap.containsKey(j))
sum += HashMap.get(j); // You can print out the pairs here. (i, j) which sums less than or equal to K. and its number is HashMap.get(j) for one i.
}
if(HashMap.containsKey(i))
HashMap.put(i, HashMap.get(i)+1);
else HashMap.put(i, 1);
}
From the two loops, I think the complexity is O(n * K).
My algorithm is a slight tweak of the algorithm which finds all pairs that sum up to certain value. Algorithm sorts the array first and initialize first = 0, last = last element. Then iteratively it examines the array. Here is the code:
- Anonymous December 06, 2014