aboutsummaryrefslogtreecommitdiff
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
parentc9b062a27109bc79e6dd015644509c745e696808 (diff)
downloadleetcode-d5e6bc72a4a72b64bb237fe8a1c22cae73f0dcab.tar.gz
leetcode-d5e6bc72a4a72b64bb237fe8a1c22cae73f0dcab.zip
3508. implement router
-rw-r--r--implement_router.c280
-rw-r--r--implement_router.py79
2 files changed, 359 insertions, 0 deletions
diff --git a/implement_router.c b/implement_router.c
new file mode 100644
index 0000000..ef73d98
--- /dev/null
+++ b/implement_router.c
@@ -0,0 +1,280 @@
+// 3508. Implement Router
+#include "leetcode.h"
+
+/*
+ * 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
+ */
+
+#define HASH_SIZE 200925
+
+struct packet {
+ int source;
+ int destination;
+ int timestamp;
+ struct packet *next;
+};
+
+struct key_node {
+ char *key;
+ struct key_node *next;
+};
+
+struct destination_info {
+ int *timestamps;
+ int size;
+ int capacity;
+};
+
+typedef struct {
+ int memoryLimit;
+ int size;
+ struct packet *head;
+ struct packet *tail;
+ struct key_node *packet_set[HASH_SIZE];
+ struct destination_info *dest_map[HASH_SIZE];
+} Router;
+
+unsigned int hash_str(const char *s) {
+ unsigned int res = 0;
+ while (*s)
+ res = res * 31 + (unsigned char)(*s++);
+ return res % HASH_SIZE;
+}
+
+unsigned int hash_int(int x) { return ((unsigned int)x) % HASH_SIZE; }
+
+char *make_key(int src, int dst, int ts) {
+ char *res = (char *)malloc(32 * sizeof(char));
+ sprintf(res, "%d-%d-%d", src, dst, ts);
+ return res;
+}
+
+bool key_exists(Router *obj, const char *key) {
+ unsigned int hash = hash_str(key);
+ struct key_node *curr = obj->packet_set[hash];
+ while (curr) {
+ if (!strcmp(curr->key, key))
+ return true;
+ curr = curr->next;
+ }
+ return false;
+}
+
+void key_insert(Router *obj, char *key) {
+ unsigned int hash = hash_str(key);
+ struct key_node *node = (struct key_node *)malloc(sizeof(struct key_node));
+ node->key = key;
+ node->next = obj->packet_set[hash];
+ obj->packet_set[hash] = node;
+}
+
+void key_remove(Router *obj, const char *key) {
+ unsigned int hash = hash_str(key);
+ struct key_node *curr = obj->packet_set[hash], *prev = NULL;
+ while (curr) {
+ if (!strcmp(curr->key, key)) {
+ if (prev)
+ prev->next = curr->next;
+ else
+ obj->packet_set[hash] = curr->next;
+ free(curr->key);
+ free(curr);
+ return;
+ }
+ prev = curr;
+ curr = curr->next;
+ }
+}
+
+struct destination_info *get_dest(Router *obj, int dst) {
+ unsigned int hash = hash_int(dst);
+ return obj->dest_map[hash];
+}
+
+struct destination_info *create_dest(void) {
+ struct destination_info *obj =
+ (struct destination_info *)malloc(sizeof(struct destination_info));
+ obj->timestamps = (int *)malloc(8 * sizeof(int));
+ obj->size = 0;
+ obj->capacity = 0;
+ return obj;
+}
+
+void add_dest_timestamp(Router *obj, int dst, int ts) {
+ unsigned int hash = hash_int(dst);
+ struct destination_info *d = obj->dest_map[hash];
+ if (!d) {
+ d = create_dest();
+ obj->dest_map[hash] = d;
+ }
+ if (d->size == d->capacity) {
+ d->capacity *= 2;
+ d->timestamps = (int *)realloc(d->timestamps, d->capacity * sizeof(int));
+ }
+ d->timestamps[d->size++] = ts;
+}
+
+void remove_dest_timestamp(Router *obj, int dst, int ts) {
+ unsigned int hash = hash_int(dst);
+ struct destination_info *d = obj->dest_map[hash];
+ if (!d)
+ return;
+ int i;
+ for (int i = 0; i < d->size; i++)
+ if (d->timestamps[i] == ts)
+ break;
+ if (i == d->size)
+ return;
+ for (int j = i; j < d->size; j++)
+ d->timestamps[j] = d->timestamps[j + 1];
+ d->size--;
+ if (!d->size) {
+ free(d->timestamps);
+ free(d);
+ obj->dest_map[hash] = NULL;
+ }
+}
+
+int lower_bound(int *arr, int n, int target) {
+ int l = 0, r = n;
+ while (l < r) {
+ int m = l + (r - l) / 2;
+ if (arr[m] < target)
+ l = m + 1;
+ else
+ r = m;
+ }
+ return l;
+}
+
+int upper_bound(int *arr, int n, int target) {
+ int l = 0, r = n;
+ while (l < r) {
+ int m = l + (r - l) / 2;
+ if (arr[m] <= target)
+ l = m + 1;
+ else
+ r = m;
+ }
+ return l;
+}
+
+Router *routerCreate(int memoryLimit) {
+ Router *obj = (Router *)malloc(sizeof(Router));
+ obj->memoryLimit = memoryLimit;
+ obj->size = 0;
+ obj->head = obj->tail = NULL;
+ memset(obj->packet_set, 0, sizeof(obj->packet_set));
+ memset(obj->dest_map, 0, sizeof(obj->dest_map));
+ return obj;
+}
+
+bool routerAddPacket(Router *obj, int source, int destination, int timestamp) {
+ char *key = make_key(source, destination, timestamp);
+ if (key_exists(obj, key)) {
+ free(key);
+ return false;
+ }
+ if (obj->size == obj->memoryLimit) {
+ struct packet *old = obj->head;
+ obj->head = old->next;
+ if (!obj->head)
+ obj->tail = NULL;
+ obj->size--;
+ char *prev_key = make_key(old->source, old->destination, old->timestamp);
+ key_remove(obj, prev_key);
+ free(prev_key);
+ remove_dest_timestamp(obj, old->destination, old->timestamp);
+ free(old);
+ }
+ struct packet *p = (struct packet *)malloc(sizeof(struct packet));
+ p->source = source;
+ p->destination = destination;
+ p->timestamp = timestamp;
+ p->next = NULL;
+ if (!obj->tail)
+ obj->head = obj->tail = p;
+ else {
+ obj->tail->next = p;
+ obj->tail = p;
+ }
+ obj->size++;
+ key_insert(obj, key);
+ add_dest_timestamp(obj, destination, timestamp);
+ return true;
+}
+
+int *routerForwardPacket(Router *obj, int *retSize) {
+ if (!obj->head) {
+ *retSize = 0;
+ return NULL;
+ }
+ struct packet *p = obj->head;
+ obj->head = p->next;
+ if (!obj->head)
+ obj->tail = NULL;
+ obj->size--;
+ char *key = make_key(p->source, p->destination, p->timestamp);
+ key_remove(obj, key);
+ free(key);
+ remove_dest_timestamp(obj, p->destination, p->timestamp);
+ int *res = (int *)malloc(3 * sizeof(int));
+ res[0] = p->source;
+ res[1] = p->destination;
+ res[2] = p->timestamp;
+ *retSize = 3;
+ free(p);
+ return res;
+}
+
+int routerGetCount(Router *obj, int destination, int startTime, int endTime) {
+ unsigned int hash = hash_int(destination);
+ struct destination_info *d = obj->dest_map[hash];
+ if (!d)
+ return 0;
+ int l = lower_bound(d->timestamps, d->size, startTime);
+ int r = upper_bound(d->timestamps, d->size, endTime);
+ return r - l;
+}
+
+void routerFree(Router *obj) {
+ while (obj->head) {
+ struct packet *tmp = obj->head;
+ obj->head = obj->head->next;
+ free(tmp);
+ for (int i = 0; i < HASH_SIZE; i++) {
+ struct key_node *key = obj->packet_set[i];
+ while (key) {
+ struct key_node *t = key;
+ key = key->next;
+ free(t->key);
+ free(t);
+ }
+ struct destination_info *d = obj->dest_map[i];
+ if (d) {
+ free(d->timestamps);
+ free(d);
+ }
+ }
+ }
+ free(obj);
+}
+
+int main() {
+ Router *obj = routerCreate(3);
+ printf("%d\n", routerAddPacket(obj, 1, 4, 90)); // expect: 1
+ printf("%d\n", routerAddPacket(obj, 2, 5, 90)); // expect: 1
+ printf("%d\n", routerAddPacket(obj, 1, 4, 90)); // expect: 0
+ printf("%d\n", routerAddPacket(obj, 3, 5, 95)); // expect: 1
+ printf("%d\n", routerAddPacket(obj, 4, 5, 105)); // expect: 1
+ int rs, *rfp = routerForwardPacket(obj, &rs);
+ for (int i = 0; i < rs; i++)
+ printf("%d ", rfp[i]); // expect: 2 5 90
+ free(rfp);
+ printf("%d\n", routerAddPacket(obj, 5, 2, 110)); // expect: 1
+ printf("%d\n", routerGetCount(obj, 5, 100, 110)); // expect:
+ routerFree(obj);
+}
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))