25 Google Interview Questions

1 Prepare Before Your Interview

Do you prepare before your interview at Google? Of course you will. But how and where to start? This report will provide you a list of 25 questions collected from Web provided by Google interview candidates. The list of questions is focus on CS fields.

2 Questions

The question listed as follows are not ordered based on any criterion. The programming languages are required to be used are usually not specific. You can practice using Java, C++, C, C#, etc. For each problem, you need figure out at least one solution. If there are multiple solutions to the problem, make sure you understand how to analyze the efficiency (both time and space).

1. Describe a data structure as well as operations on the data structure.
2. What is the difference between function overloading and overriding?
3. Given a superclass A, a subclass B of superclass A where B overrides a function foo() in A, an instance of class B, how to invoke foo() defined in class A?
4. How to check if two nodes in a graph are connected?
5. How to get the top unique search queries from a database with 100 billion entries?
6. Given a binary tree and pointers to two nodes in the tree, write an algorithm to locate the closest common ancestor.
7. Assume that you have a genealogy, describe a data structure to represent it. Given any two persons within the genealogy, describe an algorithm to determine if they share a common ancestor. Note that the algorithm is required to only output true or false.
8. Given a sorted array, how to find the index of the first occurrence of a specific integer n?
9. How to search the m-th to the last element on a linked list?
10. How to create a binary tree based on a sorted array?
11. How to locate the lowest common ancestor for a binary search tree?
12. How to find the depth of binary search tree without using recursion?
13. Assume you have a fixed-size array, you are asked to store numbers in ascending order to the array. When your numbers reach the end of the array, you start storing the new numbers from the beginning of the array (replacing the old ones of course). You are required to write an algorithm to search a specific number in this array.
14. Given n numbers, which may contain duplicates, and one number s, find out whether there are two numbers in the n numbers sums up to the number s.
15. Assume that we are interested in a number sequence where each number is a multiple of 2 or 5 (so: 2^i  *  5^j), e.g. 1,2,4,5,8,10,16, 20, 25, 32.., write an algorithm to calculate the next number in the sequence.
16. How to generate the power set of a set of numbers?
17. How to calculate the factorial numbers?
18. Given an unlimited stream of input numbers, output the median value at any moment.
19. How to reverse elements on a linked list?
20. Describe the design of a “most-recently-used” list, such as the “Recent Files” menu in Microsoft Word. The list has two public methods, getlist() and acacess(str), which retrieve the list and mark an item as accessed, respectively. Assume that the list has a maximum number of items it can hold, say 5, and it should not have duplicates. Describe a data structure to represent the list, write the algorithms for the two methods, and analyze the time efficiency of the two methods.
21. Describe a data structure that represents a sequence of integers, which can be negative, zero, or positive, assuming that you need to support an API with two public methods, insert(int) and getmedian(). Write the two method definitions and analyze their efficiency.
22. Given a very long single linked list, how to find the n-th entry from the end?
23. How to find the top search requests in Google, assuming that you could use 10000 computer in parallel?
24. How to implement a random number generator such that the random number generated is always in a particular range?
25. How to reverse a string?

3 Conclusion

If you are a CS major student, you will know how you should prepare and what courses you study at school will help you in industry in future. Keep working on your best, be persist, and you will succeed!