3508. Implement Router

Problem Statement in English

You’re given a memory limit memoryLimit. Implement a router that processes network packets with the following functionalities:

• Router(int memoryLimit): Initializes the router with the given memory limit.
• boolean addPacket(int source, int destination, int timestamp): Adds a packet with the specified source, destination, and timestamp to the router. Returns true if the packet is added successfully; returns false if a packet with the same source, destination, and timestamp already exists or if adding the packet would exceed the memory limit.
• int[] forwardPacket(): Forwards the oldest packet in the router and removes it from the system. Returns an array containing the source, destination, and timestamp of the forwarded packet. If there are no packets to forward, returns an empty array.
• int getCount(int destination, int startTime, int endTime): Returns the count of packets with the specified destination that have timestamps within the inclusive range [startTime, endTime].

Approach

To implement the router with the specified functionalities, we can use a combination of data structures:

1. Queue: To store the packets in the order they are received.
2. Set: To keep track of the unique packets for quick lookup.
3. Filtered Queue: A mapping from destination to a deque of timestamps, allowing efficient range queries.

The main operations we need to support are adding packets, forwarding packets, and counting packets by destination and time range. The combination of these data structures will allow us to implement these operations efficiently.

Solution in Python

class Router:

    def __init__(self, memoryLimit: int):
        self.lim = memoryLimit
        self.q = deque()
        self.db = set()
        self.filteredq = defaultdict(deque)

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

        if self.lim == len(self.q):
            ps, pd, pt = self.q.popleft()
            self.filteredq[pd].popleft()
            self.db.remove((ps,pd,pt))

        self.q.append(t)
        self.filteredq[destination].append(timestamp)
        self.db.add(t)
        
        return True

    def forwardPacket(self) -> List[int]:
        if not self.q:
            return []

        t = self.q.popleft()
        source, destination, timestamp = t
        self.db.remove(t)
        self.filteredq[destination].popleft()
        return [*t]


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

Complexity

• Time: $O(n)$
  Since each packet is added and removed at most once, the operations are amortized O(1).

• Space: $O(n)$
  The space complexity is O(n) due to the storage of packets in the queue and the filtered queue.

And we are done.