## Google Interview Question

SDE1s**Country:**India

Set can be implemented using RB-Tree or AVL Tree. For random number what if we just return the number from any random position from the set.

And how do you pick a random position in the tree? Presumably the random number generator should have a uniform distrubution over the set.

Randomization can be done like this :

d = random number => tree depth

So we will traverse till depth d, at each node we will generate a random boolean value :

true : move left

false : move right

At last we'll end up on a random node. But the challenge here is uniform distribution of random node selection over all the nodes which looks quiet difficult to me.

Each node could probably maintain number of children in left and right. Choosing right/left can be a function of these values.

Also proceeding to the next level can also be a function of the depth of the tree.

We can store the number of node in each sub trees. It will be easy to find the kth element in tree like that. Each time we rand a number k between 1 and N, where N is the total number of the element.

```
struct Node {
int val;
int cnt; // number of nodes in the tree
Node *left, *rigth;
}
```

```
Node * find_kth(Node *root, int k) {
if ( root == NULL || root->cnt < k) {
return NULL;
}
int lc = 0;
if (root->left != NULL) {
lc = root->left->cnt;
}
if (lc >= k) {
return find_kth(root->left, k);
} else if (lc == k -1) {
return root;
} else{
return find_kth(root->right, k - lc - 1);
}
}
```

Hi, thanks for the code. I think there might be a minor error. Correct me if I'm wrong please.

```
if (lc >= k) {
return find_kth(root->left, k);
} else if (lc == k -1) {
return node;
} else{
return find_kth(root->right, k - lc);
}
```

I think the final return should be find_kth(root->right, k-lc-1);

Because we also need to deduct their parent node.

@Akria6, yeah, your are right, it should be k-lc-1. Thank you for your correcting. I have re-edited the code.

if cnt is the number of nodes in the tree, multiple nodes may have the same values, how do you choose from them. Another thing, some k values may not exist in the node's cnt.

```
else if (lc == k -1) {
return node;
}
```

okay, neat solution, but what exactly is node here , i cant seem to find the declaration

Using a tree to implement the "set" interface is possible like the Java TreeSet class, but it's usually used for ordered sets. For un-ordered set interface it's better to use a hash-table like the java HashSet class, because it provides O(1) performance vs O(log n) performance for TreeSet.

My solution above of using a HashMap and ArrayList together to provide unordered set interface plus a random() method in O(1) time, is thus better than the tree-based implementation you describe as "neat".

O(1) solution for every set operation and random element of the set.

- Maintain a hash-table for insertion and deletion.

- Along with the hash-table, maintain a vector of pointers to the elements in the hash-table. Lets call it vector(hashtable-element-pointers).

- For insertion, add the element to hash-table, and add a pointer to the end of the vector(hashtable-element-pointers).

- For deletion, get the index of the key of vector(hashtable-element-pointers), replace that pointer with the last element of vector(hashtable-element-pointer) and perform pop_back() on the vector.

Here is the code..

```
#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
using namespace std;
// Supports set of strings and random-element in the set.
class mySet {
private:
unordered_map<string,int> myMap;
vector<unordered_map<string,int>::iterator> myMapVector;
public:
mySet() {
myMap.clear();
myMapVector.clear();
}
bool IsElementPresent(string s) {
unordered_map<string,int>::iterator it = myMap.find(s);
if( it!= myMap.end() )
return true;
return false;
}
void Insert( string s ) {
if( IsElementPresent(s) )
return;
myMap[s] = myMapVector.size();
unordered_map<string,int>::iterator it = myMap.find(s);
myMapVector.push_back(it);
}
void Delete(string s) {
if( !IsElementPresent(s) )
return;
unordered_map<string,int>::iterator it = myMap.find(s);
myMapVector[it->second] = myMapVector[myMapVector.size()-1];
myMap.erase(it);
myMapVector.pop_back();
}
string GetRandomElement() {
if(myMapVector.size() == 0 )
return NULL;
int randomIndex = rand()%myMapVector.size();
return myMapVector[randomIndex]->first;
}
};
int main()
{
mySet testSet;
testSet.Insert("zero");
testSet.Insert("one");
testSet.Insert("two");
testSet.Insert("three");
testSet.Insert("four");
testSet.Insert("five");
testSet.Insert("seven");
testSet.Insert("eight");
testSet.Insert("nine");
cout << testSet.IsElementPresent("six") << endl;
cout << testSet.IsElementPresent("five") << endl;
cout << testSet.IsElementPresent("four") << endl;
testSet.Delete("four");
cout << testSet.IsElementPresent("four") << endl;
cout << testSet.GetRandomElement() << endl;
cout << testSet.GetRandomElement() << endl;
cout << testSet.GetRandomElement() << endl;
cout << testSet.GetRandomElement() << endl;
}
```

'Set' could be implemented as a 'hashtable' with chaining as a conflict resolution.

```
T getRandomElement(){
// choose random bucket [0; buckets length)
int randomBucketIndex = rand.nextInt( buckets.length )
Bucket bucket = buckets[randomBucketIndex];
// choose random element from selected bucket, [0; bucket size)
int randomElemIndex = rand.nextInt( bucket.size );
return bucket.get(randomElemIndex);
}
```

To provide a random() function in addition to the regular "set" interface, we keep a dynamic array (e.g. vector) of the keys in addition to the hashtable which is usually used to store unsorted-set. The index of the item in the array will be stored in the hash-table as the value assoicated with the key.

- gen-y-s April 20, 2013When a key is added to the set, we append it to the array, and stoe the key in its location in the array in the hash-table. When a key is deleted from the set, we delete it from the array and the hash-table, and then move the last item in the array to where the deleted item was in the array.

To return a random key, we create a random number from 0 to the number of items minus 1, and lookup the corresponding position in the array.

All operations, inclusing the new random() method, will remain O(1).