Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

Well ordering principle suggests that the set of binary trees can actually be ordered, axiomatically. It is well known that the number of possible binary trees given node n, is
n'th Catalan Number : [ en.wikipedia.org/wiki/Catalan_number ].
C[n] is the number of rooted binary trees with n internal nodes (n + 1 leaves or external nodes).

Thus, the problem is about enumerating these configurations given *n* and then picking
one configuration at random.

Now, that means, *with equal probability* implies, a Random binary tree having n nodes,
therein generated must have a probability of 1/C[n] where C[n] is the n'th Catalan number.

In this formulation it is obvious that the problem is beyond trivial.

Unless, they are asking a random walk problem with equal probability
of having a { left node, right node, or both nodes. }, then it is very trivial.

The first problem is here :
[ tristan-interview.blogspot.in/2012/02/enumerate-all-possible-binary-trees.html ]
With the binary counting method, the problem is solved.

Again, the key issue is about the *equal probability*. They are certainly non trivial for non linear
expressions like this.

- NoOne August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

can you provide more details about this question? Like what does the equal probability means?

- tiandiao123 August 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I'd assume he means generate a sequence of random values (edit: uniformely distributed) and put them into a binary search tree. Find an efficient way to achieve this result. Neat question.

- Chris August 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Generate a random correct brace sequence, then convert it into binary tree. O(N) time, O(N) space.
Random correct brace sequence can be generated by shuffling n '(' symbols and n ')' symbols and then prepending '(' and then rotate it circularly in such a way that every prefix contains strictly more '(' than ')'
e.g.

))((
prepend (
())((
rotate
((())
remove extra brace
(())

There are C(2n,n) ways to shuffle braces and n+1 choices of the circular shift, which gives us n-th Catalan number (a sanity check)

@ChrisK: (sorry, can't comment)
Inserting random numbers into BST won't give uniform distribution. there are 6 permutations 123 132 213 231 312 321, and you see that 231 and 231 give you the same binary tree, but there is no other sequence that gives you same tree as 123

- emb August 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.home.careercup;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class RandomBinaryTree {
    public static void main(String[] args) {
        RandomBinaryTree w = new RandomBinaryTree();
        Node tree = w.randomBinaryTree(9);
        w.visitInOrder(tree);
        /*
        7[int] 5[leaf] 15[int] 8[leaf] 16[int] 3[leaf] 6[int] 
        1[leaf] 4[int] 0[root] 17[int] 13[leaf] 18[int] 11[leaf] 
        14[int] 9[leaf] 12[int] 2[leaf] 10[int] 
         */

    }

    /** crude in-order visit impl */
    private void visitInOrder(Node tree) {
        if (tree == null) return;
        visitInOrder(tree.left);
        StringBuilder s=new StringBuilder();
        if (tree.d==0){
            s.append(0+"[root] ");
        }else if ( tree.left== null && tree.right== null){
            s.append(tree.d+"[int] ");
        }else {
            s.append(tree.d+"[leaf] ");
        }
        System.out.print (s.toString());
        visitInOrder(tree.right);
    }

    /**
     * Generate binary tree with n internal nodes and n+1 leaf nodes
     * <p>
     * We start with a minimal tree with a root and two leaves.
     * Next we choose one of the leaves and then add two branches to it
     * We continue choosing leaves (randomly) and adding branches till
     * we have n+1 leaf nodes
     *
     * @param n
     * @return
     */
    Node randomBinaryTree(int n) {
        List<Node> nodeList = new ArrayList<>();
        int nodeIndex = 0;
        Node root = Node.of(nodeIndex++);
        Node firstLeaf = Node.of(nodeIndex++);
        Node secondLeaf = Node.of(nodeIndex++);
        root.left = firstLeaf;
        root.right = secondLeaf;
        nodeList.add(firstLeaf);
        nodeList.add(secondLeaf);
        Random random = new Random();

        while (nodeList.size() < n + 1) {
            int nextInternalNodeIndex = random.nextInt(nodeList.size());
            Node internalNode = nodeList.get(nextInternalNodeIndex);
            internalNode.left = Node.of(nodeIndex++);
            internalNode.right = Node.of(nodeIndex++);
            nodeList.remove(nextInternalNodeIndex);
            nodeList.add(internalNode.left);
            nodeList.add(internalNode.right);
        }
        return root;

    }

    static class Node {
        int d;
        Node left, right;

        static Node of(int v) {
            return new Node(v);
        }

        Node(int v) {
            this.d = v;
        }
    }
}

- Makarand August 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You are right (@emb, @NoOne) the question is clearly pointing to selecting a binary tree from all possible binary trees (given a number of nodes) and not generating a random sequence to generate a BST from.

I had to read how to do it in linear time and I think it's definitely very hard to do it in an interview. Especially if you need to prove the uniformity.

How ever there are two ideas that could help:
1) Makarand's code generates a *full* random binary tree. That is easier.
2) From a valid string with parenthesis you can generate a binary tree (grammatical method)

following up with 2 would lead to the following challanges:
1) if we generate a string of length 2*n with open and closing parenthesis, what is the probability to produce an open or closed parenthesis at position i. While this in the end is a relatively easy formula r*(k+r+2)/2*k(r + 1), where r is the number of not closed open parentesis and k the number of symbols yet to pick (k=2*n-i), I wouldn't be able to draw that formula in an interview.
What I could do is, enumerate all possible strings and pick one. This is exponential of course. One can actually enumerate recursively and pick while enumerating, so at the end of the process one has a valid random string of parenthesis:

n = 0
random_parent_string = ''
def rec(prefix, r, k): 
	if k>r: rec(prefix + "(", r+1, k-1) 
        if k>0 and r>0: rec(prefix + ")", r-1, k-1) 
	if k == 0:
		n += 1
		if(rand(n) == n-1): #assume rand generates uniform [0, n)
			random_parent_string = prefix; # 1st with P(1), 2nd with P(1/2), 3rd with P(1/3) ...

then generate the binary tree from this random parenthesis string.

- Chris August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming we need to build a tree that contains N nodes (N can also be random) and has a random structure, and random values.

Node *Build(int size)
{
	Node *n = NULL;
	if (size > 0) {
		n = new Node(rand());
		--size;
		int left_size = rand() % (size + 1);
		n->left_ = Build(left_size);
		n->right_ = Build(size - left_size);
	}
	return n;
}

- Alex August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex: it's not uniform, assume n = 3: P(1/3) for left size to be 0,1,2 in first recursion

if it is 1, we are done with the three

O
  /  \
O    O

but with P(1/3) left size = 0 you still have two options:

O          O 
  \            \
   O          O  
     \          /
      O     O

so 4 of the 5 possibile trees have P(1/2*1/3) and one has P(1/3)

that is not uniform. but I thought of this one, too, it's tempting...

- Chris August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK. Yes, it may be not uniform in the sense of what the interviewer was looking for (more details in description of the task would be helpful). My idea is like at the start I have N nodes, and among them, I choose the parent of the tree uniformly. I.e. any node out of the N nodes can become the parent node with equal probability. Then, I do the same thing for the left and right subtrees.

- Alex August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex: agreed a better description would be useful.Anyway I started reading into the topic a bit and figured out it's a well known topic.
I read this survey, sis.uta.fi/cs/reports/pdf/A-1998-3.pdf
or found knuths: cs.utsa.edu/~wagner/knuth/fasc4a.pdf enlighting paper ;-)

- Chris August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK. Thank you! You are right. I did stats on my solution, and distribution of tree structures is not uniform. The reason is that depending on at which place we choose the parent node, depends number of unique subtrees on the left and on the right.

- Alex August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can shuffle the input array randomly then insert It's item one by one to the binary search tree.
we get o(n) for shuffling + o(n lgn) for making the BST.

- hamid.moghadam85 September 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To have solution with equal probability we have to enumerate all possible trees and pick one randomly.
Here we create all possible Dyck words, pick one randomly and convert it to binary tree.

Generating tree by randomly picked permutation or by randomly picking leaves from list and create its children do not give solution with equal probability. E.g for n = 3 perfect binary tree has 1/3 probability whereas other five have 1/6 probability.

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.stream.IntStream;

public class RandomBinaryTree {

    private static final String ZERO_STRING = "0";
    private static final String ONE_STRING = "1";
    private static final char ZERO_CHAR = '0';

    private List<String> dyckWords;

    public Node generate(int n) {
        if (n > 0) {
            dyckWords = new ArrayList<>();
            createDyckWords(1, 0, n, ZERO_STRING);
            return convertDyckWordToTree(pickWord());
        }
        return null;
    }

    private void createDyckWords(int i, int j, int n, String word) {
        if (i == n) completeAndStoreWord(j, n, word);
        else if (i == j) {
            createDyckWords(i + 1, j, n, word + ZERO_STRING);
        } else {
            createDyckWords(i + 1, j, n, word + ZERO_STRING);
            createDyckWords(i, j + 1, n, word + ONE_STRING);
        }
    }

    private void completeAndStoreWord(int j, int n, String word) {
        StringBuilder sb = new StringBuilder();
        IntStream.range(0, n - j).forEach(i -> sb.append(ONE_STRING));
        dyckWords.add(word + sb.toString());
    }

    private String pickWord() {
        Random r = new Random();
        return dyckWords.get(r.nextInt(dyckWords.size()));
    }

    private Node convertDyckWordToTree(String word) {
        Node tree = new Node();
        Node node = tree;
        int counter = 0;
        for (int i = 0; i < word.length(); i++) {
            Node newNode = new Node();
            if (word.charAt(i) == ZERO_CHAR) {
                node.left = newNode;
            } else {
                node = node.parent;
                while (node.right != null)
                    node = node.parent;
                node.value = counter++;
                node.right = newNode;
            }
            newNode.parent = node;
            node = newNode;
        }
        return tree;
    }

    static class Node {
        Integer value;
        Node parent;
        Node left;
        Node right;

        Node() {
        }
    }

    public static void main(String[] args) {
        new RandomBinaryTree().generate(3);
    }

}

- Stane September 12, 2017 | Flag Reply


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