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.
memoryLimit
is 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
, andtimestamp
already exists in the router. - Return
true
if 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^5
1 <= source, destination <= 2 * 10^5
1 <= timestamp <= 10^9
1 <= startTime <= endTime <= 10^9
- At most
105
calls will be made toaddPacket
,forwardPacket
, andgetCount
methods altogether. - queries for
addPacket
will 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
getCount
by 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)
: storemaxSize
only.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
removed
counter. - Enqueue new packet, mark seen, and append
timestamp
totimestamps[destination]
.
forwardPacket()
: pop from queue; if empty return empty array; otherwise remove seen key and increment that destination’sremoved
counter; 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).