Implement Router - Solution & Explanation

Problem Overview: Design a router that receives packets, processes them in order, and answers queries about packets routed to specific destinations within a time range. The challenge is maintaining insertion order for forwarding while also supporting fast lookups for historical queries.

Approach 1: Naive Packet Storage (O(n) query time, O(n) space)

The simplest implementation stores all packets in an array as they arrive. Each query scans the entire list and counts packets that match the destination and fall within the requested time window. Forwarding packets is easy because you process them in order using a pointer or by removing from the front. The downside is query performance—every query requires iterating through all stored packets, resulting in O(n) time per query and poor scalability when packet volume grows.

Approach 2: Hash Map + Queue + Binary Search (O(log n) query, O(n) space)

A more efficient design separates responsibilities across multiple data structures. A queue maintains packets in arrival order so forwarding operations always process the earliest packet in O(1) time. A hash table maps each destination to a sorted list of packet timestamps. When a packet arrives, push it into the queue and append its timestamp to the destination's list.

Queries become fast because timestamps for each destination are already sorted. Use binary search to find the first timestamp >= startTime and the first timestamp > endTime. The difference between these indices gives the number of packets in the requested range. Each query runs in O(log n) time while insertions remain O(1) amortized.

This structure also works well when packets are forwarded or removed. Since the queue tracks order and the timestamp arrays remain sorted by insertion time, the router can maintain consistency while keeping operations efficient.

Recommended for interviews: The Hash Map + Queue + Binary Search design is the expected solution. It demonstrates the ability to combine multiple data structures—queue for ordering, hash map for grouping, and binary search for fast range queries. A brute force scan shows baseline understanding, but the optimized structure highlights strong system design and algorithmic thinking.