Inteview with Google.

2 huge files A and B are in sorted order. Make a combined file C which contains the total sorted order.
Extrapolate this to 1000s of sorted files containing millions of entries. Generate the combined sorted file as output

How would you design a stapler for a blind person?

How would you find the first unique url among the millions of url available?

How could you distinguish web pages which Koreans or Japanese read?

A river separates two banks, there are 3 men and 3 lions on one side that need to be taken across using a boat that can carry 2 entities at a time(irrespective of being a lion and man), subject to the condition that at no point can you have more number of lions than men on any bank, as then the lions would eat the man/men. Solve the puzzle. Then code it to make it a generic program that solves the puzzle for X men and Y lions.

Given an array of red, green and blue balls arrange them in groups of all red together, greens together and blue together. Do in a single scan of the array.

Efficiently implement 3 stacks in a single array.

Given a set of points (x,y) on a 2D coord system, identify list of 2D coords that are of distance less than x units long.

Eg.
Let x = 1;
Given (0,0), (0,1), (1, 2), (4,6);
Return 1 -> (0,0), (0,1)

Detect a cycle in graph(DFS)
Count number of bits and asked me later to do it in O(1)

Virtual functions and vtable...
What happens when a Constructor gives a call to a virtual functions
What if it is a pure virtual function

There are hundred prisoners each standing in a column. Each one is given a hat and there are two possible colors of hat which are red and white. The 100th person can see the hats of 99 people in front of him and the 99th person can see 98 people in front of him but can't see his own and the previous hat. The number of hats aren't known and the hats are placed in random order. Starting with the 100th person, each person is asked what color hat they have. If they guess wrong, they die. Come up with a strategy such that maximum people are alive. How many people are alive? (Do not use probability constraint given)

Convert a doubly linked list to a binary search tree in place.

Write the code for a change vending machine.

how to free memory allocated to an array with new function?

What's code coverage?

Identify the regular expression in a given string such that the pattern does not repeat. For example, to identify the pattern 'foo' only once in an input.
'jhkhfoojkkj' should be identified right
'kjhfooaaaaafoo' should not be

A person can take one or two steps at a time to reach a particular floor( say in a building). How many different ways can a person reach the nth floor?
More Questions from this Interview

Implement memcpy(void* src, void* dst, int len)

A duck, pursued by a fox, escapes to the center of a perfectly circular pond. The fox cannot swim, and the duck cannot take flight from the water (it’s a deficient duck). The fox is four times faster than the duck. Assuming the fox and duck pursue optimum strategies, is it possible for the duck to reach the edge of the pond and fly away without being eaten? If so, how?

Given a puzzle of letters/ characters e.g.
a e r o p s
b h a r l s
w r i s l o
a s n k t q
Write a function to which this puzzle and a word will be passed to test whether that word exists in the puzzle or not.
e.g. rain and slow will return true. rain is present in the second column and slow in the third row wrapped around.

Give you a simplest computer: CPU + 2k RAM. Write a slowest program.
(Hint: use the 2k as a huge number, then use a loop statement to loop from 0 to this number. It will take almost forever.)

Given a Starting Node and Ending Node in a Graph where each Node has a pointer to its parent and all its children nodes. Find all the leaf nodes between the Starting and Ending Node.
Given a 2D plane, suppose that there are around 6000 points on it. Find a line which passes the most number of points.


Reference and contents from:http://www.careercup.com