Implement Router

medium queue design binary search

Problem

Design a Router with a fixed memoryLimit on stored packets. addPacket(source, destination, timestamp) rejects a packet that exactly duplicates one already stored (return false); otherwise it stores it, evicting the oldest packet first if the router is full, and returns true. forwardPacket() removes and returns the oldest packet [source, destination, timestamp] in FIFO order, or [] if empty. getCount(destination, startTime, endTime) counts stored packets with that destination whose timestamp lies in [startTime, endTime]. Packets arrive in non-decreasing timestamp order.

Input

memoryLimit = 3; add(1,4,90); add(2,5,90); add(1,4,90); add(3,5,95); add(4,5,105); forward(); add(5,2,110); getCount(5,100,110)

Output[true, true, false, true, true, [2,5,90], true, 1]

The third add is a duplicate of [1,4,90] → false. The fifth add overflows the limit, so the oldest packet [1,4,90] is evicted. getCount finds only [4,5,105] with destination 5 in [100,110] → 1.

memoryLimit

operations (one per line: add s d t, forward, count d start end)

from collections import deque
from bisect import bisect_left, bisect_right

class Router:
    def __init__(self, memoryLimit):
        self.limit = memoryLimit
        self.q = deque()                 # FIFO of (src, dst, ts)
        self.seen = set()                # dedup set of (src, dst, ts)
        self.dest = {}                   # dst -> sorted timestamps
        self.head = {}                   # dst -> index of first live ts

    def addPacket(self, source, destination, timestamp):
        key = (source, destination, timestamp)
        if key in self.seen:             # duplicate -> reject
            return False
        if len(self.q) == self.limit:    # full -> evict oldest
            self._evict()
        self.q.append(key)
        self.seen.add(key)
        self.dest.setdefault(destination, [])
        self.head.setdefault(destination, 0)
        self.dest[destination].append(timestamp)
        return True

    def _evict(self):
        s, d, t = self.q.popleft()
        self.seen.discard((s, d, t))
        self.head[d] += 1                # advance past evicted ts

    def forwardPacket(self):
        if not self.q:
            return []
        s, d, t = self.q.popleft()
        self.seen.discard((s, d, t))
        self.head[d] += 1
        return [s, d, t]

    def getCount(self, destination, startTime, endTime):
        if destination not in self.dest:
            return 0
        arr, lo = self.dest[destination], self.head[destination]
        left = bisect_left(arr, startTime, lo)
        right = bisect_right(arr, endTime, lo)
        return right - left

class Router {
  constructor(memoryLimit) {
    this.limit = memoryLimit;
    this.q = [];                 // FIFO; head pointer avoids O(n) shift
    this.qh = 0;
    this.seen = new Set();       // dedup keys "s,d,t"
    this.dest = new Map();       // dst -> sorted timestamps
    this.head = new Map();       // dst -> index of first live ts
  }
  addPacket(source, destination, timestamp) {
    const key = source + "," + destination + "," + timestamp;
    if (this.seen.has(key)) return false;          // duplicate
    if (this.q.length - this.qh === this.limit) this._evict();
    this.q.push([source, destination, timestamp]);
    this.seen.add(key);
    if (!this.dest.has(destination)) { this.dest.set(destination, []); this.head.set(destination, 0); }
    this.dest.get(destination).push(timestamp);
    return true;
  }
  _evict() {
    const [s, d, t] = this.q[this.qh++];
    this.seen.delete(s + "," + d + "," + t);
    this.head.set(d, this.head.get(d) + 1);
  }
  forwardPacket() {
    if (this.q.length - this.qh === 0) return [];
    const [s, d, t] = this.q[this.qh++];
    this.seen.delete(s + "," + d + "," + t);
    this.head.set(d, this.head.get(d) + 1);
    return [s, d, t];
  }
  getCount(destination, startTime, endTime) {
    if (!this.dest.has(destination)) return 0;
    const arr = this.dest.get(destination), lo = this.head.get(destination);
    const left = lowerBound(arr, startTime, lo);
    const right = upperBound(arr, endTime, lo);
    return right - left;
  }
}
function lowerBound(a, x, lo) { let hi = a.length; while (lo < hi) { const m = (lo + hi) >> 1; if (a[m] < x) lo = m + 1; else hi = m; } return lo; }
function upperBound(a, x, lo) { let hi = a.length; while (lo < hi) { const m = (lo + hi) >> 1; if (a[m] <= x) lo = m + 1; else hi = m; } return lo; }

class Router {
    int limit;
    Deque<int[]> q = new ArrayDeque<>();            // FIFO of {src, dst, ts}
    Set<String> seen = new HashSet<>();            // dedup keys "s,d,t"
    Map<Integer, List<Integer>> dest = new HashMap<>();
    Map<Integer, Integer> head = new HashMap<>();  // dst -> first live index

    public Router(int memoryLimit) { limit = memoryLimit; }

    private String key(int s, int d, int t) { return s + "," + d + "," + t; }

    public boolean addPacket(int source, int destination, int timestamp) {
        String k = key(source, destination, timestamp);
        if (seen.contains(k)) return false;        // duplicate
        if (q.size() == limit) evict();            // full -> drop oldest
        q.addLast(new int[]{source, destination, timestamp});
        seen.add(k);
        dest.computeIfAbsent(destination, z -> new ArrayList<>()).add(timestamp);
        head.putIfAbsent(destination, 0);
        return true;
    }
    private void evict() {
        int[] p = q.pollFirst();
        seen.remove(key(p[0], p[1], p[2]));
        head.merge(p[1], 1, Integer::sum);
    }
    public int[] forwardPacket() {
        if (q.isEmpty()) return new int[0];
        int[] p = q.pollFirst();
        seen.remove(key(p[0], p[1], p[2]));
        head.merge(p[1], 1, Integer::sum);
        return p;
    }
    public int getCount(int destination, int startTime, int endTime) {
        List<Integer> arr = dest.get(destination);
        if (arr == null) return 0;
        int lo = head.get(destination);
        int left = lowerBound(arr, startTime, lo);
        int right = lowerBound(arr, endTime + 1, lo);
        return right - left;
    }
    private int lowerBound(List<Integer> a, int x, int lo) {
        int hi = a.size();
        while (lo < hi) { int m = (lo + hi) >>> 1; if (a.get(m) < x) lo = m + 1; else hi = m; }
        return lo;
    }
}

class Router {
    int limit;
    deque<array<int,3>> q;                       // FIFO of {src, dst, ts}
    set<array<int,3>> seen;                      // dedup set
    unordered_map<int, vector<int>> dest;        // dst -> sorted timestamps
    unordered_map<int, int> head;               // dst -> first live index
public:
    Router(int memoryLimit) : limit(memoryLimit) {}

    bool addPacket(int source, int destination, int timestamp) {
        array<int,3> key = {source, destination, timestamp};
        if (seen.count(key)) return false;          // duplicate
        if ((int) q.size() == limit) evict();       // full -> drop oldest
        q.push_back(key);
        seen.insert(key);
        dest[destination].push_back(timestamp);
        head.try_emplace(destination, 0);
        return true;
    }
    void evict() {
        auto p = q.front(); q.pop_front();
        seen.erase(p);
        head[p[1]]++;
    }
    vector<int> forwardPacket() {
        if (q.empty()) return {};
        auto p = q.front(); q.pop_front();
        seen.erase(p);
        head[p[1]]++;
        return {p[0], p[1], p[2]};
    }
    int getCount(int destination, int startTime, int endTime) {
        auto it = dest.find(destination);
        if (it == dest.end()) return 0;
        auto& arr = it->second;
        int lo = head[destination];
        auto left = lower_bound(arr.begin() + lo, arr.end(), startTime);
        auto right = upper_bound(arr.begin() + lo, arr.end(), endTime);
        return (int)(right - left);
    }
};

Explanation

The router is a fixed-capacity FIFO queue with two extra indexes layered on top so that duplicate detection and range counting stay fast.

The queue. A deque holds packets in arrival order. forwardPacket pops from the front (oldest), and when addPacket would overflow memoryLimit we evict the front first. That single deque gives us O(1) add, forward, and eviction.

Duplicate detection. A hash set mirrors the queue's contents keyed by (source, destination, timestamp). addPacket checks this set in O(1); every eviction or forward removes the same key so the set always matches what is currently stored.

Range counting. For each destination we keep a list of the timestamps of its stored packets. Because packets arrive in non-decreasing timestamp order, each list is already sorted, so we never sort. We also keep a head pointer per destination marking how many of its packets have been removed from the front — those leading entries are stale. getCount then binary-searches the live suffix [head, end) for the first timestamp ≥ startTime (lower bound) and the first > endTime (upper bound); the gap between them is the answer.

Eviction and forwarding always remove the globally oldest packet, which for its destination is its earliest stored timestamp — exactly the entry the head pointer skips next, so the per-destination lists stay consistent with the queue without ever deleting from the middle of an array.

In Example 1, after the fifth add overflows the limit, [1,4,90] is evicted (queue and dedup set drop it, and destination 4's head advances). getCount(5, 100, 110) binary-searches destination 5's live timestamps and finds only 105 in range, so it returns 1.

Time: add / forward O(1), getCount O(log n) Space: O(n)