## How to Select a Random Key from a Hash Map in Constant Time?

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 I'm discussing the pseudo code for a…

## 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 subtree a and node v in subtree…

## Bloom Filters

Used for determining presence of an element in a set. Uses a set of hash functions that return an integer. The returned value is used as index into a bit vector. hash1(element) => index1 hash2(element) => index2 To search an element, we check for both the index are set. If yes, element might be there.…