LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with a positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Example:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

class LRUCache
{
public:
    int cap;
    vector<int> v;
    unordered_map<int, int> mp;

    LRUCache(int capacity)
    {
        cap = capacity;
    }

    int get(int key)
    {
        auto pos = find(v.begin(), v.end(), key);
        if (pos != v.end())
        {
            v.erase(pos);
            v.push_back(key);
            return mp[key];
        }
        return -1;
    }

    void put(int key, int value)
    {
        auto pos = find(v.begin(), v.end(), key);
        if (pos != v.end())
            v.erase(pos);

        if (v.size() == cap)
        {
            mp[v[0]] = 0;
            v.erase(v.begin());
        }

        mp[key] = value;
        v.push_back(key);
    }
};

int main()
{
    LRUCache lRUCache(2);
    lRUCache.put(1, 1);
    lRUCache.put(2, 2);
    cout << "[";
    cout << lRUCache.get(1) << ", ";
    lRUCache.put(3, 3);
    cout << lRUCache.get(2) << ", ";
    lRUCache.put(4, 4);
    cout << lRUCache.get(1) << ", ";
    cout << lRUCache.get(3) << ", ";
    cout << lRUCache.get(4);
    cout << "]";

    return 0;
}

Implement a queue using two stacks

Implement a queue using two stacks. Recall that a queue is a FIFO (first-in, first-out) data structure with the following methods: enqueue, which inserts an element into the queue, and dequeue, which removes it.

Example:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

class MyQueue
{
public:
    stack<int> s1;
    stack<int> s2;

    void push(int x)
    {
        while (!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();
        }
        s1.push(x);
        while (!s2.empty())
        {
            s1.push(s2.top());
            s2.pop();
        }
    }
    int pop()
    {
        int x = s1.top();
        s1.pop();
        return x;
    }
    int peek()
    {
        return s1.top();
    }
    bool empty()
    {
        int flag = 0;
        if (s1.empty())
            flag = 1;
        return flag;
    }
};

int main()
{
    MyQueue myQueue;
    myQueue.push(1);
    myQueue.push(2);

    cout << "[";
    cout << myQueue.peek() << ", ";
    cout << myQueue.pop() << ", ";
    if (myQueue.empty())
        cout << "true";
    else
        cout << "false";

    cout << "]";

    return 0;
}

Implement min stack

Implement a stack that has the following methods:

• push(val), which pushes an element onto the stack
• pop(), which pops off and returns the topmost element of the stack. If there are no elements in the stack, then it should throw an error or return null.
• max(), which returns the maximum value in the stack currently. If there are no elements in the stack, then it should throw an error or return null.

Each method should run in constant time

Example:

Input:  push = [-20,0,-3]
Output: -20

Approach

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> v;
int min1 = INT_MAX;

void push(int x)
{
    if (x < min1)
        min1 = x;
    v.push_back(x);
}

int top()
{
    return v[v.size() - 1];
}

void pop()
{
    int x = top();
    v.pop_back();
    if (x == min1)
    {
        min1 = INT_MAX;
        for (int i : v)
        {
            if (i < min1)
                min1 = i;
        }
    }
}

int getMin()
{
    return min1;
}

int main()
{
    push(-20);
    push(0);
    push(-3);
    cout << getMin();

    return 0;
}

Design Hit Counter

Design and implement a HitCounter class that keeps track of requests (or hits). It should support the following operations:

• record(timestamp): records a hit that happened at timestamp
• total(): returns the total number of hits recorded
• range(lower, upper): returns the number of hits that occurred between timestamps lower and upper (inclusive)

Example:

Input:  counter.hit(1);
// hit at timestamp 2.
counter.hit(2);
// hit at timestamp 3.
counter.hit(3);
// get hits at timestamp 4, should return 3.
counter.getHits(4);
// hit at timestamp 300.
counter.hit(300);
// get hits at timestamp 300, should return 4.
counter.getHits(300);
// get hits at timestamp 301, should return 3.
counter.getHits(301);
Output: [3,4,3]

Approach

C++

#include <bits/stdc++.h>
using namespace std;
class HitCounter
{
public:
    HitCounter()
    {
        times.resize(300);
        hits.resize(300);
    }
    void hit(int timestamp)
    {
        int idx = timestamp % 300;
        if (times[idx] != timestamp)
        {
            times[idx] = timestamp;
            hits[idx] = 1;
        }
        else
        {
            ++hits[idx];
        }
    }
    int getHits(int timestamp)
    {
        int res = 0;
        for (int i = 0; i < 300; ++i)
        {
            if (timestamp - times[i] < 300)
            {
                res += hits[i];
            }
        }
        return res;
    }
private:
    vector<int> times, hits;
};
int main()
{
    HitCounter counter;
    counter.hit(1);
    counter.hit(2);
    counter.hit(3);
    cout << "[";
    cout << counter.getHits(4) << ", ";
    counter.hit(300);
    cout << counter.getHits(300) << ", ";
    cout << counter.getHits(301);
    cout << "]";
    return 0;
}

Implement Peek Iterator

Given an iterator with methods next() and hasNext(), create a wrapper iterator, PeekableInterface, which also implements peek(). peek shows the next element that would be returned on next().

Example:

Input:  1 2 3

Output:

2
2
1
Not Exist
0

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

class MyIterator
{
private:
    MyIterator *nextIt = NULL;
    int data;

public:
    MyIterator(MyIterator *nextPtr = NULL)
    {
        nextIt = nextPtr;
    }

    //function to get the data
    int getData()
    {
        return data;
    }

   //funtion to set the data
    void setData(int newData)
    {
        data = newData;
    }
    
    //function to set the next iterator
    void setNextIt(MyIterator *nxt)
    {
        nextIt = nxt;
    }

    //function to check for next terator
    bool hasNext()
    {
        return nextIt != NULL;
    }

    //function to get the next value
    int next()
    {
        return nextIt->getData();
    }
};

struct NoNextException : public exception
{

    const char *what() const throw()
    {
        return "Not Exist";
    }
};

class PeekableInterface : public MyIterator
{
public:
    PeekableInterface(PeekableInterface *nextPtr = NULL)
    {
        this->setNextIt(nextPtr);
    }
    int peek()
    {
        try
        {
            if (this->hasNext())
                return this->next();
            else
                throw NoNextException();
        }
        catch (NoNextException &e)
        {
            cout << e.what() << endl;
            return 0;
        }
    }
};

int main()
{

    PeekableInterface *it = new PeekableInterface();
    it->setData(1);
    PeekableInterface *it2 = new PeekableInterface(it);
    it2->setData(2);
    PeekableInterface *it3 = new PeekableInterface(it2);
    it3->setData(3);
    cout << it3->peek() <<"\n";
    cout << it3->next() <<"\n";
    cout << it2->peek() <<"\n";
    cout << it->peek() <<"\n";
    return 0;
}

Implement Trie (Prefix Tree)

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example :

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    char val = '\0';
    struct Node *child[26];
    bool isword = false;
};
Node *root = new Node();

//funtion to insert word
//into the trie
void insert(string word)
{
    Node *node = root;
    for (int i = 0; i < word.size(); i++)
    {
        char c = word[i];
        int index = c - 'a';
        if (node->child[index])
        {
            node = node->child[index];
            continue;
        }
        node->child[index] = new Node();
        node->child[index]->val = c;
        node = node->child[index];
    }
    node->isword = true;
}

//check if word is present in the
//trie
bool search(string word)
{
    struct Node *node = root;
    for (int i = 0; i < word.size(); i++)
    {
        char c = word[i];
        int index = c - 'a';
        if (!node->child[index])
            return false;
        node = node->child[index];
    }
    if (node->isword)
        return true;
    return false;
}

bool startsWith(string prefix)
{
    Node *node = root;
    for (int i = 0; i < prefix.size(); i++)
    {
        char c = prefix[i];
        int index = c - 'a';
        if (!node->child[index])
            return false;
        node = node->child[index];
    }
    return true;
}

int main()
{

    cout << "[";
    insert("apple");
    if (search("apple"))
        cout << "true, ";
    else
        cout << "false, ";
    if (search("app"))
        cout << "true, ";
    else
        cout << "false, ";
    if (startsWith("app"))
        cout << "true, ";
    else
        cout << "false, ";
    insert("app");
    if (search("app"))
        cout << "true";
    else
        cout << "false";

    cout << "]";

    return 0;
}