## 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);
}``````

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);
}
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]+",");
}

}

}``````

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!
}
}``````

Comment hidden because of low score. Click to expand.
0

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.

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;
}``````

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

``````import java.io.*;
import java.util.ArrayList;
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 */

System.in));

int N = Integer.parseInt(firstLine);

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>>();

if(node != null) {
}

while(current.size() > 0) {
List<Node> parents = current;

for(Node parent: parents) {
if(parent.left != null) {
}
if(parent.right != null) {
}
}

}

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();

}

}
}``````

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.

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)
{
push(temp->left);
}
else
{
push(temp->right);
}
}
}
temp=pop();
}
return root;
}

void getbfs(struct tnode *root)
{
int a[100][100],ind=0,in=0;
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");
}
}``````

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

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

int main() {
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;
}``````

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.

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

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?

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) {
}
}

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) {
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) {
childCount = tempCount;
tempCount = 0;
sbr.delete(0, sbr.length());
}
childCount--;
}
while (!stack.isEmpty())
System.out.println(stack.pop());
}
}

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.

### 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.