Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition

Brainteaser Problems

Brainteasers draw from a much broader and more diverse body of knowledge than programming and technical problems, so a comprehensive review is even less possible here. Since any brainteaser you encounter in an interview is likely to be unfamiliar, the problems that follow prepare you by providing opportunities to practice all of the techniques we’ve described so you can tackle anything that comes your way.

Count Open Lockers

PROBLEM Suppose you are in a hallway lined with 100 closed lockers. You begin by opening all 100 lockers. Next, you close every second locker. Then you go to every third locker and close it if it is open or open it if it’s closed — call this toggling the lockers. You continue toggling every nth locker on pass number n. After your hundredth pass of the hallway, in which you toggle only locker number 100, how many lockers are open?

This problem is designed to seem overwhelming. You don’t have time to draw a diagram of 100 lockers and count 100 passes through them. Even if you did, solving the problem that way won’t illustrate any skill or intuition, so there must be some trick that you can use to determine how many doors will be open. You just need to figure out what that trick is.

It’s unlikely that you can intuit the solution to this problem by just staring at it. What can you do? Although it’s not practical to solve the entire problem by brute force, solving a few lockers in this manner is reasonable. Perhaps you will notice some ...