Google Interview Questions for Position of SoftwareEngineer In Test
1)Efficiently implement 3 stacks in a single array.
2)Given an array of integers which is circularly sorted, how do you find a given integer.
3)Write a program to find depth of binary search tree without using recursion.
4)Find the maximum rectangle (in terms of area) under a histogram in linear time.
5)Most phones now have full keyboards. Before there there three letters mapped to a number button. Describe how you would go about implementing spelling and word suggestions as people type.
6)Describe recursive mergesort and its runtime. Write an iterative version in C++/Java/Python.
7)How would you determine if someone has won a game of tic-tac-toe on a board of any size?
8)Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division.
9)Create a cache with fast look up that only stores the N most recently accessed items.
10)How to design a search engine? If each document contains a set of keywords, and is associated with a numeric attribute, how to build indices?
11)Given two files that has list of words (one per line), write a program to show the intersection.
12)What kind of data structure would you use to index annagrams of words? e.g. if there exists the word "top" in the database, the query for "pot" should list that.