Trees and Graphs Interview Questions
- 2of 2 votes
Answerstwo BST are given find common elements in both....
- abhishek September 09, 2012 in India for idc| Report Duplicate | Flag | PURGE
Microsoft Intern Trees and Graphs - 0of 0 votes
AnswersTwo elements of BST are swapped by mistake. You have to restore the tree without changing its structure.
- Nascent August 30, 2012 in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven a binary tree and 3 nodes x,y,z, write a function which returns true if y lies in the path between x and z and false otherwise. Its been posted couple of times in past in careercup blogs, still couldn't find an apt solution which considers corner cases like
- novice12 August 29, 2012 in India
y
/ \
z x| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven two trees, how do you find one of the tree is a subtree of other?
- hari@hbiz.in August 26, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Development Manager Algorithm Data Structures Trees and Graphs - 1of 1 vote
AnswersYou are a hunter in the forest. A monkey is in the trees, but you don't know where and you can't see it. You can shoot at the trees, you have unlimited ammunition. Immediately after you shoot at a tree, if the monkey was in the tree, he falls and you win. If the monkey was not in the tree, he jumps (randomly) to an adjacent tree (he has to).
- Glude August 03, 2012 in United States
Find an algorithm to get the monkey in the fewest shots possible.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven the Pre-order of the BST .check if each non-leaf node has only one child.Linear Time is expected.
- grave July 31, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Trees and Graphs - 0of 0 votes
AnswersConvert a binary search tree into doubly linked list in sorted order in place.
- bond July 27, 2012 in India for hyd| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven a Binary tree,find the level at which the tree is complete.Complete Binary tree-All leaves should be at same level and every internal node should have two children.
- grave July 25, 2012 in India
Asked to write both Recursive and iterative code.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Trees and Graphs - 0of 0 votes
AnswersCreate the n-ary tree from the ancestor matrix.
- grave July 19, 2012 in India
matrix[i][j]=1 if i is the ancestor of j.
My answer-
find the root (row with all zeroes).
Set the column with a[i][root] =0
find all the rows with all zeroes.insert into the tree all the children.and push all into the queue.
pop and find the children ,insert into the tree with popped node as parent and push into the queue.
Can not implement properly as it needed some modifications.
This is asked from my friend at amazon bangalore.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays Data Structures Trees and Graphs - 1of 1 vote
AnswersGiven an array which contains the parent of the ith element in the n-ary tree.Parent[i] = -1 for root.
- grave July 07, 2012 in India
Find the height of the tree.
Gave O(n2) ,space O(1).
Expected Complexity- Linear
You can use extra space if you want.
Example-
{-1 0 1 6 6 0 0 2 7}
0 1 2 3 4 5 6 7 8
0 is the root here.
0 is the parent of 1 5 6
1 is parnt of 2
6 is parent of 3 4
2 is of 7 which is parent of 8.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Structures Hash Table Trees and Graphs - 0of 0 votes
Answerslunatic server solution is monitoring the wrong file entry in the server.
- PriyaDarad June 06, 2012 in United States
so company made another a problem for it to monitor AVL tree violation.
The problem should be solved in java...
problem states that...
This problem requires you to monitor a tree for violation of the AVL balance criteria as the tree is being
constructed.
The input to the program consists of a sequence of numbers. As you read in each number, check where the
node is going to be inserted into the current tree. [At the start, the tree is empty.] If that insertion can cause
the balance of any of the nodes in the tree to go beyond what is allowed by the AVL criteria, DO NOT add
the number into the tree. Instead, print out the number into the standard output. Numbers which retain the
AVL property of the tree should be added to the tree at the appropriate place as per the method discussed in
class. Continue with the remaining numbers. Please note that you do not have to do any balancing of the
tree! The input is terminated by –1.
The output from the program consists of the numbers rejected by the program. At the end, you should also
print out the count of such numbers rejected.
Hint: It would help to keep the height of the left and right subtrees of each node along with the node. Also
note that the process of checking for violation and actually inserting are quite similar; in the former case you
do not update anything but do everything else. This observation can be used to write the code.
Sample Input/Output
Input
3 5 1 6 2 4 9 7 -1
Output
7 1
(This means rejected key(s) are: key 7, totally 1 rejected key)| Report Duplicate | Flag | PURGE
Lunatic Server Solutions Developer Program Engineer Trees and Graphs - 0of 0 votes
AnswersFind the(two) nodes which are at maximum distance in a binary tree?
- grave May 31, 2012 in India
This is not finding the distance but the nodes which are farthest.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Structures Trees and Graphs - 0of 0 votes
AnswersThe second round interview: Implement a binary tree with the given interface, then discuss the implementation via remote desktop and phone.
- groupme May 29, 2012 in United States for Potsdam/* * An interface for an sorted binary tree. * * The interface provides methods for inserting values, checking if certain values are contained and iterating over the elements. * Note: Implementing classes should provide an iterator that traverse the inserted object in the sorted order. */ public interface IBinTree<V extends Comparable<V>> extends Iterable<V> { /* * Insert an object into the binary tree. Note: The tree should be sorted, inserting the same object twice is allowed but the insert is expected to be stable. */ void insert(V obj); /* * Batch-insert multiple elements. */ void insert(Vector<V> vec); /* * Check if the object is already in the tree. Return true if it is, false otherwise. */ boolean contains(V obj); }
| Report Duplicate | Flag | PURGE
Sap Labs Developer Program Engineer Trees and Graphs - 0of 0 votes
AnswersWrite a java program to do the breadth first search of a graph.
- get.santhoshkrishna May 19, 2012 in United States| Report Duplicate | Flag | PURGE
InMobi Java Trees and Graphs - 0of 0 votes
AnswersGiven a BST. Replace the node value with the sum of all the node values that are greater than the current node value.
- santosh11900 May 08, 2012 in United States for hyderabad| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven an n-ary tree, find the closest common ancestor ? Discuss the time complexity and write testcases.
- ps April 24, 2012 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Trees and Graphs - 1of 1 vote
AnswersGiven a dictionary of strings [ strings are in sorted order] you have to find the precedence of characters according to the dictionary..
- Anton April 21, 2012 in India
eat
bxy
e is ranked above b according to the dictionary.| Report Duplicate | Flag | PURGE
Google Amazon Software Engineer / Developer Algorithm Data Structures Trees and Graphs Brain Teasers - 0of 0 votes
AnswersWrite a code to find out whether the given sum exists over any path in binary tree. Should return true or false.
- shooter April 17, 2012 in India| Report Duplicate | Flag | PURGE
Adobe Java Developer Trees and Graphs - 0of 0 votes
AnswersGiven a binary tree, every node has a int value, return the root node of subtree with the largest sum up value. Java is more preferable. Caution: the return should be a node, not a integer!
- CreepyMan February 29, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersConvert a BST to sorted doubly linked list.
- y2km11 February 25, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Trees and Graphs - 0of 0 votes
AnswersWrite a method to create new tree with same structure but the values of each node will be sum of their descendents (sub tree). The leaf nodes will become 0. So if the tree is 50 30 10 40 60 55 75 (PreOrder) then new tree should be 270 50 0 0 130 0 0(PreOrder)
- sk February 23, 2012 in United States for AWSP| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersDo a merge of two binary trees and tell what the complexity of the merging is. The trees consist of m and n nodes respect.
- nihaldps February 21, 2012 in India| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Trees and Graphs - 0of 0 votes
AnswersGiven a graph (consider it to be a mxn grid). The nodes are node of a binary tree with left and right pointers. The start point (A) is at the left upper corner and the end point (B) is at right bottom corner. Each node points to its adjacent nodes in the grid (the right pointer points to the node on the right and the left points to the node just below it). The nodes at the lower and right edges will have child as null (right null for the right side edge and left null for the bottom edge). The end node at B is having both as null.
- nihaldps February 21, 2012 in India
How many paths are possible which can lead you to B, if you start from A?| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Trees and Graphs - 0of 0 votes
AnswersConstruct a Cartesian tree from in order traversal
- anonymus February 20, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven (i) a non-empty binary search tree with double values (e.g. 3.5) in each node and (ii) a key value K
- mihirk February 15, 2012 in United States
Write a method to find the closest value to K.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Coding Data Structures Java Trees and Graphs - 0of 0 votes
AnswersYou are given a function printKDistanceNodes which takes in a root node of a binary tree, a start node and an integer K. Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted order. Distance can be upwards or downwards.
- Novice Coder January 31, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersFind the density of the given binary tree
- Umar January 21, 2012| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Trees and Graphs - 0of 0 votes
AnswersFlatten a binary tree in the its inorder traversal form. Example if there is a tree like
- Dee January 12, 2012 in United States
01
0203
04050607
Flatten it to 04->02->05->01->06->03->07
Right of 4 should be pointing to 02 and so on.
The order is inorder traversal order
I was asked to use Recursion
PLease can some one post C# code for this.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Trees and Graphs - -1of 1 vote
AnswersGIven a binary tree, print the tree according to the level.
- gupta January 12, 2012 in India
eg
01
0203
04050607
0809101112131415
proceed further to find the mirror image of alternate level
01
0203
07060504
0809101112131415| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Structures Trees and Graphs