aboutsummaryrefslogtreecommitdiff
path: root/implement_router.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-09-20 15:15:25 -0600
committerJack Sangdahl <[email protected]>2025-09-20 15:15:25 -0600
commitd5e6bc72a4a72b64bb237fe8a1c22cae73f0dcab (patch)
tree14d73ca07bf3fb68d959aca8e69fdc7a31560954 /implement_router.py
parentc9b062a27109bc79e6dd015644509c745e696808 (diff)
downloadleetcode-d5e6bc72a4a72b64bb237fe8a1c22cae73f0dcab.tar.gz
leetcode-d5e6bc72a4a72b64bb237fe8a1c22cae73f0dcab.zip
3508. implement router
Diffstat (limited to 'implement_router.py')
-rw-r--r--implement_router.py79
1 files changed, 79 insertions, 0 deletions
diff --git a/implement_router.py b/implement_router.py
new file mode 100644
index 0000000..16ca470
--- /dev/null
+++ b/implement_router.py
@@ -0,0 +1,79 @@
+# 3508. Implement Router
+import bisect
+from collections import defaultdict, deque
+
+"""
+design a data structure that can efficiently manage data packets in a network
+router. each data packet consists of the following attributes: 'source',
+'destination', 'timestamp'. note that the queries for 'routerAddPacket' will
+be made in increasing order of timestamp
+"""
+
+
+class Router(object):
+ def __init__(self, memoryLimit):
+ """
+ :type memoryLimit: int
+ """
+ self.size = memoryLimit
+ self.packets = {}
+ self.counts = defaultdict(list)
+ self.queue = deque()
+
+ def addPacket(self, source, destination, timestamp):
+ """
+ :type source: int
+ :type destination: int
+ :type timestamp: int
+ :rtype: bool
+ """
+ key = self._encode(source, destination, timestamp)
+ if key in self.packets:
+ return False
+ if len(self.packets) >= self.size:
+ self.forwardPacket()
+ self.packets[key] = [source, destination, timestamp]
+ self.queue.append(key)
+ self.counts[destination].append(timestamp)
+ return True
+
+ def forwardPacket(self):
+ """
+ :rtype: List[int]
+ """
+ if not self.packets:
+ return []
+ key = self.queue.popleft()
+ packet = self.packets.pop(key)
+ dest = packet[1]
+ self.counts[dest].pop(0)
+ return packet
+
+ def getCount(self, destination, startTime, endTime):
+ """
+ :type destination: int
+ :type startTime: int
+ :type endTime: int
+ :rtype: int
+ """
+ timestamps = self.counts.get(destination, [])
+ if not timestamps:
+ return 0
+ left = bisect.bisect_left(timestamps, startTime)
+ right = bisect.bisect_right(timestamps, endTime)
+ return right - left
+
+ def _encode(self, source, destination, timestamp):
+ return (source << 40) | (destination << 20) | timestamp
+
+
+if __name__ == "__main__":
+ obj = Router(3)
+ print(obj.addPacket(1, 4, 90))
+ print(obj.addPacket(2, 5, 90))
+ print(obj.addPacket(1, 4, 90))
+ print(obj.addPacket(3, 5, 95))
+ print(obj.addPacket(4, 5, 105))
+ print(obj.forwardPacket())
+ print(obj.addPacket(5, 2, 110))
+ print(obj.getCount(5, 100, 110))