# Random Hash DS

Implement a set-like data structure with three methods:

* Insert an element 
* Remove an element (by value); and 
* Return an element chosen uniformly at random

e.g. After inserting 1, 3, 7, 2 and 9 in that order, we could remove 7, and the random number would be one of {1, 3, 2 or 9} each with 25% probability.

* Brain storm:
  * Binary tree: Constant space with logN insertions and deletions, and O(N) random returns.
  * Hash table
    * O(1) inserts and deletes.
    * O(N) random

```cpp
int main() {
    unordered_set<int> s;
    for (auto i : { 1,2,3,4,5,6,7 }) {
        s.insert(i);
    }

    srand(time(nullptr));

    while (1) {
        int random = rand() % s.size();
        auto iter = s.begin();
        std::advance(iter, random);
        cout << *iter << endl;
        pause();

    }

}
```

* Working off this idea, once thing we can do is use a secondary hash structure, like an vector (which support O(1) removal and deletions by index).
* Essentially we use the secondary vector as a container that reverses the order of our map structure. Our map is `<value, index>` and our vector is `<index, value>`. Using these two details, we can find both the value or index, in O(1) time. Removals are just swapping and removing things from the end, and modifying our map to accommodate that.

```cpp
class rand_hash{
public:
    rand_hash() : size(0) {
        srand(time(nullptr));
    }

    void insert(int element) {
        map.insert(make_pair(element, size++));
        vect.push_back(element);
    }

    void remove(int element) {
        if (map.find(element) == map.end()) return;

        // adjust vector elements
        // 1) get the index to delete from the main map
        int rem_index = map.find(element)->second;
        // 2) index to the vector and replace it with last element
        vect.at(rem_index) = vect.back();
        // 3) remove last element
        vect.erase(vect.begin() + size - 1);

        // adjust map
        // 1) Remove element
        map.erase(element);
        // 2) Fix modified element index
        map.find(vect.at(rem_index))->second = rem_index;

        size--;
    }

    int random() {
        int index = rand() % size;
        int findthis = vect.at(index);

        return map.find(findthis)->first;
    }

    void print() {
        for (auto i : map)
            cout << i.first << ":" << i.second << " ";
        pause();
    }

    void print_vec() {
        for (auto i : vect) cout << i << " ";
        pause();
    }

private:
    // value -> index
    unordered_map<int, int> map;
    vector<int> vect;

    int size;
};


int main() {
    rand_hash map;
    for (auto i : { 0,1,2,3,4,5,6 }) {
        map.insert(i);
    }
    map.print();

    map.remove(3);
    map.remove(4);
    map.print();

    while (1) {
        cout << map.random() << " ";
        pause();
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/design/random_hash_ds.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.