Google Interview Question Software Engineers
Country: United States
Interview Type: In-Person
@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 ;-)
After reading papers referenced by Chris (thanks, Chris!), I've come up with the following solution:
struct Node
{
Node* left = nullptr;
Node* right = nullptr;
};
template<class G>
Node* random_binary_tree(std::size_t n, G&& gen)
{
Node* root;
auto curr = &root;
std::stack<Node*> st;
std::size_t m = n;
while (n > 0)
{
std::uniform_int_distribution<std::size_t> distr(0, (n + m) * (n - m + 1) - 1);
if (distr(gen) < (n + 1) * (n - m))
{
const auto node = st.top();
st.pop();
curr = &(node->right);
--n;
}
else
{
const auto node = new Node;
st.push(node);
*curr = node;
curr = &(node->left);
--m;
}
}
return root;
}
std::string tree_to_braces(const Node* root)
{
if (root)
return '(' + tree_to_braces(root->left) + ')' + tree_to_braces(root->right);
else
return {};
}
int main()
{
std::mt19937 gen;
std::map<std::string, std::size_t> counts;
for (int i = 0; i < 100'000; ++i)
{
auto tree = random_binary_tree(4, gen);
auto str = tree_to_braces(tree);
++counts[str];
}
for (auto c : counts)
std::cout << c.first << " -> " << c.second << std::endl;
}
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
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;
}
}
}
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.
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: 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...
@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.
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);
}
}
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
- NoOne August 31, 2017n'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.