3508. Implement Router

MediumDesignQueueArrayHash TableBinary SearchOrdered Set

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

We need to design a data structure that efficiently manages data packets flowing through a network router. Each data packet carries three pieces of information:

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.

The router has a fixed capacity, and we must implement the Router class with the following operations:

Router(int memoryLimit): Initializes the router with a fixed memoryLimit.

memoryLimit is the maximum number of packets the router can hold at any moment.
Whenever adding a new packet would push the total beyond this limit, the oldest packet (the one that arrived first) must be removed to make room.

bool addPacket(int source, int destination, int timestamp): Adds a packet with the given attributes to the router.

A packet is treated as a duplicate if another packet already in the router shares the same source, destination, and timestamp.
Return true if the packet is successfully added (i.e., it is not a duplicate); otherwise return false.

int[] forwardPacket(): Forwards the next packet using FIFO (First In First Out) order.

Remove that packet from storage.
Return it 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 how many packets currently stored in the router (i.e., not yet forwarded) have the given destination and whose timestamps fall within the inclusive range [startTime, endTime].

Note that calls to addPacket will arrive in non-decreasing order of timestamp.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Design + Supporting Data Structures?

This problem maps to Design + Supporting Data Structures through a short path in the full flowchart.

The problem asks to implement a Router class with packet storage, duplicate detection, FIFO forwarding, and range-count queries, requiring a combination of queue, hash set, and sorted lists.

Open in Flowchart

Intuition

Let's look at what each operation needs and find the right tool for it.

First, the router behaves like a queue: packets leave in the same order they arrive (FIFO), and when memory is full, we drop the oldest one. A deque is the natural fit here — we append new packets at the tail and pop the oldest from the front, both in O(1) time.

Second, we need to quickly detect duplicates. A packet is a duplicate if the same (source, destination, timestamp) triple already lives in the router. To check membership in constant time, we keep a set of the packets currently stored. To save space and avoid storing tuples, we can encode each triple into a single integer using bit shifting (for example, a << 46 | b << 29 | c), as long as each field fits within its allotted bits.

Third comes the tricky part: getCount asks how many currently stored packets go to a given destination with a timestamp inside [startTime, endTime]. The key observation is that timestamps arrive in non-decreasing order. This means if we group timestamps by destination, each group's list is automatically sorted. On a sorted list, counting how many values fall in a range is a classic binary search task: find the left boundary for startTime and the right boundary for endTime, and the difference between the two positions is the answer.

But there's a catch — packets can be forwarded (removed from the front), and those should no longer be counted. Physically deleting them from each destination's list would be slow. Instead, we use a clever trick: for every destination we record idx, the number of packets already forwarded for that destination. Because forwarding also happens in FIFO order, the forwarded timestamps are always a prefix of the destination's sorted list. So when we run binary search, we simply start searching from index idx, effectively skipping the already-forwarded packets without ever erasing them.

Putting these pieces together:

a deque handles FIFO order and oldest-packet eviction,
a set of encoded triples handles duplicate detection,
a per-destination sorted timestamp list plus binary search handles range counting,
a per-destination forwarded counter idx keeps the counting accurate after packets leave.

Each piece independently keeps its operation fast, giving us O(1) adds and forwards and O(\log n) counting.

Pattern Learn more about Queue and Binary Search patterns.

Solution Approach

We use a Hash Map + Queue + Binary Search to handle all operations efficiently. The data structures maintained are:

vis: a set storing the hash values of packets currently in the router, used for fast duplicate detection.
q: a deque storing the packets currently in the router, used to maintain FIFO order.
idx: a hash map (defaultdict(int)) recording the number of packets already forwarded for each destination.
d: a hash map (defaultdict(list)) storing the list of timestamps for each destination.

To encode a packet into a single integer for storage in vis, we use a helper function f:

def f(self, a, b, c):
    return a << 46 | b << 29 | c

This packs source, destination, and timestamp into one integer by bit-shifting, so each triple maps to a unique value.

addPacket(source, destination, timestamp)

Compute the hash value x = self.f(source, destination, timestamp).
If x is already in vis, the packet is a duplicate, so return false.
Otherwise, add x to vis.
If the queue size has reached lim, call forwardPacket() to evict the oldest packet and free up space.
Append the new packet (source, destination, timestamp) to q, and append its timestamp to d[destination].
Return true.

Because timestamps arrive in non-decreasing order, d[destination] stays sorted automatically. The time complexity is O(1).

forwardPacket()

If q is empty, return an empty array.
Otherwise, pop the head packet (s, d, t) from q.
Remove its hash value from vis using self.f(s, d, t).
Increment idx[d] by 1 to mark that one more packet for destination d has been forwarded.
Return [s, d, t].

The time complexity is O(1).

getCount(destination, startTime, endTime)

Get the timestamp list ls = self.d[destination] and the number of forwarded packets k = self.idx[destination].
Since the first k timestamps have already been forwarded (a prefix of the sorted list), we start our search from index k.
Use bisect_left(ls, startTime, k) to find the first position i where the timestamp is >= startTime.
Use bisect_left(ls, endTime + 1, k) to find the first position j where the timestamp is > endTime.
The number of valid packets is j - i.

The time complexity is O(\log n), where n is the length of the timestamp list.

Overall, this design achieves O(1) for addPacket and forwardPacket, and O(\log n) for getCount, while the idx counter cleverly avoids ever deleting elements from the timestamp lists.

Example Walkthrough

Let's trace through a small example with memoryLimit = 3.

Initial state:

vis = {}          (encoded packets in router)
q   = []          (FIFO queue)
idx = {}          (forwarded count per destination)
d   = {}          (timestamp list per destination)

Step 1: addPacket(1, 10, 100)

Encode: x = f(1, 10, 100). Not in vis → not a duplicate.
Add x to vis. Queue size (0) < limit (3), so no eviction.
Append packet to q and timestamp to d[10].

q   = [(1,10,100)]
d   = {10: [100]}
idx = {}
→ returns true

Step 2: addPacket(2, 20, 105)

Not a duplicate. Queue size (1) < 3.

q   = [(1,10,100), (2,20,105)]
d   = {10: [100], 20: [105]}
→ returns true

Step 3: addPacket(1, 10, 110)

Different timestamp from packet 1, so not a duplicate. Queue size (2) < 3.

q   = [(1,10,100), (2,20,105), (1,10,110)]
d   = {10: [100, 110], 20: [105]}
→ returns true

Notice d[10] is [100, 110] — automatically sorted because timestamps arrive non-decreasing.

Step 4: addPacket(1, 10, 100) (duplicate!)

Encode x = f(1, 10, 100). This is already in vis.
Return immediately, no changes.

→ returns false

Step 5: addPacket(3, 10, 115)

Not a duplicate. Queue size (3) equals limit (3) → must evict the oldest.
Call forwardPacket() internally: pop (1,10,100), remove its hash from vis, and idx[10] += 1.
Now append the new packet.

After eviction:
q   = [(2,20,105), (1,10,110)]
idx = {10: 1}            ← one packet for dest 10 forwarded

After adding new packet:
q   = [(2,20,105), (1,10,110), (3,10,115)]
d   = {10: [100, 110, 115], 20: [105]}
idx = {10: 1}
→ returns true

Key point: d[10] still physically holds 100, but idx[10] = 1 marks that the first entry (a prefix) is already forwarded.

Step 6: getCount(10, 100, 115)

ls = d[10] = [100, 110, 115], k = idx[10] = 1.
Start searching from index k = 1, skipping the forwarded 100.
i = bisect_left(ls, 100, 1) → first index ≥ 100 starting at 1 → i = 1.
j = bisect_left(ls, 116, 1) → first index > 115 starting at 1 → j = 3.
Answer = j - i = 3 - 1 = 2.

The two valid stored packets are timestamps 110 and 115. The forwarded 100 is correctly excluded even though it still sits in the list — the idx offset handled it without any deletion.

→ returns 2

Step 7: forwardPacket()

Pop head (2,20,105), remove its hash from vis, idx[20] += 1.

q   = [(1,10,110), (3,10,115)]
idx = {10: 1, 20: 1}
→ returns [2, 20, 105]

This walkthrough demonstrates how each structure cooperates: the deque drives FIFO order and eviction (Steps 5, 7), the set catches duplicates instantly (Step 4), and the per-destination sorted list + idx offset + binary search delivers accurate range counts without ever deleting forwarded entries (Step 6).

Solution Implementation

1from collections import deque, defaultdict
2from bisect import bisect_left
3from typing import List
4
5
6class Router:
7
8    def __init__(self, memoryLimit: int):
9        # Maximum number of packets the router can hold at once
10        self.memory_limit = memoryLimit
11        # Set of encoded packets currently in the router, for O(1) duplicate checks
12        self.packet_set = set()
13        # FIFO queue holding packets in arrival order (source, destination, timestamp)
14        self.packet_queue = deque()
15        # For each destination: index pointing to the first timestamp not yet forwarded
16        self.forwarded_index = defaultdict(int)
17        # For each destination: list of timestamps in non-decreasing arrival order
18        self.timestamps = defaultdict(list)
19
20    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
21        # Encode the packet into a unique key to detect duplicates
22        key = self._encode(source, destination, timestamp)
23        if key in self.packet_set:
24            return False
25        self.packet_set.add(key)
26
27        # If the router is full, forward (remove) the oldest packet first
28        if len(self.packet_queue) >= self.memory_limit:
29            self.forwardPacket()
30
31        # Add the new packet to the queue and record its timestamp by destination
32        self.packet_queue.append((source, destination, timestamp))
33        self.timestamps[destination].append(timestamp)
34        return True
35
36    def forwardPacket(self) -> List[int]:
37        # Nothing to forward if the router is empty
38        if not self.packet_queue:
39            return []
40
41        # Remove the oldest packet (FIFO order)
42        source, destination, timestamp = self.packet_queue.popleft()
43        self.packet_set.remove(self._encode(source, destination, timestamp))
44        # Advance the forwarded pointer so this timestamp is excluded from counts
45        self.forwarded_index[destination] += 1
46        return [source, destination, timestamp]
47
48    def _encode(self, source: int, destination: int, timestamp: int) -> int:
49        # Pack the three fields into a single integer:
50        # timestamp uses the low 29 bits, destination the next 17 bits, source above
51        return source << 46 | destination << 29 | timestamp
52
53    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
54        # Timestamps for this destination, still sorted in arrival order
55        ts_list = self.timestamps[destination]
56        # Start searching from the first packet that hasn't been forwarded
57        start_index = self.forwarded_index[destination]
58        # Find the range [startTime, endTime] using binary search
59        left = bisect_left(ts_list, startTime, start_index)
60        right = bisect_left(ts_list, endTime + 1, start_index)
61        return right - left
62
63
64# Your Router object will be instantiated and called as such:
65# obj = Router(memoryLimit)
66# param_1 = obj.addPacket(source,destination,timestamp)
67# param_2 = obj.forwardPacket()
68# param_3 = obj.getCount(destination,startTime,endTime)
69

1class Router {
2    // Maximum number of packets the router can hold.
3    private int memoryLimit;
4
5    // Stores encoded keys of packets currently in the router, used to detect duplicates.
6    private Set<Long> packetKeys = new HashSet<>();
7
8    // FIFO queue holding packets in arrival order. Each entry is {source, destination, timestamp}.
9    private Deque<int[]> queue = new ArrayDeque<>();
10
11    // For each destination, the number of timestamps already forwarded (offset into the timestamp list).
12    private Map<Integer, Integer> forwardedOffset = new HashMap<>();
13
14    // For each destination, an append-only, non-decreasing list of arrival timestamps.
15    private Map<Integer, List<Integer>> timestampsByDest = new HashMap<>();
16
17    public Router(int memoryLimit) {
18        this.memoryLimit = memoryLimit;
19    }
20
21    public boolean addPacket(int source, int destination, int timestamp) {
22        long key = encode(source, destination, timestamp);
23        // Reject exact duplicate packets that are still inside the router.
24        if (packetKeys.contains(key)) {
25            return false;
26        }
27        packetKeys.add(key);
28        // If memory is full, forward (remove) the oldest packet first.
29        if (queue.size() >= memoryLimit) {
30            forwardPacket();
31        }
32        // Enqueue the new packet and record its timestamp for the destination.
33        queue.offer(new int[] {source, destination, timestamp});
34        timestampsByDest.computeIfAbsent(destination, k -> new ArrayList<>()).add(timestamp);
35        return true;
36    }
37
38    public int[] forwardPacket() {
39        // Nothing to forward when the router is empty.
40        if (queue.isEmpty()) {
41            return new int[] {};
42        }
43        int[] packet = queue.poll();
44        int source = packet[0], destination = packet[1], timestamp = packet[2];
45        // Remove its key so the same packet could be added again later.
46        packetKeys.remove(encode(source, destination, timestamp));
47        // Advance the forwarded offset for this destination (logical removal from the front).
48        forwardedOffset.merge(destination, 1, Integer::sum);
49        return new int[] {source, destination, timestamp};
50    }
51
52    public int getCount(int destination, int startTime, int endTime) {
53        List<Integer> timestamps = timestampsByDest.getOrDefault(destination, List.of());
54        // Skip timestamps that have already been forwarded.
55        int offset = forwardedOffset.getOrDefault(destination, 0);
56        // Count timestamps within [startTime, endTime] using binary search bounds.
57        int left = lowerBound(timestamps, startTime, offset);
58        int right = lowerBound(timestamps, endTime + 1, offset);
59        return right - left;
60    }
61
62    // Encodes a packet into a single long key for fast hashing and comparison.
63    private long encode(int source, int destination, int timestamp) {
64        return ((long) source << 46) | ((long) destination << 29) | (long) timestamp;
65    }
66
67    // Returns the first index >= fromIndex whose value is not less than target.
68    private int lowerBound(List<Integer> list, int target, int fromIndex) {
69        int left = fromIndex, right = list.size();
70        while (left < right) {
71            int mid = (left + right) >>> 1;
72            if (list.get(mid) < target) {
73                left = mid + 1;
74            } else {
75                right = mid;
76            }
77        }
78        return left;
79    }
80}
81
82/**
83 * Your Router object will be instantiated and called as such:
84 * Router obj = new Router(memoryLimit);
85 * boolean param_1 = obj.addPacket(source,destination,timestamp);
86 * int[] param_2 = obj.forwardPacket();
87 * int param_3 = obj.getCount(destination,startTime,endTime);
88 */
89

1class Router {
2private:
3    int memoryLimit;                                   // Maximum number of packets that can be stored
4    unordered_set<long long> presentPackets;           // Encoded packets currently in the router (for O(1) duplicate check)
5    deque<array<int, 3>> packetQueue;                  // FIFO queue of packets: {source, destination, timestamp}
6    unordered_map<int, int> forwardedIndex;            // For each destination, count of timestamps already forwarded
7    unordered_map<int, vector<int>> timestampsByDest;  // For each destination, the sorted list of timestamps
8
9    // Encode a packet (source, destination, timestamp) into a single 64-bit key.
10    // Layout: bits [46..) = source, bits [29..46) = destination, bits [0..29) = timestamp.
11    long long encode(int source, int destination, int timestamp) {
12        return ((long long) source << 46) | ((long long) destination << 29) | (long long) timestamp;
13    }
14
15public:
16    Router(int memoryLimit) {
17        this->memoryLimit = memoryLimit;
18    }
19
20    bool addPacket(int source, int destination, int timestamp) {
21        long long key = encode(source, destination, timestamp);
22
23        // Reject duplicate packets.
24        if (presentPackets.count(key)) {
25            return false;
26        }
27        presentPackets.insert(key);
28
29        // If memory is full, evict the oldest packet before inserting the new one.
30        if ((int) packetQueue.size() >= memoryLimit) {
31            forwardPacket();
32        }
33
34        // Store the new packet; timestamps stay sorted since they arrive non-decreasing.
35        packetQueue.push_back({source, destination, timestamp});
36        timestampsByDest[destination].push_back(timestamp);
37        return true;
38    }
39
40    vector<int> forwardPacket() {
41        // Nothing to forward when the queue is empty.
42        if (packetQueue.empty()) {
43            return {};
44        }
45
46        // Remove the oldest packet (front of the queue).
47        auto packet = packetQueue.front();
48        packetQueue.pop_front();
49
50        int source = packet[0], destination = packet[1], timestamp = packet[2];
51
52        // Erase its encoded key and advance the forwarded pointer for this destination.
53        presentPackets.erase(encode(source, destination, timestamp));
54        forwardedIndex[destination]++;
55
56        return {source, destination, timestamp};
57    }
58
59    int getCount(int destination, int startTime, int endTime) {
60        auto& timestamps = timestampsByDest[destination];
61        int start = forwardedIndex[destination];  // Skip already-forwarded timestamps
62
63        // Binary search within the still-active portion [start, end) of the timestamps.
64        auto lo = lower_bound(timestamps.begin() + start, timestamps.end(), startTime);
65        auto hi = lower_bound(timestamps.begin() + start, timestamps.end(), endTime + 1);
66        return hi - lo;
67    }
68};
69
70/**
71 * Your Router object will be instantiated and called as such:
72 * Router* obj = new Router(memoryLimit);
73 * bool param_1 = obj->addPacket(source,destination,timestamp);
74 * vector<int> param_2 = obj->forwardPacket();
75 * int param_3 = obj->getCount(destination,startTime,endTime);
76 */
77

1// Maximum number of packets the router can hold in its queue.
2let lim: number;
3// Set of encoded packet keys currently stored, used for O(1) duplicate checks.
4let vis: Set<number>;
5// FIFO queue of packets, each stored as [source, destination, timestamp].
6let q: [number, number, number][];
7// For each destination, the number of timestamps already forwarded (consumed).
8let idx: Map<number, number>;
9// For each destination, the list of timestamps in arrival (sorted) order.
10let d: Map<number, number[]>;
11
12/**
13 * Initializes the router with a given memory (queue) limit.
14 * @param memoryLimit Maximum number of packets the queue can hold.
15 */
16function Router(memoryLimit: number): void {
17    lim = memoryLimit;
18    vis = new Set();
19    q = [];
20    idx = new Map();
21    d = new Map();
22}
23
24/**
25 * Encodes (source, destination, timestamp) into a single numeric key
26 * for fast duplicate detection.
27 */
28function f(a: number, b: number, c: number): number {
29    return ((BigInt(a) << 46n) | (BigInt(b) << 29n) | BigInt(c)) as unknown as number;
30}
31
32/**
33 * Adds a packet to the router.
34 * Returns false if the same packet already exists; otherwise stores it
35 * (evicting the oldest packet if the queue is full) and returns true.
36 */
37function addPacket(source: number, destination: number, timestamp: number): boolean {
38    const x = f(source, destination, timestamp);
39    // Reject exact duplicate packets.
40    if (vis.has(x)) {
41        return false;
42    }
43    vis.add(x);
44    // Evict the oldest packet when at capacity.
45    if (q.length >= lim) {
46        forwardPacket();
47    }
48    q.push([source, destination, timestamp]);
49    // Record the timestamp for this destination (kept in arrival order).
50    if (!d.has(destination)) {
51        d.set(destination, []);
52    }
53    d.get(destination)!.push(timestamp);
54    return true;
55}
56
57/**
58 * Forwards (removes) the oldest packet in the queue.
59 * Returns the forwarded packet as [source, destination, timestamp],
60 * or an empty array if the queue is empty.
61 */
62function forwardPacket(): number[] {
63    if (q.length === 0) {
64        return [];
65    }
66    const [s, dst, t] = q.shift()!;
67    // Remove its key so the same packet could be added again later.
68    vis.delete(f(s, dst, t));
69    // Advance the consumed pointer for this destination.
70    idx.set(dst, (idx.get(dst) ?? 0) + 1);
71    return [s, dst, t];
72}
73
74/**
75 * Counts how many packets currently in the queue for the given destination
76 * have a timestamp within [startTime, endTime].
77 */
78function getCount(destination: number, startTime: number, endTime: number): number {
79    const ls = d.get(destination) ?? [];
80    // Skip timestamps already forwarded for this destination.
81    const k = idx.get(destination) ?? 0;
82    const i = lowerBound(ls, startTime, k);
83    const j = lowerBound(ls, endTime + 1, k);
84    return j - i;
85}
86
87/**
88 * Standard lower_bound binary search: returns the first index in [from, arr.length)
89 * whose value is not less than target.
90 */
91function lowerBound(arr: number[], target: number, from: number): number {
92    let l = from,
93        r = arr.length;
94    while (l < r) {
95        const m = Math.floor((l + r) / 2);
96        if (arr[m] < target) {
97            l = m + 1;
98        } else {
99            r = m;
100        }
101    }
102    return l;
103}
104
105/**
106 * Your Router object will be instantiated and called as such:
107 * Router(memoryLimit)
108 * var param_1 = addPacket(source,destination,timestamp)
109 * var param_2 = forwardPacket()
110 * var param_3 = getCount(destination,startTime,endTime)
111 */
112

Time and Space Complexity

Time Complexity:

__init__: O(1) — only initializes empty containers.
addPacket: O(1) amortized — computing the key via f is O(1), the set membership check and insertion are O(1) on average, the deque append is O(1), and the list append to self.d[destination] is O(1) amortized. When the memory limit is reached, it calls forwardPacket once, which is O(1). Therefore the overall cost is O(1).
forwardPacket: O(1) — popleft on the deque is O(1), the set removal is O(1) on average, and incrementing self.idx[d] is O(1).
f: O(1) — only bit-shift and bitwise-or operations.
getCount: O(log n) — two binary searches via bisect_left over the timestamp list of the given destination, where n is the number of timestamps stored for that destination. The subtraction j - i is O(1).

Space Complexity:

The space complexity is O(n), where n is the number of packets currently stored. The deque self.q and the set self.vis each hold at most n entries (bounded by memoryLimit), and the dictionary self.d accumulates timestamps per destination, totaling O(n) across all destinations. The self.idx dictionary stores at most one entry per distinct destination, which is also bounded by O(n). Hence the total space is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Checking the memory limit after adding the key to `packet_set`

A subtle ordering bug can occur if you mix up the sequence of operations inside addPacket. In the correct code, the flow is:

Check for duplicate → return False if found.
Add the key to packet_set.
If full, forward the oldest packet (which removes a different key).
Append the new packet.

The key insight is that the eviction in step 3 removes the oldest packet's key, which is guaranteed to be different from the new packet's key (since the new key is not a duplicate). If you reverse steps 2 and 3—i.e., evict before adding the new key—the logic still works, but a real danger arises if you accidentally add the new packet to the queue before the eviction check:

# WRONG: append first, then evict
self.packet_queue.append((source, destination, timestamp))   # now size = limit + 1
if len(self.packet_queue) > self.memory_limit:
    self.forwardPacket()   # evicts the packet we just added if limit logic is off

Solution: Always evict before appending the new packet, and use the correct comparison (>= when checking before append, since reaching the limit means there's no room for one more):

if len(self.packet_queue) >= self.memory_limit:
    self.forwardPacket()
self.packet_queue.append((source, destination, timestamp))

Pitfall 2: Insufficient bit-width in the `_encode` function

The encoding source << 46 | destination << 29 | timestamp reserves:

29 bits for timestamp (values up to ~5.3 × 10⁸)
17 bits for destination (values up to ~131,071)
The rest for source

If any field exceeds its allotted bit range, the bits will overflow and collide, causing two distinct packets to produce the same key. This leads to false duplicate detections (addPacket wrongly returns False). For example, if destination can reach 2 × 10⁹, 17 bits is far too few.

Solution: Verify the constraints carefully and size each field accordingly, or sidestep bit-packing entirely by using a tuple as the key:

key = (source, destination, timestamp)   # always unique, no overflow risk
self.packet_set.add(key)

Tuples hash safely regardless of value magnitude, eliminating any overflow concern at the cost of slightly higher memory per key.

Pitfall 3: The timestamp lists grow without bound

Because forwarded packets are never physically removed from self.timestamps[destination] (only the forwarded_index pointer advances), the lists keep growing for the lifetime of the object. Over millions of addPacket calls, this causes unbounded memory growth, even though the router only "holds" memoryLimit packets at a time.

Solution: This is an intentional trade-off—keeping the list append-only preserves sorted order and gives O(1) appends with O(log n) getCount. For very long-running scenarios, periodically compact each list by dropping the already-forwarded prefix and resetting the index:

def _maybe_compact(self, destination):
    k = self.forwarded_index[destination]
    ls = self.timestamps[destination]
    # Compact when more than half the list is stale
    if k > len(ls) // 2:
        self.timestamps[destination] = ls[k:]
        self.forwarded_index[destination] = 0

This bounds memory usage at the expense of an occasional O(n) slice operation, amortized to O(1) per forwarded packet.

Pitfall 4: Forgetting that `forwardPacket` must also update `forwarded_index`

When addPacket internally calls forwardPacket to evict the oldest packet, it relies on forwardPacket correctly incrementing forwarded_index[destination]. If you implement the eviction logic inline in addPacket (e.g., just self.packet_queue.popleft() without bumping the index), then getCount will over-count, because it will still consider the evicted timestamp as "currently stored."

Solution: Always route eviction through the single forwardPacket method (as the correct code does) so the bookkeeping stays consistent in one place, rather than duplicating the pop-and-update logic.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which technique can we use to find the middle of a linked list?

Fast-slow pointers

Two pointers moving in opposite direction

Binary search

Depth first search

I don't know