Watch 10 video solutions for Implement Router, a medium level problem involving Array, Hash Table, Binary Search. This walkthrough by codestorywithMIK has 7,911 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Design a data structure that can efficiently manage data packets in a network router. Each data packet consists of the following attributes:
source: A unique identifier for the machine that generated the packet.destination: A unique identifier for the target machine.timestamp: The time at which the packet arrived at the router.Implement the Router class:
Router(int memoryLimit): Initializes the Router object with a fixed memory limit.
memoryLimit is the maximum number of packets the router can store at any given time.bool addPacket(int source, int destination, int timestamp): Adds a packet with the given attributes to the router.
source, destination, and timestamp already exists in the router.true if the packet is successfully added (i.e., it is not a duplicate); otherwise return false.int[] forwardPacket(): Forwards the next packet in FIFO (First In First Out) order.
[source, destination, timestamp].int getCount(int destination, int startTime, int endTime):
[startTime, endTime].Note that queries for addPacket will be made in non-decreasing order of timestamp.
Example 1:
Input:
["Router", "addPacket", "addPacket", "addPacket", "addPacket", "addPacket", "forwardPacket", "addPacket", "getCount"]
[[3], [1, 4, 90], [2, 5, 90], [1, 4, 90], [3, 5, 95], [4, 5, 105], [], [5, 2, 110], [5, 100, 110]]
Output:
[null, true, true, false, true, true, [2, 5, 90], true, 1]
Explanation
Router router = new Router(3); // Initialize Router with memoryLimit of 3.[1, 4, 90] is removed as number of packets exceeds memoryLimit. Return True.[2, 5, 90] and remove it from router.[100, 110] is [4, 5, 105]. Return 1.Example 2:
Input:
["Router", "addPacket", "forwardPacket", "forwardPacket"]
[[2], [7, 4, 90], [], []]
Output:
[null, true, [7, 4, 90], []]
Explanation
Router router = new Router(2); // InitializeRouter with memoryLimit of 2.[7, 4, 90].[].
Constraints:
2 <= memoryLimit <= 1051 <= source, destination <= 2 * 1051 <= timestamp <= 1091 <= startTime <= endTime <= 109105 calls will be made to addPacket, forwardPacket, and getCount methods altogether.addPacket will be made in non-decreasing order of timestamp.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Array Scan | Insert: O(1), Query: O(n) | O(n) | Small datasets or quick prototype implementations |
| Hash Map + Queue + Binary Search | Insert: O(1), Query: O(log n) | O(n) | General case with frequent range queries and ordered packet processing |