Amazon NG: Flight Route Visiting All Cities (Eulerian Path)

Amazon NG VO opens each round with BQ before coding, and this "flight route visiting all cities" was one round's coding question. Many see "graph + traversal" and misjudge it as topological sort—it's actually an Eulerian Path. Based on an oavoservice student's debrief, this post lays out the criterion and solution, plus a neat follow-up: when each airport can reach only one city, the graph degenerates into a linked list and the problem drops a dimension. At the end you'll find VO assist / VO proxy paths for anyone in a new-grad, career-switch, or SDE job search.

1. Problem Background

2. Problem

Given a set of flight maps (cities as nodes, routes as edges), find a route letting the pilot traverse all routes (each edge exactly once), connecting all cities.

3. Framing: this is an Eulerian Path, not topological sort

Many candidates see "graph + traversal" and misjudge it as topological sort—it isn't. "Each edge exactly once" is precisely an Eulerian Path.

The criterion (undirected graph): the graph is connected, and the number of odd-degree vertices is exactly 0 (Eulerian circuit, start anywhere and return) or 2 (Eulerian path, from one odd vertex to the other).

def has_eulerian_path(n, edges):
    # undirected graph: degree count + connectivity
    from collections import defaultdict
    deg = defaultdict(int)
    adj = defaultdict(list)
    for u, v in edges:
        deg[u] += 1
        deg[v] += 1
        adj[u].append(v)
        adj[v].append(u)

    odd = sum(1 for node in deg if deg[node] % 2 == 1)
    if odd not in (0, 2):
        return False

    # connectivity: DFS from any vertex with edges, all such vertices reachable
    start = next(iter(deg))
    seen = set()
    stack = [start]
    while stack:
        u = stack.pop()
        if u in seen:
            continue
        seen.add(u)
        for v in adj[u]:
            if v not in seen:
                stack.append(v)
    return len(seen) == len(deg)

Time complexity: O(V + E). Space complexity: O(V + E).

4. Follow-up: each airport reaches only one city → degenerates to linked-list reconstruction

Follow-up: if each city's airport can reach only one city (out-degree 1 per node), how do you optimize?

This constraint degenerates the input from a graph into a linked list: each node has exactly one successor, so the whole route is a single chain. The problem shifts from Eulerian Path to reconstructing a linked list / finding its order—given a pile of (from, to) pairs, assemble the unique order from start to end.

def reconstruct_route(pairs):
    # pairs: [(from, to)], each from is unique → effectively a singly linked list
    nxt = {a: b for a, b in pairs}
    targets = set(nxt.values())
    # start: never appears as the target of any edge
    start = next(a for a in nxt if a not in targets)
    route = [start]
    while route[-1] in nxt:
        route.append(nxt[route[-1]])
    return route

Time complexity: O(n). Space complexity: O(n).

Grind for the essence: once a graph degenerates into a linked list, the principle holds—simpler structure, simpler solution. Spotting this degeneration lets you switch from a complex Eulerian Path to an O(n) linked-list reconstruction fast.

5. On-the-Spot Reminders

• "Traverse every edge exactly once" is the Eulerian Path signal—don't reflexively write topological sort.
• An Eulerian Path requires checking both degree parity and connectivity—neither condition is optional.
• Follow-ups often reduce dimensionality by adding constraints (graph → list); recognizing the degenerate structure yields a better solution fast.
• State "this is Eulerian Path, not topological sort" verbally first—correcting the misconception is itself a plus.

FAQ

Q1: Why is the flight-route question Eulerian Path, not topological sort?

Because it requires "each edge exactly once," which is the definition of an Eulerian Path; topological sort orders nodes in a directed acyclic graph—different problems. The undirected Eulerian Path criterion is connected with 0 or 2 odd-degree vertices.

Q2: What's the difference between an Eulerian path and an Eulerian circuit?

A circuit starts and ends at the same vertex—in an undirected graph all vertices have even degree; a path has different start/end with exactly 2 odd-degree vertices (start and end). Both require the graph to be connected (ignoring isolated vertices).

Q3: Why does the graph degenerate to a linked list in the follow-up?

When each node's out-degree is capped at 1—each city flies to exactly one city—the whole structure becomes a single chain of "exactly one successor per node," essentially a linked list. So you just build a from→to hash map and walk from the start: O(n) reconstruction.

Q4: How do I prepare efficiently for Amazon NG coding rounds?

Drill by topic—graph theory (Eulerian path / topological / connectivity), trees, linked lists, DP—timed and narrating your reasoning, while also preparing BQ. For timed mocks by Amazon NG question type plus BQ, line-by-line walkthroughs, or full VO assist / VO proxy support, see the path below.

Preparing for Amazon NG VO?

Amazon NG is a BQ + coding loop where coding loves dimension-reducing follow-ups on classic graph problems. oavoservice offers full Amazon prep: timed mocks on Eulerian path / graph theory / linked list / DP high-frequency questions, per-question polishing of problem-type recognition and follow-up adaptation, and parallel prep of STAR stories across the 16 LPs. Coaches include senior big-tech engineers with a Bar Raiser perspective, with full VO assist / VO proxy support.

Add WeChat Coding0201 now to get Amazon questions and coaching.

Contact

• WeChat: Coding0201
• Email: [email protected]
• Telegram: @OAVOProxy