Implement Router

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.

• to check for unique packets, I have uniquePackets (set<tuple<int, int, int>>)
• to handle the packet forwarding in a FIFO order, I have packetQueue (queue<tuple<int, int, int>>)
  • both instances use tuple<int, int, int> instead of vector<int> (which is the form some functions return) because tuple have less overhead than vector
• finally, to be able to search for packets that are currently stored in the router with a specific destination and have timestamps in the inclusive range [startTime, endTime], we use packetCount (unordered_map<int, vector<int>>)

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

• addPacket
  • Time: O(n + log(n)) where n denotes the maximum number of packets (memoryLimit)
    • time complexity could be possible if you keep adding packets that have the same destination, since erasing the first element takes O(n) time
    • could use lazy deletion, where we keep an index value of all the packets that have been sent
      • this approach is worse for memory tho
  • Space: O(1)
• forwardPacket
  • Time: O(n + log(n))
  • Space: O(1)
• getCount
  • Time: O(log(n))
  • Space: O(1)
• overall
  • Space: O(n)

learnings

• using vector<int> inside of sets and queues take too much memory and are too slow (lots of overhead)
• remembered how to use tuple
• lower_bound and upper_bound are useful in-built binary search functions that i should use more often

time taken

• 58 minutes and 14 seconds what-