Even More Google Interview Questions

This is another batch of the Google interview questions I managed to assemble. I heard to prepare for an interview with companies such as say, Google or Microsoft, you need to take 6 months to do the preparation for the interview questions.

* Implement division (without using the divide operator, obviously).

* Given a function that returns a random number between 1-5, write one that returns a random number between 1-7.

* Write a function (with helper functions if needed) called by Excel that takes an Excel column value (A,B,C,D… AA,AB,AC,… AAA…) and returns a corresponding integer value (A=1,B=2,… AA=27…).

* Write a function (and dictate it to your interviewer) that reverse the order of words in a sentence. The final algorithm should work in-place! E.g.: "This is a sample" --> "sample a is This".

* How would you implement a stack to achieve constant time for "push", "pop" and "find mininum" operations?

* You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.

* What should you consider when choosing a (sorting) alogrithm?

* Is it always better to use O(n log n) than O(n^2) (sorting) algorithm?

* There are 8 stones which are similar except one which is heavier than the others. To find it, you are given a pan balance. What is the minimal number of weighing needed to find the heaviest stone?

* Order the functions in order of their asymptotic performance:

* What is the best and worst performance time for a hash tree and binary search tree?

* You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game.You need to tell the algorithm first and then need to write the code.

* How do you put a Binary Search Tree in an array in a efficient manner?

* Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN. Write an in-place algorithm to rearrange the elements of the array as A = i1 c1 i2 c2 ... in cn.

* How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?

* Given a Binary Tree, programmatically can you prove it is a Binary Search Tree?

* Write a function to find the middle node of a single link list.

* Classic - Egg Problem
1. You are given 2 eggs. You have access to a 100-storey building.
2. Eggs can be very hard or very fragile, meaning it may break if dropped from the first floor or will not even break if dropped from 100 th floor.
3. Both eggs are identical. You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
4. Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

* Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same values and same structure.

* Implement put/get methods of a fixed size cache with LRU replacement algorithm.

* You have to get from point A to point B. You don’t know if you can get there. What would you do?

* Write a function to determine whether a number is a power of two (used a bit-shifting based algorithm).

* Describe the stack ADT (abstract data type)- include functions and variables that might be useful.

* How would you design google maps

* Write a function that outputs an integer in ASCII format.

* (string class) What is the best and worst time for the operation 'equals'?

* (string class) How do you spe.ed up the 'equals' operation?

* Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?

* Write some code to reverse a string.

* Describe an algorithm to find out if an integer is a square? (e.g. 16 is, 15 isn't)

* Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?