Match an Address Against a List of IP Ranges

Insert each range as a prefix into a binary trie keyed on the address bits, with its action on the last node. To look up an address, walk its bits from the top and remember the last action you pass: that is the longest, most specific matching range. At most 32 steps for IPv4, however many ranges there are.

mediumPattern: Tries·From Devana's Cloudflare question set

Problem

A request's source address must be checked against a large list of ranges, such as 10.0.0.0/8 or 192.168.5.0/24, on every request. Each range carries an action like block or allow. Ranges overlap, and when they do the most specific one wins: an address in both a /16 and a /24 gets the /24's action.

Write a PrefixTable with insert(prefix, action) and lookup(address), which returns the action of the longest matching prefix, or None. A linear scan over a hundred thousand ranges is far too slow.

class PrefixTable:
    def insert(self, prefix: str, action: str) -> None: ...
    def lookup(self, address: str) -> str | None: ...

This is one of Devana's own questions, written in the style of Cloudflare's interviews. It is not a question leaked from Cloudflare, and Devana is not affiliated with Cloudflare.

Constraints

• IPv4 only in this version: dotted addresses, and prefixes with lengths from 0 to 32.
• A prefix of length L matches an address whose first L bits equal the prefix's first L bits.
• The longest matching prefix decides. 0.0.0.0/0 matches everything and acts as a default.
• Inserting the same prefix again replaces its action.
• Up to 10^5 prefixes; the cost of a lookup must not depend on how many there are.

Examples

Input:  insert("192.168.0.0/16", "allow")
        insert("192.168.5.0/24", "block")
        lookup("192.168.5.9")
Output: "block"

Input:  the same table
        lookup("192.168.6.1")
Output: "allow"

Hints

Open one at a time, and try the problem again after each.

Approach: from brute force to optimal

How to say it in the interview

State the rule that decides everything, longest prefix wins, then propose the trie and give the cost of a lookup: at most 32 steps for IPv4, independent of the number of ranges. Mentioning the 33 hash maps alternative shows that you are choosing rather than reciting.

Solution

Python

class PrefixTable:
    """A binary trie over IPv4 address bits; a node may carry an action."""

    def __init__(self):
        self.root = {}

    @staticmethod
    def _to_int(address):
        a, b, c, d = (int(part) for part in address.split("."))
        return (a << 24) | (b << 16) | (c << 8) | d

    def insert(self, prefix, action):
        address, length = prefix.split("/")
        bits, node = self._to_int(address), self.root
        for i in range(int(length)):
            node = node.setdefault((bits >> (31 - i)) & 1, {})
        node["action"] = action

    def lookup(self, address):
        bits, node = self._to_int(address), self.root
        best = node.get("action")                  # a /0 matches everything
        for i in range(32):
            node = node.get((bits >> (31 - i)) & 1)
            if node is None:
                break
            best = node.get("action", best)        # a longer match replaces it
        return best

JavaScript

class PrefixTable {
  // A binary trie over IPv4 address bits; a node may carry an action.
  constructor() {
    this.root = { children: [null, null], action: null };
  }

  static toInt(address) {
    const [a, b, c, d] = address.split(".").map(Number);
    return ((a << 24) | (b << 16) | (c << 8) | d) >>> 0;
  }

  insert(prefix, action) {
    const [address, length] = prefix.split("/");
    const bits = PrefixTable.toInt(address);
    let node = this.root;
    for (let i = 0; i < Number(length); i++) {
      const bit = (bits >>> (31 - i)) & 1;
      if (!node.children[bit]) node.children[bit] = { children: [null, null], action: null };
      node = node.children[bit];
    }
    node.action = action;
  }

  lookup(address) {
    const bits = PrefixTable.toInt(address);
    let node = this.root;
    let best = node.action; // a /0 matches everything
    for (let i = 0; i < 32; i++) {
      node = node.children[(bits >>> (31 - i)) & 1];
      if (!node) break;
      if (node.action !== null) best = node.action; // a longer match replaces it
    }
    return best;
  }
}

Both versions are tested against the same cases, including every example on this page.

• JavaScript's bitwise operators work on signed 32-bit integers, so >>> 0 and >>> keep addresses from 128.0.0.0 upward from turning negative.
• The root can carry an action too, which is how 0.0.0.0/0 works as a default.
• The Python version keeps children under the keys 0 and 1 and the action under "action" in the same dict. They cannot collide, because the keys have different types.

Follow-up questions

Common mistakes

• Returning the first match found instead of the longest one.
• Sorting ranges by start and binary searching, which breaks as soon as ranges nest.
• Signed shifts in JavaScript turning high addresses negative.
• Forgetting that a zero-length prefix lives at the root.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Related problems

• Resolve Inherited Folder Permissions: Walk the folder tree from the root and keep the nearest explicit rule; invalidate only the subtree that changed.
• Consistent Hashing for a Cache Tier: Virtual nodes on a sorted ring; each key belongs to the first position at or after its hash.
• Tries: the pattern guide, with more practice questions.