Hardware interview practice

IPv4 longest-prefix-match model

HardComputer ArchitectureC++

A switch reference model searches up to 64 IPv4 route entries. Write a C++ longest-prefix-match function with fixed error and tie rules.

Starting point

Question code

struct route { uint32_t prefix; uint8_t length, port; };
int lpm(const route *r, size_t n, uint32_t addr,
uint8_t *port, size_t *index);

Reviewed example

Input

Routes are 10.0.0.0/8 to port1 and 10.1.0.0/16 to port2; address is 10.1.2.3.

Expected output

lpm returns 1, port=2, and index identifies the /16 entry.

Both prefixes match, but the sixteen-bit prefix is longer and therefore wins.

What to cover

Require port and index, allow r=null only when n=0, require n<=64, and require every length<=32; return -1 and preserve outputs on an error.
An entry matches when the top length bits of addr and prefix agree; length zero is the default route and performs no shift by 32.
Choose the matching entry with the greatest length; if identical lengths tie, choose the lower array index.
Return 1 and write port/index on a match; return 0 and preserve both outputs when no entry matches.

Continue practicing