Question 1 / 1 (Path Explosion

Directi Interview Question for Software Engineer / Developers

0

of 2 votes

7
Answers
Question 1 / 1 (Path Explosion EASY)
You were given a Binary Tree (not necessarily a Binary Search Tree) to play with, say T. T had some special properties

Each internal node in T had exactly 2 children
Each internal node in T was represented by an uppercase English alphabet (A-Z)
Each leaf node in T was represented by a lowercase English alphabet (a-z)
You were told remember T as long as you could. Hence, you memorised the string formed by traversing T in post-order. You used something similar to the pseudocode below

toPostOrderString (node)
if node is leaf
return node.value
else
T = ""
T = T + toPostOrderString(node.left)
T = T + toPostOrderString(node.right)
T = T + node.value
return T
Now, time has come to use that string again. The Eye has contacted you. Yes, the secret organisation mentioned in "Now you see me" ( don't tell anyone they are real !! )

You remember the string you memorised back then. You must reconstruct the binary tree T. You are also given a string A. All the characters of A are uppercase English alphabets. Let us assume that T has L leaves. Then, there will be exactly L paths from the root to the leaves - 1 unique path to each leaf.

You have to tell The Eye the number of paths out of L, on which, A exists as a sub-sequence. Look at the explanation for the Sample Case 1 for clarity.

You have to implement the method explodePaths in the code. explodePaths is passed the following parameters, respectively

N, the number of nodes in T
S, the string representation of the post-order traversal of T. Of course, the length of S will be equal to N.
K, the length of the string A
A, the string you must find in the paths from the root of T, to the leaves in T.
Note

It is not necessary that T is balanced. But, each internal node always has exactly 2 children. It is possible that both those children are internal nodes also. It is possible that only one of those children is an internal node.
For the given string S, because of the constraint that each internal node has exactly 2 children, you will always be able to determine the tree T, uniquely.
It is not necessary that all characters in T are unique. There may be several nodes with the same value.
In this problem statement, by sub-sequence we mean not necessarily contiguous. This is different from a sub-string.
Do not print the answer in explodePaths. Just return the value. The code-template interviewstreet provides does the input and output itself.
Consider the following tree

A
/ \
t B
/ \
/ \
B A
/ \ / \
x y a b
This tree is given in Sample Case 1 as

N = 9
S = "txyBabABA"
K = 2
A = "AA"
Now, there are 5 leaf nodes, and hence, 5 paths from the root to leaves - 1 for each leaf.

- A-t
- A-B-B-x
- A-B-B-y
- A-B-A-a
- A-B-A-b
Out of these 5 paths, you have to find the number of paths, on which "AA" exists as a sub-sequence. Of course, there are only 2 such paths

- A-B-A-a
- A-B-A-b
Hence the expected answer is 2.

In the same T above

The answer for A = "BB", is 2
The answer for A = "BA", is 2
The answer for A = "AB", is 4
The answer for K = 1 and A = "A", is 5
The answer for K = 1 and A = "B", is 4
The Sample Case 2 has a little more complicated T. The string S in Sample Case 2 is yeBgeuCBxAB.

Constraints

N ≤ 10000
K ≤ 100
The expected time complexity of the algorithm is O(N).
- MJRocks October 04, 2013 in India | Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Trees and Graphs

Email me when people comment.

An error occurred in subscribing you.

Country: India
Interview Type: Written Test

Email me when people comment.

An error occurred in subscribing you.

Comment hidden because of low score. Click to expand.

of 0 vote

#include <iostream>
#include <vector>
#include <string.h>
#include <cstring>
#include <stack>
#include <algorithm>

/*input
txyBabABA
AA
*/


using namespace std;
vector<string> pa;

typedef struct t
{
    char data;
    struct t *left;
    struct t *right;
} tree;

tree* make_node(char data)
{
    tree *t = new tree;
    t->data = data;
    t->left = NULL;
    t->right = NULL;
    return t;
}
bool check_leaf(char c)
{
    if(c>=65&&c<97)
        return false;
    else if(c>=97&&c<122)
        return true;
}

tree* build_tree(string A,int *i)
{
    tree *t = make_node(A[*i]);
    if(i<0)
        return NULL;
	//if leaf then return the node no further building of tree.
    if(check_leaf(A[*i]))
        return t;
    *i = *i-1;
    //populate right subtree
    t->right = build_tree(A,i);
    *i = *i-1;
    //populate left subtree
    t->left = build_tree(A,i);
    return t;
}
void c_path(tree *t,char *path,int *i)
{
    if(t==NULL)
        return;
    if(check_leaf(t->data))
    {
        path[*i+1] = t->data;
        path[*i+2] = '\0';
        pa.push_back(path);
        return;
    }
    else{
        *i=*i+1;
        path[*i] = t->data;
        c_path(t->left,path,i);
        c_path(t->right,path,i);
        *i=*i-1;
        return;
    }
}

int sub_search(string a,string b)
{
    int i=0,j=0;
    while(i<a.size())
    {
        while(a[i]!=b[j]&&i<a.size())
            i++;
        if(i<a.size()&&j<b.size())
        {
            i++;
            j++;
        }
        else if(i>=a.size())
            return 0;
        if(j>=b.size())
            return 1;
    }
}






void print(tree *t)
{
    if(t==NULL)
        return;
    cout<<t->data<<" ";
    print(t->left);
    print(t->right);
}

int main()
{
    string post_order,po,a;
    cin>>post_order;
    cin>>a;
    int i= post_order.size()-1;
    tree *t = build_tree(post_order,&i);
    char *p= new char[10];
    i=-1;
    c_path(t,p,&i);
    int j = pa.size()-1;
    i=0;
    int cnt=0;

    while(j>=0){
        po = pa[j--];
        //cout<<po<<endl;
        cnt+=sub_search(po,a);
    }
    cout<<cnt;
    return 0;
}

- arpitbaheti7 October 12, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

#include "stdafx.h"
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int check(string path, string A)
{
	if (A.length() > path.length())
		return 0;

	int i,j=0;

	for (i = 0; i < path.length(); i++)
	{
		if (A[j] == path[i])
			j++;

		if (j == A.length())
			return 1;
	}
	return 0;
}
int explode_paths(int N, string S, int K, string A)
{
	int i, j, count = 0, c = 0;
	string path;
	vector<int> child_count;

	for (i = N - 1; i >= 0; i--)
	{
		path.push_back(S[i]);

		if (islower(S[i]))
		{
			cout << path << endl;

			c++;

			if (check(path, A))
				count++;

			path.pop_back();
			child_count.back()++;

		}
		else
			child_count.push_back(0);

		while (!child_count.empty() && child_count.back() == 2)
		{
			path.pop_back();
			child_count.pop_back();
			if (!child_count.empty())
			child_count.back()++;
		}

	}

	return count;
}
int _tmain(int argc, _TCHAR* argv[])
{
	int N, K, res;
	string S, A;
	N = 9;
	S = "txyBabABA";
	K = 2;
	A = "AA";
	cout << "Paths:" << endl << endl;
	res = explode_paths(N, S, K, A);
	cout << endl <<"No of times "<< A <<" occurs: "<< res << endl;
	return res;
}

- shivamsinha91 November 05, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

import java.util.Stack;
class Node
{
Node(char c)
{
this.c=c;
}
char c;
Node left,right;
}

class TreeProb
{
int z=0;
int explodePaths(int n, String s, int k, String a)
{
Node root=createBinary(s,n);
check(root,a);
return z;
}

void check(Node n, String s)
{
if(s.length()==0)
{
if((int)n.c>91)z++;
else
{
if(n.left!=null)check(n.left,s);
if(n.right!=null)check(n.right,s);
}
}
else
{
if(n.c==s.charAt(0))s=s.substring(1);
if(n.left!=null)check(n.left,s);
if(n.right!=null)check(n.right,s);
}
}
Node createBinary(String s, int n)
{
Stack<Node> s1 = new Stack<Node>();
Node root=null;
char c;
for(int i=0;i<n;i++)
{
Node n1=null;
if((int)(c=s.charAt(i))>91)
s1.push(new Node(c));
else
{
n1 = new Node(c);
n1.right=s1.pop();
n1.left=s1.pop();
s1.push(n1);
}
if(i==(n-1))root=n1;
}
return root;
}
}

class Tree
{
public static void main(String args[])
{
TreeProb d = new TreeProb();
System.out.println(d.explodePaths(15,"lgxBdeCAYkftKZX",1,"A"));
}
}

- Anon November 07, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

import java.util.Stack;
class Node
{
	Node(char c)
	{
		this.c=c;
	}
	char c;
	Node left,right;
}

class TreeProb
{
	int z=0;
	int explodePaths(int n, String s, int k, String a)
	{
		Node root=createBinary(s,n);
		check(root,a);
		return z;
	}
	
	void check(Node n, String s)
	{
		if(s.length()==0)
		{
			if((int)n.c>91)z++;
			else
			{
				if(n.left!=null)check(n.left,s);
				if(n.right!=null)check(n.right,s);
			}
		}
		else 
		{
			if(n.c==s.charAt(0))s=s.substring(1);
			if(n.left!=null)check(n.left,s);
			if(n.right!=null)check(n.right,s);
		}
	}
	Node createBinary(String s, int n)
	{
		Stack<Node> s1 = new Stack<Node>();
		Node root=null;
		char c;
		for(int i=0;i<n;i++)
		{
			Node n1=null;
			if((int)(c=s.charAt(i))>91)
				s1.push(new Node(c));
			else
			{
				n1 = new Node(c);
				n1.right=s1.pop();
				n1.left=s1.pop();
				s1.push(n1);
			}
			if(i==(n-1))root=n1;
		}
		return root;
	}
}


class Tree
{
	public static void main(String args[])
	{
		TreeProb d = new TreeProb();
		System.out.println(d.explodePaths(15,"lgxBdeCAYkftKZX",1,"A"));
	}	
}import java.util.Stack;
class Node
{
	Node(char c)
	{
		this.c=c;
	}
	char c;
	Node left,right;
}

class TreeProb
{
	int z=0;
	int explodePaths(int n, String s, int k, String a)
	{
		Node root=createBinary(s,n);
		check(root,a);
		return z;
	}
	
	void check(Node n, String s)
	{
		if(s.length()==0)
		{
			if((int)n.c>91)z++;
			else
			{
				if(n.left!=null)check(n.left,s);
				if(n.right!=null)check(n.right,s);
			}
		}
		else 
		{
			if(n.c==s.charAt(0))s=s.substring(1);
			if(n.left!=null)check(n.left,s);
			if(n.right!=null)check(n.right,s);
		}
	}
	Node createBinary(String s, int n)
	{
		Stack<Node> s1 = new Stack<Node>();
		Node root=null;
		char c;
		for(int i=0;i<n;i++)
		{
			Node n1=null;
			if((int)(c=s.charAt(i))>91)
				s1.push(new Node(c));
			else
			{
				n1 = new Node(c);
				n1.right=s1.pop();
				n1.left=s1.pop();
				s1.push(n1);
			}
			if(i==(n-1))root=n1;
		}
		return root;
	}
}


class Tree
{
	public static void main(String args[])
	{
		TreeProb d = new TreeProb();
		System.out.println(d.explodePaths(15,"lgxBdeCAYkftKZX",1,"A"));
	}	
}

- Anonymous November 07, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

import java.util.Stack;
class Node
{
	Node(char c)
	{
		this.c=c;
	}
	char c;
	Node left,right;
}

class TreeProb
{
	int z=0;
	int explodePaths(int n, String s, int k, String a)
	{
		Node root=createBinary(s,n);
		check(root,a);
		return z;
	}
	
	void check(Node n, String s)
	{
		if(s.length()==0)
		{
			if((int)n.c>;91)z++;
			else
			{
				if(n.left!=null)check(n.left,s);
				if(n.right!=null)check(n.right,s);
			}
		}
		else 
		{
			if(n.c==s.charAt(0))s=s.substring(1);
			if(n.left!=null)check(n.left,s);
			if(n.right!=null)check(n.right,s);
		}
	}
	Node createBinary(String s, int n)
	{
		Stack<Node> s1 = new Stack<Node>();
		Node root=null;
		char c;
		for(int i=0;i<n;i++)
		{
			Node n1=null;
			if((int)(c=s.charAt(i))>;91)
				s1.push(new Node(c));
			else
			{
				n1 = new Node(c);
				n1.right=s1.pop();
				n1.left=s1.pop();
				s1.push(n1);
			}
			if(i==(n-1))root=n1;
		}
		return root;
	}
}


class Tree
{
	public static void main(String args[])
	{
		TreeProb d = new TreeProb();
		System.out.println(d.explodePaths(15,"lgxBdeCAYkftKZX",1,"A"));
	}	
}

- Kirit November 07, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

#include<iostream>
using namespace std;

struct node
{
    char val;
    node *lc;
    node *rc;
}*root;

void setLeft(node *a,char c)
{
    node *temp=new node();
    temp->val=c;
    temp->lc=NULL;
    temp->rc=NULL;
    a->lc=temp;
}

void setRight(node *a,char c)
{
    node *temp=new node();
    temp->val=c;
    temp->lc=NULL;
    temp->rc=NULL;
    a->rc=temp;
}

void buildTree(node *root,string s,int& len)
{
    if(root->val>=65&&root->val<=90)
    {
        len--;
        setRight(root,s[len]);
        buildTree(root->rc,s,len);
        len--;
        setLeft(root,s[len]);
        buildTree(root->lc,s,len);
    }
}

void checkLeaf(node *a,int &count)
{
    if(a->val>=97&&a->val<=122)
    {
        count++;
        return;
    }
    checkLeaf(a->lc,count);
    checkLeaf(a->rc,count);
}

void explorePath(node *root,string a,int pos,int &count,int k)
{
    if(root==NULL)
    return;

    if(pos==k-1)
    {
        if(root->val!=a[pos])
        {
            explorePath(root->lc,a,pos,count,k);
            explorePath(root->rc,a,pos,count,k);
        }
        if(root->val==a[pos]&&(root->val>=97&&root->val<=122))
        {
            count++;
            return;
        }

        else if(root->val==a[pos]&&(root->val>=65&&root->val<=90))
        {
            checkLeaf(root->lc,count);
            checkLeaf(root->rc,count);
            return;
        }
    }

    else
    {if(root->val==a[pos])
    pos++;
    explorePath(root->lc,a,pos,count,k);
    explorePath(root->rc,a,pos,count,k);
    }
}

int main()
{
    int n,k;
    string s,a;
    cin>>n>>s>>k>>a;
    n--;
    root=new node();
    root->val=s[n];
    root->lc=root->rc=NULL;
    buildTree(root,s,n);
    int count=0;
    explorePath(root,a,0,count,k);
    cout<<count;
    return 0;
}

- tanu.psaxena.bce10@itbhu.ac.in November 03, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

CareerCup

Directi Interview Question for Software Engineer / Developers

Books

Videos

Resume Review

Mock Interviews