Network engineer coding interview questions

As asked

Given a weighted directed graph representing network routers and link costs, implement Dijkstra's shortest-path algorithm to compute the minimum-cost path from a source router to all other routers. This models how OSPF computes the SPF tree. Return a dictionary mapping each node to its minimum cost from the source.

Sample answer outline

Use a min-heap (priority queue) initialized with (0, source). Pop the lowest-cost node, iterate over its neighbors; if cost + edge_weight < known dist, update and push. Return the dist dictionary. Candidate should note time complexity O((V+E) log V) with a heap, discuss how OSPF uses this on the LSDB to build the forwarding table, and mention negative-weight edges are not valid for link costs.

Reference implementation (python)

import heapq

def dijkstra(graph: dict[str, list[tuple[str, int]]], src: str) -> dict[str, int]:
    # graph = {'A': [('B', 10), ('C', 3)], ...}
    dist = {node: float('inf') for node in graph}
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        cost, u = heapq.heappop(heap)
        if cost > dist[u]:
            continue
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(heap, (dist[v], v))
    return dist

Expect these follow-ups

• How would you modify this to return the actual path (list of routers) not just the cost?
• Why does OSPF trigger a partial SPF recalculation rather than a full one when a leaf changes?

As asked

Write a function that takes a CIDR block (e.g., '10.0.0.0/16') and an integer N (a power of 2), and returns a list of N equal sub-CIDR strings. For example, split('10.0.0.0/16', 4) returns ['10.0.0.0/18', '10.0.64.0/18', '10.0.128.0/18', '10.0.192.0/18']. This is a common task when allocating IP space across regions.

Sample answer outline

Compute new prefix length as original + log2(N). Step through the address space by incrementing by 2^(32 - new_prefix). Convert integer addresses back to dotted-quad strings. Candidate should handle edge cases: N must be a power of 2, resulting prefix must not exceed /32, and should mention Python's ipaddress module as the idiomatic approach.

Reference implementation (python)

import ipaddress
import math

def split_cidr(cidr: str, n: int) -> list[str]:
    network = ipaddress.ip_network(cidr, strict=False)
    bits_needed = int(math.log2(n))
    new_prefix = network.prefixlen + bits_needed
    subnets = list(network.subnets(new_prefix=new_prefix))
    return [str(s) for s in subnets]

# split_cidr('10.0.0.0/16', 4)
# => ['10.0.0.0/18', '10.0.64.0/18', '10.0.128.0/18', '10.0.192.0/18']

Expect these follow-ups

• How would you check if two CIDR blocks overlap before allocating them?
• What is the longest prefix match (LPM) algorithm and how is it implemented efficiently in hardware?

As asked

Implement a DNS cache that stores A-record results with per-entry TTL. It should support lookup(domain) which returns the cached IP if not expired, and store(domain, ip, ttl_seconds) which inserts or updates an entry. Use an LRU eviction policy when the cache is full (capacity is a constructor parameter). This models what a stub resolver or DNS forwarder maintains.

Sample answer outline

Combine an OrderedDict for LRU ordering with stored (ip, expiry_timestamp) values. On lookup, check if current time > expiry and treat as a miss (remove the entry). On store, if at capacity evict the least-recently-used entry. Move accessed entries to end of OrderedDict on hit. Candidate should discuss thread-safety (add a lock for concurrent resolver use) and note that negative caching (NXDOMAIN) should also be stored with the SOA MINIMUM TTL.

Reference implementation (python)

import time
from collections import OrderedDict

class DNSCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: OrderedDict[str, tuple[str, float]] = OrderedDict()

    def lookup(self, domain: str) -> str | None:
        if domain not in self.cache:
            return None
        ip, expiry = self.cache[domain]
        if time.time() > expiry:
            del self.cache[domain]
            return None
        self.cache.move_to_end(domain)
        return ip

    def store(self, domain: str, ip: str, ttl: int) -> None:
        if domain in self.cache:
            self.cache.move_to_end(domain)
        elif len(self.cache) >= self.cap:
            self.cache.popitem(last=False)
        self.cache[domain] = (ip, time.time() + ttl)

Expect these follow-ups

• How would you extend this to support multiple A records (round-robin) for one domain?
• What TTL value should a negative cache entry use according to RFC 2308?

As asked

Implement a sliding-window rate limiter that allows at most max_requests requests per window_seconds from a given source IP. This models per-source rate limiting in a firewall or DDoS protection appliance. is_allowed(ip, timestamp) returns True if the request is permitted.

Sample answer outline

Store a deque of timestamps per IP. On each call, pop timestamps older than (timestamp - window_seconds) from the left, then check if the deque length is below max_requests. If yes, append timestamp and return True; otherwise return False. Space is O(max_requests * unique_IPs). Candidate should mention the fixed-window alternative and its boundary burst problem, and note that in production this would use Redis ZRANGEBYSCORE and ZADD atomically with Lua scripting for distributed enforcement.

Reference implementation (python)

from collections import defaultdict, deque

class RateLimiter:
    def __init__(self, max_requests: int, window_seconds: float):
        self.max_req = max_requests
        self.window = window_seconds
        self.buckets: dict[str, deque[float]] = defaultdict(deque)

    def is_allowed(self, ip: str, timestamp: float) -> bool:
        dq = self.buckets[ip]
        cutoff = timestamp - self.window
        while dq and dq[0] < cutoff:
            dq.popleft()
        if len(dq) < self.max_req:
            dq.append(timestamp)
            return True
        return False

Expect these follow-ups

• How does a token bucket algorithm differ from a sliding window in burst handling?
• Why must a distributed rate limiter use atomic operations and what race condition occurs without them?

As asked

A Layer 7 load balancer needs to route requests to 10 backend servers with session stickiness. Implement consistent hashing so that adding or removing a server reshuffles the minimum number of keys. Include virtual nodes to avoid hotspots. This models what Nginx, HAProxy, or a CDN origin selection algorithm does internally.

Sample answer outline

Use a sorted list of (hash(server + replica_id), server) virtual node entries. To route a key, hash it and binary-search for the first virtual node >= that hash (wrapping around). Adding a server inserts its virtual nodes; only keys between its predecessor and its new position migrate. Candidate should discuss vnodes-per-server (100 to 200 is typical) to smooth distribution, and note that this is the algorithm behind memcached, Cassandra, and CDN origin selection.

Reference implementation (python)

import hashlib
import bisect

class ConsistentHashRing:
    def __init__(self, servers: list[str], vnodes: int = 150):
        self.ring: list[tuple[int, str]] = []
        self.vnodes = vnodes
        for s in servers:
            self._add(s)
        self.ring.sort()

    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def _add(self, server: str) -> None:
        for i in range(self.vnodes):
            h = self._hash(f"{server}-{i}")
            self.ring.append((h, server))

    def get(self, key: str) -> str:
        h = self._hash(key)
        keys = [r[0] for r in self.ring]
        idx = bisect.bisect_left(keys, h) % len(self.ring)
        return self.ring[idx][1]

Expect these follow-ups

• What happens to in-flight HTTP sessions when a backend is removed from the ring?
• How does a load balancer handle a backend that is slow but not failed (circuit breaker pattern)?

As asked

A router's forwarding table contains CIDR prefixes. Implement a binary trie that stores IPv4 prefixes and supports longest-prefix-match lookup for a destination address. This is the fundamental algorithm inside every IP router's FIB lookup. Return the next-hop for the most specific matching prefix.

Sample answer outline

Build a binary trie where each bit of the IP address (MSB first) is an edge (0 or 1). At prefix insertion, walk the trie for prefix_len bits and store next-hop at that node. At lookup, walk all 32 bits keeping track of the last node that had a stored next-hop. Return that best-match next-hop. Candidate should discuss hardware implementations (TCAM, DIR-24-8) that achieve O(1) lookup, and note that modern routers use Patricia tries to compress empty branches.

Reference implementation (python)

class TrieNode:
    def __init__(self):
        self.children = [None, None]
        self.next_hop = None

class PrefixTrie:
    def __init__(self):
        self.root = TrieNode()

    def _ip_to_bits(self, ip: str) -> list[int]:
        parts = list(map(int, ip.split('.')))
        bits = []
        for p in parts:
            for i in range(7, -1, -1):
                bits.append((p >> i) & 1)
        return bits

    def insert(self, prefix: str, next_hop: str) -> None:
        ip, plen = prefix.split('/')
        bits = self._ip_to_bits(ip)
        node = self.root
        for b in bits[:int(plen)]:
            if node.children[b] is None:
                node.children[b] = TrieNode()
            node = node.children[b]
        node.next_hop = next_hop

    def lookup(self, ip: str) -> str | None:
        bits = self._ip_to_bits(ip)
        node, best = self.root, self.root.next_hop
        for b in bits:
            node = node.children[b]
            if node is None:
                break
            if node.next_hop:
                best = node.next_hop
        return best

Expect these follow-ups

• What is a TCAM and why does it support O(1) LPM lookup where a software trie cannot?
• How does BGP route aggregation (supernetting) reduce FIB size?

As asked

Given a graph of switches and their trunk connections, write a function that detects whether the topology contains a cycle (which would cause a broadcast storm if STP were disabled). Return True if a loop exists, False otherwise. This models the input validation a network automation tool might perform before provisioning.

Sample answer outline

Use DFS with a visited set and a recursion stack (or a parent tracking approach for undirected graphs) to detect back edges. For an undirected graph (trunk links are bidirectional), track the parent node to distinguish tree edges from back edges. Return True if any back edge is found. Candidate should note the analogy to STP which detects loops and blocks ports to create a loop-free spanning tree.

Reference implementation (python)

def has_loop(adj: dict[str, list[str]]) -> bool:
    visited = set()

    def dfs(node: str, parent: str | None) -> bool:
        visited.add(node)
        for neighbor in adj.get(node, []):
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True  # back edge = loop
        return False

    for node in adj:
        if node not in visited:
            if dfs(node, None):
                return True
    return False

Expect these follow-ups

• If you find a loop, which edge would STP logically block and what determines that choice?
• How does RSTP detect topology changes faster than classic 802.1D?

As asked

Write a function that computes the minimum TCP receive window size needed to fully saturate a link given its bandwidth (in Mbps) and round-trip time (in milliseconds). This models the bandwidth-delay product calculation a network engineer performs when tuning TCP buffer sizes for long-fat networks.

Sample answer outline

BDP = bandwidth_bytes_per_sec * rtt_seconds. TCP can have at most one BDP of data in flight before needing an ACK; if the window is smaller than BDP the sender stalls waiting for ACKs. Candidate should convert units carefully (Mbps to bytes/sec, ms to seconds), return result in bytes, and note that TCP window scaling (RFC 7323) is needed for windows above 65535 bytes, and that most OS buffer sizes default to 4 to 8 MB which is adequate for most paths.

Reference implementation (python)

def min_tcp_window(bandwidth_mbps: float, rtt_ms: float) -> int:
    """
    Returns minimum TCP window in bytes to fully utilize the link.
    BDP = bandwidth (bytes/sec) * RTT (seconds)
    """
    bandwidth_bytes_per_sec = bandwidth_mbps * 1_000_000 / 8
    rtt_seconds = rtt_ms / 1000
    bdp = bandwidth_bytes_per_sec * rtt_seconds
    return int(bdp)

# Example: 1 Gbps link, 100ms RTT
# min_tcp_window(1000, 100) => 12_500_000 bytes (~12 MB)

Expect these follow-ups

• What is a 'long fat network' (LFN) and why do default TCP buffers underperform on it?
• How does BBR congestion control differ from CUBIC in terms of how it determines the sending rate?

As asked

Write a function overlap(net1: str, net2: str) -> bool that returns True if two CIDR blocks share any IP addresses. This is used by network automation tools to validate IP allocation before provisioning to prevent routing conflicts. Handle both IPv4 and IPv6 inputs.

Sample answer outline

Use Python's ipaddress.ip_network and the overlaps() method, or manually compare whether the network address of one is within the range of the other. Candidate should handle the edge case of a /32 or /128 host route overlapping with a larger prefix, and note that overlapping allocations would cause black holes or routing instability in production.

Reference implementation (python)

import ipaddress

def overlap(net1: str, net2: str) -> bool:
    n1 = ipaddress.ip_network(net1, strict=False)
    n2 = ipaddress.ip_network(net2, strict=False)
    return n1.overlaps(n2)

# overlap('10.0.0.0/24', '10.0.0.128/25') => True
# overlap('10.0.0.0/24', '10.0.1.0/24')   => False

Expect these follow-ups

• Given a list of 10,000 CIDR prefixes, how would you efficiently find all pairs that overlap?
• What does the 'strict' parameter in ipaddress.ip_network do and when would you turn it off?

As asked

Write a function that takes a list of BGP route strings in the format 'NETWORK/PREFIX NEXT-HOP AS-PATH' and returns only routes with prefix length >= min_prefix. This models a common network automation task: parsing router CLI output (or structured data from pyEOS/Netmiko) and applying policy filters programmatically.

Sample answer outline

Split each line on whitespace, extract the first field, split on '/' to get prefix length, cast to int, and compare. Return filtered list. Candidate should mention that production automation would use structured output (JSON from RESTCONF, gRPC from gNMI, or Netmiko/Napalm) rather than screen scraping, and that regex is a fallback for legacy platforms. Should handle malformed lines gracefully.

Reference implementation (python)

def filter_routes(routes: list[str], min_prefix: int) -> list[str]:
    result = []
    for line in routes:
        parts = line.strip().split()
        if not parts:
            continue
        try:
            network, prefix_len = parts[0].split('/')
            if int(prefix_len) >= min_prefix:
                result.append(line)
        except (ValueError, IndexError):
            continue
    return result

# routes = ['192.168.0.0/24 10.0.0.1 65001 65002',
#           '10.0.0.0/8 10.0.0.2 65003']
# filter_routes(routes, 24) => ['192.168.0.0/24 ...']

Expect these follow-ups

• How would you convert this to use structured data from a gNMI path instead of CLI parsing?
• What is NAPALM and how does it abstract multi-vendor router interfaces?

As asked

Explain how traceroute works at the packet level and implement a simplified version in Python that sends UDP probes with incrementing TTL and listens for ICMP Time Exceeded replies to discover each hop. Handle timeouts for unresponsive hops.

Sample answer outline

Each probe is a UDP packet (or ICMP echo in some implementations) sent with TTL=1, TTL=2, etc. When a router decrements TTL to 0, it drops the packet and sends ICMP Type 11 (Time Exceeded) back to the source; the source's IP in that ICMP reply is the hop's address. Candidate should use raw sockets (IPPROTO_RAW), set IP_TTL socket option, bind a listener socket for ICMP, and implement a per-hop timeout loop sending 3 probes and printing '*' for timeouts. Note root/administrator privileges required for raw sockets.

Reference implementation (python)

import socket, struct, time

def traceroute(dest: str, max_hops: int = 30, timeout: float = 1.0):
    dest_ip = socket.gethostbyname(dest)
    for ttl in range(1, max_hops + 1):
        send_sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM, socket.IPPROTO_UDP)
        recv_sock = socket.socket(socket.AF_INET, socket.SOCK_RAW, socket.IPPROTO_ICMP)
        recv_sock.settimeout(timeout)
        send_sock.setsockopt(socket.IPPROTO_IP, socket.IP_TTL, ttl)
        send_sock.sendto(b'', (dest_ip, 33434))
        try:
            data, addr = recv_sock.recvfrom(512)
            print(f"{ttl}  {addr[0]}")
            if addr[0] == dest_ip:
                break
        except socket.timeout:
            print(f"{ttl}  *")
        finally:
            send_sock.close()
            recv_sock.close()

Expect these follow-ups

• Why do some hops show '*' even though routing continues past them?
• How does TCP traceroute (tracetcp) differ from UDP traceroute in terms of firewall traversal?