Implement Router

main.md

Question

Approach

I maintain the packets in a FIFO deque to respect insertion/forwarding order, and a set of (source, destination, timestamp) to detect duplicates in O(1). For destination/time range queries, I keep a sorted list of timestamps per destination (dest2times[destination]). On insert, I insort the timestamp to keep the list sorted; on delete (due to eviction or forwarding), I remove a single occurrence using bisect_left. getCount(dest, l, r) is then the count of timestamps in [l, r] via two binary searches (bisect_left/bisect_right). When memory would be exceeded on addPacket, I evict the oldest packet from the deque and update all indices. All operations are efficient: O(log k) for range counts/updates per destination (plus list shift cost on deletion), and O(1) for duplicate checks.

Implementation

class Router:

    def __init__(self, memoryLimit: int):
        self.limit = memoryLimit
        self.q = deque() 
        self.seen = set()
        self.dest2times = defaultdict(list)

    def _insert_dest_time(self, dest: int, ts: int) -> None:
        lst = self.dest2times[dest]
        bisect.insort(lst, ts)

    def _remove_dest_time(self, dest: int, ts: int) -> None:
        lst = self.dest2times[dest]
        i = bisect.bisect_left(lst, ts)
        if i < len(lst) and lst[i] == ts:
            lst.pop(i)
        if not lst:
            del self.dest2times[dest]

    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        pkt = (source, destination, timestamp)
        if pkt in self.seen:
            return False

        self.q.append(pkt)
        self.seen.add(pkt)
        self._insert_dest_time(destination, timestamp)

        if len(self.q) > self.limit:
            os, od, ot = self.q.popleft()
            self.seen.discard((os, od, ot))
            self._remove_dest_time(od, ot)
        return True

    def forwardPacket(self) -> List[int]:
        if not self.q:
            return []
        s, d, t = self.q.popleft()
        self.seen.discard((s, d, t))
        self._remove_dest_time(d, t)
        return [s, d, t]

    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        lst = self.dest2times.get(destination, [])
        left = bisect.bisect_left(lst, startTime)
        right = bisect.bisect_right(lst, endTime)
        return right - left

Complexities

• addPacket:

  • Duplicate check: O(1)
  • Insert timestamp: O(log k) for bsearch + O(k) shift for list insertion (amortized by Python list); k = #packets for that destination currently stored
  • Possible eviction: same costs for removal

• forwardPacket: O(log k) bsearch + O(k) for removal shift (for that destination)
• getCount: O(log k) via two binary searches
• Space: O(N) for stored packets, indices, and sets, where N ≤ memoryLimit.