Question: Nvidia OA | TTL Cache | OFF - Campus | 5th August 2023
2
Entering edit mode

ADD COMMENTlink 10 months ago Delta 2.5k
0
Entering edit mode

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

 

vector<int> count_cache_items(vector<vector<int>> &data, int a, vector<int> &queries)

{

    // Sort the data by their expiration times (data[i][0] + data[i][1])

    sort(data.begin(), data.end(), [](const vector<int> &a, const vector<int> &b)

         { return a[0] + a[1] < b[0] + b[1]; });

 

    vector<int> result;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> cache; // Min-Heap

 

    int dataIndex = 0;

    for (int query : queries)

    {

        // Remove expired items from the cache

        while (!cache.empty() && cache.top().first <= query)

        {

            cache.pop();

        }

 

        // Add items from data to the cache that are still alive at the current query time

        while (dataIndex < data.size() && data[dataIndex][0] <= query)

        {

            cache.push({data[dataIndex][0] + data[dataIndex][1], dataIndex});

            dataIndex++;

        }

 

        // The number of items in the cache is the size of the priority queue

        result.push_back(cache.size());

    }

 

    return result;

}

 

int main()

{

    vector<vector<int>> data = {{105231, 183}, {105334, 34}, {105198, 543}};

    int a = 3;

    vector<int> queries = {105338, 105410};

 

    vector<int> result = count_cache_items(data, a, queries);

 

    for (int count : result)

    {

        cout << count << " ";

    }

 

    return 0;

}

ADD COMMENTlink 8 months ago SARTHAK NARANG • 0

Login before adding your answer.

Similar Posts
Loading Similar Posts