Destination City

Destination City

What is this problem about?

The Destination City coding problem gives you a list of paths where each path is a pair [cityA, cityB], representing a one-way trip from A to B. You are told that the paths form a line without any cycles. Your task is to find the "destination city," which is the city that has no outgoing path to any other city.

Why is this asked in interviews?

Yelp and Meta use this "Easy" question to test your understanding of graph properties and your ability to use sets for membership testing. It's a test of "Out-degree" logic. It evaluations whether you can identify the node in a directed graph that has an out-degree of zero.

Algorithmic pattern used

The Hash Table interview pattern (specifically a Hash Set) is the most efficient approach here.

1. Create a Set of all cities that appear as a starting point (cityA).
2. Iterate through all cityB values.
3. The first cityB that is not in the set of starting points is the destination city.

Example explanation

Paths: [["London", "NY"], ["NY", "Lima"], ["Lima", "Sao Paulo"]].

1. Starting cities: {"London", "NY", "Lima"}.
2. Check destinations:
   • "NY": in starting set.
   • "Lima": in starting set.
   • "Sao Paulo": NOT in starting set. Result: "Sao Paulo".

Common mistakes candidates make

• Brute Force: Using nested loops to check if each destination city appears as a starting city ($O(N^2)$).
• Graph Construction: Over-engineering the problem by building a full adjacency list or performing a DFS traversal.
• Null Handling: Not considering that the list of paths could be empty (though usually not an issue with this problem's constraints).

Interview preparation tip

Whenever a problem asks you to find an element that appears in one list but not another, think of a Hash Set. It reduces the lookup time from $O(N)$ to $O(1)$.