Microsoft Interview Question: Toggling Lockers

This was allegedly a Microsoft interview question: A high school has this ritual on the last day of school: The students go into the hall and stand by their closed lockers. At the first blow of a whistle, the students open every locker. At the second whistle, the students close every second locker (lockers 2, 4, 6, etc., are slammed shut). At the third whistle, the students toggle every third locker. To "toggle" means to close it if it's open, and to open it if it's closed. They toggle lockers 3, 6, 9, etc. At whistle four, they toggle every fourth locker. At whistle five, they toggle every fifth locker, and so on. Let's make things easy and say it's a small school with only 100 lockers. At the one hundredth whistle, the student standing next to locker 100 (and only that student) toggles his locker. Which lockers are then open?

One effective strategy to tackle this kind of brain teaser problem consists of 3 steps:

1. Get your hands dirty: explore the problem by trying it out;
2. Observe the pattern and make a conjecture;
3. Seal the deal: prove the conjecture.

In this problem, you are going to focus on the first step: get your hands dirty.

If you encounter this problem in an interview, get your hands dirty means simulating the toggle by hand. However, trying it with 100 lockers will take you quite some time, but there is nothing special about the number 100. You can reduce the number of lockers to 10. Then you can quickly find the answer and make a conjecture. Since you are not in an interview here, there is no reason not to try the 100 lockers using a computer.

Simulating the locker problem is quite easy in R: Use 0 to represent closed lockers and 1 to represent open lockers. Set x to be a vector of length 100 and set every element to 0 initially to represent 100 closed lockers. The following is the code.

n <- 100 # number of lockers = 100
# initialize x to 0's
x <- rep(0,n)
for (i in 1:n) {
  # toggle lockers i, 2i, 3i, ... at the ith whistle
  lockers <- seq(i,n,i)

  # toggle lockers: 
  MISSING CODE
}
# lockers that are open at the end  
open_lockers <- which(x==1)

a. The command seq(i,n,i) determines which lockers to toggle at the ith whistle. What are the numbers returned by the command seq(i,n,i) when i=32? Enter the numbers separated by commas (e.g. 1,2,4,7).

b. The line with MISSING CODE is to toggle lockers, i.e. change 0 to 1 and 1 to 0. Which of the following command should be used?
x[lockers] <- x[lockers]-1
x[lockers] <- 1-x[lockers]
x[lockers] <- x[lockers]+1
x[lockers] <- x[!lockers]
None of the above

c. Instead of using 0 and 1 to represent closed and open lockers, we can use FALSE to represent closed lockers and TRUE to represent open lockers. In this case, the toggle operator is simply the NOT (!) operator. The following code produces the same result as the code above:

n <- 100 # number of lockers = 100
# initialize x to FALSE's
x <- rep(FALSE,n)
for (i in 1:n) {
  # toggle lockers i, 2i, 3i, ... at the ith whistle
  lockers <- seq(i,n,i)

  # toggle lockers: 
  x[lockers] <- !x[lockers]
}
# lockers that are open at the end  
open_lockers <- MISSING CODE

What should MISSING CODE in the last line be?
length(x)
which(x==FALSE)
which(x)
sum(x)
which(!x)

d. Copy and paste the one of the codes above to your R console to run it. Look at the content of the variable 'open_lockers'.

Which lockers are open at the end? Enter the numbers in ascending order separated by commas. If you don't feel like entering all the numbers by hand, type cat(open_lockers,sep=", ") in your R console and then copy and paste the output.