The great physicist Richard Feynman once applied for a job at Microsoft (so runs the guaranteed-apocryphal story). “Well, well, Dr. Feynman,” the interviewer began. “We don’t get many Nobel Prize winners, even at Microsoft! But before we can hire you, there’s a slight formality. We need to ask you a question to test your creative reasoning ability. The question is, why are manhole covers round?”
“That’s a ridiculous question,” Feynman said. “For one thing, not all covers are round. Some are square!”
“But considering just the round ones, now,” the interviewer went on, “why are they round?”
“Why are round manhole covers round?! Round covers are round by definition! It’s a tautology.”
“Uh—right. If you’ll excuse me, Dr. Feynman, I’d like to consult with our human resources department.” The interviewer left the room for ten minutes. When he returned, he announced, “I’m happy to say that we’re recommending you for immediate hiring into our marketing department.”
This joke pokes fun at one of the most famous brainteaser questions, long associated with Microsoft and alleged to have been devised by Steve Ballmer himself. It expresses deep ambivalence about this style of interviewing. Feynman (a childhood hero of Sergey Brin’s) shows more creative thinking than does Microsoft’s so-called right answer.
A true story: Brin did graduate work in Stanford’s computer science building, named for its donor, William Gates. Each room in the Gates Building had a four-digit number. “We were offended at having four-digit numbers when you don’t have ten thousand rooms,” Brin explained. He devised a new numbering system using three digits. The building doesn’t have a thousand rooms, either, but Brin reasoned that he had to retain the convention that the first digit gives the floor. “I just had the numbers roll around the building,” Brin said. “Even numbers were exterior, odd numbers were interior. The second digit told you how far around the building you had to go.”
Google’s people like to think of themselves as having a uniquely creative approach to design. In this worldview, Microsoft is sometimes cast as a bad example. Though the invidious comparisons have less to do with the real Microsoft than with outsiders’ jokes, there is a slender basis in history. Microsoft began in an age when small computers were for hobbyists and everyone wrote spaghetti code. Google was founded a generation later, when a new discipline of algorithm theory had changed the way software was written. Microsoft has, of course, recruited many of the world’s best coders and computer scientists. But it has baggage—legacy products, legacy users, and a corporate culture forged in the 1980s. Google entered the new millennium with a clean slate. As the tech blogger Joel Spolsky wrote,
A very senior Microsoft developer who moved to Google told me that Google works and thinks at a higher level of abstraction than Microsoft. “Google uses Bayesian filtering the way Microsoft uses the ‘if’ statement,” he said. That’s true. Google also uses full-text-search-of-the-entire-Internet the way Microsoft uses little tables that list what error IDs correspond to which help text. Look at how Google does spell checking: it’s not based on dictionaries; it’s based on word usage statistics of the entire Internet, which is why Google knows how to correct my name, misspelled, and Microsoft Word doesn’t.
This “higher level of abstraction” figures in many of Google’s interview questions. Try this one:
? You want to make sure that Bob has your phone number. You can’t ask him directly. Instead you have to write a message to him on a card and hand it to Eve, who will act as go-between. Eve will give the card to Bob, and he will hand his message to Eve, who will hand it to you. You don’t want Eve to learn your phone number. What do you ask Bob?
This question is usually asked of software engineers, who instantly recognize the names “Bob” and “Eve.” In computer science textbooks, it’s conventional to speak of “Alice” sending a coded message to “Bob” (it sounds a bit more human than saying “A sends a message to B”). The rote villain of the textbooks is a snoop called “Eve” (for “eavesdropper”). Coded messages are vitally important on the Internet—they’re the basis of e-commerce and cloud computing. Eve’s many guises include hackers, spammers, and phishers. It is not too much of an exaggeration to say that this interview question presents, in a kernel, the central problem of our wired world.
It also reveals very different ways of thinking about problems. There is a technically brilliant solution. Every textbook discussion of Bob and Eve segues into an exposition of RSA cryptography, the type used by PayPal and other forms of electronic commerce. Suffice it to say that RSA involves some heavy computation. That’s okay, as it’s always done by computer. The smart interviewee is led to wonder whether there’s any way to explain RSA to Bob, as part of a message that could fit on the back of a business card. This is something like telling your grandmother how to build an iPad so clearly that she could make one.
It can be done! It’s possible to explain a bare-bones implementation of RSA to a naive Bob who doesn’t know how to code. (I give the whole explanation in the “Answers” section.) A lean version of the instructions will fit on a three-by-five-inch index card, even a business card if you’ve got microscopic handwriting. The candidate who succeeds in drafting his RSA message to Bob will feel he’s knocked the ball out of the park.
Not so fast. He’s just given the “Microsoft answer.” Eve or no Eve, Bob is sure to balk at following complicated instructions just for the mundane task of confirming a phone number. Google interviewers expect engineers to know RSA, of course, but they’re especially impressed by those who come up with a simpler, more practical answer.
The Microsoft Answer
The Google Answer
Tell Bob to call you (ideally, give a specific time). If your phone rings, bingo. If not, that tells you he doesn’t have the right number. That’s all the question asks for (“You want to make sure that Bob has your phone number…”). Why do things the hard way?
This question tests something rarer than education—the capacity to ignore what you learned when it isn’t helpful. In business there’s no one to tell you what part of your education applies (if any). There is an overwhelming temptation to use whatever intellectual tools are at hand and to pat yourself on the back for using the highest-powered tool possible. Google doesn’t want people who instinctively do things the hard way because they can. They want those with a knack for intuiting simple solutions that work.
This raises the all-important question, what separates the entrepreneur from the engineer? In part, it’s the ability to not think like an engineer sometimes. An engineer can’t help falling in love with the clever ideas and algorithms that have gone into a new product. An entrepreneur has to ignore them and judge whether the end users will want, or be able, to use the product. Since Google is a place where job descriptions are fluid, it tries to find employees with the ability to put themselves in someone else’s head. Many of its interview questions bear on that theme.
? An executioner lines up 100 prisoners single file and puts a red or a blue hat on each prisoner’s head. Every prisoner can see the hats of the people in front of him in line—but not his own hat, nor those of anyone behind him. The executioner starts at the end of the line and asks the last prisoner the color of his hat. He must answer “red” or “blue.” If he answers correctly, he is allowed to live. If he gives the wrong answer, he is killed instantly and silently. (While everyone hears the answers, no one knows whether an answer was right.) On the night before a lineup, the prisoners confer on a strategy to help them. What should they do?
Like “Bob and Eve,” this feints at being a familiar type of question, in this case an old-school logic puzzle. It’s unquestionably related to a riddle created by the American mathematician and computer scientist Alonzo Church (1903–95). In the 1930s, Church invented a puzzle about three gardeners who have spots of dirt on their foreheads. No one can see his own forehead, of course, and there’s no mirror. The gardeners are told that at least one has dirt on his forehead and have to deduce who is smudged. One of Church’s students, the logician Raymond Smullyan, took the idea and ran with it, producing scores of ingenious puzzles in a series of popular books. In later variations by Smullyan and others, the telltale “spots of dirt” are replaced with hats or colored dots or anything that might plausibly be visible to everyone except the wearer. Stories are embellished with amusing motives, like trying to deduce whose wife is cheating on whom, or who is the spy. Many of these puzzles are used in interviews throughout the corporate world.
Solutions usually hinge on the assumption that everyone involved is a “perfect logician.” That means that person A can deduce x based on what B deduced from y and C failed to deduce from z. It will not come as a shock to learn that the intended solutions have nothing to do with the real world. In many cases, these puzzles penalize those who understand how real people think and act.
As it’s used at Google, the executioner question is a subtle deconstruction of the genre. There is no definitive right answer. The best responses show appreciation of the human element and its unintended consequences.
Start by looking at what happens when the prisoners have no plan at all. Should the prisoners just guess their hat colors randomly, they would be right about 50 percent of the time. That means that about 50 of the 100 would survive, on average.
Any plan must do better than that to be worthwhile. Conceptually, the prisoners want to send information up the line. The last prisoner, #100, sees the color of everyone’s hat except his own. Were he free to speak his last words, he could recite the hat colors of the 99 prisoners in front of him, saving them all. That’s forbidden. He is permitted only one word, and it must be either “red” or “blue.” That’s a one-bit message when he really wants to send a ninety-nine-bit message.
Because this last prisoner has no way of learning his own hat’s color, he has nothing to lose. He might as well use his answer to do something useful, like name the hat color of the guy directly in front of him. This will permit #99 to give the right answer. Number one hundred will have a fifty-fifty chance of being spared, too, since his hat might happen to be the same color as #99’s.
Why not have everyone answer with the hat color of the prisoner in front? That won’t work. Imagine you’re somewhere in the middle of the line. The prisoner behind you says “red,” meaning your hat is red. The hat in front of you is blue. Do you save your own life by answering “red,” or do you pass on the right answer to the prisoner ahead of you by saying “blue”? You can’t do both.
One scheme—call it plan A—is for the even-numbered prisoners to answer with the hat color they see immediately in front of them, and for the (lucky) odd-numbered people to take advantage of this information to save themselves. Under plan A, all 50 odd-numbered people will live. The even-numbered people have to take their chances. You can expect that about half of them will be killed. In all, this brings the number of likely survivors up to 75. That’s certainly better than not having a plan at all.
This survival rate could be improved, were the prisoners able to send poker-cheat “signals.” Let prisoner #100 name the color of #99’s hat. Number ninety-nine clears his throat before answering if and only if the hat in front is the same color as his own. He then names his correct hat color. The throat-clearing signal would allow #98 to name his hat color and send a similar signal to #97. Everyone except #100 could save himself, and #100 would still have a fifty-fifty chance of survival. That’s a survival rate of 99.5 out of 100.
Secret signals are not usually considered a legitimate solution. You’re to assume that each prisoner’s answer must be “red” or “blue,” and nothing more. There is an entirely legal scheme that’s about as good. Plan B, let’s call it, has the last prisoner count the number of red hats he sees in front of him and answer according to whether this number is odd or even. The rule could be, “red” means “the number of red hats I see is odd,” and “blue” means “the number of red hats I see is even.”
Plan B doesn’t help the last prisoner’s chances of survival (nothing can). It does offer a way to save everyone else. Say you’re #99 and you hear #100 say “blue.” That means he sees an even number of red hats. You count the number of red hats you see in front of you. Is it also even? If so, then your hat cannot be one of the red hats #100 saw. Therefore, your own hat must be blue. By saying “blue,” you save your own skin. The beauty of the plan is that “blue” also helps #98. He knows that #100 saw an even number of red hats and that yours wasn’t one of them (because you gave the same answer). This allows #98 to deduce his own hat’s color.
In general, everyone knows the parity of the total number of red hats (exclusive of prisoner #100’s, which is out of sight and out of mind). Everyone also knows the colors of the hats behind him (since this has been announced) and can use that to deduce his own hat’s color. By announcing the color of his own hat, each prisoner saves himself and supplies the information subsequent prisoners will need.
Plan B requires that everyone remember #100’s answer and keep a running total of how many people behind them said “red.” Each needs to add this number to the number of red hats he sees in front of him, then compare the sum with #100’s answer. If #100 said “red,” meaning he saw an odd number of red hats—and if you’re aware of 47 red hats (the 21 you see and the 26 people behind you you’ve heard say “red”)—then that jibes. All the reds are accounted for, and your hat must be blue. If there is a discrepancy, it must be due to your hat’s being red. You say whatever color your hat is.
Does the above paragraph strike you as a little confusing? Now imagine you’re explaining it to a hundred prisoners at Attica, or to your sister-in-law, or to the Midwest sales force. Real people make mistakes, especially when someone’s about to garrote them. Let just one prisoner slip up, and the plan falls apart.
There are some engineers who wouldn’t think of this. They are happy to stop with a technically valid answer that no one can understand. That’s why your TV setup has four remotes, all confusing.
The better answers to this question go beyond the mere logic-puzzle response. A candidate should ask, how practical is plan B, really?
One saving grace is that there are only two possible answers. When somebody gets confused and screws up, there’s still an even chance he’ll say the right thing by dumb luck. But in the long run, the inevitable errors compromise plan B. Remember, Google likes answers that scale up. For “100 prisoners” read “1,000” or “an indefinite large number.” As John Maynard Keynes said, in the long run, we’re all dead. Well, close. When the line is long enough that some make errors, about half the prisoners will be acting on the right information and surviving—while the other half will be acting on wrong information and be slaughtered like sitting ducks. Allowing for errors, the asymptotic survival rate of plan B is only 50 percent. That’s no better than what you’d expect by having no plan at all.
At any rate, plan B’s real survival rate may be less than the 75 percent rate offered by plan A (where errors do not propagate forward). Not that plan A is foolproof, either. The even-numbered prisoners are asked to nobly save the odd-numbered ones and get nothing in return. Picture how that would go down at San Quentin. However it’s decided who gets to be the odd-numbered ones, the division will stoke long-simmering resentments. The even-numbered prisoners can’t improve their own fifty-fifty survival chance. But a malicious prisoner could settle a score by intentionally giving the wrong answer to an odd-numbered prisoner in front of him. Since errors don’t propagate, the realistic survival rate of plan A is only a little less than the theoretical 75 percent.
Ideally the prisoners should do trial runs of both plans and choose the one with the higher survival rate—in practice. It’s good to mention that to conclude your answer. In this and more realistic situations, no one can predict infallibly how people will take to a new idea—you have to try it out.
Who’s smarter, a computer science PhD or your mom? After years of interviewing at Google, Paul Tyma, an engineer, resolved to find out. Suppose you’re given a million sheets of paper (runs one of Tyma’s interview riddles). Each is the record of a university student. You’re to sort them in order of age (number of years old). How would you do it?
Tyma posed this question to his mother, who knew absolutely nothing about computer science. Mrs. Tyma’s answer was more efficient than those of many of the highly educated applicants Tyma has interviewed.
How can this be? Mom Tyma’s answer was, she’d make stacks. Take the first record off the top of the pile and look at the age. If it’s a twenty-one-year-old, it goes in the twenty-one-year-olds’ stack. If the next record is a nineteen-year-old, it goes in the nineteen-year-olds’ stack. And so on. You have to look at each record only once, and when you’re finished, you simply collect the stacks in order of ascending age. Done!
That procedure is about twenty times faster than quicksort, the algorithm that many Google applicants suggest. Some candidates go nuts when told of Mom Tyma’s solution. Quicksort is “guaranteed” to be asymptotically fastest! The textbook said so!
They’re forgetting the mathematical fine print. Quicksort is based on comparisons: is this number bigger than that? You don’t always need comparisons to sort. You don’t here because there are many, many records and only a few distinct ages of college students. Quicksort is versatile, like a Swiss Army knife, but Mom’s stacks happen to be a much better tool for this particular task.
One of the oft-cited mysteries of creativity is that revolutionary ideas often come from nonexperts with an outsider’s perspective. The computer science grads were so used to thinking of high-powered algorithms that they couldn’t not think of them. Without that mental baggage, Mrs. Tyma intuited a better solution. Sometimes “creativity” is just common sense.
With apologies to the folks in Redmond, I’ll end on another Microsoft joke because it makes the point well (a point that applies everywhere, not just at Microsoft): A helicopter was flying around above Seattle when a malfunction disabled all of its electronic navigation and communications equipment. The clouds were so thick that the pilot couldn’t tell where he was. Finally, the pilot saw a tall building, flew toward it, circled, and held up a handwritten sign that said WHERE AM I? in large letters. People in the tall building quickly responded to the aircraft, drawing their own large sign: YOU ARE IN A HELICOPTER. The pilot smiled, looked at his map, determined the route to Sea-Tac Airport, and landed safely. After they were on the ground, the copilot asked the pilot how he had done it. “I knew it had to be the Microsoft building,” he said, “because they gave me a technically correct but completely useless answer.”
Avoiding Technically Correct but Useless Answers
Each of these questions has a simple, practical answer and a complicated or useless one. That’s a hint, but be warned: it’s often easier to find the complicated answer than the simple one. (Answers begin here.)
? If you had a stack of pennies as tall as the Empire State Building, could you fit them all in one room?
? You have ten thousand Apache servers, and one day to generate $1 million. What do you do?
? There are two rabbits, Speedy and Sluggo. When they run a 100-meter race, Speedy crosses the finish line while Sluggo is at the 90-meter mark. (Both rabbits run at a constant speed.) Now we match them up in a handicapped race. Speedy has to start from 10 meters behind the start (and run 110 meters), while Sluggo starts at the usual mark and runs 100 meters. Who will win?
? You’ve got an analog watch with a second hand. How many times a day do all three of the watch’s hands overlap?
? You’re playing football on a desert island and want to toss a coin to decide the advantage. Unfortunately, the only coin on the island is bent and is seriously biased. How can you use the biased coin to make a fair decision?