diff options
author | Jack Sangdahl <[email protected]> | 2025-09-20 15:15:25 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-20 15:15:25 -0600 |
commit | d5e6bc72a4a72b64bb237fe8a1c22cae73f0dcab (patch) | |
tree | 14d73ca07bf3fb68d959aca8e69fdc7a31560954 /implement_router.py | |
parent | c9b062a27109bc79e6dd015644509c745e696808 (diff) | |
download | leetcode-d5e6bc72a4a72b64bb237fe8a1c22cae73f0dcab.tar.gz leetcode-d5e6bc72a4a72b64bb237fe8a1c22cae73f0dcab.zip |
3508. implement router
Diffstat (limited to 'implement_router.py')
-rw-r--r-- | implement_router.py | 79 |
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)) |