Flipkart Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




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

This is a BFS problem, in a backward order (if you will). Simply use queue(s) to solve the problem:

void traverse_helper(const vector<int>& T, queue<int> Q)
{
	if( Q.empty() ) return;

	// P: queue to print out nodes
	// R: queue for the next traversal
	queue<int> P,R; 

	// BFS
	while( !Q.empty() ) {
		int node = Q.front(); Q.pop(); P.push(node);
		for(int j=0; j<T.size(); j++)
			if( T[j]==node )
				R.push(j);
	}
	traverse_helper(T,R);

	// print the node
	printf("[ ");
	while( !P.empty() ) {
		printf("%d ", P.front());
		P.pop();
	}
	printf("]\n");
}

void backward_traversal(const vector<int>& T)
{
	if( T.empty() ) return;

	queue<int> Q; 
	for(int i=0; i<T.size(); i++)
		if( T[i]==-1 )
			Q.push(i);
	traverse_helper(T, Q);
}

- mombasa February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

I have another solution. I will find level of each node and save it in Sorted Hash Map (TreeMap). So my tree map will be of the form
TreeMap<Integer, List<String>>


To find level of a node
Level(n) = Level(input[n]) +1, if input[n] > -1
1, else (as it is root)

package practise;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class ParentValueGraph {

	public ParentValueGraph() {
		// TODO Auto-generated constructor stub
	}
	
    private static int levelIndex[];
    static String values[];
    private static TreeMap<Integer, List<String>> levelMap= new TreeMap<Integer, List<String>>();
	public static int getLevelIndex(int index){
		if(levelIndex[index] == -2){
			if(Integer.parseInt(values[index]) == -1){
				levelIndex[index] = 1;
			}else{
		        levelIndex[index] = getLevelIndex(Integer.parseInt(values[index]))+1;
			}
			List<String> elemList = levelMap.get(levelIndex[index]);
			if(elemList == null){
				elemList = new ArrayList<String>();
				levelMap.put(levelIndex[index], elemList);
			}
			elemList.add(index+"");
		    return levelIndex[index] ;
		}
		else{
			return levelIndex[index];
		}
		
	}
	
	public static String joinStr(List<String> words,char token) {
	    StringBuilder wordList = new StringBuilder();
	    for (String word : words) {
	        wordList.append(word + token);
	    }
	    return new String(wordList.deleteCharAt(wordList.length() - 1));
	}
	
	public static void main(String args[]){
		String input = "8 7 0 5 5 8 7 0 -1";
		values = input.split(" ");
		
		levelIndex = new int[values.length];
		for(int i = 0; i < values.length; i++)
			levelIndex[i]=-2;
		
		for(int i = 0; i < values.length;i++){
			getLevelIndex(i);
		}
	    Set<Integer> reverse = levelMap.descendingKeySet();
		for(Integer r : reverse){
			List<String> elem = levelMap.get(r);
			System.out.println(joinStr(elem,' '));
			
		}
		for(int i = 0; i < values.length;i++){
			System.out.print(levelIndex[i]+",");
		}
		
	}

}

- Suraj Prakash June 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is just like BFS with one additional Stack and a loop over that stack.
Why not simply avoid recursion, but instead use a typical BFS Queue first to queue-up all the nodes, until no children are found. While iterating over the Queue, pop() individual node but DONT print it, but instead put it in a Stack.
In the end, simply go over the stack, print nodes => Stack will reverse the order.
I argue this is way more efficient on most machines than any of above algorithms, because it does not use Recursion but a literal Stack..

void ReverseLevelPrint ( Tree* root )
{
   std::stack<Tree *> s;
   std::queue<Tree *> q;

   q.push(root);
   while ( ! q.empty() )
   {
      Tree *node = q.pop();
      if (node->left) q.push (node->left);
      if (node->right) q.push (node->right);
   }

   while( ! s.empty() )
   {
      print ( s.pop() );   // You know what I mean!
   }
}

- Nix March 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well stack idea is better. But it won't solve the main problem here. The key point is to get the node value and identifying the parent child relation among nodes. So it would be better if you implement the above code with the input set in mind.

- Akshay December 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <cstdlib>
#include <iostream>

#include <map>

using namespace std;

struct Node{
	int data;
	Node* left;
	Node* right;
};

Node* NewNode(int data)
{
	Node* newNode =  new Node();
	newNode->data = data;
	newNode->left = NULL;
	newNode->right = NULL;

	return newNode;

}
int FindRoot(std::map<int,int> mapChildParent)
{
	for (int i=0; i< mapChildParent.size(); i++)
		if(mapChildParent[i] == -1)
			return i;
	
	return -1;
}
void FindChild(int iChildArray[], std::map<int, int> myMap, int iParentIndex)
{
	
	int iCount = 0;
	for (int i=0; i< myMap.size(); i++)
	{	if(myMap[i] == iParentIndex)
		{
			iChildArray[iCount] = i;
			iCount++;
		}
	}
}
void prepareSubTree (Node* parentNode, map<int, int> myMap)
{
	int iChildArray[2] = {-1, -1};
	FindChild(iChildArray, myMap, parentNode->data);

	if (iChildArray[0] != -1)
	{
		Node* temp = NewNode(iChildArray[0]);
		parentNode->left = temp;
		prepareSubTree(temp, myMap);
	}
	if (iChildArray[1] != -1)
	{
		Node* temp = NewNode(iChildArray[1]);
		parentNode->right = temp;
		prepareSubTree(temp, myMap);
	}
	
}
int height( Node* node)
{
   if (node==NULL)
       return 0;
   else
   {
     /* compute the height of each subtree */
     int lheight = height(node->left);
     int rheight = height(node->right);
 
     /* use the larger one */
     if (lheight > rheight)
         return (lheight+1);
     else 
          return (rheight+1);
   }
}


void printGivenLevel(struct Node* root, int level)
{
  if(root == NULL)
    return;
  
  if(level == 1)
  {
    cout << root->data;
    cout <<  ' ' ;
  } 
  else if (level > 1)
  {
    printGivenLevel(root->left, level-1);
    printGivenLevel(root->right, level-1);
  }
}

void printReverseLevelOrder(Node* root)
{
	// print reverse level order order
  int iHeight = height(root);
  int i;
  for(i=iHeight; i>=1; i--)
  {
     printGivenLevel(root, i);
     cout << endl;
  }	
}
int main(int argc, char *argv[])
{
	int iNum ;
    cin  >> iNum;
	
	int* arr = new int[iNum];
    for (int i=0; i < iNum; i++)
        cin >> *(arr+i);
    
	std::map<int, int> myMap;   // store child-parent relationship in a map data structure
	for(int i=0; i<iNum; i++)
		myMap[i] = arr[i];
	
	int iRootIndex = FindRoot(myMap);

	Node* root = NewNode(iRootIndex);

	prepareSubTree(root, myMap);

	printReverseLevelOrder(root);
	return 0;
}

- avinash February 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    
    public static void main(String args[] ) throws Exception {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */
        
        BufferedReader sysIn = new BufferedReader(new InputStreamReader(
				System.in));

        String firstLine = sysIn.readLine();
        
        int N = Integer.parseInt(firstLine);

        String secondLine = sysIn.readLine();
		String[] inputString = secondLine.split("\\s+");
        
        if(inputString.length != N) {
			throw new RuntimeException("Number of elements can't be more than "+N);
		}
        
        int [] array = new int[inputString.length];
		for(int i=0;i<inputString.length;i++){
			array[i] = Integer.parseInt(inputString[i]);
		}
        
        Solution tree = new Solution();
        tree.buildTree(array);
        tree.levelOrderTraversal();
        

        
    }
    
    private static class Node {
		int value;
		Node left;
		Node right;

		Node(int value) {
			this.value = value;
			left = right = null;
		}

	}
    
    private Node root;
    
    Solution(){
		root = null;
	}
	

    public  void buildTree(int[] array) {

		root = findRoot(array);
		buildTree(array, root);
	}
	
	private Node findRoot(int [] array) {
		Node node = null;
		for(int i=0;i<array.length;i++) {
			if(array[i] == -1){
				
				node =  new Node(i);
			}
		}
		
		return node;
	}

	private void buildTree(int[] array, Node node) {
		
		if(node == null) {
			return;
		}
		
		boolean leftChild = false;
		
		for(int i=0;i<array.length;i++) {
			
			if(array[i]  == node.value) {
				
				if(!leftChild) {
					node.left = new Node(i);
					buildTree(array, node.left );
					leftChild = true;
				} else {
					node.right = new Node(i);
					buildTree(array,node.right);
				}
			}
		}

	}

    
  	public void levelOrderTraversal() throws IOException {
		levelOrderTraversal(root);
	}

    
    private void levelOrderTraversal(Node node) throws IOException {
		
		BufferedWriter sysOut = new BufferedWriter(new OutputStreamWriter(
				System.out));
		List<List<Node>> result = new ArrayList<List<Node>>();
		
		List<Node> current = new LinkedList<Node>();
		if(node != null) {
			current.add(node);
		}
		
		while(current.size() > 0) {
			result.add(current);
			List<Node> parents = current;
			current = new LinkedList<Node>();
			
			for(Node parent: parents) {
				if(parent.left != null) {
					current.add(parent.left);
				}
				if(parent.right != null) {
					current.add(parent.right);
				}
			}
			
		}
		
		
		for(int i = result.size() - 1; i>=0;i--){
			List<Node> level = result.get(i); 
			StringBuilder buff = new StringBuilder();
			for(Node levelNode: level) {
				buff.append(levelNode.value+ " ");
			}
			sysOut.write(buff.toString().trim());
			sysOut.write("\n");
			sysOut.flush();
			
		}
		
	}
}

- Anonymous February 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is it sure:

that it is an binary tree only???

i mean in any of the test case does not say , that an parent can have more than 2 children.

- Ashish March 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct tnode *addnode(int num)
{
       struct tnode * root = (struct tnode *) malloc(sizeof(struct tnode));
       root->val=num;
       root->left = NULL;
       root->right=NULL;
       return root;
}

struct tnode * create(int a[],int n)
{
     int i=0;
     while(a[i]!=-1)
        i++;
     struct tnode * root = addnode(i);
     push(root);
     struct tnode * temp = pop();
     while(temp!=NULL)
     {
        for(i=0;i<n;i++)
        {
           if(a[i]==temp->val)
           {
              if(temp->left==NULL)
              {
                 temp->left = addnode(i);
                 push(temp->left);
              }
              else
              {
                 temp->right = addnode(i);
                 push(temp->right);
              }
           }
        } 
        temp=pop();
     }
     return root;
}

void getbfs(struct tnode *root)
{
     int a[100][100],ind=0,in=0;
     struct tnode *dummy = addnode(-1);
     push(root);
     push(dummy);
     struct tnode *temp = pop();
     while(temp!=NULL)
     {
        while(temp!=dummy)
        {
           a[ind][in++]=temp->val;
           if(temp->left!=NULL)
              push(temp->left);
           if(temp->right!=NULL)
              push(temp->right);
           temp=pop();
        }
        if(temp==dummy)
        {
           a[ind][in]=-1;
           ind++;
           in=0;
        }
        temp=pop();
        if(temp!=NULL)
           push(dummy);
     }
     while(ind-->0)
     {
        in=0;
        while(a[ind][in]!=-1)
        {
           printf("%d\t",a[ind][in]);
           in++;
        }
        printf("\n");
     }
}

- Nitin April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include<map>
#include<vector>
using namespace std;

int main() {
	// your code goes here
	int T, N;
	int n;
	map<int, vector<int> >myMap;
	map<int, vector<int> >::iterator itr;
	cin>>T;
	int root;
	for(int i=0; i<T; i++)
	{
		cin>>N;
		for(int j = 0; j< N; j++)
		{
			cin>>n;
			cout<<n<<" ";
			if(n==-1)
				root = j;
			(myMap[n]).push_back(j);
		}
			//update
			vector<int> currLevel;
			vector<int> nxtLevel;
			int lvl = 0;
			map<int, vector<int> > newMap;
			(newMap[lvl]).push_back(root);
			currLevel.push_back(root);
			cout<<"lvl:"<<lvl<<"size: "<<(newMap[lvl]).size()<<endl;
			lvl++;
			while(1)
			{
				while(!currLevel.empty())
				{
					root = currLevel[0];
					currLevel.erase(currLevel.begin());
					if((itr = myMap.find(root)) != myMap.end())
						nxtLevel.insert(nxtLevel.end(), itr->second.begin(), itr->second.end());
				}
				if(nxtLevel.empty())
					break;
				currLevel = newMap[lvl] = nxtLevel;
				nxtLevel.clear();
				cout<<"lvl:"<<lvl<<"size: "<<(newMap[lvl]).size()<<endl;
				lvl++;
			}
			itr = newMap.end();
			for(itr--; itr != newMap.begin(); itr--)
			{
				for(int i=0; i< itr->second.size(); i++)
					cout<<itr->second[i]<<" ";
				cout<<endl;
			}
			for(int i=0; i< itr->second.size(); i++)
				cout<<itr->second[i]<<" ";
			cout<<endl;
	
	}
	return 0;
}

- Amit June 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A better solution would be to create node and store each node in List of doubly LinkedList and keep track of tail node.

LinkedList<LinkedList<Node>>

So while reading the array keep on creating Node and keep on placing them in correct list.

- Gourav December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Input Format -
First line of the input contains number of nodes in the tree (N)
Next line contains N (space seperated) numbers that denote where i-th number will denote the parent node of i-th node.
Third line contains two integers within the range of [0,N1]
whose common ancestor you have to find.
Output format:-First line has the depth of the tree.
Second line has the maximum number of children among all the nodes.
Third line has the nearest common ancestor to two given nodes n1 and n2.

can someone pls help me with this?

- Vignesh iyer December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package office.test1;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

public class ReverseLevel {

public static void main(String[] args) {
// int size = 5;
// int size = 9;
int size = 45;
// String input = "-1 0 0 2 1";
// String input = "8 7 0 5 5 8 7 0 -1";
String input =
"24 42 4 30 29 43 22 15 26 36 26 16 3 22 21 41 18 16 34 41 12 29 32 30 43 15 4 38 36 -1 24 42 18 6 21 38 6 17 32 17 3 34 12 14 14";
String values[];
Integer[] numbers = new Integer[size];


values = input.split(" ");
Integer[][] arr = new Integer[size][2];

Queue<Integer> queue = new ArrayDeque<Integer>();
Stack<String> stack = new Stack<String>();

for (int i = 0; i < size; i++) {
numbers[i] = Integer.parseInt(values[i]);
if (numbers[i] == -1) {
queue.add(i);
}
}

for (int j = 0; !queue.isEmpty(); j++) {
Integer node = queue.remove();
arr[j][0] = node;
arr[j][1] = 0;
for (int i = 0; i < size; i++) {
if (numbers[i] == node) {
queue.add(i);
arr[j][1]++;
}
}
}

int childCount = 0;
int tempCount = 0;
StringBuilder sbr = new StringBuilder();
for (int i = 0; i < size; i++) {
sbr.append(arr[i][0] + " ");
tempCount += arr[i][1];
if (childCount == 0) {
stack.add(sbr.deleteCharAt(sbr.length() - 1).toString());
childCount = tempCount;
tempCount = 0;
sbr.delete(0, sbr.length());
}
childCount--;
}
while (!stack.isEmpty())
System.out.println(stack.pop());
}
}

- Vikram February 07, 2016 | Flag Reply


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