Directi Interview Question for Senior Software Development Engineers


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[0]);
    
    //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;
}

- uuuouou April 21, 2014 | Flag Reply
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>();
temp.add(node.data);
result.add(temp);
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>();
temp.add(root.data);
temp.addAll(l);
temp.addAll(r);

result.add(temp);
}
}

for (List<Integer> r: right) {
for (List<Integer> l : left) {
List<Integer> temp = new ArrayList<Integer>();
temp.add(root.data);
temp.addAll(r);
temp.addAll(l);

result.add(temp);
}
}

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>();
temp.add(root.data);
temp.addAll(l);

result.add(temp);

}
return result;
}

}

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

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

- Priyanka Dubey April 22, 2014 | Flag Reply
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];
    
    //Add its children
    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)
    
    //Recursse
    permutation.results = tp.traverseall(permutation.boundary, permutation.traversal);
    
    //Concatenate results from all iterations
    results = results.concat(permutation.results);
  }

  return results;
}

- Ankit Sinha June 28, 2014 | Flag Reply
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[0] ;
    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[0]].size();i++)
        l.push_back(ve[v[0]][i]) ;
    incl.push_back(v[0]) ;
    print_edge(incl,ve,l) ;
    return 0;
}

- Shishir April 30, 2014 | Flag Reply
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

- sJyoti April 06, 2016 | Flag Reply
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[0]
    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[0]]
            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]]
    [[1], [2, 3]]
    [[1, 2], [3]]
    [[1], [2], [3]]

    """
    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[0]]]
            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)

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

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.

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

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.

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

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

- Ankit Sinha June 28, 2014 | 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