Google Interview Question for SDE1s


Country: India




Comment hidden because of low score. Click to expand.
2
of 4 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).

- gen-y-s April 20, 2013 | Flag Reply
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.

- Cerberuz April 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous April 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Cerberuz April 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- bbarodia April 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nikhil May 08, 2013 | Flag
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.

- Anonymous April 15, 2013 | Flag Reply
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);
   }
}

- notbad April 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Akira6 April 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- notbad April 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- aileen May 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This method is great!

- 790042744@qq.com May 10, 2013 | Flag
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

- niku April 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gen-y-s April 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ niku I'm sorry, it should be

return root;

- notbad April 23, 2013 | Flag
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;
}

- chetan.j9 May 09, 2013 | Flag Reply
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);
	}

- m@}{ May 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How do you implement union operation with this?

- alex May 14, 2013 | Flag


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More