• 0

Implementation of Advanced set which have the functionality as "Set" in c++ along with extra functionality-Random number generator.Returns the random number from the set.

Country: India

Comment hidden because of low score. Click to expand.
1
of 3 vote

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.
When 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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

implement set as AVL tree in array representation.
Find random number based on the index of array.

Comment hidden because of low score. Click to expand.
0
of 0 vote

could someone please post a more well defined version of this problem.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

This method is great！

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

Comment hidden because of low score. Click to expand.
0

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".

Comment hidden because of low score. Click to expand.
0

@ niku I'm sorry, it should be

``return root;``

Comment hidden because of low score. Click to expand.
0
of 2 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

'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);
}``````

Comment hidden because of low score. Click to expand.
0

How do you implement union operation with this?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.