Skip to question
ASIC.FYI

Q266FreeFirmware

Longest-Prefix-Match Routing Table

Difficulty
Hard
Topic
Data Structures
Language
SV
Interview prompt

Question

Implement an IPv4 routing table that returns the next hop associated with the longest prefix matching a 32-bit destination address.

Starting point

Question code

class RouteTable;
  bit insert(bit [31:0] prefix, int prefix_len, int next_hop);
  bit remove(bit [31:0] prefix, int prefix_len);
  bit lookup(bit [31:0] addr, output int next_hop);
endclass
Reviewed example

Trace one case

Input
routes: 10.0.0.0/8 -> A, 10.1.0.0/16 -> B
lookup: 10.1.2.3
Expected output
next_hop = B

Both prefixes match, but /16 is longer and therefore wins over the broader /8 route.

What to cover

Requirements

  1. Support prefix lengths from /0 through /32.
  2. A repeated insert updates the existing route rather than creating a duplicate.
  3. Lookup must select the most-specific match and report failure if none exists.
  4. Normalize or reject prefixes whose host bits are nonzero.
Continue practicing
Q237 · AlgorithmsDynamic Connectivity with Disjoint SetsQ217 · Data StructuresExpiring Key-Value StoreQ264 · Data StructuresExact Streaming Median