Trees and Graphs Interview Questions
- 0of 0 votes
AnswersPrint all the paths from the root to the leaf in a tree
- rahulm January 06, 2012 in United States for RCX| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven a sorted array, construct a balanced BST.
- rahulm January 06, 2012 in United States for RCX| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven a binary tree where each node contains an integer value and a value k, print all paths which sum upto this value k
- rahulm January 06, 2012 in United States for RCX| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersAverage of Nodes in tree.
- racejakebannon December 12, 2011 in United States| Report Duplicate | Flag | PURGE
Trees and Graphs - 0of 0 votes
AnswersGiven a BST and two values m and n . We need to find out all the nodes whose values are in range of m and n .
- raiprince001 December 06, 2011 in India for Bing| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven a Binary tree where nodes may have positive or negative value, store the sum of the left and right subtree in the nodes.
Eg-10 -2 6 8 -4 7 5
Output:
- Puzzle November 19, 2011 in India20(-2+6+4+12) 4(8-4) 12(7+5) 0 0 0 0
| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Trees and Graphs Data Structures - 0of 0 votes
AnswersTo build a tree expression - (1 +3) * 4 - all numbers and operators are nodes in a tree. Was a reversal tree I guess....wrote my custom logic
- ashishdaga1 November 08, 2011 in United States for General| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersQuestion 2)
- msankith October 30, 2011 in India
Given a binary tree which contains values at each node , find whether the path exist from root to the "LEAF NODE" such that sum of the values of d path nodes is equal to the GIVEN SUM. if so return true or else return false| Report Duplicate | Flag | PURGE
Microsoft Developer Program Engineer Trees and Graphs - 0of 0 votes
AnswersGiven a BST find the kth largest element in the BST with single traversal and without using any extra space.
- erarpitagarwal October 20, 2011 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersA binary tree is given we need to print vertical sums of nodes. for example
1 2 3 4 5 | | 5 | | | | / | \ | | | | / | 8 | | | / | / | \| | 4 | / | 10 | / | \ 9 | | | / | \ | | 7 | 6 | | | | | | | | | | | ----------------------------------------------- 7 4 20 8 10
Here we need to print sum 7,4,20,8,10.
- sumanth.nitw October 17, 2011 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersConvert a binary search tree to a sorted doubly linked list in O(n) time and in place. Manipulate the existing tree. Donot create a new tree.
- python.c.madhav October 15, 2011 in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Data Structures Trees and Graphs Algorithm - 0of 0 votes
AnswersGiven a Binary tree and a pointer to some node in the tree, find the left and right neighbors of the input node. The neighbor nodes are on the same level/depth as of input node.
- Saurabh October 15, 2011 in India
Don't use BFS/level order traversal.
There is no parent pointer.| Report Duplicate | Flag | PURGE
Flipkart Software Engineer / Developer Trees and Graphs - 1of 1 vote
AnswersFind if a binary tree is bst
- anonym October 10, 2011 in -| Report Duplicate | Flag | PURGE
Amazon Flipkart Groupon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersYou are given a binary tree that has many binary search trees as subtrees. Find the largest (in terms of nodes) binary search tree (subtree). You are given the root node to binary tree. (Binary tree is different from binary search tree).
- takiisc October 08, 2011 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersHow can you merge two BST inplace so that preserving the BST property?
- learner October 06, 2011 in India
Provide algo only, dont write code| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Trees and Graphs - 0of 0 votes
Answersgive a binary tree (not BST)where tree node, with extra pointer inorder-successor, initaliy all inorder-successor pointer set to NULL.
- jayesh30785 September 27, 2011 in India
write a code to set all pointer to its inordersuccessor.
struct Node
{
int data;
Node *left, *right;
Node *successor;
};| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures Trees and Graphs Algorithm - 0of 0 votes
AnswersHow will u check whether a given tree is symmetric with structure wise not with the data.....
ex:
Symmetric structure wise5 / \ 3 9 \ / 4 8
Not symmetric
- sekhar740 September 27, 2011 in -5 / \ 5 9 / / 3 8
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersQ2:Implement T9 moblie phone dictionary .But the problem was just to find all the posible outputs given the the sequence of key pressed.
- tylerDurden September 15, 2011 in India for Data Storage
My Solution :Recursion
private static String[] mapping = { "ABC", "DEF", "GHI", "JKL", "MNO",
"PQR", "STU", "VW", "XY", "Z*#" };
public static void combinations(int[] number, char[] buf, int numIndex) {
for (int i = 0; i < mapping[number[numIndex]].length(); i++) {
buf[numIndex] = mapping[number[numIndex]].charAt(i);
if (numIndex < number.length - 1) {
combinations(number, buf, numIndex + 1);
} else
System.out.println(buf);
}
}
public static void main(String[] args) {
int num[] = { 0, 1};// { 4, 8, 5, 9, 0, 3, 1, 7,6,2 };
PhoneBook.combinations(num, new char[num.length], 0);
}
He was looking for Trie data structure :(| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersLowest common ancestor of bst
- dheeraj2311 August 06, 2011
After that modified it for binary tree| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven a binary tree we have to update another pointer sibling in the node such that every node sibling is the left node of current node.If there is no left node then its sibling should point to the right most node at that level...!!
- keerthy August 03, 2011| Report Duplicate | Flag | PURGE
Chronus Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven a Binary Tree ( Comprising of +ve & -ve numbers ), represent each node of the tree with sum of its LeftSubTree & RightSubTree
- S.K.S Harsha July 30, 2011
For Example :-
10 | 20
-2 6 | 4 12
8 -4 7 5 | 8 -4 7 5| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersFind the element closest to a given input element in a BST
- fountain July 26, 2011 in United States for SCVMM (Server tools)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Trees and Graphs - 0of 0 votes
AnswersWritten Round1: To get mirror image of a binary tree.
- vicky July 25, 2011| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Trees and Graphs - 0of 0 votes
AnswersRound1: Q1
- Ray July 20, 2011
Find the vertical sum in a binary tree.
Input:
(Plz construct the tree using the pre-order and in-order traversals)
Pre-order: 1 2 4 5 3 6 7
In-order: 4 2 5 1 6 3 7
Output:
Arr-Index Sum
0 4
1 2
3 12
4 3
5 7| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersRound 2: Q2:
- Abee July 20, 2011
Given a tree, in addition to the left and right pointer, it has a third pointer, that is set to NULL.
Set the third pointer to a node, which will be the successor of the current node, when the tree is traversed in the zig-zag order. In other words, if we traverse the tree using this third pointer alone, then we will be traversing the tree in the zig-zag order.
Input:
(Plz construct the tree using the pre-order and in-order traversals)
Pre-order: 1 2 4 5 3 6 7
In-order: 4 2 5 1 6 3 7
So, after the pointer is fixed, the traversal of the tree using the third pointer should give,
1 3 2 4 5 6 7| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
Answershow do you test given BST is a valid BST?
- kvap June 27, 2011| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Trees and Graphs - 1of 1 vote
AnswersGiven a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is maximum where F(X,Y) = sum of nodes in the path from root to X + sum of nodes in the path from root to Y - sum of nodes in the common path from root to first common ancestor of the Nodes X and Y
- jobseeker June 16, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 1of 1 vote
AnswersA rooted binary tree with keys in its nodes has the binary search tree
- Rahul June 09, 2011
property (BST property) if, for every node, the keys in its left
subtree are smaller than its own key, and the keys in its right
subtree are larger than its own key. It has the heap property if, for
every node, the keys of its children are all smaller than its own key.
You are given a set of n binary tree nodes that each contain an
integer i and an integer j. No two i values are equal and no two j
values are equal. We must assemble the nodes into a single binary tree
where the i values obey the BST property and the j values obey the
heap property. If you pay attention only to the second key in each
node, the tree looks like a heap, and if you pay attention only to the
first key in each node, it looks like a binary search tree.Describe a
recursive algorithm for assembling such a tree| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures Trees and Graphs