Flipkart Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
4
of 6 vote

1. Allocate a global bit vector of size h where h is height of the tree.
2. Traverse the tree in post-order fashion.
3. At each node do the following:
a) if leaf node: set the kth bit of the vector as 1 where k is the height of the current node.
b) else check if the k+l bit is set and add the value of the current node to sum.

Time complexity: O(n)
Space: O(logn)

The idea is to figure out the height of all leaf nodes and then choose all the nodes that are level 'l' from every leaf node.

- Anonymous July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yeah this worked. one corner case, if l == 0 should end up in adding all leaf nodes.

- BigFish July 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

very nice solution, post order is used to encounter leaves first

- Abhishek August 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

seems wrong to me.
Consider complete binary tree of height 10. now delete right half of leaf nodes. So now of left leaves have depth 10, and on right, leaves have depth 9. assign l =2, and watch, how your algo does.

- code-breaker October 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this algo fails as how do you ensure that any node is away for leaf only by l. for example
3
4 1
2 7
8
for this tree and l as 1 your algo gives ans as 12 but it should be 11.
as it is counting 1 also bcz (k+l) is set for it.

- Anonymous October 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

tree structure correction
3
/ \
4 1
/ \
2 7
/
8

- Anonymous October 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

yes this solution will not work..!!
in this example

3
  / \
 4  1
 / \
2 7
/
8

and if l = 1 then we need to sum 2, 4 and 3 and answer should be 9, not 11 or 12.

- Anonymous October 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

algorithm is correct with one addition, that we unset the bit(k+l)th after summing the (k)th element.

- sonesh November 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you unset the (k+l)th bit, then u might end up adding a node twice if it has two leaf nodes at level l.

- Sree April 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Thumbs up for @Anonymous on July 17, 2012
Great one! I am just following your steps.

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *left;
    struct node *right;
}node ;

node* newNode (int data) {
    node *temp = (node *) malloc (sizeof(node));
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
/* Calculates height as well as total
   number of nodes present in the tree */
int height (node *root, int *count) {
  int left, right ;
  if (!root)
    return 0 ;
  *count = *count + 1  ;

  /* Leaf node */
  if ( root->left == NULL && root->right == NULL )
    return 1 ;
  left = height (root->left,count) ;
  right = height (root->right,count) ;
  return 1+((left>right) ? left : right ) ;
}

/* Post order traversal and puts the element in the array,
   also puts the height of the tree nodes in another array */
int givePostOrderUtil (int* arr, node* root, int len, int* tLevel, int level) {
  if (root) {
    len = givePostOrderUtil (arr, root->left, len, tLevel, level+1) ;
    len = givePostOrderUtil (arr, root->right, len, tLevel, level+1) ;
    arr[len] = root->data ;
    tLevel[len] = level ;
	/* Special marks which indicates this as a leaf node */
    if ( root->left == NULL && root->right == NULL )
      tLevel[len] = -level ;
    len ++ ;
  }
  return len ;
}

/* Post order traversal driver function */
int* givePostOrder (node *root, int size, int** tLevel) {
  int *arr = (int *) malloc (sizeof(int)*size) ;
  int *tlevel = (int *) malloc (sizeof(int)*size) ;
  givePostOrderUtil (arr, root, 0, tlevel, 0) ;
  *tLevel = tlevel ;
  return arr ;
}

int giveSumParticularOrder (int* arr, int *tLevel, int tHeight, int count, int level) {
  int *bitArr, i, sum = 0 ;

  /* Array denotes for leaf nodes */
  bitArr = (int *) malloc (sizeof(int) * tHeight) ;
  for ( i = 0 ; i < tHeight ; i ++ )
    bitArr[i] = 0 ;

  for ( i = 0 ; i < count ; i ++ ) {
    /* marks as leaf node */
    if ( tLevel[i] < 0 ) {
      bitArr[-tLevel[i]] = 1 ;
    }
    else {
	  /* check the marker boundary and if the bit set then it will be
	     a child at that extra depth. Collect the value and adds */
      if ( (tLevel[i]+level) < tHeight && bitArr[tLevel[i]+level] ) {
        sum += arr[i] ;
      }
    }
  }
  return sum ;
}

int main () {
  int cNode = 0, i, *arr, *tLevel, tHeight ;
  node *root = newNode(1) ;
  root->left = newNode(2) ;
  root->right = newNode(3) ;
  root->left->left = newNode(4) ;
  root->left->right = newNode(5) ;
  root->right->left = newNode(6) ;
  root->right->right = newNode(7) ;
  root->left->right->left = newNode(8) ;
  root->left->right->right = newNode(9) ;
  root->right->right->right = newNode(10) ;

  tHeight = height(root,&cNode) ;

  arr = givePostOrder (root, cNode, &tLevel) ;
  for ( i = 0 ; i < cNode ; i ++ )
    printf ( "\n%d (%d)", arr[i], tLevel[i]) ;
  printf ( "\nMaximum sum is : %d", giveSumParticularOrder (arr, tLevel, tHeight, cNode, 2) ) ;
  return 0 ;
}

- Psycho August 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I suggest a modification to Anonymous ans, instead maintaining a bit set/or reset we maintain a actual vector of keys while going down through preorder traversal.
If we encounter any leaf, we simply add the value at vector.size()-K to a hash. In the end we sum the values in the hash.
More precisely,

Let V be Vector
Let map<int,bool> be HashMap
Start with root of the tree.
if ( root != NULL )
	1. if root != Leaf
		push root->data to V
		preOrder(root->left)
		preOrder(root->right)
		Pop from V
	2. else if root == Leaf
		push root->data to V
		map [ V [ V.size() - K - 1 ] ] = true;
                Pop from V

Now, sum all the values in the map to get desired answer :)

- NaMo June 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

1) perform post-order traversal of tree. maintain stack explicitly.
also maintain whether particular number is already added or not in stack
2) whenever you reach at leaf node get stack[top - k]->value and add it to ans.
code:

int sumup(Node * tree, int K, stack * st)
{ 
	if (tree == NULL) return 
    if (tree->left == NULL && tree->right == NULL)
    { 
        if (stack->top < k || st->array[stack->top-K]->already_added) return 0;  
        st->array[stack->top-K]->already_added = True 
        return st->array[stack->top-K]->value ; 
    } 
    int ans = 0; 
    st.push(tree);
    ans += sumup(tree->left, K, st); 
    ans += sumup(tree->right,K, st);
    st.pop(tree); 
    return ans; 
}

- jigs July 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't understand the question.

- eugene.yarovoi July 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@eugene : Suppose your binary tree leaves are at 5, 8, 7, 9, 2, 1 levels from the root level say level 0. Now you have given a number say 4, now you have to sum up all the values that are present in 4 levels up from those leaves.

- Psycho July 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

please give an example ..

- Amith manepu July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A
/ \
B C
/ \ \
E F D
/ \
G H

here in dis tree there are only three leaves G , H , D the reqd. ans would be ( E + F + C ) if the level is 1 and if the level given is 2 it would be ( B + A ) ...hope its all clear now ..

- deadman_22 July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

no its not like this
for level 1 sum= B+C
for level 2 sum =E+F+D

since when level got started counted from leaves
:)

- shreyans July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@shreyans Deadman says correctly.. questions asked " which are at a particular level from all of its existing leaves.".. so we have to calculate from leaves ,not from root

- rizwan August 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Calculates the sum of a particular level from leaves
int a[]={0,0,0,0,0,0},s;
int levelSum(struct btreenode *root,int h,int g){
if(root==NULL) return 0;
levelSum(root->leftchild,h+1,g);
levelSum(root->rightchild,h+1,g);
if(root->leftchild==NULL && root->rightchild==NULL)
a[h]=1;
else{
if(a[h+g]==1)
s+=root->data;
}

return s;
}

- Amit Sinha August 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Save the binary tree in an array (like storing a heap-store NULL in the places which are vacant in the tree)
Calculate the sum by adding the entries from 2^(n-1) up-til either length of the array(in case it is the last level) or up-til 2^(n-1) entries.

- Anonymous September 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Save the binary tree in an array (like storing a heap-store NULL in the places which are vacant in the tree)
Calculate the sum by adding the entries from 2^(n-1) up-til either length of the array(in case it is the last level) or up-til 2^(n-1) entries.

- pooja September 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You can solve this by using BFS.

- bansaldhiraj March 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

There's a much simple solution, i.e. calculate the height of the left-subtree and the right sub-tree, and pick the maximum. You can leverage the power of recursion to do that -- the code is self-explanatory, but basically you call bstHeight recursively on each on each node's left and right child, starting with the root. If the current node is null, return 0, otherwise add 1. In the end, after all recursive calls have been issued, you end up with as many 1s as there are levels in the particular sub-tree. They are added up to the total, and all you have to do is pick the max value.

struct Node
{
	int i;
	Node* left;
	Node* right;

	Node(int i, Node* left=NULL, Node* right=NULL)
		: i(i), left(left), right(right)
	{}
};

int bstHeight(const Node* const root)
{
	if (!root)
		return 0;

	return std::max(1 + bstHeight(root->left), 1 + bstHeight(root->right));
}

int main()
{
	Node* root = new Node(10);
	// left sub-tree
	root->left = new Node(5);
	root->left->left = new Node(2);
	root->left->left->right = new Node(3);
	// right sub-tree
	root->right = new Node(12);
	root->right->right = new Node(12);
	root->right->right->right = new Node(12);
	root->right->right->right->right = new Node(12);
	root->right->right->right->right->right = new Node(12);
	root->right->right->right->right->right->right = new Node(12);
	root->right->right->right->right->right->right->right = new Node(12);
	root->right->right->right->right->right->right->right->right = new Node(12);
	root->right->right->right->right->right->right->right->right->right = new Node(12);
	root->right->right->right->right->right->right->right->right->right->right = new Node(12);

	cout << "bstHeight(" << root->i << "): " << bstHeight(root) << endl << endl;

	deleteTree(root);
}

void deleteTree(Node* root)
{
	if (!root)
		return;

	Node* left = root->left;
	Node* right = root->right;

	cout << "delete " << root->i << "\n";
	delete root;

	deleteTree(left);
	deleteTree(right);
}

- vs June 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your algo will just find height of tree not what question is asking for. pls read question.

- Anonymous June 25, 2013 | 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