3827. Implement Router¶

Difficulty: Medium

3827. Implement Router

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 increasing order of timestamp.

Example 1:

Input:
["Router", "addPacket", "addPacket", "addPacket", "addPacket", "addPacket", "forwardPacket", "addPacket", "getCount"]
[[3], [1, 4, 90], [2, 5, 90], [1, 4, 90], [3, 5, 95], [4, 5, 105], [], [5, 2, 110], [5, 100, 110]]

Output:
[null, true, true, false, true, true, [2, 5, 90], true, 1]

Explanation

Router router = new Router(3); // Initialize Router with memoryLimit of 3.
router.addPacket(1, 4, 90); // Packet is added. Return True.
router.addPacket(2, 5, 90); // Packet is added. Return True.
router.addPacket(1, 4, 90); // This is a duplicate packet. Return False.
router.addPacket(3, 5, 95); // Packet is added. Return True
router.addPacket(4, 5, 105); // Packet is added, [1, 4, 90] is removed as number of packets exceeds memoryLimit. Return True.
router.forwardPacket(); // Return [2, 5, 90] and remove it from router.
router.addPacket(5, 2, 110); // Packet is added. Return True.
router.getCount(5, 100, 110); // The only packet with destination 5 and timestamp in the inclusive range [100, 110] is [4, 5, 105]. Return 1.

Example 2:

Input:
["Router", "addPacket", "forwardPacket", "forwardPacket"]
[[2], [7, 4, 90], [], []]

Output:
[null, true, [7, 4, 90], []]

Explanation

Router router = new Router(2); // Initialize Router with memoryLimit of 2.
router.addPacket(7, 4, 90); // Return True.
router.forwardPacket(); // Return [7, 4, 90].
router.forwardPacket(); // There are no packets left, return [].

Constraints:

2 <= memoryLimit <= 10⁵
1 <= source, destination <= 2 * 10⁵
1 <= timestamp <= 10⁹
1 <= startTime <= endTime <= 10⁹
At most 10⁵ calls will be made to addPacket, forwardPacket, and getCount methods altogether.
queries for addPacket will be made in increasing order of timestamp.

Solution¶

class Router {
    private HashSet<Tuple> packets;
    private ArrayList<Tuple> arr;
    private Deque<Tuple> dq;
    private HashMap<Integer, ArrayList<Tuple >> map;
    private int limit;

    static class Tuple {
        int src, dest, time;
        public Tuple(int src, int dest, int time) {
            this.src = src;
            this.dest = dest;
            this.time = time;
        }
        @Override
        public String toString() {
            return "(" + src + " " + dest + " " + time + ")";
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null || getClass() != obj.getClass())
                return false;
            Tuple current = (Tuple)(obj);
            return current.src == src && current.dest == dest && current.time == time;
        }
        @Override
        public int hashCode() {
            return Objects.hash(src, dest, time);
        }
    }

    public Router(int memoryLimit) {
        packets = new HashSet<>();
        dq = new ArrayDeque<>();
        arr = new ArrayList<>();
        map = new HashMap<>();
        limit = memoryLimit;
    }

    public boolean addPacket(int source, int destination, int timestamp) {
        if (packets.contains(new Tuple(source, destination, timestamp)))
            return false;
        if (dq.size() == limit) {
            Tuple oldest = dq.pollFirst();
            if (map.containsKey(oldest.dest)) {
                ArrayList<Tuple> current = map.get(oldest.dest);
                current.remove(oldest);
                map.put(oldest.dest, current);
            }
            packets.remove(oldest);
            arr.remove(0);
        }
        Tuple current = new Tuple(source, destination, timestamp);
        if (packets.contains(current))
            return false;

        packets.add(current);
        dq.addLast(current);
        arr.add(current);
        if (!map.containsKey(current.dest))
            map.put(current.dest, new ArrayList<>());
        map.get(current.dest).add(current);
        return true;
    }

    public int[] forwardPacket() {
        if (dq.size() == 0)
            return new int[] {};
        Tuple toForward = dq.pollFirst();
        packets.remove(toForward);
        if (map.containsKey(toForward.dest)) {
            ArrayList<Tuple> current = map.get(toForward.dest);
            current.remove(toForward);
            map.put(toForward.dest, current);
        }
        int res[] = new int[3];
        res[0] = toForward.src;
        res[1] = toForward.dest;
        res[2] = toForward.time;
        return res;
    }

    public int getCount(int destination, int startTime, int endTime) {
        int left_ind = bs_left_ind(startTime, destination);
        int right_ind = bs_right_ind(endTime, destination);
        if (left_ind == -1 || right_ind == -1)
            return 0;
        return right_ind - left_ind + 1;
    }

    private int bs_left_ind(int start_time, int dest) {
        ArrayList<Tuple> domain = new ArrayList<>();
        if (map.containsKey(dest))
            domain = map.get(dest);
        int low = 0, high = domain.size() - 1;
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (domain.get(mid).time >= start_time) {
                ans = mid;
                high = mid - 1;
            } else
                low = mid + 1;
        }
        return ans;
    }

    private int bs_right_ind(int end_time, int dest) {
        ArrayList<Tuple> domain = new ArrayList<>();
        if (map.containsKey(dest))
            domain = map.get(dest);
        int low = 0, high = domain.size() - 1;
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (domain.get(mid).time <= end_time) {
                ans = mid;
                low = mid + 1;
            } else
                high = mid - 1;
        }
        return ans;
    }
}

/**
    Your Router object will be instantiated and called as such:
    Router obj = new Router(memoryLimit);
    boolean param_1 = obj.addPacket(source,destination,timestamp);
    int[] param_2 = obj.forwardPacket();
    int param_3 = obj.getCount(destination,startTime,endTime);
*/

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here