Tag: data structure

SIngle Thread LRUCache in C++

#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; } […]

Euler Traversal & LCA in a Tree

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 […]