Implement Router - Practice Coding Problems

Implement Router - Problem

Array Hash Table Binary Search Design Queue Ordered Set Medium

Design a data structure that can efficiently manage data packets in a network router. Each data packet consists of the following attributes:

source: A unique identifier for the machine that generated the packet
destination: A unique identifier for the target machine
timestamp: The time at which the packet arrived at the router

Implement the Router class:

Router(int memoryLimit): Initializes the Router object with a fixed memory limit. memoryLimit is the maximum number of packets the router can store at any given time. If adding a new packet would exceed this limit, the oldest packet must be removed to free up space.
bool addPacket(int source, int destination, int timestamp): Adds a packet with the given attributes to the router. A packet is considered a duplicate if another packet with the same source, destination, and timestamp already exists in the router. Return true if the packet is successfully added (i.e., it is not a duplicate); otherwise return false.
int[] forwardPacket(): Forwards the next packet in FIFO (First In First Out) order. Remove the packet from storage. Return the packet as an array [source, destination, timestamp]. If there are no packets to forward, return an empty array.
int getCount(int destination, int startTime, int endTime): Returns the number of packets currently stored in the router (i.e., not yet forwarded) that have the specified destination and have timestamps in the inclusive range [startTime, endTime].

Note that queries for addPacket will be made in non-decreasing order of timestamp.

Input & Output

Example 1 — Basic Router Operations

$ Input: operations = [["Router", 3], ["addPacket", 1, 2, 100], ["addPacket", 3, 4, 200], ["addPacket", 1, 2, 100], ["forwardPacket"], ["getCount", 2, 50, 150]]

› Output: [null, true, true, false, [1, 2, 100], 1]

💡 Note: Initialize router with capacity 3. Add packet (1,2,100) - success. Add packet (3,4,200) - success. Try to add duplicate (1,2,100) - fails. Forward first packet [1,2,100]. Count packets to destination 2 in time range [50,150] - returns 1 (no packets match).

Example 2 — Memory Limit Enforcement

$ Input: operations = [["Router", 2], ["addPacket", 1, 2, 100], ["addPacket", 3, 4, 200], ["addPacket", 5, 6, 300], ["forwardPacket"]]

› Output: [null, true, true, true, [3, 4, 200]]

💡 Note: Initialize router with capacity 2. Add two packets fills capacity. Adding third packet removes oldest (1,2,100). Forward returns (3,4,200) which was the oldest remaining.

Example 3 — Count Range Query

$ Input: operations = [["Router", 5], ["addPacket", 1, 10, 100], ["addPacket", 2, 10, 150], ["addPacket", 3, 20, 200], ["getCount", 10, 90, 160]]

› Output: [null, true, true, true, 2]

💡 Note: Add three packets. Count packets to destination 10 in time range [90,160]. Two packets match: (1,10,100) and (2,10,150).

Constraints

1 ≤ memoryLimit ≤ 1000
-10⁶ ≤ source, destination ≤ 10⁶
1 ≤ timestamp ≤ 10⁶
At most 1000 calls will be made to addPacket, forwardPacket, and getCount
Queries for addPacket will be made in non-decreasing order of timestamp

Visualization

Tap to expand

Understanding the Visualization

Input Operations

Sequence of router operations including add, forward, and count

Router Processing

Handle packets with memory limit, detect duplicates, maintain FIFO order

Output Results

Return operation results: boolean for add, array for forward, count for queries

Key Takeaway

🎯 Key Insight: Router combines queue for FIFO ordering with hash set for constant-time duplicate detection

Asked in

a Amazon 15 m Microsoft 12 G Google 8 f Meta 6

The key insight is to combine a queue for FIFO ordering with a hash set for O(1) duplicate detection. The optimal approach uses a queue to maintain packet order and a hash set to check duplicates efficiently. Time: O(1) for add/forward, O(n) for count. Space: O(n) for storing packets and hash set.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Linear Search	O(n)	O(n)	Store packets in list, check duplicates by scanning all packets
Optimized - Hash Set + Queue	O(1)	O(n)	Use queue for FIFO ordering and hash set for O(1) duplicate detection

Brute Force - Linear Search — Algorithm Steps

Store packets in a simple list
For duplicates, scan entire list linearly
For counting, iterate through all packets checking conditions

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Packets

Add packets to simple list, scan all for duplicates

Forward FIFO

Remove first packet from list

Count Query

Scan all packets to count matches

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int source, destination, timestamp;
} Packet;

typedef struct {
    int memoryLimit;
    Packet* packets;
    int count;
} Router;

Router* createRouter(int memoryLimit) {
    Router* router = (Router*)malloc(sizeof(Router));
    router->memoryLimit = memoryLimit;
    router->packets = (Packet*)malloc(memoryLimit * sizeof(Packet));
    router->count = 0;
    return router;
}

bool addPacket(Router* router, int source, int destination, int timestamp) {
    // Check for duplicates
    for (int i = 0; i < router->count; i++) {
        if (router->packets[i].source == source && 
            router->packets[i].destination == destination && 
            router->packets[i].timestamp == timestamp) {
            return false;
        }
    }
    
    // Remove oldest if at capacity
    if (router->count >= router->memoryLimit) {
        for (int i = 1; i < router->count; i++) {
            router->packets[i-1] = router->packets[i];
        }
        router->count--;
    }
    
    router->packets[router->count].source = source;
    router->packets[router->count].destination = destination;
    router->packets[router->count].timestamp = timestamp;
    router->count++;
    return true;
}

int* forwardPacket(Router* router, int* returnSize) {
    if (router->count == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    int* result = (int*)malloc(3 * sizeof(int));
    result[0] = router->packets[0].source;
    result[1] = router->packets[0].destination;
    result[2] = router->packets[0].timestamp;
    
    for (int i = 1; i < router->count; i++) {
        router->packets[i-1] = router->packets[i];
    }
    router->count--;
    
    *returnSize = 3;
    return result;
}

int getCount(Router* router, int destination, int startTime, int endTime) {
    int count = 0;
    for (int i = 0; i < router->count; i++) {
        if (router->packets[i].destination == destination && 
            startTime <= router->packets[i].timestamp && 
            router->packets[i].timestamp <= endTime) {
            count++;
        }
    }
    return count;
}

int main() {
    printf("[null,true,true,false,[1,2,100],1]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each addPacket and getCount operation scans all stored packets linearly

✓ Linear Growth

Space Complexity

O(n)

Store up to memoryLimit packets in a list

⚡ Linearithmic Space

12.4K Views

Medium Frequency

~35 min Avg. Time

256 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler