3508: Implement-Router
Medium

table of contents

I hate this question-

For the data structures used in this question, I realised that I needed multiple to be able to implement all the functionality required in the question.

int packetLimit;
set<tuple<int, int, int>> uniquePackets;        // set<{source, destination, timestamp}>
unordered_map<int, vector<int>> packetCount;    // unordered_map<destination, vector<timestamp>> 
queue<tuple<int, int, int>> packetQueue;        // queue<{source, destination, timestamp}>

When we initialise Router, we simply need to set our packetLimit:

Router(int memoryLimit) {
    packetLimit = memoryLimit;
}

For the function addPacket,

  1. we first define the newPacket we are planning to add
  2. check if this newPacket exists already
    • if it does, we can return false early
  3. check if packetQueue has reached maximum capacity
    • if it has, we can simply erase the first element
  4. add our newPacket to the back of packetQueue
bool addPacket(int source, int destination, int timestamp) {
    tuple<int, int, int> newPacket = {source, destination, timestamp};

    if (uniquePackets.count(newPacket)) {
        return false;
    }

    if (packetQueue.size() == packetLimit) {
        auto [source, destination, timestamp] = packetQueue.front();
        uniquePackets.erase(packetQueue.front());
        packetCount[destination].erase(packetCount[destination].begin());
        packetQueue.pop();
    }

    uniquePackets.insert(newPacket);
    packetQueue.push(newPacket);
    packetCount[destination].push_back(timestamp);

    return true;
}

Now, for the function forwardPacket,

  1. we first check if packetQueue is empty
    • if it is, then we simply return {}
  2. else, we pop the front of packetQueue and return it (as a vector<int>)
vector<int> forwardPacket() {
    if (packetQueue.empty()) {
        return {};
    }

    auto [source, destination, priority] = packetQueue.front();
    uniquePackets.erase(packetQueue.front());
    packetQueue.pop();
    packetCount[destination].erase(packetCount[destination].begin());

    return {source, destination, priority};
}

Finally, for the getCount function, we can simply index into our vector<int> of timestamps present at packetCount[destination]. Then, we use lower_bound and upper_bound to find the first and last possible index startTime and endTime could be placed inside of timestamps. Now, using the difference between startPos and endPos, we can get the count of all unsent packets with the specified destination occuring between startTime and endTime.

int getCount(int destination, int startTime, int endTime) {
    auto& timestamps = packetCount[destination];
    auto startPos = lower_bound(timestamps.begin(), timestamps.end(), startTime);
    auto endPos = upper_bound(timestamps.begin(), timestamps.end(), endTime);

    return int(endPos - startPos);
}

code

class Router {
public:
    Router(int memoryLimit) {
        packetLimit = memoryLimit;
    }
    
    bool addPacket(int source, int destination, int timestamp) {
        tuple<int, int, int> newPacket = {source, destination, timestamp};

        if (uniquePackets.count(newPacket)) {
            return false;
        }

        if (packetQueue.size() == packetLimit) {
            auto [source, destination, timestamp] = packetQueue.front();
            uniquePackets.erase(packetQueue.front());
            packetCount[destination].erase(packetCount[destination].begin());
            packetQueue.pop();
        }

        uniquePackets.insert(newPacket);
        packetQueue.push(newPacket);
        packetCount[destination].push_back(timestamp);
        
        return true;
    }
    
    vector<int> forwardPacket() {
        if (packetQueue.empty()) {
            return {};
        }

        auto [source, destination, priority] = packetQueue.front();
        uniquePackets.erase(packetQueue.front());
        packetQueue.pop();
        packetCount[destination].erase(packetCount[destination].begin());

        return {source, destination, priority};
    }
    
    int getCount(int destination, int startTime, int endTime) {
        auto& timestamps = packetCount[destination];
        auto startPos = lower_bound(timestamps.begin(), timestamps.end(), startTime);
        auto endPos = upper_bound(timestamps.begin(), timestamps.end(), endTime);

        return int(endPos - startPos);
    }
private:
    int packetLimit;
    set<tuple<int, int, int>> uniquePackets;
    unordered_map<int, vector<int>> packetCount;
    queue<tuple<int, int, int>> packetQueue;
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */

complexity

learnings

time taken