Trees and Graphs Interview Questions
- 0of 0 votes
AnswersA parent array P is given where P[i] denotes the parent of the ith node in the tree(the tree is generic). Parent of root is indicated with -1. I need to find the height/depth of tree. (Best sol in O(n))
- gopi.komanduri October 30, 2014 in India| Report Duplicate | Flag | PURGE
ADP Analyst Algorithm Arrays C# Data Structures Trees and Graphs - 0of 0 votes
AnswersGiven a binary tree,Write a function to return all of the nodes from a given node and a given distance. The function has three parameters root, the given node and the given distance. For example
- Danielnguyen0130 August 29, 2014 in United States
5
/\
4 7
/\
6 10
\
12
Calling the function F(root,7,1) will the return all the nodes from node 7 with the distance 1 which is 6,10,5
another example is F(root.7,2) will the return nodes 12,4| Report Duplicate | Flag | PURGE
Trees and Graphs - 0of 0 votes
AnswersWrite a function to return all of the nodes from a given node and a given distance. The function has three parameter root, the given node and the given distance. For example
- Danielnguyen0130 August 29, 2014 in United States
5
/\
4 7
/\
6 10
\
12
Calling the function F(root,7,1) will the return all the nodes from node 7 with the distance 1 which is 6,10,5
another example is F(root.7,2) will the return nodes 12,4| Report Duplicate | Flag | PURGE
Trees and Graphs - -1of 1 vote
AnswersGive a Binary tree, write a function to return all the nodes from a given with a given distance. The function has three parameters root of tree, a given node, a given distance. For example,
- Danielnguyen0130 August 28, 2014 in United States
5
/\
4 7
/\
3 10
\
12
calling the function F(root,7,1) will return nodes 3,5,10
calling F(root,7,2) will return nodes 12,4| Report Duplicate | Flag | PURGE
Trees and Graphs - 0of 2 votes
AnswersDesign a system like friend's functionality in facebook. should have all features of facebook's friends functionality. like for each person , he can have any number of friends , he will get suggestions for new firends , showing common friends if we visits any other profile . algo should be scalable , robust .
- gopi.komanduri August 02, 2014 in United States| Report Duplicate | Flag | PURGE
Computer Scientist Algorithm Android Application / UI Design Arrays Bit Manipulation C# C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures Database Distributed Computing Dynamic Programming Hash Table Java Large Scale Computing Linked Lists Math & Computation Object Oriented Design Problem Solving Sorting SQL Stacks System Design Trees and Graphs XML - 0of 0 votes
AnswersContext:
- codercoder July 19, 2014 in United States
There's a network of computers. Each computer accepts connections at certain incoming port numbers and can make outgoing connections to a possibly different set of outgoing port numbers. Some computers are connected through cables to each other. Computer A can directly transmit data to computer B if and only if:
there is a direct cable connection between computer A and B,
there exists a port number X, that is an outgoing port on computer A and an incoming port on computer B.
Some of the computers are connected directly to the outside, unsafe network. If there is a way to connect to computer Z either directly or indirecly from the outside network, that computer Z is "at risk". If there is no way to connect to computer Z from outside network, that computer is "safe".
Question:
Write a program that given:
computers (each computer has incoming and outgoing port numbers),
cable connections between computers (a pair of computers),
computers accessible from outside network,
Print out all "safe” computers and all possible ways to access a specific computer from outside network.| Report Duplicate | Flag | PURGE
Trees and Graphs - 0of 2 votes
AnswersHow to design a multi key hash map ( key count can be dynamic. if there are two keys , initiallly which can be used to find the value , keys can be increased to three as well ex: consider school structure. Intially , consider , student id is key , later , should be searchable even with key name , later with grade.
- gopi.komanduri July 05, 2014 in India| Report Duplicate | Flag | PURGE
Analyst Algorithm Arrays C# C++ Coding Data Structures Dynamic Programming Experience Hash Table Large Scale Computing Linked Lists Problem Solving Sorting Trees and Graphs - 1of 3 votes
AnswersDesign a telephone directory for large ppl (he gave example like design for India). fields will be , first name , last name , number . this should be searchable with first name , last name , number as welll.
- gopi.komanduri July 04, 2014 in India
later added more complexity like do the same for organisation where even it contains designations. so this should be searchable with designations.| Report Duplicate | Flag | PURGE
Analyst Algorithm Arrays C C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures Dynamic Programming Hash Table Ideas Large Scale Computing Linked Lists Object Oriented Design Problem Solving Trees and Graphs - 5of 5 votes
AnswersGiven a self-balancing tree (AVL), code a method that returns the median.
- Diego May 16, 2014 in United States
(Median: the numerical value separating the higher half of a data sample from the lower half. Example: if the series is
2, 7, 4, 9, 1, 5, 8, 3, 6
then the median is 5.)| Report Duplicate | Flag | PURGE
Facebook iOS Developer Trees and Graphs - -2of 2 votes
AnswersHow to draw graph for the given set
- chetna.1695 May 14, 2014 in United States
G={(4,6,0,7),(2,0,8,5),(12,3,0,0),(0,0,9,8)}| Report Duplicate | Flag | PURGE
Trees and Graphs - 0of 0 votes
AnswersHe asked me to print root to leaf path WITHOUT using recursion . I got stuck at it and used too much space according to him .
- !@# May 02, 2014 in India
I constructed a visited array , path array and a stack .
Is there any other optimal algorithm ?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Trees and Graphs - 1of 1 vote
Answersa[] is an array containing elements of a BST .
- rahul May 02, 2014 in India
2D array is given where arr[i][j] gives the root of the tree formed by taking elements from index i to j from a[] . construct the BST .| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Trees and Graphs - 0of 0 votes
Answerspublic interface FirstCommonAncestor {
- gul2u April 30, 2014 in United States
/**
* Given two nodes of a tree,
* method should return the deepest common ancestor of those nodes.
*
* A
* / \
* B C
* / \ \
* D E M
* / \
* G F
*
* commonAncestor(D, F) = B
* commonAncestor(C, G) = A
*/
public Node commonAncestor(Node nodeOne, Node nodeTwo)
{
}
}
class Node {
final Node parent;
final Node left;
final Node right;
public Node(Node parent, Node left, Node right, data) {
this.parent = parent;
this.left = left;
this.right = right;
this.data = data
}
boolean isRoot() {
return parent == null;
}
}| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersAn UIView A2 is subclassed from the same parent as an UIView A1.
- valheru April 23, 2014 in United States
Given inputs of A1, A2, and an UIView that is in the tree of UIViews of A1 somewhere, return the exact UIView that mirrors this in A2.
Example setup:
A1------------
| |
UIView UIView
|
UIView <-- Given this
A2------------
| |
UIView UIView
|
UIView <-- Find/return this| Report Duplicate | Flag | PURGE
Facebook iOS Developer Trees and Graphs - 1of 1 vote
AnswersDisconnect two nodes in a graph by removing minimum number of edges.
- hulk April 20, 2014 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven two stations at random, show all possible routes between those stations (if any)
- static416 April 06, 2014 in Canada
- Stations links are listed below
- Links between stations are bi-directional
- Routes generated should not have cycles
cambridge<>stansted
stansted<> harlow
harlow<>london
london<>hatfield
hatfield<>peterborough
cambridge<>hatfield
cambridge<>ely
peterborough<>ely
peterborough<>birmingham
birmingham<>manchester
manchester<>glasgow
glasgow<>edinburgh
edinburgh<>newcastle
newcastle<>thirsk
thirsk<>york
york<>manchester
york<>peterborough| Report Duplicate | Flag | PURGE
Software Engineer / Developer Trees and Graphs - 3of 5 votes
AnswersGiven a Binary Tree (balanced or not) write a method that transforms the tree in a degenerate tree (basically a data structure like a sorted linked list where each node has the left child null) and returns the new root. This must be made in place, no external memory usage is allowed.
- Ray February 23, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Trees and Graphs - 1of 1 vote
AnswersWrite code to find the next least node in a binary search tree given a node?
- mav February 20, 2014 in United States| Report Duplicate | Flag | PURGE
Trees and Graphs - 1of 1 vote
AnswersOne of the many ways of representing a tree is to have an array(of length same as number of nodes), where each element in the node denotes the parent of that node.
- avinash February 18, 2014 in India
Eg -
{-1, 0, 0, 1, 1} would represent a tree with -
* 0 as root
* 1 and 2 as children of 0
* 3 and 4 as children of 1
Given a similar representation, you have to print reverse level order traversal of the corresponding tree.
Level order traversal of a tree is where we traverse levels of tree one by one.
Eg -
For the above given tree, level order traversal would be -
0
1 2
3 4
And hence, the reverse level order traversal is -
3 4
1 2
0
Please note -
* An element with parent = -1 is the root element.
* An element with the least index becomes the left most child. (ie. a node with always be on left of all its siblings that have higher index than it)
* When printing a level of tree you need to maintain left to right order.
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.
Output Format -
Print reverse level order traversal of the corresponding tree, with every new level starting in a different line.
Notes/Limits -
* 1 <= N <= 50
* There will be only one root element in any given test case
* Given numbers will always form a valid undivided tree
* Output should be in the exact format as specified (including whitespaces)
Sample Test Cases -
Input -
5
-1 0 0 2 1
Output -
4 3
1 2
0
Input -
9
8 7 0 5 5 8 7 0 -1
Output -
1 6
2 7 3 4
0 5
8
Input -
45
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
Output -
1 31
20 42 9 28
12 40 33 36
3 23 37 39 6 13 27 35
0 30 11 17 22 38 7 25
5 24 16 32 15 19
8 10 43 44 18 41
2 26 14 34
4 21
29
Input -
33
17 25 0 14 7 2 5 25 18 8 16 27 10 9 19 7 31 31 19 0 8 14 9 17 18 2 30 16 30 10 5 -1 27
Output -
13 22
26 28 4 15 9 20
6 30 1 7 3 21 8 24
5 25 14 18
12 29 11 32 2 19
10 27 0 23
16 17
31| Report Duplicate | Flag | PURGE
Flipkart Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven a binary search tree of n nodes, find all the pair of nodes whose sum is equal to a given number k in O(n) time and constant space.
- MaveRick12 February 12, 2014 in India| Report Duplicate | Flag | PURGE
Amazon Trees and Graphs - 0of 0 votes
AnswersDetermine if a tree is a valid BST with no duplicated values. (This means that if the binary tree has a duplicated number it should return "invalid" even if it's an actual BST)
- meh January 28, 2014 in United States
I gave an O(n) solution and interviewer seemed happy with it.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 2 votes
AnswersIn the Amazon Office, Employees are use to sit in cubical offices and all the offices are connected with some other offices, but they are not arranged in any well defined order. Offices are connected means they are sharing their walls with other offices. There are two types of Employees in Amazon i.e. 'Testers' and 'Developers'. Manager of Amazon don't want any 'Tester' and 'Developer' to sit in nearby cubical office, it means there should not be any shared wall between two 'Testers'/'Developers'.
- vinod January 24, 2014 in India
Input:- First line consist of an integer n, which is number of common walls.
Next n lines consist of 2 integers a and b, which represents the Office Number between which the wall is being shared.
Output: - Print 'Yes', if condition of the manager can be satisfied and print 'No' if not.
Example: -
1-2-3
|
4
Office number 2 is sharing its 3 walls with Office 1,3 & 4.....that is why if Office 2 has a 'Developer' than Office 1,3 & 4 cannot have any 'Developer'.
INPUT:-
3
1 2
2 3
2 4
Output: -
Yes
Any better approach then DFS i.e. O(V+E)..??| Report Duplicate | Flag | PURGE
Amazon Intern Trees and Graphs - 0of 0 votes
AnswersReplace each node with the sum of all greater nodes in a given BST?
- vinod January 21, 2014 in India| Report Duplicate | Flag | PURGE
Amazon Intern Trees and Graphs - 0of 0 votes
AnswersGiven a binary search tree whose nodes are integers, find the frequency of occurrence of each digit in the tree.tr
- lks January 07, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 3of 3 votes
AnswersGiven a binary tree. Modify it in such a way that after modification you can have a preorder traversal of it using only right pointers. During modification you can use right as well as left pointers. Write complete code and dry run it for some test cases
- behinddwalls December 08, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 0of 0 votes
AnswersFind cousins of a given node in a Binary tree and BST.
My Approach:
- behinddwalls December 07, 2013 in United StatesSteps:(Using level order Traversal) 1. Create a queue q and en-queue root element and take variable qSize and a flag=true 2. Start a loop and check queue is empty or not { if qSize==0 then qSize=q.size(); if not flag then print the current queue (q) Start one more loop and check for qSize>0 { qSize-- x=deque(); if((x.left != null && x.left== key) || (x.right!= null && x.right== key)) { flag=false continue } enqueue(x.left) enqueue(x.right) } }
| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - -6of 8 votes
AnswersGiven two Btrees. these trees "may" have right and left branches swapped. Now compare it
- Bee November 03, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 0of 2 votes
AnswersQuestion 1 / 1 (Path Explosion EASY)
- MJRocks October 04, 2013 in India
You were given a Binary Tree (not necessarily a Binary Search Tree) to play with, say T. T had some special properties
Each internal node in T had exactly 2 children
Each internal node in T was represented by an uppercase English alphabet (A-Z)
Each leaf node in T was represented by a lowercase English alphabet (a-z)
You were told remember T as long as you could. Hence, you memorised the string formed by traversing T in post-order. You used something similar to the pseudocode below
toPostOrderString (node)
if node is leaf
return node.value
else
T = ""
T = T + toPostOrderString(node.left)
T = T + toPostOrderString(node.right)
T = T + node.value
return T
Now, time has come to use that string again. The Eye has contacted you. Yes, the secret organisation mentioned in "Now you see me" ( don't tell anyone they are real !! )
You remember the string you memorised back then. You must reconstruct the binary tree T. You are also given a string A. All the characters of A are uppercase English alphabets. Let us assume that T has L leaves. Then, there will be exactly L paths from the root to the leaves - 1 unique path to each leaf.
You have to tell The Eye the number of paths out of L, on which, A exists as a sub-sequence. Look at the explanation for the Sample Case 1 for clarity.
You have to implement the method explodePaths in the code. explodePaths is passed the following parameters, respectively
N, the number of nodes in T
S, the string representation of the post-order traversal of T. Of course, the length of S will be equal to N.
K, the length of the string A
A, the string you must find in the paths from the root of T, to the leaves in T.
Note
It is not necessary that T is balanced. But, each internal node always has exactly 2 children. It is possible that both those children are internal nodes also. It is possible that only one of those children is an internal node.
For the given string S, because of the constraint that each internal node has exactly 2 children, you will always be able to determine the tree T, uniquely.
It is not necessary that all characters in T are unique. There may be several nodes with the same value.
In this problem statement, by sub-sequence we mean not necessarily contiguous. This is different from a sub-string.
Do not print the answer in explodePaths. Just return the value. The code-template interviewstreet provides does the input and output itself.
Consider the following tree
A
/ \
t B
/ \
/ \
B A
/ \ / \
x y a b
This tree is given in Sample Case 1 as
N = 9
S = "txyBabABA"
K = 2
A = "AA"
Now, there are 5 leaf nodes, and hence, 5 paths from the root to leaves - 1 for each leaf.
- A-t
- A-B-B-x
- A-B-B-y
- A-B-A-a
- A-B-A-b
Out of these 5 paths, you have to find the number of paths, on which "AA" exists as a sub-sequence. Of course, there are only 2 such paths
- A-B-A-a
- A-B-A-b
Hence the expected answer is 2.
In the same T above
The answer for A = "BB", is 2
The answer for A = "BA", is 2
The answer for A = "AB", is 4
The answer for K = 1 and A = "A", is 5
The answer for K = 1 and A = "B", is 4
The Sample Case 2 has a little more complicated T. The string S in Sample Case 2 is yeBgeuCBxAB.
Constraints
N ≤ 10000
K ≤ 100
The expected time complexity of the algorithm is O(N).| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven set of N threads generate sum of all numbers in an array of known size M
- vik October 04, 2013 in United States| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer / Developer Trees and Graphs - 2of 2 votes
AnswersQuestion 1 / 3 (Odd even level difference)
- Harjit Singh September 27, 2013 in India for TCS
You are given a function calcDifference which takes in the root pointer of a binary tree as it's input. Complete the function to return the sum of values of nodes at odd height - sum of values of node at even height. Consider the root node is at height 1
Sample Input:
Sample Output
-74
Explanation:
[ (1 + 4 + 5 + 6 + 7 ) ? (2 + 3 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15) = -74 ]| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm C++ Trees and Graphs