Flipkart Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
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]+",");
}
}
}
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!
}
}
#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;
}
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();
}
}
}
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");
}
}
#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;
}
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?
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());
}
}
This is a BFS problem, in a backward order (if you will). Simply use queue(s) to solve the problem:
- mombasa February 18, 2014