You have to get from point A to point B
You don’t know whether you can get there. What do you do?
The MBA answer: “I would pull out my cell phone and enter point A and point B in Google Maps.
If point B isn’t on Google Maps, I’d take a taxi and submit the receipt to accounting. Next question?”
The computer science Ph.D. answer: “Oh, I get it. You’re asking about the problem of searching a Network….”
When asked of a software engineer, this question is expected to lead to a discussion of the relative merits of specific search algorithms. Though these algorithms were devised for searching computer memories and the Internet, they are equally relevant to navigating a shopping mall, a garden maze, or the quaint villages of Umbria. I will give a commonsense answer that is ultimately not so far from the computer scientists.
To rephrase the question, you’re at point A, you want to find point B, and there’s no app for that.
You have to stick to the roads or paths leading from A. You’ll recognize point B when and if you
come to it. But you might not come to it. Point B could be off the road network and unreachable.
You should begin by asking several important questions of the interviewer:
1. Can I ask for directions? Can I use GPS? Do I have any way of estimating the direction of or
distance to point B?
2. In the event that point B is not reachable from A, is there any way of realizing that, short of a
3. Am I interested in finding point B as quickly as possible, or in finding the fastest route from point A to point B as quickly as possible?
Interviewers like to hear that you’re smart enough to ask for directions, but you’ll be told that you
can’t count on getting foolproof guidance.
Question 2 is important because, well, the better engineers like to avoid throwing infinite time and effort into a bottomless pit. You don’t want to search the whole planet to determine that you can’t get there (B) from here (A).
That last question, 3, maybe a little confusing. To give one example, you might be lost in a
cornfield maze at point A with two screaming kids. You want to find the exit, point B. All you care
about is getting out of the frigging maze.
You’d want a search procedure that would find point B with due dispatch. However, there are
almost always false turns and the route you’d take wouldn’t necessarily be the very shortest route from A to B. In this situation, that would be okay.
Alternatively, maybe you want to commute from home (A) to work (B) on public transportation.
You will be repeating the route you find every working day of your life. You are not just looking for B; you’re looking for the shortest route between A and B.
Any search has an element of trial and error. There is usually an element of knowledge or
intuition, too. You may have beliefs on how to get to B, based on maps, hunches, street smarts, the wisdom of French Canadian trappers, or a road sign saying POINT B 17 MILES. A search procedure should marshal whatever information you have (and allow for the possibility that this information is not reliable). You’ll begin by exploring the route that you believe is most likely to be the shortest route to B. Make a map as you go, in case you have to backtrack and try different routes.
So far this is incontestable. To impress the interviewer, you’ll need to say something not quite so
obvious. Try this: the fundamental philosophical question of searching for a destination is, “When should I turn back?”
There may come a time when you feel you are lost—meaning that you believe you have strayed far from the most direct path from A to B. Do you backtrack to where you were before you were lost? Or do you try to find the most direct path from where you are now (lost) to point B?
There’s a good chance you’ve heard this issue debated on your last road trip. If the jokes about
male drivers are correct, men are loath to backtrack or ask for directions. Suppose a friendly stranger assures Ashley and Ben that point B is just down that road, saying, “You can’t miss it.” They drive half an hour, expecting every moment to glimpse B around the next bend. It never happens. “We’re obviously not on the right road,” Ashley announces. “Let’s go back to where we were before we got those directions.”
“There’s no point in turning back,” counters Ben. “We’ve come a long way, and we must be closer to B than we were. There’s got to be a sign up ahead.”
Ben’s strategy resembles what computer scientists call the best-first algorithm. Whenever you
come to a fork in the road, you follow the presumed shortest route to B, based on your current state of knowledge. In the happy case where this knowledge is 100 percent accurate, Ben will make a beeline for point B.
Ashley’s strategy is more like the A* search algorithm (pronounced “A-star”), described by the
computer scientists Peter Hart, Nils Nilsson, and Bertram Raphael in 1968. This says (roughly) that you should stick as close as possible to the shortest path from A to B. You’re probably wondering how that’s any different from Ben’s strategy. It’s not, as long as the searcher has reliable directions.
The difference arises when the searcher strays from the direct route. In deciding what to do, Ben looks at a single number: his guesstimate of how far B is from his present location. He always tries to move in the direction of B. Ashley looks at two numbers: her estimated distance to B and her known road distance from A. Ashley’s goal is to minimize both numbers or, more exactly, their sum. Ashley tries to explore the points that are most likely to lie on the shortest route from A to B.
Who’s right, Ben or Ashley? Ashley’s search procedure is better at dealing with wrong turns. The diagram shows the gist of the matter. Starting out from A, the searcher comes to a fork in the road and must choose either the right or the left path. Should Ben choose the left path—a mistake!—he will endure a lengthy trudge. Though long and circuitous, this route takes him ever closer to B.
Should Ashley take the same wrong turn, she would eventually realize that she’s come an awfully long way from A, and B is still far away. This would tell her she’s not likely to be on the shortest path. Ashley would backtrack to the fork and try the other path. She’d probably find B quicker than Ben would. In general, you’d expect there to be many forks, rather than just one, and decisions all along the way. Similar trade-offs apply a search method with an optimal propensity to backtrack beats one that backtracks too infrequently.
This interview question further slants things in favor of an A*-like search by saying that you don’t
know whether you can get from A to B. If there’s no way of getting to B, Ben will wander aimlessly, forever chasing a will-o’-the-wisp. Ashley will explore systematically outward from point A, as she’s minimizing the distance from A. She will form a map of the territory that will help to establish that there is no way of getting from A to B. That will prevent wasting further resources.
A* search has particular merit when the goal is to find the shortest path of all. For that reason, it’s used in mapping apps and in video games, to route characters through their virtual worlds. A*-like searches arguably have psychological advantages, too. As fallible humans, we are prone to self-justifying convictions. It’s seductively easy to burn resources exploring the wrong route, the wrong business plan, the wrong romantic partner, the wrong idea—all the while convinced that success is just around the next corner. An A* search is able to pull the plug on an unprofitable venture and begin anew somewhere else. That’s an idea of wide relevance. Success is about not giving up too easily but also about knowing when to throw in the towel.
Bottom line: the best way to get from point A to point B is to stick close to the route you currently
believe is shortest (an A* search)—that, rather than focusing just on finding point B.