## Directi Interview Question for Senior Software Development Engineers

• 2

Country: India

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

Though several insertion sequences can result into the same BST, a simple fact that can be concluded by observing is that:
as long as for any subBST the root is inserted before its subtrees, we can build the same BST after changing the insertion sequence.
It's like in the topological graph A->B and A->C, all we need to make sure is that A is done before B and C, while the order of B and C does not matter.

Now let's take the insertion sequence in the example of the problem,
the tree structure is like this:

``````4
3      6
1      5 7
2``````

to build the same BST, all we need to maintain after changing the insertion sequence is such relative order:
4->3 and 4->6
3->1
1->2
6->5 and 5->7

To get all the insertion sequences that can result into given BST, we can
(1)recursively get all the insertion sequences of the subtrees
(2)merge subtrees' insertion sequence into one while keeping each sequence's relative order
(3)push the root's value into the merged sequence's front

code in C++:

``````#include <iostream>
#include <list>
using namespace std;

struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;

TreeNode(int v):val(v), left(NULL), right(NULL){}
};
class BSTBuilder{
public:
//insert value into BST, return false if already in the BST
bool insertBST(TreeNode*& root, int value){
if(root == NULL){
root = new TreeNode(value);
return true;
}

TreeNode* p = root;
while(true){
if(p->val == value) return false;
if(p->val > value){
if(p->left == NULL){
p->left = new TreeNode(value);
break;
}
else p = p->left;
}
else{
if(p->right == NULL){
p->right = new TreeNode(value);
break;
}
else p = p->right;
}
}
return true;
}
//build a BST taking arr[] as the insertion sequence
TreeNode* buildBST(int arr[], int n){
TreeNode* root = NULL;
for(int i = 0; i < n; ++i) insertBST(root, arr[i]);
return root;
}
//free memory allocated for BST
void deleteBST(TreeNode*& root){
if(root == NULL) return;

deleteBST(root->left);
deleteBST(root->right);
delete root;
root = NULL;
}
};
class BSTRestorer{
private:
typedef list<int> List;
typedef list<List> ListList;
typedef List::iterator Iter;
private:
//insert value at front of each list in ll
void insertAtFront(ListList& ll, int value){
for(ListList::iterator iter = ll.begin(); iter != ll.end(); ++iter){
iter->push_front(value);
}
}
//insert r's each item into l, while keeping the relative order
//and insert the merged list into all
void insertWithRelativeOrder(ListList& all, List& l, Iter firstAvailable, List& r, Iter cur){
if(cur == r.end()){
all.push_back(l);
return;
}

Iter tmp;
int val = *cur++;
for(; firstAvailable != l.end(); ++firstAvailable){
tmp = l.insert(firstAvailable, val);
insertWithRelativeOrder(all, l, firstAvailable, r, cur);
l.erase(tmp);
}
tmp = l.insert(firstAvailable, val);
insertWithRelativeOrder(all, l, firstAvailable, r, cur);
l.erase(tmp);
}
//restore all the insertion sequences that result into the BST
void restore(TreeNode* root, ListList& insertionSequence){
if(root->left == NULL && root->right == NULL){
insertionSequence.push_back(List());
insertionSequence.back().push_back(root->val);
return;
}
//get all insertion sequence of subtrees
if(root->left != NULL && root->right != NULL){
//get left subtree's and right subtree's insertion sequence
ListList leftInsertionSequence, rightInsertionSequence;
restore(root->left, leftInsertionSequence);
restore(root->right, rightInsertionSequence);
//combine insertion sequence of subtrees
for(ListList::iterator iter = leftInsertionSequence.begin();
iter != leftInsertionSequence.end();
++iter){
for(ListList::iterator jter = rightInsertionSequence.begin();
jter != rightInsertionSequence.end();
++jter){
insertWithRelativeOrder(insertionSequence,
*iter,
iter->begin(),
*jter,
jter->begin()
);
}
}
}
else restore(root->left != NULL ? root->left : root->right, insertionSequence);
//root->val is the first item of a tree insertion sequence
insertAtFront(insertionSequence, root->val);
}
public:
//interface to outside
void restoreBST(ListList& insertionSequence, TreeNode* root){
insertionSequence.clear();
if(root != NULL) restore(root, insertionSequence);
}
};

int main()
{
BSTBuilder builder;
BSTRestorer restorer;
list<list<int> > insertionSequence;
int arr[] = {4, 3, 1, 2, 6, 5, 7}, n = sizeof(arr) / sizeof(arr);

//build BST according to the insertion sequence
TreeNode* root = builder.buildBST(arr, n);
//generate all insertion sequences of the BST
restorer.restoreBST(insertionSequence, root);
//print those insertion sequences
for(list<list<int> >::iterator iter = insertionSequence.begin();
iter != insertionSequence.end();
++iter){
for(list<int>::iterator i = iter->begin(); i != iter->end(); ++i) cout << *i << ' ';
cout << '\n';
}
//free memory
builder.deleteBST(root);

return 0;
}``````

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

public class PrintCombinationOfTree {

public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode node1 = new TreeNode(4);
TreeNode node2 = new TreeNode(3);
TreeNode node3 = new TreeNode(6);
TreeNode node4 = new TreeNode(1);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(7);
TreeNode node7 = new TreeNode(2);

node1.left = node2;
node1.right = node3;
node2.left = node4;
node4.right = node7;
node3.left = node5;
node3.right = node6;

PrintCombinationOfTree p = new PrintCombinationOfTree();
List<List<Integer>> result = p.getTreeList(node1);
for (List l: result) {
System.out.println(l);
}
}

private List<List<Integer>> getTreeList(TreeNode node) {
if (node.left == null && node.right == null) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
return result;
}

List<List<Integer>> left = null;
List<List<Integer>> right = null;
if (node.left !=null) {
left = getTreeList(node.left);
}

if (node.right !=null) {
right = getTreeList(node.right);
}

if (left != null && right != null) {
return getList(node, left, right);
}

return getList(node, left!=null?left:right);
}
private List<List<Integer>> getList(TreeNode root, List<List<Integer>> left, List<List<Integer>> right) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
for (List<Integer> l: left) {
for (List<Integer> r : right) {
List<Integer> temp = new ArrayList<Integer>();

}
}

for (List<Integer> r: right) {
for (List<Integer> l : left) {
List<Integer> temp = new ArrayList<Integer>();

}
}

return result;
}

private List<List<Integer>> getList(TreeNode root, List<List<Integer>> list) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
for (List<Integer> l: list) {
List<Integer> temp = new ArrayList<Integer>();

}
return result;
}

}

class TreeNode {
int data;
TreeNode left;
TreeNode right;

public TreeNode(int data) {
this.data = data;
}
}

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

To get the same BST, a number should be listed only after its parent.
This is identical to traversing through the BST. So the permutations can be arrived at by performing all possible traversals of the tree.

``````//Traverse the tree in all possible permutations
//Take a node from the boundary and
//  append it to the traversal.
//  Remove the node from the boundary and
//  add its children. Recurse with the new boundary.
//Iterate with all nodes in the bounbdary,
//  concatenate and return the results
//Initially, the traversal will be empty,
//  and the boundary will be the root
tp.traverseall = function (boundary, traversal) {
var results = [], i, permutation, node;

traversal = traversal || [];

if(boundary.length === 0) {
//Entire tree has been traversed
//Return the input traversal itself as the only result
return [traversal]
}

for (i=0; i< boundary.length; i++) {
permutation = {
boundary:null,
traversal:null,
results:null
};

//Remove the ith node
permutation.boundary = boundary.slice();
permutation.boundary.splice(i, 1);

node = boundary[i];

if(node.left) {
permutation.boundary.push(node.left);
}
if(node.right) {
permutation.boundary.push(node.right);
}

//Fork a new traversal from the input traversal and
//append the current node to it.
permutation.traversal = traversal.slice();
permutation.traversal.push(node.data)

permutation.results = tp.traverseall(permutation.boundary, permutation.traversal);

//Concatenate results from all iterations
results = results.concat(permutation.results);
}

return results;
}``````

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

``````#include<stdio.h>
#include<iostream>
#include<vector>
#include<map>
#include<list>
#include<conio.h>
using namespace std;
class node
{
public:
int x;
node *left , *right ;
};
node* create_tree(vector<int> v)
{
node* root = new node ;
root->x = v ;
root->left = root->right = NULL ;
for(int i=1;i<v.size();i++)
{
node *temp = new node ;
temp->x = v[i] ;
temp->left = temp->right = NULL ;
node *temp2 , *temp1 = root ;
while(temp1 != NULL)
{
temp2 = temp1 ;
if(temp->x < temp1->x)
temp1 = temp1->left ;
else
temp1 = temp1->right ;
}
if(temp->x < temp2->x)
temp2->left = temp ;
else
temp2->right = temp ;
}
return root ;
}
void inorder(node *temp)
{
if(temp != NULL)
{
inorder(temp->left) ;
cout<<temp->x<<" " ;
inorder(temp->right) ;
}
}
map<int,vector<int> > edge_store(node* temp,map<int,vector<int> > v)
{
if(temp!= NULL)
{
if(temp->left != NULL)
v[temp->x].push_back(temp->left->x) ;
if(temp->right != NULL)
v[temp->x].push_back(temp->right->x) ;
v = edge_store(temp->left,v) ;
v = edge_store(temp->right,v) ;
}
return v ;
}
void print_edge(vector<int> incl,map<int,vector<int> > ve,list<int> l)
{
if(l.empty())
{
for(int i=0;i<incl.size();i++)
cout<<incl[i]<<" " ;
cout<<endl ;
}
list<int>::iterator it = l.begin();
while(it != l.end())
{
vector<int> temp(incl) ;
list<int> templist(l) ;
for(int i=0;i<ve[*it].size();i++)
templist.push_back(ve[*it][i]) ;
temp.push_back(*it) ;
list<int>::iterator lit ;
for(lit = templist.begin();lit != templist.end();lit++)
{
if(*it == *lit)
break ;
}
templist.erase(lit) ;
it++ ;
print_edge(temp,ve,templist) ;
}
}
int main()
{
int n;
cin>>n;
vector<int> v(n) ;
for(int i=0;i<n;i++)
cin>>v[i] ;
node *root = create_tree(v) ;
map<int,vector<int> > ve ;
ve = edge_store(root,ve) ;
vector<int> incl;
list<int> l;
list<int>::iterator it ;
for(int i=0;i<ve[v].size();i++)
l.push_back(ve[v][i]) ;
incl.push_back(v) ;
print_edge(incl,ve,l) ;
return 0;
}``````

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

Can't I do level order traversal and for each level resursively try all permutations resulting in a new sequence each time.

This solution is base don teh fact that for every level its next child insertion order does not matter

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

``````from __future__ import print_function

import itertools
import re
import sys

def iter_binary_tree_permutations(numbers):
"""Iterates all permutations of a given sequence such that the permutation
makes the same binary search tree as the original sequence.

"""
if not numbers:
yield []
return
root = numbers
left = []
right = []
for n in itertools.islice(numbers, 1, None):
if n < root:
left.append(n)
else:
right.append(n)
for lp, rp in itertools.product(iter_binary_tree_permutations(left),
iter_binary_tree_permutations(right)):
for p in iter_splices(lp, rp):
yield [root] + p

def iter_splices(a, b):
"""Iterates all splices for two given sequences.

>>> for splice in iter_splices([1, 2], [3, 4]): print(splice)
[1, 2, 3, 4]
[3, 1, 2, 4]
[3, 4, 1, 2]
[1, 3, 2, 4]
[1, 3, 4, 2]
[3, 1, 4, 2]

"""
if not a:
yield b
return
indices = range(len(b) + 1)
for partitions in iter_partitions(a):
k = len(partitions)
for pivots in itertools.combinations(indices, k):
ret = b[:pivots]
for i in xrange(k - 1):
ret.extend(partitions[i])
ret.extend(b[pivots[i]:pivots[i + 1]])
ret.extend(partitions[k - 1])
ret.extend(b[pivots[k - 1]:])
yield ret

def iter_partitions(a):
"""Iterates all partitions for a given sequence.

>>> for partitions in iter_partitions([1, 2, 3]): print(partitions)
[[1, 2, 3]]
[, [2, 3]]
[[1, 2], ]
[, , ]

"""
yield [a]
indices = range(1, len(a))
for num_pivots in xrange(1, len(a)):
for pivots in itertools.combinations(indices, num_pivots):
ret = [a[:pivots]]
for i in xrange(num_pivots - 1):
ret.append(a[pivots[i]:pivots[i + 1]])
ret.append(a[pivots[num_pivots - 1]:])
yield ret

if __name__ == '__main__':
numbers = [4, 3, 1, 2, 6, 5, 7]
# numbers = [int(n) for n in re.split(r'\s*,\s*', sys.stdin.read().strip())]
for p in iter_binary_tree_permutations(numbers):
print(p)``````

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

No explanation, no algo, Do you really think that everyone want to debug your code and try to understand what you had in mind? Post your idea first its more important then the code.

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

Well, it's a simple, recursive solution.

Suppose that for an integer sequence S, there is a function f that returns a set of sequences f(S) where all sequences in f(S) makes the same binary search tree.

If S has only one element, then f(S) is a set of size 1 and it has S as an element.

If S has more than one element, we can split it into one element r and two sequences A and B, where r is the first element of S, A is such that x < r for all x in A, B is such that x >= r for all x in B. If you make a binary search tree from S, then r would be the root and all elements in A will be descendants of the left child of the root and all elements in B will be descendants of the right child.

Now we can create new sequences which make the same tree by "mixing" elements A and B and inserting r at the front, but preserving the orders in A and B; for example, if A is [1, 2, 3], and B is [4, 5, 6], mixing A and B would produce sequences like [1, 4, 2, 5, 3, 6] and [1, 2, 4, 3, 5, 6].

But note that in the tree of S, A and B each makes a subtree of their own. Therefore we need to mix all combinations of f(A) and f(B).

Here is the summary of the algorithm:

For an integer sequence S, f(S) is a set of sequences which make the same binary tree as S.

If the size of S is 1, f(S) = {S}.

If the size of S is more than 1, split S into r, A, B where r is the first element of S, A is a subsequence of S where x < r for all x in A, B is a subsequence of S where x >= r for all x in B. Then f(S) = {X | X = (r, W)} for all W ∈ g(Y, Z) where Y ∈ f(A), Z ∈ f(B), and g(Y, Z) is a function returning a set of sequences which have Y and Z as subsequences.

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

If it is simple, the explanation could have been shorter ;)
And it could focus more on g(Y,Z) as it seems to be half the code size

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.

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