Problem
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.
memoryLimitis the maximum number of packets the router can store at any given time.- If adding a new packet would exceed this limit, the oldest packet must be removed to free up space.
bool addPacket(int source, int destination, int timestamp): Adds a packet with the given attributes to the router.
- A packet is considered a duplicate if another packet with the same
source,destination, andtimestampalready exists in the router. - Return
trueif the packet is successfully added (i.e., it is not a duplicate); otherwise returnfalse.
int[] forwardPacket(): Forwards the next packet in FIFO (First In First Out) order.
- Remove the packet from storage.
- Return the packet as an array
[source, destination, timestamp]. - If there are no packets to forward, return an empty array.
int getCount(int destination, int startTime, int endTime):
- Returns the number of packets currently stored in the router (i.e., not yet forwarded) that have the specified destination and have timestamps in the inclusive range
[startTime, endTime].
Note that queries for addPacket will be made in increasing order of
timestamp.
Examples
Example 1
| |
Example 2
| |
Constraints
2 <= memoryLimit <= 10^51 <= source, destination <= 2 * 10^51 <= timestamp <= 10^91 <= startTime <= endTime <= 10^9- At most
105calls will be made toaddPacket,forwardPacket, andgetCountmethods altogether. - queries for
addPacketwill be made in increasing order oftimestamp.
Solution
Method 1 – Queue + Duplicate Set + Per-destination Timestamps (Offset + Binary Search)
Intuition
We must support three operations efficiently: insert packets in arrival order with duplicate detection, forward (pop) the oldest packet, and count how many current packets for a given destination have timestamps in a given inclusive range. Because addPacket calls come with non-decreasing timestamps, we can append timestamps per destination into a vector (or list). Removing arbitrary elements from the middle of those vectors would be expensive; instead we track how many leading timestamps have been logically removed for each destination (an “offset”). This lets us avoid expensive deletes and answer range queries by binary-searching the destination’s timestamp list starting from the offset.
Key ideas:
- Use a queue for FIFO order and a hash-set for duplicate detection (constant-time checks).
- For each destination keep a list of timestamps appended in arrival order.
- On eviction/forward, increment the destination’s offset counter instead of removing from the list.
- Implement
getCountby performing binary search (lower/upper bound) on the per-destination timestamp list starting at the offset — this is O(log k) where k is the number of timestamps for that destination.
This matches the working Java approach and avoids TLE by preventing repeated O(n) deletions.
Approach (step-by-step)
Router(memoryLimit): storemaxSizeonly.addPacket(source, destination, timestamp):- If packet is duplicate (seen set), return false.
- If capacity reached, pop from queue, remove its seen key, and increment that destination’s
removedcounter. - Enqueue new packet, mark seen, and append
timestamptotimestamps[destination].
forwardPacket(): pop from queue; if empty return empty array; otherwise remove seen key and increment that destination’sremovedcounter; return the packet array.getCount(destination, startTime, endTime):- If no timestamps for destination, return 0.
- Let off =
removed[destination](default 0). - Do
lo = lowerBound(list, startTime, off)andhi = upperBound(list, endTime, off); returnmax(0, hi - lo).
Code
| |
| |
| |
| |
| |
| |
| |
Complexity
- ⏰ Time complexity:
O(1)addPacket: amortized O(1) (append + hash/queue ops).forwardPacket: O(1).getCount: O(log k) where k is number of timestamps stored for the destination (binary search).
- 🧺 Space complexity:
O(m)— Where m is the memory limit (number of packets stored).