Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

This question can be solved by using just one traverse of the binary tree.

The idea is, do a whatever order of travel, if it is the kth node we are traveling, then replace the previously selected node with probability 1/k.

Node* randomSelect(Node* node) {
	Node* selectedNode = node;
	queue.enqueue(node);
	int count = 1;
	while(!queue.empty()){
		Node* t = queue.dequeue();
		if(1.0/count >= rand())
			selectedNode = t;
		if(t.left != NULL)
			queue.enqueue(t.left);
		if(t.right != NULL)
			queue.enqueue(t.right);
		count++	
	}
	return selectedNode;
}

This uses the idea of selecting a random node from a linkedlist where you don't know how long it is.

- Nova2358 July 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wow this is great!
Just to help somebody count the probability that for example the root node will be selected = 1* 1/2 (it was not replaced by second) * 2/3 (not replaced by third) * 3/4 (not replaced by 4th) = 1/4.

- mbriskar May 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is interesting but it loops N times every time. If you know the total number of nodes it'd be faster to just pick a random number from 0 - N-1 using a uniformly distributed PRNG and then just traverse that many nodes. You're guaranteed not to traverse N nodes every single time.

- sabujp October 02, 2019 | Flag
Comment hidden because of low score. Click to expand.
4
of 6 vote

What I suggest is this: Let define two variables lcount and rcount whith each node. lcount is the number of nodes on left subtree and rcount is the number of nodes in right sub tree. Now we do an preorder traversal. At each node we select that node with probability 1/(1+lc+rc). We go to the left sub tree with probability lc/(1+lc+rc) and go to the right sub tree with probability rc(1+rc+lcc). If we reached a leaf select that node. You can easily check that the probability of selecting each node is 1/n (n number of nodes).

Node* preOrder(Node * node)
{
	int lc= node->lc, rc=node->rc;
	if (node->left ==NULL && node->right==NULL)
		return node;
	int r= rnd()*(lc+rc+1)+1;
	if (r==1)
		return node;
	if (r>1 && r<=lc+1)
		return preOrder( node->left)
	if (r>lc+1)
		return preOrder( node->right);
}

- jobseeker April 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

Why bother?

if you have a lcount and rcount.

Select a random number (say R) in 1,2,..., lcount+rcount+1.

Now traverse the tree picking the element whose inorder position is R.

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

@jobseeker - can you explain what this statement does?
int r= rnd()*(lc+rc+1)+1;
Also i cant understand "At each node we select that node with probability 1/(1+lc+rc). We go to the left sub tree with probability lc/(1+lc+rc) and go to the right sub tree with probability rc(1+rc+lcc)."

Can you please elaborate?

Also i thought of the same approach as Anonymous has mentioned. But i guess your algo is O(Log n)

- Ragavenderan May 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

He is doing "Now we do an preorder traversal." The algo is linear, not O(Lgn)

- Second Attempt September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Pre Order for what? Did you mean by taking a counter and do a preorder and reduce the counter. And return the node when counter is zero?

- Andy2000 September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the complexity is log(n) i.e O(h) only , note that he is either going ti left or right , it is not a preorder traversal , dunno why he called it as preorder traversal

- Geek January 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

This question can be solved with 2 traversals of the tree. Count the number of nodes n in the first traversal. Generate a random number between 1 and n, and return the nth node in the 2nd traversal. Now the question becomes how to solve it with just one traversal.

This question is similar to the one "randomly return a number from a incoming stream of infinitely many numbers". We keep a variable x that stores the value we want to return and a count n of total numbers we have seen so far. We set x to the first number we see. When the 2nd number comes in, we keep x the same with probability 1/2 and set x to the 2nd number with probability 1/2. When the third number comes, we set x to the new number with probability 1/3, and keep x unchanged with probability 2/3. When we see nth number, we set x to this number with probability 1/n.

We apply the same algorithm to a binary tree with unknown nodes. Here is my code, tested.

struct Node
{
    int d;
    Node * left;
    Node * right;
};

const Node * getRandomNodeHelper(const Node * root, const Node * result, int & count)
{
    if (!root)
    {
        count--;
        return result;
    }
    if (0 == rand() % count)
        result = root;
    const Node * lresult = getRandomNodeHelper(root->left, result, ++count);
    return getRandomNodeHelper(root->right, lresult, ++count);
}

const Node * getRandomNode(const Node * root)
{
    const Node * r;
    int count = 1;
    return getRandomNodeHelper(root, r, count);
}

- -db May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The nodes should keep the number of children. This way random access can be done in log(n).

- Mugatu April 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you describe it how to do in log(n) time?

- superffeng April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you describe it how to do in log(n) time?

- superffeng April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Let's say that the tree has n nodes, each node is labeled with the number of children + 1 and you want to find k-th node of the inorder traversal.
You start from root which is labeled 'n'. Look at left child's label: if the label is less than k then go left looking for k-th node. Otherwise go right and look for (n-k)th element. Either way you go down one level hence the number of such steps is at most the height of the tree, log(n).

- Mugatu April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

but when return the root node itself in your solution?

- superffeng April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here's some pseudocode:
c - current node
k - the k-th node to find (k-th of inorder traversal), from 1 to n

repeat steps 1..7:

1. if c.left.label = k then return c.left //found it
2. if c.left.label >k then c= c.left //go left
3. else //c.left.label < k
{
4. k = k-c.left.label // we just eliminated c.left.label nodes
5. if k=1 then return c // found it, (the current node is on c.left.label + 1 position)
6. k--;
7. c=c.right //go right
}

- Mugatu April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thank you, another question, how can you make sure the probability to return a node is 1/n in your function

- superffeng April 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

at every node toss a 3 sided coin to select left or right or stop.

- Anonymous April 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not correct. Probability of selecting the root is 1/3, but it should be 1/n, when is the number of nodes. What I suggest is generate a random number between 1 to n (lets say i) and the traverse to tree in inorder until we reach the i-th item. This is an O(n) time algorithm.

- Anonymous April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct treeNode
{
int data;
int count ; // this node childrens count

struct node *left, *right;
};

step1: asume , tree size is n.
spep2: use 0 to n-1 random genrator. random genrator everytime returns one of the value in between 0 to n-1 .

step3: now we know the node index to return, we can return this node in O(logn ) time by using tnode->count field.

e.g

int main()
{
index = NrandomGen() ;

randomNodeGenerator(root, index);
}

struct treeNode * randomNodeGenerator( struct treeNode *root, int nodeIndex)
{

if( (root) || (root->left == NULL && root->right == NULL))
{
	return root;
}
else if ( root->left == NULL )
{
  if(nodeIndex == 0)
  {
	return root;
  }
  else
  {
		nodeIndex = nodeIndex -1; 
		return randomNodeGenerator(root->right, nodeIndex );
  }
}
else
{
	if(nodeIndex == 0)
	{
		return root;
	}
	else if( root->left->count + 1 == index )
	{
		return root;
	}
	else if ( (root->left->count + 1 ) < index )
	{
		nodeIndex = nodeIndex - root->left->count -2 ; 
		return randomNodeGenerator(root->right, nodeIndex );
	}
	else
	{
		return randomNodeGenerator(root->left, nodeIndex );
	}
}

}

Time complexity O(logn );

- siva.sai.2020 April 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good.

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

Not good. You can not use node count as a substitute for a proper node counter - there will be duplicates and gaps. I ran through examples with this logic that did not generate a result.

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

You need to return a random _node_ from a binary tree. What duplicates and gaps?

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

There might be bugs in the code and runtime is incorrect, but the idea is essentially correct.

- Anonymous April 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If you know the total node count (say n), traverse the tree any way you like and in each node, choose it with a 1/n probability. If you run out of nodes without a result, start over.

- Anonymous April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

why assume there is child number count? to construct a number count, still need O(n).

given a root with no knowledge of size or whatever. One traversal is good.

- yongning April 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we generate a random number between 0 to number of nodes in the tree.
Now return the node by doing /preorder, postorder or inorder traversal using the random number.
Further traversal can also be chosen randomly

- DashDash May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about generate a number k between 1 to n, and do a BFS until totally k element has been traversed?

- Anonymous May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is same what I was thinking.

- Andy2000 September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

time O(logn), space O(1)

use numc in Node struct to denote how many children the node has:

struct Node
{
	int data;
	Node* left;
	Node* right;
	int numc;
};

Pseudo code:
Node* func(Node* curr)
{
return curr if its numc is 0
otherwise:
1/(numc+1) possibility return the curr;
//implement this by: int r=random(1, numc+1);
//if(r==numc+1) return curr;
numc/(numc+1) possibility: //else
{
return func(curr->left) if curr->right is NULL;
return func(curr->right) if curr->left is NULL;
otherwise:
left/(left+right) possibility return func(curr->left);
right/(left+right) possibility return func(curr->right);
// left=left subtree size = curr->left->numc+1; right is similar as left
}
}

//implement left/(left+right) possibility by: int r=random(1,left+right);
if(r>=1&&r<=left) //means left/(left+right) possibility.
{ //do something}

- penny June 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a very simple solution:
store the BIN TREE in an array with non existing childs marked as null.
Generate the random number and return the value corresponding to that
node.

- Rohit June 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution is not allowed b/c of extra space.

- Andy2000 September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is applying reservoir sampling during tree traversal

void randomBTreeNode (Node * current, Node * & retVal, int & numNodesSoFar)
{
	if (0 == numNodesSoFar && NULL == current)
	{
		retVal = NULL;
		return;
	}

	srand (time(NULL));
	double r = static_cast<double> (rand ()) / static_cast<double> (RAND_MAX);
	++ numNodesSoFar;
	if (r < 1.0 / numNodesSoFar)
	{
		retVal = current;
	}

	if (NULL != current -> m_left)
	{
		randomBTreeNode (current -> m_left, retVal, numNodesSoFar);
	}
	if (NULL != current -> m_right)
	{
		randomBTreeNode (current -> m_right, retVal, numNodesSoFar);
	}
}

- meanmee December 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When testing the above code replace

srand (time(NULL));
	double r = static_cast<double> (rand ()) / static_cast<double> (RAND_MAX);

with

/* in main */
int randomNums [100];
srand (time(NULL));
for (int i = 0; i < 100; ++i)
{
	randomNums [i] = rand ();
}
/* in randomBTreeNode */
double r = static_cast<double> (randomNums [numNodesSoFar]) / static_cast<double> (RAND_MAX);

to get different random numbers for each step ... otherwise due to the fast cpus these days all random numbers generated will be the same for all steps; alternatively sleep for 5 seconds before generating each random number.

- meanmee December 04, 2012 | 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