APPLE ASKS ITS future employees to solve Khan Academy brain teasers, we learned while digging around for information about the questions Apple recruiters asks.
You may not have heard of the Khan Academy, but it’s a serious brainiac-creating effort, a nonprofit backed by money from Google and the Bill and Melinda Gates Foundation.
Make no mistake – these are very, very tough questions, even for senior-level software engineers. But happily, they all have a single correct answer.
So if you want to be best prepared for your interview with Apple, you should study these questions. They will probably pop up in some form during the recruiting process:
(Image: anyjazz65 on Flickr/Creative Commons)
1. You stand in front of two doors—one with treasure, and one with a slow, painful death …
This is a bit of a warmup, compared to some of the other teasers. You’re at the end of a quest and you approach two doors, and your treasure is behind one of two doors. Behind the other door is a slow, painful death. Beside the doors, there are two people. Both of them know which door has the treasure, and both know which door has the slow, painful death. One always tells the truth, and one always lies. But you don’t know who is who, and you can only ask one question to ask of one of them. What question do you ask, and which person do you ask, and what do you do based on what they tell you?
ANSWER: Ask either one, “Which door would the other guy say is the correct one?”
By asking this question to the truthteller, you will get the incorrect door, because he will honestly say what the liar would say. If you ask the liar, you will get the incorrect door, because he will lie about what the truthteller would tell you—the correct door. By asking either guy, you will get the incorrect door, and you can thereby select the correct one.
2. Five individuals stand in front of you, and only one always tells the truth…
There are five guys in front of you, and four of them are “togglers,” while the fifth person is a truthteller. A toggler is either going to tell you the truth or lie when you ask them a question. The second time you ask them a question, they are going to switch. If they told you the truth the first time, they will lie the second time, and vice versa. You can ask two questions of any person—to either the same person or two different people. What do you ask to figure out who the truthteller is?
Here’s a hint: you want to ask a question, no matter what they say, in such a way that you know what they will do the second time — whether they are telling the truth or lying.
ANSWER: First ask, “Are you the truthteller?” Then ask, “Who is the truthteller?” or “Who is not the truthteller?” depending on the response.
When you ask the first question, they will say yes or no. If someone says yes, then they are the truthteller, or they are a lying toggler. If they are the truthteller, they’ll tell the truth on the second question. If they are a lying toggler, they’ll tell the truth on question number two.
If they say yes, you know they will tell the truth the second time—so ask, “Who is the truthteller?” You’ll get the right answer. If they say no to the first question, then they cannot be the truthteller, so they are a truthful toggler. If they say no, ask, “Who is not the truthteller?” They will then tell you who the truthteller is.
3. Aliens are about to turn Earth into a mushroom farm, and have abducted 10 humans…
These humans are tasked with proving Earth is worthy of joining the intergalactic council of planets. The fate of humanity is in your hands. Tomorrow, the ten humans will be lined up one behind the other in a dark room. While the room is completely pitch black, the aliens will place a hat on each person’s head—a purple hat or a green hat. Then the lights are turned on.
You can’t see your own hat, and the hat distribution is random—it could be all green hats or all purple hats, or 9 green and 1 purple, or any combination. Starting with the person in the back, the aliens ask, “What colour is the hat on your head?” Every other person can hear the answer, and if the person is right, he or she will live and 600 million people will be saved. If you’re wrong, you get blown up, and the people you represent are turned into a mushroom farm. How do you save as many lives as you can?
Hint: The human in the back can see all the hats in front of him or her, and there is a solution that will guarantee saving 9 of the 10 humans.
ANSWER: Keep track of whether the green hats are even or odd.
The first human is guessing and has a 50/50 chance of surviving, while the other 9 are guaranteed to be saved. The human in front counts the number of green hats, and if the number of green hats is an odd number, the human will say green. If the number is even, the human guesses purple.
Then, the next human knows that the person behind him saw either an odd number or even number of green hats. The next human counts the number of green hats, and if it’s still odd, then that human has a purple hat.
That human says purple, and will live. And then there will be an odd number of green hats forward, then that third person can determine if he or she is wearing a green or purple hat. If the second person sees an even number of green hats, then obviously that person has a green hat, and will survive. The humans just have to keep track if the number of green hats in front of them is odd, or even, and they can automatically determine the colour of their hats. Thus, you’re guaranteed to save at least 9 people.
4. 100 perfect logicians are sitting in a room…
There’s a new reality television program in which 100 people sit in a circle in a room, all with infallible powers of logic. Before they enter the room, they are told at least one person has a blue forehead. When you determine your forehead is blue, you need to leave the room when the lights turn off. Then the lights are turned back on, with those people who have deduced they have blue foreheads having left the room. Now, let’s say we’ve painted everyone’s forehead blue. What happens?
Hint: Think about what happens when there are less than 100 people with a blue forehead.
ANSWER: The lights go on and off 100 times, and then everyone leaves on the 100th time.
The light gets turned on and off 100 times, and after the 100th time, all logicians leave the room.
If everyone sees 99 blue foreheads, the lights get turned off, and they turn on again, and everyone sees 99 blue foreheads again. That happens 100 times, and then everyone leaves the room.
Here’s how to understand it: imagine only one person has a forehead that’s blue. The game masters said at least one person has a blue forehead, then as soon as they turn the lights off, then that person leaves. Now imagine if you have two people with blue foreheads. Here’s what one of the guys is thinking: “I have a blue forehead or I don’t have a blue forehead. If I don’t have a blue forehead, then the other blue forehead is going to deduce he or she has a blue forehead, and that person will leave.”
“If I don’t have a blue forehead, then the other person will stay, and therefore I must also have a blue forehead. So we must both leave when the lights turn off the second time.” Repeat the logic to the 100th step, and you have your answer!
5. You have a six-by-six grid…
You start in the top left corner, and your goal is to get to the bottom right corner. You can only move to the right or down. You can’t move diagonally and you can’t move backwards. How many different ways are there to get from the start to the finish?
ANSWER: There are 252 ways, thanks to how symmetric the problem is.
Pick any random cell. Assume it took you “n” steps to get to the cell above it, and “m” steps to get to the cell to the left of it. Then the number of ways to get to the random cell is equal to the sum of those two steps—n + m. So, fill out the six-by-six grid with that logic. So there are 252 ways to get to the bottom-right step.
6. The logicians sit in a circle, with numbers painted on their foreheads…
There are three people sitting in a room, all with infallible powers of logic. Each logician has a unique number greater than 0 on their forehead. One number is the sum of the other two numbers. You see a logician with the number 20 and one with the number 30. The game master goes around in the circle, and asks each logician what their number is. Each logician says he or she cannot guess his number the first time around. Then they ask the question again. What is your number, and why?
ANSWER: It depends on what the third person says on the first round.
Assume the other two logicians are 20 and 30 again. If the first logician is 10, then the second logician will either say, “I’m either 40, or 20.” The second logician will say, “I am either 30, or 10, but I can’t be 10 because every number has to be unique.” If the third logician should be able to deduce he is 30, but the third logician couldn’t figure out what number is on his or her forehead. So the first logician does not have a 10 on his or her forehead — so it must be 50.
7. You have 100 light bulbs lined up in a row…
100 light bulbs line up in a row are turned on in the first pass. Then you switch every other light bulb. So all even-numbered light bulbs are turned off. Then you switch every third light bulb. Any light bulb that was off is turned back on, and any light bulb that was already on was shut off.
Then you do it for every fourth bulb, then every fifth bulb. How many light bulbs are on after 100 passes?
Hint: if you are on pass “n” (where n is any number between 1 and 100), then any bulb that is a factor of that number “n,” the light bulb will get switched. Say you’re on the 8th light bulb—every time you go through of its factors (1, 2, 4, 8), it will switch. If you have an odd number of factors, you should have an odd number of “factors.”
ANSWER: Just ten bulbs—all of which are perfect squares.
The trick is to check how many light bulbs in the row have an odd number of factors.
The first bulb has an odd number of factors, the second has an even number of factors, four has an odd number of factors. So one and four will remain lit. The ninth bulb will have an odd number of factors, so it will remain lit. All the lights that are going to be on are perfect squares, because they have an odd number of factors. One, four, nine, sixteen.
You have 100 passes, so you can go up to 10 times 10 — 10 squared. So you have 10 perfect squares—1, 2, 3, 4, 5, 6, 7, 8, 9 and 10. They correspond to the 1st, 4th, 9th, 16th, 25th, 36th, 49th, 64th, 81st and 100th bulb, which will all remain on. So, there will be 10 light bulbs that remain on.
8. Now you have a cube, each with a three-by-three grid…
This is a harder problem than the first path-counting problem. Now you want to get from the back-left corner of the cube to the front-right of the cube. You can move toward the front, you can move down, or you can move upward. How many different ways are there to get to the end?
ANSWER: Split the cube into “layers” and make your move—there are 90 of them.
You can split the cube into three three-by-three grids. The pink one is the top layer, the middle is the purple, and the lowest is orange. Now, instead of counting the paths you can get to one square from the cells adjacent, you count the paths from the left (n), the right (m) and the level above (r). So the path for any square is n + m + r.