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

  1. The map can grow to memory size.
  2. You can use any readymade hash map.

Solution

I’m discussing the pseudo code for a Python solution. All operations work in constant time except remove().

randMap = {}

def insert(k, v):
    randMap[k] = v    

The random must pick a random key. But how? We can store all the keys in a list and then run random() on the list indexes.

randMap = {}
indexMap = {}
keyList = []
last = 0
def insert(k, v):
    randMap[k] = v
    keyList.append(k)
    last += 1
    
    # Maintain index of each key
    indexMap[k] = len(keyList)    
def getRandom():
    start = 0
    end = len(keyList) - 1
    randomIndex = random(start, end)
    key = keyList[randomIndex]
    
    return key

How do you delete a key?

This is the crux of the problem. Deletion of a key would need us to change the index array too. That means we need to shift all elements of the array and complexity would shoot to O(n).

def remove(k):
    # Remove from the hash map
    randMap.pop(k, None)
    
    # Remove from key list
    index = indexMap[k]
    
    # This is O(n) operation
    keyList.remove(index)

    # Pop the index too
    indexMap.pop(k) 

How to improve deletion?

  1. Delete the entry and mark the entry invalid. The probability distribution does not change, however with more and more deletions, you have a sparse array. Thus you would need multiple getRandom() to get a valid key.
  2. Move the last element to the deleted element. Adjust the index of the last element.
def remove(k):
    # Remove from the hash map
    randMap.pop(k, None)

    index = indexMap[k]
    indexMap[last] = index
    
    # This is O(1) operation
    keyList[index] = keyLast[last]

    # Pop the index too
    indexMap.pop(k)
    last -= 1 

This is a constant time solution.

Advertisements

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?

enter image description here
Assume we want LCA of a node u in subtree a and node v in subtree c. A Euler walk of the tree will have all nodes of the subtree a followed by the LCA node ROOT and all the nodes of subtree c.

Thus Euler walk/ traversal of a tree will always have the LCA for any two nodes.

References

Written with StackEdit.

Headless link list implementation in C

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 are appended to the head.

That looked ugly to me and so I wrote it in a generic manner. Using a temporary pointer, I wrote a single loop to create N link list nodes, keeping head intact.

Here is the code:

#define NULL (char*)0

typedef struct node_ {
        int n;
        struct node_ *next;
} node;

int main()
{
        int i = 5;
        node *head = NULL;
        node *temp = NULL;

        while (i-- > 0) {
                head = malloc(sizeof(node));
                head->n = i;
                head->next = temp;
                temp = head;
        }

        temp = head;