Routers choose among overlapping routes using longest-prefix matching: the matching CIDR block with the most fixed network bits wins.
Design an Ipv4RouteTable class:
Ipv4RouteTable(String[] routes, String[] nextHops) stores aligned CIDR routes and next-hop names.String lookup(String ip) returns the next hop of the most-specific matching route, or "NO_ROUTE" when nothing matches.
Normalize each CIDR base under its mask. If two matching routes have the same prefix length, return the next hop from the route that appeared first in the constructor input. Constructor state must not change across lookups.
Example 1:
Input:
Output:
Explanation: 10.1.2.3 matches /0, /8, and /16, so /16 wins. 10.2.3.4 matches /0 and /8. The public address matches only the default route.
Example 2:
Input:
Output:
Explanation: Masking normalizes 192.168.1.10/24 to the network 192.168.1.0/24. The longer /25 and /32 routes override it where applicable.
Constraints
0 <= routes.length == nextHops.length <= 10^5- Every route is a valid IPv4 CIDR with prefix length in
[0, 32]. - Every lookup address is a valid dotted-quad IPv4 address.
1 <= nextHops[i].length <= 100- At most
100 calls are made to lookup. "NO_ROUTE" is not used as a next-hop name.
Perform Longest-Prefix Route Lookupmedium