Archive for ‘interview questions’

July 23, 2011

Interview Question: Flipping Switches

by Mikael

This came up a long time ago, I only recently recalled it:

Consider a sequence of 100 switches all initially set to “off”. Flip every switch. Now starting with the first switch, flip every second one (i.e. #0, #2, #4, …). Then, starting again with the first, flip every third switch (i.e. #0, #3, #6, …). Proceed in that manner, always starting with the first switch, switching every fourth, then fifth, then sixth switch etc.. Once the first switch has been flipped a hundred times, which switches are set to “on”?

read more »

July 23, 2011

Interview Question: Data Structure for Tic-Tac-Toe

by Mikael

Got this recently:

Tic-Tac-Toe decision tree

Tic-Tac-Toe decision tree

How would you design a data structure for the game Tic Tac Toe? The main objective is to provide: A method, as efficient as possible, for checking the board to see if there is a winner.

read more »

July 22, 2011

Interview Question: Cars on a Road

by Mikael

The question was posed roughly like this:

Suppose there is a very long road. Suppose there is a sequence of cars, C1, C2, C3, … that each move with its own constant speed that is such that C1 is slower than C2 which is slower than C3, and so on. The cars enter the road in the same sequence (C1 then C2 etc.) but at random locations. They are not allowed to overtake each other, so if a faster car catches up to a slower one, the faster must reduce speed and fall in behind.

After some time, how many groups of cars will there be on the road?

read more »