Flipkart Interview Question Software Engineer / Developers
Hi Tulley,
Running your algo for this case is not working. Check if this is what you meant
1
/ \
2 3
/ \
5 4
/
6
After sorting the array, it will look like this
1 2 3 4 5 6
1 0 1 1 1 1 1
2 0 0 0 0 1 1
3 0 0 0 1 0 0
5 0 0 0 0 1 0
4 0 0 0 0 0 0
6 0 0 0 0 0 0
I = 1
queue = Root
isLeftChild = false
XOR of
0 1 1 1 1 1
0 0 0 0 1 1
will give
0 1 1 1 0 0
Left will be 2
Right will 3 then will be changed to 4
so we have
1
/ \
2 4
This is not same as what we started with and as we are not modifying the root again root's children are not going to change
You r right. Instead of doing XOR, when we are at colom J then the entries AncestorMatrix[I->N][J] must be checked. If more than 1 exist in the entries AncestorMatrix[I->N][J] then the AncestorMatrix[I][J] wont be considers as child.
Same is corrected now. Please check again if u find any more bug.
Dear Tulley,
Running the modified algo on the same example with little change
1
/ \
2 3
/
4
/
5
After sorting
1 2 3 4 5
1 0 1 1 1 1
2 0 0 0 1 1
4 0 0 0 0 1 <- not 3 its 4
3 0 0 0 0 0
5 0 0 0 0 0
Notice that I have removed the child on 3 from the previous example I posted, just to make it simple.
I am assuming that you meant AncestorMatrix[K][J]==1 instead of AncestorMatrix[I][J]==1 inside the K loop
I = 1 -> node 1 (0 1 1 1 1)
0 1 1 1 1
R = 1
out of j = 2 3 4 5 which have A[i][j] = 1 only 2 & 3 will escape the continue...so we have
1
/ \
2 3 queue = 2 3
I = 2 -> node 2 (0 0 0 1 1)
queue = 2 3
R = 2
out of j = 4 5 which have A[i][j] = 1 only 4 will escape the continue...so we havee
1
/ \
2 3 queue = 3 4
/
4
I = 3 -> "node 4" (0 0 0 0 1)
queue = 3 4
R = 3
only j = 5 has A[i][j] = 1 and it will escape the continue...so we have
1
/ \
2 3 queue = 4 5
/ \
4 5
1) we are not going to modify 3 after this so we will end up with this tree...which is not the same as the original.
2)you introduced another 'for' loop, so in the worst case your algo will run O(n^3). I have not verified this fact but i think the worst case will be when all nodes have only left child or only right child
-> What you can try is instead of building the tree top to bottom in your 2 loop algo (the one before this one), you can try bottom up.
-> Or you might want to consider sorting the array column wise based on the number of 1s and arranging the rows to match the column order. then see the problem from the column perspective instead of row..
Generally it is desirable to have the input array unmodified. So when you sort you are not actually sorting the array, instead have an auxillary array that will hold the indices in sorted.
yes the time complexity is O(N^3). but i think Tulley's algo is correct. The row corresponding to 3 is not containing any "1" and also when I=3 then AncestorMatrix[4->5][j] contains 1 so loop will continue, then y are u adding any child of 3.
hey anonymous,
The row corresponding to 3 is not containing any "1" true....but because we sorted the matrix, the matrix is going to look like this.
1 2 3 4 5
1 0 1 1 1 1
2 0 0 0 1 1
4 0 0 0 0 1 <- not node 3 its node 4
3 0 0 0 0 0
5 0 0 0 0 0
So when "R" is node 3(which we got from the queue)..it is not guaranteed to inspect the row corresponding to 3, as in this case where we are inspecting node 4's row even though "R" is 3 and I = 3
After I = 2
1
/ \
2 3 queue = 3 4
/
4
And for your second statement. K loop will run from "K = I + 1 to max-row - 1" that is "K = 3+1 to 5-1" or "K = 4 to 4". So for J = 1,2,3,4,5 we are checking if A[4][J] is 1, if it is then we skip. From the above matrix we can see that there are no 1s anywhere in the row 4 (that is node 3's row). So R->left = newNode() is executed and I am assuming Tulley is setting the value somewhere there.
/*A binary tree is represented in a array as the ancestor array, build the binary tree from this array.
eg
1
|
2 3
|
4 5
The array would be
1 2 3 4 5
1 x 1 1 1 1
2 0 x 0 1 1
3 0 0 x 0 0
4 0 0 0 x 0
5 0 0 0 0 x
where if i isAncestor of j, a[i][j] would be set to 1
*/
private static int [] columnCounts = null;
private static int [] rowCounts = null;
public static void createTreeFromAncestorMatrix(int [][] mat){
initializeColumnRowCounts(mat, columnsCount, rowCounts);
//Steps
// 1 : Find out the root first. Root will be the one who is ancestor of all the elements hence the row with all the onces except 1 will be root.
// This will O(n2)
int rootIndex = findRootIndex(mat);
// 2 : Once root is found, create the tree recursively.
Node rootNode = getNode(mat, rootIndex);
// 4 : Whatever is left is a parent matrix. Create a tree out of it by starting from the root and create nodes. Do it recursively.
}
private initializeColumnRowCounts(int [][]mat, int [] columnsCount, int[] rowCount){
columnCounts = int[max.size()];
rowCounts = int[max.size()];
for(int i = 0; i< mat.size();i++){
for(int j = 0; j< mat.size();j++){
if(mat[i][j] ==1){
rowCounts[i]++;
columnCoutns[j]++;
}
}
}
}
/*For one node this will be O(n)
For all the nodes taken together this will become O(n2)
*/
private static Node getNode(int [][]mat, int ancestoryNodeIndex){
/*Remove indirect children starts*/
for(int j=0;j<mat.size();j++){
if(mat[ancestorNodeIndex][j] == 1 && columnCounts[j] > 1){
mat[ancestorNodeIndex][j] == 0;
columnCounts[j]--;
rowCounts[ancestorNodeIndex]--;
}
}
/*Remove indirect children ends*/
/*Find left node and right node*/
int leftIndex = -1;
int rightIndex = -1;
for(int j=0; j < mat.size();i++){
if(mat[ancestorNodeIndex][j] ==1) {
if(leftIndex == -1 ){
leftIndex = j;
}else{
rightIndex = j;
}
}
}
/*Create LeftNode*/
Node leftChild = null;
if(leftIndex != -1){
leftChild = getNode(mat, leftIndex);
}
/*Create rightNode*/
Node rightChild = null;
if(rightIndex != -1){
leftChild = getNode(mat, rightIndex);
}
return new Node(leftChild, rightChild);
}
private static int findRootIndex(int [][]mat){
for(int i = 0;i < mat.size(); i++){
int count = 0;
for(int j = 0; j<mat.size(); j++){
count+= mat[i][j];
}
if(count == mat.size()-1){
return i;
}
}
}
<pre lang="" line="1" title="CodeMonkey76197" class="run-this">import java.util.*;
/*
Give an ancestor array where a[i][j] = 1 if i is ancestor of j, build the binary tree from the array
A non-recursive algorithm implementation in O(n2)
*/
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
/*
0
/ \
1 2
/
3
/
4
*/
int[][] mtx = {{0,1,1,1,1},{0,0,0,1,1},{0,0,0,0,0},{0,0,0,0,1},{0,0,0,0,0}};
Node root = buildBinaryTreeFromAncestor(mtx);
}
public static Node buildBinaryTreeFromAncestor(int[][] ancsMtx){
//acnCount represents number of ancestors i'th node has.
int[] acnCount = new int[ancsMtx.length];
int rootIdx = -1;
//First count number of 1's for each column. The column having zero 1's is the root node.
//Later the one's count is used below to identify whether a node is immediate child or not. - O(n2)
for(int i=0;i<ancsMtx.length;i++){
int colCount = 0;
for(int j=0;j<ancsMtx.length;j++){
colCount += ancsMtx[j][i];
}
acnCount[i] = colCount;
if(colCount == 0){
rootIdx = i;
}
}
//nodes keep a queue of child nodes which are yet to be processed
Queue<Node> nodes = new LinkedList<Node>();
Node root = new Node(rootIdx);
nodes.offer(root);
//Dummy nodes are added to at the end of processing of each level of nodes
//While dequeueing if dummy node is found, then we simply increment the current level
nodes.offer(new DummyNode());
int curLevel = 1;
//Iterates through the queue till its empty - While loop will run for max of N times and within each loop its N times - so O(n2)
while(!nodes.isEmpty()){
Node curNode = nodes.poll();
//If its a dummy node, then just incrment the level and continue with the next iteration of the loop
if(curNode instanceof DummyNode){
curLevel++;
continue;
}
for(int i=0;i<ancsMtx.length;i++){
//For immediate childs, the curNode.data will be ancestor of i, i.e. the matrix [curNode.data][i] should be one
// and number of ancestors of i'th column node should be equal to current level
boolean isImmediateChild = ancsMtx[curNode.data][i] == 1 && acnCount[i]==curLevel;
if(isImmediateChild){
Node nd = new Node(i);
nodes.offer(nd);
//First add the node to left, if its already occupied, add it as right child
if(curNode.left == null){
curNode.left = nd;
}
else{
curNode.right = nd;
}
}
}
//We are adding dummy node at the end representing end of a level
nodes.offer(new DummyNode());
}
return root;
}
}
class Node{
int data;
Node left;
Node right;
public Node(){
}
public Node(int data){
this.data = data;
}
public String toString(){
return data+"";
}
}
class DummyNode extends Node{
}
</pre>
The idea is to find the root first and then call a helper function recursively to build subtrees and then make root the root of these subtrees. Code is as below-
node * UtilityBuildTreeFromAncestorArray(int ancestor[size][size], node *root, int CurrentRootIndex, int &rootone_count)
{
node *temp = 0, *CurRoot = new node(CurrentRootIndex + 1);
int i, j, one_count = 0;
for(i = 0;i < size; ++i)
{
if(ancestor[CurrentRootIndex][i] == 1)
{
++one_count;
UtilityBuildTreeFromAncestorArray(ancestor, CurRoot, i, one_count);
}
}
if(one_count == 0)
{
if(!root->left)
{
root->left = CurRoot;
}
else if(root->right == 0)
root->right = CurRoot;
--rootone_count;
for(i = 0;i < size; ++i)
{
ancestor[i][CurRoot->data - 1] = 0;
}
}
return root;
}
node *BuildTreeFromAncestorArray(int ancestor[size][size], int size = 5)
{
node *root = 0, *temp = 0;
bool ch = false;
int one_count = 0, i, ii, j;
for(i = 0;i < size; ++i)
{
for(ii = 0;ii < size; ++ii)
{
if(ancestor[i][ii] == 1)
++one_count;
}
if(one_count == size - 1) // root found
{
root = new node (i + 1) ;
break;
}
}
for(i = 0;i < size; ++i)
{
if(ancestor[root->data - 1][i] == 1)
UtilityBuildTreeFromAncestorArray(ancestor, root, i, one_count);
}
return root;
}
Unique Tree is not possible. Below algo is applicable for n-ary tree also with small modification.
Algo+Pseudocode:
- Tulley April 09, 2011Bool isLeftChildDone=FALSE Bool isImmidiateChild=TRUE; 1. Sort the rows of matrix in descending order of number of 1s. (this will form root as root is ancestor of all nodes) 2. R=newNode(); Root=R. Enque(Root). 3. FOR (I=1 to NumOfRow-1) && (Queue is not empty) { isLeftChildDone=FALSE; /*Make Tree*/ R=Dequeue(); FOR (J=1 to NumOfCol) { FOR (K=I+1 to numOfRow-1) { IF(AncestorMatrix[K][J]==1) isImmidiateChild=FALSE; break; } IF (isImmidiateChild==FALSE) { isImmidiateChild=TRUE; continue; } IF (AncestorMatrix[I][J]==1) { IF (isLeftChildDone==FALSE) { R->leftChild=newNode(); isLeftChildDone=TRUE; Enqueue(R->leftChild); } ELSE { R->rightChild=newNode(); Enqueue(R->rightChild); } } } }