Interview Question
All of the recent talkabout Mr. Tetris had me thinking of a new interview question. Think of the normal tetris game: a sequence of random shapes appears on the screen, and the user responds with sequences of left, right, down arrow and spacebar until the screen is filled. Now, suppose that you are given a list of keys pressed in sequence from the beggining to the end of the game. Can you use this sequence of keypresses to figure out what sequence of shapes appeared in the game? Of course, it’s not possible to know the exact sequence, but this can serve as an interesting starting point to discuss the problem. Simplifying steps can be introduced; extra points if the interviewee asks for clarification on these points or others:
- Given a sequence of keystrokes and a sequence of shapes, how would you determine whether the sequence of shapes is a sequence that might match the keys given, or could not possibly match the keys given?
- Suppose that you know every third shape. How does that change the solution?
- Suppose that you know every point at which a row cleared (and how many rows).
- Suppose that you know every time a shape falls (as if space is always pressed).
This interview question is too complicated tobe useful for determining the skill of an applicant for designing algorithms, but would be good for determining an applicant’s ability to decompose a problem and discuss possible solution approaches.