2025-09-20

Problem

Qn - Implement Router

Approach

We create a set with the (source,destination,timestamp) as the key for duplicate detection

We create a queue for the FIFO behaviour

We create a hashtable to map destination to an array, where the first element is an index, and the second is an array. [x, [...]], where the index points to the location in the array to start searching from. Why do we need this pointer? This is to prevent removals from being O(n) in time, as we remove the first element. We also can’t make it a queue as we need random access to binary search into that array

The only interesting implementation is at the getCount function, where we binary search to get the starting and ending indexes.

Complexity

• Time:
  • addPacket: $O(1)$
  • forwardPacket: $O(1)$
  • getCount: $O(2logn)$
• Space: $O(numberofcalls)$

Code

class Router:
 
    def __init__(self, memoryLimit: int):
        self.queue = deque()
        self.limit = memoryLimit
        self.packets = 0
        self.set = set()
        self.map = dict()
 
    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        # if duplicate, return false
        key = (source,destination,timestamp)
        if key in self.set: return False
        
        # if exceed limit, evict the oldest packet
        if self.packets == self.limit: self.forwardPacket()
 
        # else add to the queue
        self.set.add(key)
        self.queue.append(key)
        self.packets += 1
        if destination in self.map: self.map[destination][1].append(key)
        else: self.map[destination] = [0, [key]]
        return True
 
    def forwardPacket(self) -> List[int]:
        if not self.queue: return []
        data = self.queue.popleft()
        self.set.remove(data)
        self.packets -= 1
        self.map[data[1]][0] += 1
        return list(data)
 
    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        if destination not in self.map: return 0
        start_search_ind, arr = self.map[destination]
        start_ind = bisect_left(arr,startTime,start_search_ind,key=lambda x: x[2])
        end_ind = bisect_right(arr,endTime,start_search_ind,key=lambda x: x[2])
        return end_ind-start_ind
 
 
# Your Router object will be instantiated and called as such:
# obj = Router(memoryLimit)
# param_1 = obj.addPacket(source,destination,timestamp)
# param_2 = obj.forwardPacket()
# param_3 = obj.getCount(destination,startTime,endTime)