Trees and Graphs Interview Questions
- 1of 1 vote
Answersmerge two binary search trees
- mh4wt@virginia.edu December 18, 2016 in United States| Report Duplicate | Flag | PURGE
Microsoft Intern Java Trees and Graphs - 0of 0 votes
AnswersYou are given a binary tree. Each node in the tree is a house and the value of node is the cash present in the house. A thief can rob houses in alternate levels only. If thief decides to rob house at level 0 then he can rob houses in levels 2,4,6... or he can rob houses in levels 1,3,5,7...Find out the maximum possible amount thief can rob.
- 256.cool December 14, 2016 in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Trees and Graphs - 1of 3 votes
AnswersCreate a function to calculate the height of an n-ary tree.
- theNightsKing16 November 03, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Trees and Graphs - 0of 0 votes
AnswersFrom here : question?id=5660692209205248
- NoOne October 19, 2016 in United States
In-order traversal:
A->B->C->D->E->F->H->L->M-P->R->S->T
Write a function (pseudo-code is fine) that given a starting node, advances to the next in-order node in a binary tree.
Please also provide a data-structure definition of a node.| Report Duplicate | Flag | PURGE
Arista Networks Software Developer Algorithm Trees and Graphs - 0of 0 votes
AnswersGiven an n-ary tree, find the longest sequence in it. The sequence doesn't end to start at the root. It can go from leaf to leaf.
- ul October 16, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Trees and Graphs - 0of 0 votes
AnswersNeed to traverse below n-ary in postorder and throw error message if the node are cyclic
- sunny346 October 13, 2016 in United States
Node001
/ | \
/ | \
/ \ \
Node002 Node003 Node004
/ / | \
/ / | \
Node005 Node006 Node007 Node008
/
/
Node009
\
\
Node003
In above case it should through error because Node009 has child Node003 which is derived from it.| Report Duplicate | Flag | PURGE
Trees and Graphs - 0of 0 votes
AnswerHi Implemented this sample code for N-ary postOrder Traversal.
- sunny346 October 11, 2016 in India
Now i want to throw error statement id the parent node is dependent on child.
Can some one help
package dependencyAlgorithm;
import java.util.*;
public class Dependency
{
class MainRule
{
String ruleName;
ArrayList<MainRule> subrule;
public MainRule(String name)
{
this.ruleName=name;
subrule=new ArrayList<>();
}
}
public static void postOrder(MainRule rootRule)
{
Stack<List<MainRule>> stack = new Stack<>();
MainRule rule = rootRule;
List<MainRule> list = null;
while (true)
{
if(rule != null)
{
list = rule.subrule;
for(int i=0;i<list.size();i++)
{
if(rule.ruleName == list.get(i).ruleName)
break;
}
rule = null;
if(list!=null && list.size()>0)
{
//push the list in the stack (do not modify original tree structure).
stack.push(new ArrayList<>(list));
//get first item from this list
rule = stack.peek().get(0);
System.out.print("\n1 ListSize: "+list.size());
}
}
else if (!stack.isEmpty())
{
System.out.print("\n2 \n");
list = stack.pop();
System.out.print("\n2 ListSize: "+list.size());
rule = list.remove(0); //shift left
System.out.print("\n2.1 ListSize: "+list.size());
System.out.print("\n"+rule.ruleName+" ");
rule = null;
if(list.size()>0)
{
System.out.print("\n3 ListSize "+list.size());
stack.push(list); //push back remaining list into stack
rule = stack.peek().get(0); //prepare for next iteration
}
}
else
break;
}
System.out.println(rootRule.ruleName);
}
/*
Fml001
/ | \
/ | \
/ | \
Fml002 C001_Base Tot001
/ / | \
/ / | \
Fml003 Fml004 R001_Base R001_TxPat
/
/
Tot002
\
\
C001_TxPat
*/
public void createBinaryTree()
{
MainRule rootRule;
MainRule Fml001 =new MainRule("Fml001");
MainRule Fml002=new MainRule("Fml002");
MainRule Fml003=new MainRule("Fml003");
MainRule Fml004=new MainRule("Fml004");
MainRule C001_Base=new MainRule("C001_Base");
MainRule R001_Base=new MainRule("R001_Base");
MainRule Tot001=new MainRule("Tot001");
MainRule Tot002 =new MainRule("Tot002");
MainRule R001_TxPat =new MainRule("R001_TxPat");
MainRule C001_TxPat =new MainRule("C001_TxPat");
rootRule=Fml001;
rootRule.subrule.add(Fml002);
rootRule.subrule.add(C001_Base);
rootRule.subrule.add(Tot001);
Fml002.subrule.add(Fml003);
C001_Base.subrule.add(Fml004);
C001_Base.subrule.add(R001_Base);
C001_Base.subrule.add(R001_TxPat);
R001_Base.subrule.add(Tot002);
Tot002.subrule.add(C001_TxPat);
postOrder(rootRule);
}
public static void main(String[] args)
{
Dependency dependency=new Dependency();
// Creating a tree structure
System.out.println("Path Traversed:");
dependency.createBinaryTree();
}
}| Report Duplicate | Flag | PURGE
Cognzant Technology Solutions Dev Lead Trees and Graphs - 1of 1 vote
AnswersGiven two (binary) trees, return the first pair of non-matching leaves
- bobshanely October 03, 2016 in United States
Tree 1: A, B, C, D, E, null, null
Tree 2: A, D, B
Output: (E,B)| Report Duplicate | Flag | PURGE
Facebook Intern Trees and Graphs - 4of 4 votes
AnswersGiven a undirected graph with weights, return the sum of the weight of each path between two nodes (shortest path between two vertices). Assume there are no cycles.
Example:Input: A | 1 B 2 / \ 3 C D Output: 18 since A to B has weight 1 A to C has weight 3 A to D has weight 4 B to C has weight 2 B to D has weight 3 C to D has weight 5
Edit: Thanks, wangchenClark0512, forgot about C to D
- djway August 18, 2016 in United States
Edit2: @Lukas, The question is just the sum of the shortest paths between two vertices. Also, all edges are positive.
Edit3: Assume the graph has no cycles, did not get to the follow-up, but follow-up probably is probably change your algorithm so that is works for cycles| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersSuggest a data structure and implement efficient phrase search along with word search in a huge chunk of text.
- novicedhunnu August 14, 2016 in India for N/A| Report Duplicate | Flag | PURGE
Microsoft Software Developer Trees and Graphs - 7of 7 votes
AnswersYou are given a graph with no cycles, each node representing different cities and there are stadiums for baseball games in all cities.
Each node contains a value representing the population of the city, and a list of neighbors. (feel free to extend data structure)
Every time there is a baseball game at a city, everyone from all the different cities will go to the city with the baseball game.
Return the maximum traffic between a city and its neighbours when there is a game at that city, for all cities. (Does not have to be sorted)
The total run-time after returning everything should be O(n).
Examples:
- djway August 10, 2016 in United StatesInput: 1 2 \ / 5 / \ 4 3 Output: 1 14 2 13 3 12 4 11 5 4 Input: 38 / 8 / 7 / 1 2 \ / \ 5 15 / \ 4 3 Output: 1 82 2 53 3 80 4 79 5 70 7 46 15 68 8 38 38 45
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 1of 1 vote
AnswersThere are n number of conference rooms available in a company for the meeting. You need to book a meeting for a particular time slot. Write an algorithm to determine the number of conference rooms available for the meeting with given start time and end time.
- coder May 17, 2016 in United States for Devices
Hint: any conference room with non- overlapping meeting will be selected.| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 0of 0 votes
AnswersWrite a program to identify if a given binary tree is balanced or not.
- NS March 03, 2016 in United States| Report Duplicate | Flag | PURGE
JP Morgan Software Engineer / Developer Trees and Graphs - 4of 4 votes
AnswersGiven the root of a binary tree containing integers, print the columns of the tree in order with the nodes in each column printed top-to-bottom.
- takepwn February 26, 2016 in United StatesInput: 6 / \ 3 4 / \ \ 5 1 0 / \ / 9 2 8 \ 7 Output: 9 5 3 2 6 1 7 4 8 0 Input: 1 / \ 2 3 / \ / \ 4 5 6 7 When two nodes share the same position (e.g. 5 and 6), they may be printed in either order: Output: 4 2 1 5 6 3 7 or: 4 2 1 6 5 3 7
| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Trees and Graphs - 0of 0 votes
AnswerGiven a sorted integer array. Convert it to a balanced BST (Size of array is given)
- Saurabh Singhal January 16, 2016 in India| Report Duplicate | Flag | PURGE
Arista Networks Software Engineer Data Structures Trees and Graphs - 3of 3 votes
AnswersGiven a forest of balanced binary trees and two nodes, n1 and n2, find the closest common parent of n1 and n2. Nodes have parameters "parent", "left" and "right", and you cannot access the values of the nodes. If n1 and n2 are not on the same tree, return NULL.
- Matt Cooper December 26, 2015 in United States for Software Engineering
Try to do this in O(log(n)) time and O(1) space.| Report Duplicate | Flag | PURGE
Facebook Intern Trees and Graphs - 1of 1 vote
AnswersYou have a BST and you need to assign an appropriate value to neighbor of all nodes (Explained in below example)
Node Structurenode { node leftChild, node rightChild, T data, node neighbor }
A
- avinash.setty December 12, 2015 in United States for Marketplace
/ \
B C
/ \ \
D E F
Based on above tree,
Node: Neighbor
A: NULL
B: C
D: E
E: F| Report Duplicate | Flag | PURGE
Amazon SDE-2 Trees and Graphs - 0of 0 votes
AnswersGiven two identical dom trees and an element in one of those trees, find the corresponding element in the other tree and highlight it.
- killdos October 11, 2015 in United States| Report Duplicate | Flag | PURGE
Ebay Java Developer Algorithm Trees and Graphs - 0of 0 votes
AnswersDesign a train system which suggests shortest path and transfer needed to reach from source to destination. What can be the optimization.
- hm September 30, 2015 in United States
For example:
A system may have 10 trains from t1 to t10.
There are total 100 stops in the system s1 to s100.
Each train has fixed set of stops. You could allow to change and transfer train of source and destination does not cover using just 1 train.
What all can be APIs, data structure, optimizations scalable option.| Report Duplicate | Flag | PURGE
Software Engineer Algorithm Problem Solving Software Design System Design Trees and Graphs design - 0of 0 votes
AnswersFind the next value of a given value in a Binary Search Tree. Assume each node has reference to its parent
- JSDUDE September 24, 2015 in United States| Report Duplicate | Flag | PURGE
Tableau Software Engineer / Developer Trees and Graphs - 6of 6 votes
AnswersPost order traversal for an N-ary tree iterative way.
- hm September 14, 2015 in United States
Given,
struct Node {
int val;
vector<Node*> children;
};
Without modifying original structure.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm C++ Trees and Graphs - 0of 0 votes
AnswersPost order traversal for an N-ary tree iterative way.
- hm September 14, 2015 in United States
Given,
struct Node {
int val;
vector<Node*> children;
};
To simplify you can modify the structure.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm C++ Trees and Graphs - 0of 0 votes
AnswersRound 2
- sonesh July 12, 2015 in United States
Question 3 : You have to implement an external iterator which iterate the binary tree InOrder. You have to figure out what kind of iterator one should use, and implement each of those function. required complexity is O(N) time + O(log(N)) space| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Coding Data Structures Trees and Graphs - -3of 3 votes
AnswersRound 1(taken by DATA SCIENTIST 2)
- sonesh July 12, 2015 in United States
Question 1 : You are given a street map of a city, Every day you travel from your home to work. some day you take bus or someday your our car. Bus fare is also not constant, it may change in future, may increase or decrease ?
you have to find shortest path from your home to your work ?.
Note that : you have to expose this as library, so no custom assumptions. need to find out how you incorporate variable bus fare ?, also it is up-to the user to choose between bus and his car ?, in case of bus, you have to minimise the total money, and in case of care, you have to minimise the distance.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Data Structures Trees and Graphs - 0of 0 votes
AnswersGiven an N-ary tree with thousands of nodes, pair the leaf nodes which do NOT SHARE the common path. i.e. Two Leaves can be Paired only if they do NOT have a common edge that was used in a previous pairing.
- nemesis July 05, 2015 in United States
For example,
A
/ | \
B C D
/ / | \
E F G H
Leaf nodes: E, F, G, H & D
Possible Pairs in O/Ps:
a) (E-F), (G-H) or
b) (E-G), (F-H) or
c) (E-H), (F-G) or
d) (E-D), (F-G) or
e) (E-D), (G-H) or
f) (E-D), (F-H) or
g) (D-H), (F-G) or
h) (D-G), (F-H) or
i) (D-F), (G-H)
Note: If we pair(join) say, (E-F) then we can NOT pair any of the (D-G) or (D-H) as they SHARE the COMMON path from A to C.
i.e. E-B-A-C-F —> (E-F) pair
D-A-C-G —> (D-G) pair
D-A-C-H —> (D-H) pair
So the above case is NOT possible| Report Duplicate | Flag | PURGE
Trees and Graphs - 0of 2 votes
AnswersSerialize & Deserialize a binary tree
- JSDUDE June 24, 2015 in United States| Report Duplicate | Flag | PURGE
Uber Software Developer Trees and Graphs - 1of 1 vote
AnswersGiven two binary trees ( not BST) , return true if both of them have same inorder else return false.
Eg.B / \ A C
A \ B \ C
Both of the trees have same inorder ( A-B-C) hence function will return true
- Anonymous April 25, 2015 in United States
P.S.
Please note, we can write inorder method call it once for first tree and then second tree, and finally compare both inorder.
We want to parallely do inorder on both tree, if there is mismatch between inorder nodes of both trees, we can stop the traversal and return false| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersAssuming you have a binary tree which stores integers, count the number of nodes whose value is lower than the value of its upper nodes.
- sandeep.nie April 22, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm Trees and Graphs - 4of 4 votes
Answersin a tree any root can have any number of children. Every node has an integer value. Find the maximum length on consecutive number sequence anywhere in the tree. For example if root is 2 and one child is 3, its child is 4 its child is 6 then max length will be 3. I was able to write the code the find of one sequence but when one sequence ends and other starts I was not able to handle that case. I think its hard to do by recursion. Is there any other trick or algorithm for this??
- ajrules2105 March 10, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 1of 3 votes
Answersdesign and implement a calculater that can calculate expressions like:
- srcnaks February 02, 2015 in -
+ 2 4
* 8 ( + 7 12)
( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 )
(PS:all items are space delimetered.)
Example answers
+ 2 4 => 2 + 4 = 6
* 8 ( + 7 12) => 8 * ( 7 + 12 ) = 152
( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) => 7+8*12+2*(9+4)*7+3 = 148| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures Problem Solving Stacks String Manipulation Trees and Graphs