Plan a road trip between gas stations: A Sample Coding Interview Solution

The coding question

A car has to drive from a start point to an end point on a grid, and can only drive a fixed distance on a full tank. Given a list of gas station locations, can it make the trip?

Ask a few questions first

Ask	What we'll assume
How do we measure distance?	It's a grid of streets, so Manhattan distance: how far apart in x plus how far apart in y.
Does the car start full?	Yes, and every station fills it all the way up.
Does the car have to stop at the stations in order?	No. It can go to any station it can reach.
Can the distance be exactly the tank size?	Yes, reaching a point with an empty tank is fine.
Do we need the route, or just yes or no?	Just yes or no to start. The route is a follow-up.

A couple of examples

Input	Output
start (0, 0), end (10, 0), stations [(3, 0), (7, 0)], tank 4	True: 0 to 3 to 7 to 10, each hop 4 or less
start (0, 0), end (10, 0), stations [(3, 0), (8, 0)], tank 4	False: 3 to 8 is 5, too far
start (0, 0), end (6, 6), stations [(3, 3)], tank 6	True: each hop is 3 + 3 = 6

Start with brute force

Try every order of visiting stations, and check whether any order gets you to the end without a hop longer than the tank. It's correct but it's checking every possible route.

Cost: with n stations there are n! orders, so it's hopeless past about 10 stations.

A better way

The order doesn't matter, only which places can reach which. Treat the start, the end and every station as points. Two points are connected if they're within one tank of each other, since you'd arrive there and fill up.

Now the question is just: is the end connected to the start? That's a graph traversal. Run a breadth-first search from the start and see if it ever reaches the end.

Put the start, all the stations and the end into one list of points.
Start a queue with the start point, and mark it seen.
Take a point off the queue. If it's the end, return True.
Otherwise, add every unseen point within one tank of it to the queue and mark it seen.
If the queue empties without reaching the end, return False.

The code

solution.pypython

from collections import deque


def can_make_trip(start, end, stations, tank):
    stops = [start] + list(stations) + [end]
    goal = len(stops) - 1

    def distance(a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    seen = {0}
    queue = deque([0])
    while queue:
        here = queue.popleft()
        if here == goal:
            return True
        for nxt in range(len(stops)):
            if nxt not in seen and distance(stops[here], stops[nxt]) <= tank:
                seen.add(nxt)
                queue.append(nxt)
    return False

	Cost	Why
Time	O(n²)	Each of the n points checks the distance to every other point once
Space	O(n)	The seen set and the queue hold at most n points

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

No stations: it's just whether the end is within one tank of the start.
Start and end are the same point: True, even with a tank of 0.
A hop of exactly the tank size: it should count, so use <= not <.
Stations listed out of order: the search doesn't care about list order.
A station that's unreachable but sits right next to the end: still False.

Common mistakes

Assuming you visit stations in list order, or greedily driving to the nearest one. The nearest station can lead to a dead end.
Forgetting to mark points as seen, which loops forever between two close stations.
Using straight-line distance when the interviewer said grid, or the other way round. Ask first.
Building the whole graph up front and then searching. That works, but it's extra code for no gain.

Follow-up questions

What if you want the fewest stops?

Breadth-first search already finds that. Each level of the search is one more stop, so track the level when you reach the end.

What if stations charge different prices and you want the cheapest trip?

Now edges have costs, so use Dijkstra's algorithm with a heap instead of a plain queue.

What if there are a million stations?

Checking every pair is too slow. Put stations in a grid of buckets one tank wide, and only compare a point with stations in its own and neighboring buckets.

How the time adds up

Minutes	What you're doing
0–5	Clarify distance, refueling and what to return
5–10	Brute force over every order, and why it's too slow
10–20	Turn it into a graph and pick breadth-first search
20–35	Write the code
35–40	Walk through the examples and edge cases
40–45	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Bloomberg.