Ten Google Interview Questions that DID NOT COME FROM ME

[bugzpodder]

TeN Google Interview Questions that DID NOT COME FROM ME

honestly at least half of them are pretty bad.

SOURCE: http://mathnews.uwaterloo.ca/Issues/mn10704/googlequestions.php

1. Please describe a data structure that accomplishes the functions INSERT and FIND-MEDIAN in the best possible asymptotic time.
2. Given a circularly sorted array, describe the fastest way to locate the largest element.
3. Given a binary search tree and an integer k, describe the most efficient way to locate two nodes of the tree that sum to k.
4. Given an arbitrarily connected graph, explain how to ascertain the reachability of a given node.
5. If you have one billion numbers and one hundred computers, what is the best way to locate the median of the numbers?
6. Describe an API for a cache, with all of the associated function signatures. Provide pseudocode for the simple one.
7. Implement a special type of integer iterator. It will be a wrapper over a regular integer iterator, except that this iterator will only iterate over negative numbers. Show how you'd write the next() and hasNext() functions to work with the next negative integer instead of just the next integer.
8. You are making an AI to play Tic-Tac-To. Make a function that takes a board position as an input and returns a good position to play. Describe how you'd represent the board, and how you'd determine where to play next.
9. You are given 1001 numbers in an array. There are 1000 unique numbers and 1 duplicate. How do you locate the duplicate as quickly as possible?
10. Say you are implementing exponentiation for a certain processor. How would you minimize the number of multiplications required for this operation?.

[Unforgiven]

I'd take a stab at them just for fun, but I fear looking stupid on a page that can be indexed by Google ;)

[alex.john95]

Hey the interview questions you provided were quite usefull.

Thanks

[DemonWasp]

I'll take a stab at this. My answers are, of course, not necessarily very good, as I'm only a 2nd year CS student.

1. Please describe a data structure that accomplishes the functions INSERT and FIND-MEDIAN in the best possible asymptotic time.

A balanced binary search tree can insert in O(log n) and find-median in O(1)

2. Given a circularly sorted array, describe the fastest way to locate the largest element.

Absolute fastest I couldn't say, but what be useful is something as follows:

A. If N < (small threshold, maybe 10-100), just look the naive way.
B. Scan the array (of size N) at every N / 10 values. Find the pair where the direction is reversed (ie 9 of the 10 decrease, one increases, or vice-versa); there may not be one -> try again, using N / 100, then N / 1000.
C. Scan recursively within the isolated section.

Of course, this doesn't really improve the Big-O order, and it performs terribly on the cache. The actual fastest way may be the naive search because it could have better cache performance, and because it doesn't ever waste any time thrashing about like step B does. This also all depends on where the array is stored.

3. Given a binary search tree and an integer k, describe the most efficient way to locate two nodes of the tree that sum to k.

Iterate over the tree, building a queue of k minus each value (possibly discarding a node that has value = 0.5 * k, depending on whether the nodes must be unique). Now the queue contains a complete listing of all the numbers that could sum with another number in the list to equal k; search for each one in the list.

The first step is O ( n ), the second step is O ( n * log n ), for overall complexity of O ( n * log n )

4. Given an arbitrarily connected graph, explain how to ascertain the reachability of a given node.

Build a breadth-first search tree. If the final BFST contains the node, then yes, else no. (I can also explain how to make a BFST, I just won't do that here)

5. If you have one billion numbers and one hundred computers, what is the best way to locate the median of the numbers?

Define "best". If you mean "best" as "executes fastest", then you should do something like:
a. Partition the list evenly (10M numbers per computer)
b. Sort each partition individually (QSort, MergeSort, whatever)
c. Mergesort the lists (via a network)
d. Retrieve middle element
Of course, if you mean "easiest", then just sort the numbers on one machine and use the others to run Folding@Home.

6. Describe an API for a cache, with all of the associated function signatures. Provide pseudocode for the simple one.

What kind of cache do you mean?

7. Implement a special type of integer iterator. It will be a wrapper over a regular integer iterator, except that this iterator will only iterate over negative numbers. Show how you'd write the next() and hasNext() functions to work with the next negative integer instead of just the next integer.

I'm confused. Say what?

8. You are making an AI to play Tic-Tac-To. Make a function that takes a board position as an input and returns a good position to play. Describe how you'd represent the board, and how you'd determine where to play next.

The board gets to be a char[9] with special getters / setters, so it emulates a 3x3 board. The AI would check whether there's an immediate threat and counter it, otherwise it looks for one of a select few danger patterns and counters them

code:

eg. X-- -O- --X

using predefined responses (play in a non-corner in the example). Otherwise, it can just play adjacent to any existing piece, or in the middle or corner as the first play.

9. You are given 1001 numbers in an array. There are 1000 unique numbers and 1 duplicate. How do you locate the duplicate as quickly as possible?

Insert the numbers into a balanced binary search tree, when the duplicate comes up it will find that the value already exists in the tree, and it can then return. O ( n * log n ).

10. Say you are implementing exponentiation for a certain processor. How would you minimize the number of multiplications required for this operation?

Group the multiplications. Specifically, use the binary value of the power. For example:

x ^ 27?
> note that 27 (base10) == 11011 (base2)
> so x ^ 27 = x^1 * x^2 * x^8 * x^16
> so calculate x^1, x^2, x^4, x^8, x^16 sequentially and store them (this costs you 4 multiplications, since you can get each successive term by squaring the previous one)
> multiply the ones that are required (see decomposition of 27 into powers of 2) together (3 multiplications)

Total cost 7 multiplications, rather than the 26 required in the naive way.


I would NOT get hired by Google. In fact, I'd probably be kickbanned from the premises immediately for this .

[Andy]

I worked at google last summer, and I can confirm you that the interview questions are indeed very similar to these.

Response to DemonWasp's solutions

1. a balanced binary search tree does not guarantee equal elements on both sides. all it does is insure the height of both subtrees do not differ by more than 1.
a data structure that could solve this problem is a median heap. with log(n) insert and constant retrieval

2. binary search log(n)

3. use a hashtable to keep track of the numbers you need to sum to k, run BFS trough the tree and populate hashtable. O(n)

4. no need for BFST, just BFS and bit array will do.

5. you can find the median of two sorted arrays in o(log n) time, extrapolate and you'll get a better run time.

8. Tic tac toe has optimal strategies that can be mapped on to board positions. rotate the board if needed

9. use a bitmap

10. yeah thats what i would do too

[DemonWasp]

Response to Andy:

1. Whoops.

2. Yeah, I wasn't thinking terribly clearly answering this one.

3. Say what? I'm confused, please explain.

4. Okay, yes. Sorta what I meant: when coding it, I wouldn't construct data structures I didn't need.

5. Actually, even better: instead of doing a Mergesort, just do the "merge" and throw away the top 500M numbers, then the next-highest is your median. O ( n log n ) on the mergesorts (n = 0.01 * 1B ). Avoids the mess of actually merging the whole thing (unnecessary network traffic, cpu use, and ram consumption).

8. That works, but you only need a few special cases (and their rotations). Everything else can be handled by the general rules I gave.

9. Again, I'm confused. You lost me completely here.

Clearly I'm not quite Google-material yet.

[Andy]

3.
suppose you had the numbers {1, 2, 5, 9, 12, 14}
and k = 11

for i from 1 to n
if hashtable[i] = true
return i, k-i
hashtable[k-i] = true

the hash table will have entires for 10, 9, 6
and the function would return

5. you dont need merge short. merge sort is nlogn, you can find the median of two two sorted lists in logn, which means you can find the median of ALL numbers in nlogn, your algo is n^2logn

8. your algo is not optimal

9. use a bitmap. if the numbers are {1, 2, 3, 4, 5, 1}

you would set bitmap[1], bitmap[2], bitmap[3], bitmap[4], bipmap[5] to true, and then when you try to set 1 again, you'll find the duplicate.

[DemonWasp]

3. Your explanation to this has just confused me a lot more.

5. Err...sort on the 100 computers for O ( n log n ) + pull off top half of the numbers for O ( n ) = O ( n log n )?

Also, how does one find the median of two sorted lists in log n?

8. It's a tic-tac-toe AI: my home computer could feasibly play every single human on the planet at the same time, and expect to tie/win in all cases

9. That's probably faster, yes. However, it does poorly for small lists with sparse numbers, since you have allocate a ton of RAM for it. For most lists, though, my method would require more RAM.

[Andy]

3. uhh i dont get how to explain it anymore.. if you have ai, then you're looking for k-ai, so just record it on a hashtable.

4. the run time you get with my algo is log(100)*(10mil * log(10mil)

to find the median of two sorted lists? its pretty easy, think about it!

9. you dont have to use a bitmap, you can use a hashtable

[DemonWasp]

3.

You subtract each number in the tree from k, and insert that result into a hashtable - O ( n ).

You then iterate over the tree, checking whether the hashtable contains the value of each node - O ( n ) ?

Because yes, that's faster. Much faster, for a large enough tree. However, it does eat more space (funny how often you find that memory-speed tradeoff).

5. Alternately, I could just use Google to answer their own question. Apparently I fail at simple algorithm-making, as that one totally escaped me, despite being pretty simple.

So yes, with that change it's much better.

9. Hashtables are pretty magical, alright. Perhaps better, you could choose between the two depending on how many numbers you had in the list versus size of the ints (shorts and bytes would generally be bitmaps, longs generally hashmaps, etc).

[Andy]

Yes you could look up the answer, but then you're only hurting yourself. You don't need to be a genius to get hired by google, being able to design simple algorithms is often enough, and the only way to become better at it is through practice.

Though the pay is nothing spectacular, working at google (the new york office for me) certainly was, and I would recommend everyone to try to do an internship there.

[bugzpodder]

After quickly review the posts, some quick comments:

1. median heap is an ADT. if you quote this, be prepared to talk about its implementation. the easiest way is probably still a standard self-balancing binary search tree

2. actually it can be done using binary search. but it's not as simple as you think.

3. two iterators will do. no need for hash table.

5. Not sure what is the best way to do this.

The rest of the questions are really dumb for one reason or another.

google interview questions varies a lot between interviewers. (I've had, what, 10 interviews with them?) And honestly, these are very bad examples of them. Go look them up.

ps heard some of your friends talk about you on fedbus a while back andy. they said if you worked for google, you are set for life! hehe congrats

[arihs]

Quote:

5. you dont need merge short. merge sort is nlogn, you can find the median of two two sorted lists in logn, which means you can find the median of ALL numbers in nlogn, your algo is n^2logn

Given that you find the median of two lists on log(n) - how do you get from there to finding the median of all lists in nlog(n)? I'm not sure that it's that trivial..
The only thing I can think up is using something similar to the O(n) linear algo, but its quite messy, because you'll have to do a lot of moving around between the computers...

Can you clarify you idea?