#include <iostream> #include <list> #include <unordered_map> using namespace std; size_t capacity; class LRUCache { public: bool Lookup(int key, int *price) { auto it = hash_table.find(key); if (it == hash_table.end()) { return false; } *price = it->second.second; // update the key in the queue MoveToFront(key, it); return true; } […]

Given an array of integers where each value 1 <= x <= len(array), write a function that finds all the duplicates in the array. C++ Solution $ g++ -std=c++11 ./FindDuplicates.cc $ ./a.out 1 2 Reference https://www.byte-by-byte.com/findduplicates/

Premise A hashmap has a time complexity of O(1) for all operations. Problem You have to find a constant time method to uniformly random selection of a key in a Hash map. Assumptions The map can grow to memory size. You can use any readymade hash map. Solution […]

Euler Traversal Start as ROOT –> Subtree-1 –> ROOT –> Subtree-2 –> ROOT –> Subtree-3 –> ROOT Recurse at each subtree as above All nodes of a subtree appear together, contiguously in the traversal. Why Euler Traversal Gets LCA? Assume we want LCA of a node u in […]

Singly link list A link list is a non-linear data structure with a head pointer. The rest of the nodes in the list could be accessed by using “next” of head. The code to create a list of N node involves creating head separately. Rest of the nodes […]