Implement Router

Implement Router

What is this problem about?

The Implement Router interview question asks you to design a component that manages network routes. A router holds a collection of IP prefixes and their corresponding destinations. Given a target IP address, the router must find the "Best Match" route. In networking, the best match is defined as the Longest Prefix Match—the route whose prefix matches the most bits of the target IP. You need to implement functions to add a route and query a target IP.

Why is this asked in interviews?

Cisco and Microsoft frequently use this "Medium" problem to test a candidate's ability to model real-world hardware logic using software data structures. It evaluates your mastery of Trie interview patterns and your understanding of bitwise operations. Longest Prefix Match is a core algorithm in internet routing, and being able to implement it efficiently demonstrates your ability to design systems that handle high-throughput data.

Algorithmic pattern used

This problem is most efficiently solved using a Trie (Prefix Tree).

1. Binary Trie: Each node in the Trie represents a bit (0 or 1).
2. Insertion: When adding a route (like 192.168.1.0/24), you convert the IP to its 32-bit binary representation and insert the first 24 bits into the Trie. Mark the final node with the route's destination.
3. Search: To query an IP, traverse the Trie bit by bit using the IP's binary representation. Keep track of the last destination encountered during the path. That last one corresponds to the longest prefix match.

Example explanation

Routes:

• Route A: 10.0.0.0/8 $o$ "Destination 1"
• Route B: 10.1.0.0/16 $o$ "Destination 2" Target IP: 10.1.5.5

1. Binary starts with 00001010 (10). Trie matches Route A. Current best: "Destination 1".
2. Next bits match Route B (10.1...). Trie matches Route B. Current best: "Destination 2".
3. Traverse further; no longer matches in Trie. Result: "Destination 2" (because /16 is a longer match than /8).

Common mistakes candidates make

• Exact Match Only: Failing to realize that the router should return the most specific match, not necessarily an exact one.
• Inefficient Search: Using a list of routes and checking each one ($O(N)$), which is too slow for high-speed routing. The Trie provides $O( ext{bits})$ which is $O(32)$ for IPv4.
• String Conversion: Treating IPs as strings instead of 32-bit integers, which makes bitwise prefix comparison much harder and slower.

Interview preparation tip

Always discuss the trade-offs between a Trie and a Sorted List. A sorted list allows for binary search on ranges ($O(\log N)$), while a Trie allows for bitwise matching ($O(W)$). In networking, $W$ (the word size, e.g., 32 or 128) is often small enough that the Trie is significantly faster.