Google Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




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

var getFirstKElements = function (arr1, arr2, k) {
    var result = [];
    for (var i = 0; i < k; i++) {
        if (arr1[0] < arr2[0]) {
            result.push(arr1.shift());
        }
        else{
            result.push(arr2.shift());   
        }
    }
    return result;
}

- echen57 February 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Use 'merge' subroutine of mergesort.

- Murali Mohan February 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Depends on the definition of elements here. Its not necessary for the 10 million to fit into memory.
Use a 2 way merge of external mergesort. I/P Buffers needs to be (size of RAM) / 4
and OP size of RAM /2

- Anonymous February 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time Complexity O(n) where n ==length of 1st N values to return

public ArrayList<Node> firstN(int n,Node curr1,Node curr2)
{
  //note please do these 2 steps using bitwise divison using strings to avoid integer overflow error
int noMaxInt=n/Integer.Max;
int remainder=n%Integer.Max;

ArrayList<Node> toSend=new ArrayList<Node>();

for(int i=0;i<noMazInt;i++)
{
for(int i=0;i<integer.Max;i++)
{
if(curr1.value<=curr2.value)
{
toSend.add(curr1);
curr1=curr1.next;
}
else
{
toSend.add(curr2);
curr2=curr2.next;
}
}
}
while(remainder !=0)
{
if(curr1.value<=curr2.value)
{
toSend.add(curr1);
curr1=curr1.next;
}
else
{
toSend.add(curr2);
curr2=curr2.next;
}
remainder--;
}

return toSend;
}

}

- Danish Shaikh (danishshaikh556@gmail.com) February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Returning k element in sorted order.

public static String returnElement(ArrayList<Integer> first, ArrayList<Integer> second, int k) {
		String res ="";
		int time = 0;
		int left = 0;
		int right = 0;
		
		while(time < k) {
			if(first.get(left) < second.get(right)) {
				res += first.get(left) + " ";
				time++;
				left++;
			} else if(first.get(left) > second.get(right)) {
				res += second.get(right) +" ";
				time++;
				right++;
			} else {
				res += first.get(left) + " " + second.get(right) + " ";
				left++;
				right++;
				time++;
			}
		}
		
		
		return res;
	}

- nlavee November 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

pseudo code

// L1 and L2 are the two sorted list, and RL is the return list
ArrayList<int> GetFirstKElements(ArrayList<int> L1, ArrayList<int> L2, int k) {
	int i, j, len1, len2, count;
	i = j = len1 = len 2 = count = 0;

	ArrayList<int> RL = new ArrayList<int>();

	len1 = L1.size();
	len2 = L2.size();

	while(count < k) {
		if(i<len1 && j<len2) {
			if(L1.get(i) < L2.get(j) {
				RL.add(L1.get(i));
				i++;
			} else {
				RL.add(L2.get(j));
				j++;
			}
		} else if (i>= len1 && j<len2) {
			RL.add(L2.get(j);
			j++;
		} else if(i<len1 && j>=len2) {
			RL.add(L1.get(i);
			i++;
		}
		
		count++;
	}
	
	return RL;
}

- Aritra February 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Those who downvoted, please care to add some explanation for others to understand.

- Just curious February 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution looks fine. If you could write the logic before giving the code it will be easy for everyone to understand. That the only reason I could guess for the downvote.

- kr.neerav February 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(k) seriously?

- ewq February 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ewq, you have a better idea? It's list question, can't random access.

- Anonymous February 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can't do better than this, O(k). Just run this code and if input or output cannot fit into memory OS will handling swapping in/out pages. Or you can always persist partial output to file and later append next batch.

- AK February 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

If you don't care about whether the returned numbers are in order (which the problem doesn't ask for) I think you can get a log(k) solution by using a form of binary search to decide how many numbers from each list you want. Start by looking at the k/2 element from each list. Whichever one is smaller, switch to the k/4 element of that list and the 3k/4 of the other list. Then, depending on which of these is smaller, add k/8 to one side and subtract k/8 from the other. Once 2^n is more than k, you can stop and the position of the pointers will tell you how many numbers to return from each list.

- jj February 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 votes

it's a list, how can you start by looking at the k/2 element?

- Anonymous February 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How will you output k integers in time which is less than k ? The minimum possible steps the algorithm needs is O(k). It is not possible to do it in O(log k).

- Robin May 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Assuming these are arrays and not lists:
here is an algorithm similar to what jj suggested (actually identical, but explained differently).
1. compere elements in the first array and second array at position floor(k/2)
2. logically remove the first k/2 elements from the array which has the min and make then part of the answer(i.e. remember that the array now starts at position k/2).
3. repeat the exact same problem for k-k/2=k/2, i.e. find the smallest k/2 elements from the two new arrays.

this indeed gives logk time complexity

the nice thing is that the algorithm is generalizable:
given n sorted arrays, find the k smallest elements:
1. compere elements in the first array and second array at position floor(k/n)
2. logically remove the first k/n elements from the array which has the min and make then part of the answer(i.e. remember that the array now starts at position k/n).
3. repeat the exact same problem for k-k/n, i.e. find the smallest (n-1)k/n elements from the new arrays.
4. when k/n is 1 (or 2, or some small value), just dump them into a heap of size k (the newest value of k)

The complexity of this is "left as an exercise to the reader", because I have no clue how to compute it. Intuition tells me it is nlognk, but I have no idea how to prove it.(not even an upper bound)

Which bring us to the second problem: what if we have n sorted lists ?
1. we use a min heap of size n
2. we put all the first elements into the heap. We have n lists, and the heap is of size n, so that's nice.
3. we remove the min from the heap, add it to the final result, and insert the next element from the same list where the min was previously (min->next)
4. we continue to do step 3 k times (actually k-1)

complexity?
to build the heap of n elements is O(n). To do a replaceminwithnewelement in a heap of size n is O(logn) and we have to do it k times. So n+klogn. Lets check. if n=2 (we have 2 lists, and we keep moving the pointer in the list with the smaller element, which is essentially a heap of size 2), it will take k operations. Indeed 2+klog2 is O(k).

- Stefan March 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your algorithm seems to be incorrect.

Consider the case,
List1: 1, 4, 6, 10, 11
List2: 2, 3, 20, 40, 60

And you need to find the top 2 elements. Using your algorithm we compare 4 and 3 and end up picking 2, 3 from List 2 as the answer.

- scorpionnishme May 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you step by a fraction of k instead of a fraction of the respective sizes of the arrays? What if one array is very small (smaller than k/2), k/2 would be out of bounds.

- Anonymous May 22, 2014 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book on 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