Square | Phone | IP Routing Table

Anonymous User

768

First interview as part of a general process. Made a bunch of different applications so I'm not sure exactly which this is for, but my experience level is Junior for what it's worth.

Problem:

We want to construct an IP routing table that matches binary IP addresses with a port based on the longest matching prefix. It needs to support 2 functions: insert(ipPrefix: string, port: number): void and lookup(ip: string): number. IP addresses are represented as binary strings that are 6 characters long. Examples:

IP Prefix    Port
==================
10          => 3
010         => 4
1111        => 5

lookup("010110") = 4
lookup("111111") = 5

Part 1: Implement the above functions.

This was pretty straightforward, use a binary trie (i looked up what this was called after the interview, but the idea made intuitive sense to me) and store port numbers as leaf nodes. Traversing to the left child represents a 0, traversing to the right represents a 1. To perform a lookup, iterate through each character until you either reach a leaf node or no path forward is possible. I was also asked about a different approach we could use to compare this one. I said that we could always just brute force every entry and look for the longest match. This is also similar to the following LC problem: https://leetcode.com/problems/implement-trie-prefix-tree/

class TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(value: number) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const DIRECTIONS = ["left", "right"];

class RoutingTable {
    table: TreeNode = new TreeNode(-1);

    constructor() { }
    
    insert(ipPrefix: string, port: number): void {
        let curr = this.table;
        for (let i = 0; i < ipPrefix.length; i++) {
            const curr_dir = DIRECTIONS[Number(ipPrefix[i])];
            if (curr[curr_dir]) curr = curr[curr_dir];
            else {
                curr[curr_dir] = new TreeNode(-1);
                curr = curr[curr_dir];
            }
        }
        curr.value = port;
    }

    lookup(ip: string): number {
        let curr = this.table;
        for (let i = 0; i < ip.length; i++) {
            const curr_dir = DIRECTIONS[Number(ip[i])];
            if (curr[curr_dir]) curr = curr[curr_dir];
            else break;
        }
        return curr.value;
    }
}

Part 2: Now we want to add support for a default port for when no entry in the table matches. We should be able to set this and have it returned no matter the state of our table. For example:

const ip = new RoutingTable();
ip.insert("10", 3);
ip.insert("010", 4);
ip.insert("1111", 5);

console.log(ip.lookup("010110")); // 4
console.log(ip.lookup("111111")); // 5
console.log(ip.lookup("000000")); // -1

ip.setDefaultPort(999);
console.log(ip.lookup("000000")); // 999

Again, pretty straightforward. I opted to use my existing default value of -1 and simply return the default port if we have a lookup returning a port less than zero.

...

class RoutingTable {
    table: TreeNode = new TreeNode(-1);
    defaultPort = -1;

    ...

    lookup(ip: string): number {
        let curr = this.table;
        for (let i = 0; i < ip.length; i++) {
            const curr_dir = DIRECTIONS[Number(ip[i])];
            if (curr[curr_dir]) curr = curr[curr_dir];
            else break;
        }

        return curr.value < 0
            ? this.defaultPort
            : curr.value;
    }

    setDefaultPort(port: number): void {
        this.defaultPort = port;
    }
}

Part 3: Up until now, we've only worried about unstructured binary IP addresses. What if we want to support real IPv4 addresses?

IP Prefix    Port
==================
34.126       => 301
34.120       => 120

lookup("34.126.7.1") = 301
lookup("34.120.8.1") = 120
lookup("192.168.0.1") = -1

My initial response was that we could simply convert them to binary and do the same thing, but I was asked what I would do if we didn't want to do the conversion. I opted to instead change the radix of the tree from 2 to 10 and basically do the same thing. Represent the children of a node using a dictionary to other nodes. Also add mappings for "." to deal with lookups like lookup("3.4.12.6") vs lookup("34.126.7.1").

class TreeNode {
    value: number;
    children: {
        [index: string]: TreeNode
    }

    ...
}

class RoutingTable {
    ...
    
    insert(ipPrefix: string, port: number): void {
        let curr = this.table;
        for (let i = 0; i < ipPrefix.length; i++) {
            const child = curr.children[ipPrefix[i]];
            if (child) curr = child;
            else {
                curr.children[ipPrefix[i]] = new TreeNode(-1);
                curr = curr.children[ipPrefix[i]];
            }
        }
        curr.value = port;
    }

    lookup(ip: string): number {
        let curr = this.table;
        for (let i = 0; i < ip.length; i++) {
            const child = curr.children[ip[i]];
            if (child) curr = child;
            else break;
        }

        return curr.value < 0
            ? this.defaultPort
            : curr.value;
    }

    ...
}

Thoughts:
Not sure how I did just yet, but overall I'm happy with the interview process. The interviewer was helpful and cooperative. It was also really interesting in that he had specific questions for me and wanted to thoroughly talk through the solution first before writing any code. Most other interviews I have dont really do this and instead want me to get straight into it. I did make a few silly mistakes that the interviewer helped out with, but I'm hoping this didn't reflect too poorly on me. I got to the final part with about ~5-10 minutes remaining, but was able to get it working since the changes to the previous versions were fairly minimal. I should also mention that they said they wanted unit tests specifically, but they were happy with simple printing of answers to the console.

Comments (5)