Ten Google interview questions
Actual, real interview questions!
- Please describe a data structure that accomplishes the functions
INSERT and FIND-MEDIAN in the best possible asymptotic time.
- Given a circularly sorted array, describe the fastest way to
locate the largest element.
- 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.
- Given an arbitrarily connected graph, explain how to ascertain
the reachability of a given node.
- If you have one billion numbers and one hundred computers, what
is the best way to locate the median of the numbers?
- Describe an API for a cache, with all of the associated function
signatures. Provide pseudocode for the simple one.
- 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.
- 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.
- 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
- Say you are implementing exponentiation for a certain processor.
How would you minimize the number of multiplications required for this
Copyright © 1998 mathNEWS.