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 | |
parent | c9b062a27109bc79e6dd015644509c745e696808 (diff) | |
download | leetcode-d5e6bc72a4a72b64bb237fe8a1c22cae73f0dcab.tar.gz leetcode-d5e6bc72a4a72b64bb237fe8a1c22cae73f0dcab.zip |
3508. implement router
-rw-r--r-- | implement_router.c | 280 | ||||
-rw-r--r-- | implement_router.py | 79 |
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)) |