## Trees and Graphs Interview Questions

- 0of 0 votes

AnswersImagine you have a computer keyboard that has all the letters mismatched

- klausv December 23, 2018 in United States

example:

typing q gives you a

typing w gives you b

all 26 letters in the alphabet are there, but typing one letter will give you another one

you are asked to write an algorithm to find whatever word you tried to type and count how many cycles you did to find the word

a restriction was set you need to type the whole word every time, not go character by character

note: a graph was suggested to represent the letter mappings| Report Duplicate | Flag | PURGE

Amazon SDE-2 Trees and Graphs - 0of 0 votes

AnswersThere are N nodes in a graph connected by exactly N-1 edges. There is exactly 1 shortest path from one node to any other node. The nodes are numbered from 1 to N. Given Q queries which tell source node and the destination nodes. Find the most visited node after traveling those Q paths. For example, say Q=3

- sudhiammula November 23, 2018 in India

and 3 queries are

1 5

2 4

3 1

So travel from node 1 to node 5, then from node 2 to node 4, then from node 3 to node 1. Finally, find what is the most visited node after the Q queries.

Finding every path and incrementing every visited node count is a naive solution. The interviewer asked me to optimize it.| Report Duplicate | Flag | PURGE

Samsung SDE1 Trees and Graphs - 1of 1 vote

AnswersGiven an array of integers, find out how many unique BST can be generated from the array.

- kieth October 07, 2018 in United States| Report Duplicate | Flag | PURGE

Google SDE1 Trees and Graphs - 0of 0 votes

AnswersFirst common Ancestor of Binary tree . Java Solution needed.

- sarunreddy82 May 11, 2018 in United States

Class Node {

Node Parent;

Node LeftChild;

Node rightChild;

int val;

}

publlic Node firstAncestor(Node leftNode, Node rightNode){

// We don't get the root node here. From left and right child we need to find it's parent and find the lowest common ancestor.

}| Report Duplicate | Flag | PURGE

xyz Trees and Graphs - 1of 1 vote

AnswersGiven a binary tree, where each node represents an integer, find the max value of path sum.

- LeetCoder May 07, 2018 in United States| Report Duplicate | Flag | PURGE

Facebook Android Engineer Trees and Graphs - 1of 1 vote

AnswersSuppose you have a list of tasks which need to be executed. Some of these tasks have dependencies which must be executed before they are. Please provide a method which, when given a list of tasks, will provide a valid ordering in return.

- prasad.hybris May 02, 2018 in United States

Example:

Input: [ A, B, C, D ]

A <- B, C

B <- C, D

D <- C

Return: [ C, D, B, A ]| Report Duplicate | Flag | PURGE

Google Technical Support Engineer Trees and Graphs - -1of 1 vote

AnswersDefine a class 'Space' which has a member string variable that indicates if the space is a "tree", a "house" or an empty space and another member variable that will store the 'space neighbors' (left, right, up and down only)

- d4niel February 27, 2018 in United States

Given a 'Grid' (list) of Spaces write the code for the findAll(start) method to find all the trees and houses given a 'Space' as start point

Example, Grid of 'Spaces':

T 0 0 H 0

0 0 0 0 0

H H T H 0

Where Ts are trees and Hs are houses| Report Duplicate | Flag | PURGE

Facebook Software Engineer Trees and Graphs - 0of 0 votes

AnswersGiven a Tree where each node contains an attribute say color(R,G,B... etc). find subtree with maximum number of attributes.

- smartbobby2K February 15, 2018 in United States

Input:

G

/ \

B R

/ \ / \

B B R R

/ \ / \

B R R R

Output:

Input:

R

/ \

R R

\ / \

R R R| Report Duplicate | Flag | PURGE

Microsoft Software Developer Trees and Graphs - 0of 0 votes

Answerslet's say you're given an arbitrary list of relations r1 and r2 from objects in a set of arbitrary size. find the size of th largest subset with the property that no two are related. for e.g., given set S = {a,b,c,d,e,f} and relations {a,d}, {b,c}, {a,c}, {a,e}, find the subset of S such that no two a connected.

- jablaboo November 12, 2017 in United States| Report Duplicate | Flag | PURGE

Google Trees and Graphs - 0of 0 votes

AnswersGiven a root to a binary tree, find the level of the tree with the minimum sum.

- Ladym October 10, 2017 in Israel

for example:

50

/ \

6 2

/ \ /

30 80 7

the answer is: level 2| Report Duplicate | Flag | PURGE

Microsoft Junior programmer Trees and Graphs - 2of 2 votes

AnswersA binary tree is started burning from a leaf node. What is the time(1ms to burn from node to node) it takes to entire tree get burned? The fire will spread to all the paths from a node.

- SIVA R August 20, 2017 in United States| Report Duplicate | Flag | PURGE

Trees and Graphs - 0of 0 votes

AnswersGiven a binary tree, write a recursive method boolean method(int x, int y) which will return true

- bojanlozanovski77 August 16, 2017 in United States

1. if node y (meaning a node with a value of int y) is a node that is contained in one of the two possible subtrees of x,

2. true if x==y, and a node with a value x==y exists, otherwise

3. return false,

basicallly whether x contains y? I had a question like this on my exam, I solved this problem using four arguments in my function. I wonder whether it is even possible to solve it with only 2 int arguments and recursively.| Report Duplicate | Flag | PURGE

Trees and Graphs - 0of 0 votes

AnswersGiven a list/array of "Assign" trees with integers, operators and variables, return the result of the requested "Result" tree expression.

Example:

- thetinysheep August 13, 2017 in United States`"Assign" / \ "x" "+" / \ 2 3 "Assign" / \ "y" "-" / \ 5000 30 "Assign" / \ "z" "*" / \ 50 x "Return" \ "-" / \ z "*" / \ 1 y`

| Report Duplicate | Flag | PURGE

Facebook Software Developer Trees and Graphs - 0of 0 votes

AnswersI've got these trees of integers; they're like regular trees, but they can share nodes.

- NinjaCoder July 20, 2017 in United States

I need to know if any branch of this tree sums to 100.

7

/ \

8 6

/ \ / \

2 3 9

/ \ / \ / \

5 4 1 100

Follow up question was how would you change the code to handle negative numbers.| Report Duplicate | Flag | PURGE

Amazon Software Engineer Trees and Graphs - 0of 0 votes

AnswersFind distance between any two nodes of binary tree and binary search tree.

- Raje July 19, 2017 in India| Report Duplicate | Flag | PURGE

Amazon SDE-2 Trees and Graphs - 0of 0 votes

AnswersGiven a binary tree of integers, write code to store the tree into a list of integers and recreate the original tree from a list of integers.

- Null0 May 13, 2017

Here's what your method signatures should look like (in Java):

List<Integer> store(Node root)

Node restore(List<Integer> list)

Example Tree:

5

/ \

3 2

/ / \

1 6 1| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm Data Structures Java Trees and Graphs - 0of 0 votes

AnswersYou are given a NxN boolean matrix, where matrix(i,j) will be one if 'i' is a parent of 'j' in a tree, otherwise, it is zero.

- sonesh May 11, 2017 in United States

Construct this tree.| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm Trees and Graphs - 0of 0 votes

AnswersYou are given an array of nodes where each node consists of node name, isValid flag, and parent Node index. so, this array actually represents a tree(forest). where root node has -1 as its index for the parent node. rest all node have their parent's index value.

- sonesh May 08, 2017 in United States

You will be given this array and an index. You have to cut down the subtree from the index. Cutting down a tree means, making all the nodes of that subtree false(Isvalid flag).

He was expecting O(N) solution.| Report Duplicate | Flag | PURGE

Two Sigma Software Engineer / Developer Arrays Coding Trees and Graphs - 0of 0 votes

AnswersQ 4. You are given a binary tree, and you have to return list of lists of node. where same level nodes should be in the same list, nodes are in opositive order in next list from the previous list

Ex:`4 / \ 3 5 / \ \ 1 10 -4`

Output would be

- sonesh April 28, 2017 in United States

[[4], [5, 3], [1, 10, -4]]

Desigred Complexity : O(N) + O(N).| Report Duplicate | Flag | PURGE

Hitachi Data Systems Software Engineer / Developer Linked Lists Stacks Trees and Graphs - 0of 0 votes

AnswersYou are given a BST of integers and an integer K. You have to find the smallest greater integer then K in the BST.

Ex

- sonesh April 20, 2017 in United States`40 --- 50 --- 80 | | | 45 20 --- 30 | | 10 K = 35 Output: 40`

| Report Duplicate | Flag | PURGE

Hitachi Data Systems Software Engineer / Developer Trees and Graphs - 2of 2 votes

AnswersGiven the following set of strings, write a function that stores this information.

- JSDUDE April 19, 2017 in United States

// /Electronics/Computers/Graphics Cards

// /Electronics/Computers/Graphics Cards

// /Electronics/Computers/SSDs

// /Electronics/Computers/Graphics Cards

// /Electronics/Computers/SSDs

// /Electronics/TVs

// /Electronics/Computers/Graphics Cards

// /Electronics/TVs

// /Electronics/TVs

// /Garden

// /Automotive/Parts

Your datastructure should be able to provide information as such:

// / = 11

// /Electronics = 9

// /Electronics/Computers = 6

// /Electronics/Computers/Graphics Cards = 4

// /Electronics/TVs = 3

// etc

// ["/Electronics/Computers/Graphics Cards", "/Garden"]| Report Duplicate | Flag | PURGE

NVIDIA Senior Software Development Engineer Data Structures Trees and Graphs - 0of 0 votes

AnswersQ1. You are given a binary search tree (with unique values) and two values. You need to find their lowest common ancestor. (Expected Complexity O(log(n)) + O(1))

- sonesh April 13, 2017 in United States

Q2. Now let's assume the tree has duplicates, and when a duplicate number come, the insertion logic chooses left node. (Expected Complexity O(log(n)) + O(1))

Q3.Now let's assume the input tree is a binary tree instead of the binary search tree.(Expected Complexity O(n) + O(1))| Report Duplicate | Flag | PURGE

Bloomberg LP Software Engineer / Developer Trees and Graphs - 0of 0 votes

Answers/**

* A tournament tree is a binary tree

* where the parent is the minimum of the two children.

* Given a tournament tree find the second minimum value in the tree.

* A node in the tree will always have 2 or 0 children.

* Also all leaves will have distinct and unique values.

* 2

* / \

* 2 3

* / \ | \

* 4 2 5 3

*

* In this given tree the answer is 3.

*/

- lkpunisher April 05, 2017 in United States`class Node { Integer value; Node left, right; Node(Integer value, Node left, Node right) { this.value = value; this.left = left; this.right = right; } } class Solution { /** * This should return the second minimum * int value in the given tournament tree */ public static Integer secondMin(Node root) { } }`

| Report Duplicate | Flag | PURGE

Linkedin Senior Software Development Engineer Trees and Graphs - 0of 0 votes

Answersfind the given Binary tree is mirrored tree or not

- Jagadeesh March 12, 2017 in India for Kindle

should be like

60

/ \

30 30

/ \ / \

20 50 50 20| Report Duplicate | Flag | PURGE

Amazon SDE-2 Trees and Graphs - 0of 0 votes

AnswersGiven a BST (Binary Search Tree) , Each node value should replace with sum of the node which are greater-than the given node.

- Jagadeesh March 12, 2017 in India for Kindle

conditions :

No Extra space / variable can use

Modify the existing tree in optimal way.| Report Duplicate | Flag | PURGE

Amazon SDE-2 Trees and Graphs - 2of 2 votes

AnswersGiven a Binary tree and value X. Find X in the tree and return its parent

- neelabhsingh January 18, 2017 in India for Hyderabad

X:

10

4 3

5 7 9 8

If X = 7, return 4| Report Duplicate | Flag | PURGE

Amazon SDE-2 Trees and Graphs - -4of 4 votes

Answersna

- Anonymous January 10, 2017 in United States| Report Duplicate | Flag | PURGE

Trees and Graphs - -3of 3 votes

AnswersConvert an unordered tree to a binary tree

- mh4wt@virginia.edu December 18, 2016 in United States| Report Duplicate | Flag | PURGE

Microsoft Intern Java Trees and Graphs - 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

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window