Sample interview problems

Here are some problems that have been used in interviews in the past.

1. Tidy boxes.  You are given 10 boxes, each large enough to contain exactly 10 wooden building blocks, and a total of 100 blocks in 10 different colours. There may not be the same number in each colour, so you may not be able to pack the blocks into the boxes in such a way that each box contains only one colour of block. Show that it is possible to do it so that each box contains at most two different colours. A sample interview dialogue for this question is available.


2. Searching for the maximum.  The real-valued function f(x), defined for 0 ≤ x ≤ 1, has a single maximum at x = m. If 0 ≤ u < v ≤ m then f(u) < f(v), and if m ≤ u < v ≤ 1 then f(u) > f(v). You are told nothing else about f, but you may ask for the value of f(x) for any values of x you choose. How would you find the approximate value of m?  How accurately could you find m if you could choose only 10 values of x for which to evaluate f(x)?


3. Death by chocolate.  You are locked in a room with your worst enemy. On a table in the centre of the room is a bar of chocolate, divided into squares in the usual way. One square of the chocolate is painted with a bright green paint that contains a deadly poison. You and your enemy take it in turns to break off one or more squares from the remaining chocolate (along a straight line) and eat them. Whoever is left with the green square must eat it and die in agony. You may look at the bar of chocolate and then decide whether to go first or second. Describe your strategy.


4. Monkey beans.  An urn contains 23 white beans and 34 black beans. A monkey takes out two beans; if they are the same, he puts a black bean into the urn, and if they are different, he puts in a white bean from a large heap he has next to him. The monkey repeats this procedure until there is only one bean left. What colour is it?


5. Lily-pad lunacy. Eleven lily pads are numbered from 0 to 10. A frog starts on pad 0 and wants to get to pad 10. At each jump, the frog can move forward by one or two pads, so there are many ways it can get to pad 10. For example, it can make 10 jumps of one pad, 1111111111, or five jumps of two pads, 22222, or go 221212 or 221122, and so on. We'll call each of these ways different, even if the frog takes the same jumps in a different order. How many different ways are there of getting from 0 to 10?


6. Missing numbers.  Imagine you are given a list of slightly less than 1,000,000 numbers, all different, and each between 0 and 999,999 inclusive. How could you find (in a reasonable time) a number between 0 and 999,999 that is not on the list?


7. Scribble.  The game of Scribble is played with an inexhaustible supply of tiles, and consists of forming 'words' according to certain rules. Since each tile bears one of the letters P, Q, or R, these are not words that will be found in an ordinary dictionary. The game begins with the word PQ on the board; each move consists of applying one of the following rules:
   • If the word on the board is Px, for some shorter word x, you may change it to Pxx. For example, if the word is PQRRQ then you may change it to PQRRQQRRQ.
   • If the word on the board is xQQQy, for some shorter words x and y, then you may change it to xRy, replacing the sequence QQQ with a single R.
   • If the word on the board is xRRy, for some shorter words x and y, then you may change it to xy, deleting the sequence RR entirely.

   (i) For each of the following words, say whether you can make it or not by following the rules of the game: QPR, PQQ, PQR, PR. (ii) Given any word, how can you decide whether it can be made or not?

Some general hints:

• If the problem contains specific numbers (like 10, 100, 23, 34), does it become easier if we replace those numbers with smaller ones, or even by 0 or 1 or 2?  If there are no specific numbers, can you solve the problem in small examples, such as a 2 x 1 bar of chocolate?


• Are there other simplifying assumptions that you can try?  What if the bar of chocolate consists of just one row of squares?  What if the green square is in one corner?


• Is there a way of reducing the problem as given to a smaller one?  Is there a way of filling the first box of blocks that eliminates a colour, leaving us with 9 boxes and 9 colours?


• Some of these problems have definitive answers, other do not – or not answers that can be reached during a half-hour conversation, anyway. Most of them can be solved in several stages, beginning with easy cases and getting more general; some problems can be generalised beyond what is asked in the question.