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, and timestamp already exists in the router.
  • Return 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.

  • 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.

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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.  
router.addPacket(1, 4, 90); // Packet is added. Return True.  
router.addPacket(2, 5, 90); // Packet is added. Return True.  
router.addPacket(1, 4, 90); // This is a duplicate packet. Return False.  
router.addPacket(3, 5, 95); // Packet is added. Return True  
router.addPacket(4, 5, 105); // Packet is added, `[1, 4, 90]` is removed as
number of packets exceeds memoryLimit. Return True.  
router.forwardPacket(); // Return `[2, 5, 90]` and remove it from router.  
router.addPacket(5, 2, 110); // Packet is added. Return True.  
router.getCount(5, 100, 110); // The only packet with destination 5 and
timestamp in the inclusive range `[100, 110]` is `[4, 5, 105]`. Return 1.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input:  
["Router", "addPacket", "forwardPacket", "forwardPacket"]  
[[2], [7, 4, 90], [], []]
Output:  
[null, true, [7, 4, 90], []]
**Explanation**
Router router = new Router(2); // Initialize `Router` with `memoryLimit` of 2.  
router.addPacket(7, 4, 90); // Return True.  
router.forwardPacket(); // Return `[7, 4, 90]`.  
router.forwardPacket(); // There are no packets left, return `[]`.

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 to addPacket, forwardPacket, and getCount methods altogether.
  • queries for addPacket will be made in increasing order of timestamp.

Examples

Solution

Method 1 – HashSet with Queue (Sliding Window)

Intuition

We need to efficiently check for duplicates and maintain insertion order to evict the oldest packet when the memory limit is reached. A combination of a queue (for order) and a set (for fast lookup) is ideal.

Approach

  1. Use a queue to store packets in the order they arrive.
  2. Use a set to quickly check for duplicates. Store each packet as a tuple (source, destination, timestamp).
  3. When adding a packet:
    • If the packet is a duplicate (already in the set), return false.
    • If the memory limit is reached, remove the oldest packet from both the queue and the set.
    • Add the new packet to both the queue and the set, then return true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Router {
    int mem;
    queue<tuple<int,int,int>> q;
    unordered_set<string> s;
    string key(int a, int b, int c) { return to_string(a)+"#"+to_string(b)+"#"+to_string(c); }
public:
    Router(int memoryLimit) : mem(memoryLimit) {}
    bool addPacket(int src, int dst, int t) {
        string k = key(src, dst, t);
        if (s.count(k)) return false;
        if (q.size() == mem) {
            auto [a, b, c] = q.front(); q.pop();
            s.erase(key(a, b, c));
        }
        q.emplace(src, dst, t);
        s.insert(k);
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

type packet struct{a, b, c int}

type Router struct {
    mem int
    q   []packet
    s   map[[3]int]struct{}
}

func Constructor(memoryLimit int) Router {
    return Router{mem: memoryLimit, s: map[[3]int]struct{}{}}
}

func (r *Router) AddPacket(a, b, c int) bool {
    k := [3]int{a, b, c}
    if _, ok := r.s[k]; ok {
        return false
    }
    if len(r.q) == r.mem {
        old := r.q[0]
        r.q = r.q[1:]
        delete(r.s, [3]int{old.a, old.b, old.c})
    }
    r.q = append(r.q, packet{a, b, c})
    r.s[k] = struct{}{}
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Router {
    int mem;
    Queue<int[]> q = new LinkedList<>();
    Set<String> s = new HashSet<>();
    String key(int a, int b, int c) { return a+"#"+b+"#"+c; }
    public Router(int memoryLimit) { mem = memoryLimit; }
    public boolean addPacket(int a, int b, int c) {
        String k = key(a, b, c);
        if (s.contains(k)) return false;
        if (q.size() == mem) {
            int[] old = q.poll();
            s.remove(key(old[0], old[1], old[2]));
        }
        q.offer(new int[]{a, b, c});
        s.add(k);
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Router(private val mem: Int) {
    private val q = ArrayDeque<Triple<Int, Int, Int>>()
    private val s = mutableSetOf<Triple<Int, Int, Int>>()
    fun addPacket(a: Int, b: Int, c: Int): Boolean {
        val k = Triple(a, b, c)
        if (k in s) return false
        if (q.size == mem) {
            val old = q.removeFirst()
            s.remove(old)
        }
        q.addLast(k)
        s.add(k)
        return true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from collections import deque
class Solution:
    def __init__(self, memoryLimit: int):
        self.mem = memoryLimit
        self.q = deque()
        self.s = set()
    def addPacket(self, src: int, dst: int, t: int) -> bool:
        k = (src, dst, t)
        if k in self.s:
            return False
        if len(self.q) == self.mem:
            old = self.q.popleft()
            self.s.remove(old)
        self.q.append(k)
        self.s.add(k)
        return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

use std::collections::{VecDeque, HashSet};
struct Router {
    mem: usize,
    q: VecDeque<(i32, i32, i32)>,
    s: HashSet<(i32, i32, i32)>,
}
impl Router {
    fn new(memory_limit: usize) -> Self {
        Self { mem: memory_limit, q: VecDeque::new(), s: HashSet::new() }
    }
    fn add_packet(&mut self, a: i32, b: i32, c: i32) -> bool {
        let k = (a, b, c);
        if self.s.contains(&k) { return false; }
        if self.q.len() == self.mem {
            if let Some(old) = self.q.pop_front() {
                self.s.remove(&old);
            }
        }
        self.q.push_back(k);
        self.s.insert(k);
        true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Router {
  private mem: number;
  private q: [number, number, number][] = [];
  private s = new Set<string>();
  private key(a: number, b: number, c: number) { return `${a}#${b}#${c}`; }
  constructor(memoryLimit: number) { this.mem = memoryLimit; }
  addPacket(a: number, b: number, c: number): boolean {
    const k = this.key(a, b, c);
    if (this.s.has(k)) return false;
    if (this.q.length === this.mem) {
      const [oa, ob, oc] = this.q.shift()!;
      this.s.delete(this.key(oa, ob, oc));
    }
    this.q.push([a, b, c]);
    this.s.add(k);
    return true;
  }
}

Complexity

  • ⏰ Time complexity: O(1) — All operations (add, remove, check) are constant time due to set and queue.
  • 🧺 Space complexity: O(m) — Where m is the memory limit (number of packets stored).