Try this interview question.
Google is known for asking tricky logic puzzles during their job interviews. The one above is actually quite simple if you think about it in the right way.
The first thing we need to figure out is how many steps there are in the shortest or most efficient path. You need to get across three columns and two rows so it will take at least five steps.
If R indicates right and U indicates up, here are some possible paths:
RRRUU
UURRR
URRUR
As you may notice, there is never any need to go down or left. Moving in either of those directions would lead to a longer path. Furthermore, all of the shortest paths include three “R” and two “U.” The puzzle boils down to figuring out how many orders you can put those letters in.
We could choose to write out all of the possible orders, but it would be a lot more fun to use math.
Basically we’re looking at five steps and wondering where to put the two “U”s. If you are familiar with the area of math called combinatorics, you might write that as 5C2 (spoken as 5 choose 2).
This can be expanded to 5!/((5-3)!3!)=10
If that doesn’t mean anything to you, let’s think about it this way.
You have five steps and want to choose two of them for your “U”s. For the first “U,” you have five steps to choose from. It could be the first step you take, the second step and so on.
For the second “U,” you only have four blank spots remaining, which leads to 5x4=20 ways to choose two spots for your “U”s. However, since both “U”s are the same — it doesn’t matter which one goes first — you actually have to divide that number by 2.
Thus, there are 20/2=10 ways to get from point A to point B as efficiently as possible.
In case you’re curious, they are:
UURRR
URURR
URRUR
URRRU
RUURR
RURUR
RURRU
RRUUR
RRURU
RRRUU
You might also like: The Mystery of the Missing Dollar
Facebook comments