Implement Router

• Data Structures: Use a java.util.Queue (e.g., ArrayDeque) to store packets for FIFO order and a java.util.Set for O(1) duplicate checks.
• Packet Representation: Create a custom Packet class or record with source, destination, and timestamp fields. Implement equals() and hashCode() for correct behavior in the Set.
• addPacket(source, destination, timestamp):
  1. Create a Packet object.
  2. Check if the packet exists in the Set. If yes, return false.
  3. If the Queue size equals memoryLimit, remove the oldest packet by calling poll() on the Queue and remove() on the Set.
  4. Add the new packet to the Queue using offer() and to the Set using add().
  5. Return true.
• forwardPacket():
  1. If the Queue is empty, return an empty array.
  2. Remove the oldest packet using poll() from the Queue.
  3. Remove the same packet from the Set.
  4. Return the packet's data.
• getCount(destination, startTime, endTime):
  1. Initialize a counter to zero.
  2. Iterate through every packet in the Queue.
  3. For each packet, check if its destination and timestamp match the query parameters.
  4. If they match, increment the counter.
  5. Return the final count.

In this implementation, we use two main data structures: a java.util.Queue (specifically an ArrayDeque for efficiency) to maintain the order of packets and a java.util.Set (a HashSet) to keep track of existing packets for quick duplicate checks. A simple Packet record or class is defined to hold the packet's attributes.

• Adding a packet: We first check for duplicates using the HashSet. If the packet is unique, we check if the router is at its memoryLimit. If so, we evict the oldest packet by removing it from the front of the Queue and also from the HashSet. Finally, the new packet is added to the back of the Queue and to the HashSet.

• Forwarding a packet: This follows the FIFO principle. We simply remove the packet from the front of the Queue (if not empty) and also from the HashSet to keep the data structures synchronized.

• Counting packets: This is the brute-force part. The method iterates through every single packet currently in the Queue and checks if it meets the criteria (matching destination and timestamp within the specified range). While simple, this linear scan is the primary performance bottleneck of this approach.

1import java.util.Queue;2import java.util.Set;3import java.util.HashSet;4import java.util.LinkedList;5 6class Router {7    // Using a record for an immutable Packet data carrier8    private record Packet(int source, int destination, int timestamp) {}9 10    private final int memoryLimit;11    private final Queue<Packet> packetQueue;12    private final Set<Packet> packetSet;13 14    public Router(int memoryLimit) {15        this.memoryLimit = memoryLimit;16        this.packetQueue = new LinkedList<>(); // LinkedList or ArrayDeque work well17        this.packetSet = new HashSet<>();18    }19 20    public boolean addPacket(int source, int destination, int timestamp) {21        Packet newPacket = new Packet(source, destination, timestamp);22        if (packetSet.contains(newPacket)) {23            return false; // Duplicate packet24        }25 26        if (packetQueue.size() == memoryLimit) {27            Packet oldestPacket = packetQueue.poll();28            packetSet.remove(oldestPacket);29        }30 31        packetQueue.offer(newPacket);32        packetSet.add(newPacket);33        return true;34    }35 36    public int[] forwardPacket() {37        if (packetQueue.isEmpty()) {38            return new int[0];39        }40        Packet packetToForward = packetQueue.poll();41        packetSet.remove(packetToForward);42        return new int[]{packetToForward.source(), packetToForward.destination(), packetToForward.timestamp()};43    }44 45    public int getCount(int destination, int startTime, int endTime) {46        int count = 0;47        for (Packet packet : packetQueue) {48            if (packet.destination() == destination && packet.timestamp() >= startTime && packet.timestamp() <= endTime) {49                count++;50            }51        }52        return count;53    }54}

• Data Structures: In addition to the Queue and Set from the brute-force approach, we add a Map<Integer, TreeMap<Integer, Integer>> named destTimestamps.
  • The outer Map's key is the destination ID.
  • The inner TreeMap's key is the timestamp, and its value is the count of packets for that destination at that exact timestamp.
• addPacket(source, destination, timestamp):
  1. Perform duplicate check and memory limit eviction as before.
  2. When evicting the oldest packet, locate its destination's TreeMap and decrement the count for its timestamp. If the count becomes zero, remove the timestamp entry from the TreeMap.
  3. When adding the new packet, locate its destination's TreeMap (or create one) and increment the count for its timestamp.
• forwardPacket():
  1. Remove the packet from the Queue and Set.
  2. Update the destTimestamps map by decrementing/removing the packet's timestamp, similar to the eviction step in addPacket.
• getCount(destination, startTime, endTime):
  1. Look up the destination in the destTimestamps map. If not found, return 0.
  2. Get the corresponding TreeMap.
  3. Use TreeMap.subMap(startTime, true, endTime, true) to get a view of the relevant timestamp range.
  4. Iterate through the values (counts) of this sub-map and sum them up. Return the total.

We keep the Queue for FIFO order and the Set for duplicate checks. The main enhancement is a Map<Integer, TreeMap<Integer, Integer>> destTimestamps. This structure organizes packets by destination, and for each destination, it keeps a sorted map of timestamps to their frequencies.

• Adding/Forwarding Packets: When a packet is added or removed, we perform the O(1) operations on the Queue and Set, but we also need to update our new map. We find the TreeMap for the packet's destination and update the count for its timestamp. Since TreeMap is a balanced binary search tree, adding, removing, or updating an entry takes O(log K) time, where K is the number of unique timestamps for that destination.

• Counting Packets: This is where the TreeMap shines. Instead of a linear scan of all packets, we first access the specific destination's TreeMap in O(1). Then, we use the subMap method to efficiently isolate only the timestamps within the [startTime, endTime] range. This operation takes O(log K). We then iterate only over this (typically much smaller) sub-map to sum the packet counts. While the worst-case still involves iterating over all K entries (making it O(K)), the average case for smaller time ranges is much improved.

1import java.util.Queue;2import java.util.Set;3import java.util.HashSet;4import java.util.LinkedList;5import java.util.Map;6import java.util.HashMap;7import java.util.TreeMap;8 9class Router {10    private record Packet(int source, int destination, int timestamp) {}11 12    private final int memoryLimit;13    private final Queue<Packet> packetQueue;14    private final Set<Packet> packetSet;15    private final Map<Integer, TreeMap<Integer, Integer>> destTimestamps;16 17    public Router(int memoryLimit) {18        this.memoryLimit = memoryLimit;19        this.packetQueue = new LinkedList<>();20        this.packetSet = new HashSet<>();21        this.destTimestamps = new HashMap<>();22    }23 24    public boolean addPacket(int source, int destination, int timestamp) {25        Packet newPacket = new Packet(source, destination, timestamp);26        if (packetSet.contains(newPacket)) {27            return false;28        }29 30        if (packetQueue.size() == memoryLimit) {31            Packet oldestPacket = packetQueue.poll();32            packetSet.remove(oldestPacket);33            removeTimestamp(oldestPacket.destination(), oldestPacket.timestamp());34        }35 36        packetQueue.offer(newPacket);37        packetSet.add(newPacket);38        addTimestamp(destination, timestamp);39        return true;40    }41 42    public int[] forwardPacket() {43        if (packetQueue.isEmpty()) {44            return new int[0];45        }46        Packet packetToForward = packetQueue.poll();47        packetSet.remove(packetToForward);48        removeTimestamp(packetToForward.destination(), packetToForward.timestamp());49        return new int[]{packetToForward.source(), packetToForward.destination(), packetToForward.timestamp()};50    }51 52    public int getCount(int destination, int startTime, int endTime) {53        if (!destTimestamps.containsKey(destination)) {54            return 0;55        }56        TreeMap<Integer, Integer> timestamps = destTimestamps.get(destination);57        // Get a view of the map for the given range58        Map<Integer, Integer> subMap = timestamps.subMap(startTime, true, endTime, true);59        int count = 0;60        for (int freq : subMap.values()) {61            count += freq;62        }63        return count;64    }65 66    private void addTimestamp(int destination, int timestamp) {67        destTimestamps.computeIfAbsent(destination, k -> new TreeMap<>());68        TreeMap<Integer, Integer> timestamps = destTimestamps.get(destination);69        timestamps.put(timestamp, timestamps.getOrDefault(timestamp, 0) + 1);70    }71 72    private void removeTimestamp(int destination, int timestamp) {73        TreeMap<Integer, Integer> timestamps = destTimestamps.get(destination);74        timestamps.put(timestamp, timestamps.get(timestamp) - 1);75        if (timestamps.get(timestamp) == 0) {76            timestamps.remove(timestamp);77        }78        if (timestamps.isEmpty()) {79            destTimestamps.remove(destination);80        }81    }82}

• Data Structure: This approach replaces the TreeMap from the previous solution with an Order Statistic Tree (OST). An OST is a balanced binary search tree (e.g., Red-Black Tree) where each node is augmented to store the size of its subtree.
• Core Operations of OST: An OST supports standard BST operations (add, remove) in O(log K) time, plus a crucial rank(x) operation, which also runs in O(log K) and returns the number of elements in the tree less than or equal to x.
• addPacket / forwardPacket: The logic is identical to the TreeMap approach, but operations are performed on the OST. Adding or removing a timestamp takes O(log K) time.
• getCount(destination, startTime, endTime):
  1. Look up the destination's OST in the map.
  2. The count of items in the range [startTime, endTime] is calculated as ost.rank(endTime) - ost.rank(startTime - 1).
  3. Since each rank query takes O(log K) time, the entire getCount operation is completed in O(log K) time, regardless of the range size.

The key to this optimal approach is using a data structure that can answer range-count queries in logarithmic time. An Order Statistic Tree is a perfect candidate.

We would structure our class with a Map<Integer, OrderStatisticTree>, where each destination maps to an OST that stores its timestamps. An OST, by keeping track of subtree sizes at each node, can determine the rank of any element (i.e., how many elements are smaller than or equal to it) in O(log K) time, where K is the number of elements in the tree.

With this rank function, getCount becomes trivial and fast. The number of packets with timestamps in the inclusive range [startTime, endTime] is simply the total count of packets with timestamps up to endTime minus the total count of packets with timestamps up to startTime - 1. This translates to rank(endTime) - rank(startTime - 1).

Because both addPacket and forwardPacket also only require logarithmic-time updates to the OST, all three public methods of the Router class achieve a worst-case time complexity of O(log N), where N is the memory limit.

Note: Since java.util does not contain an OST, the code below is conceptual. In a competitive programming context, one might use a Fenwick Tree with coordinate compression or implement a custom balanced BST to achieve this.