Trees and Graphs Interview Questions
- 0of 0 votes
AnswersGiven 2 quad-trees find the intersection of black-pixels.
- chandeepsingh85 September 26, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersDefine a quad-tree for a black and white image. Count the number the of black pixels.
- chandeepsingh85 September 26, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 2of 2 votes
AnswersYou are given a grid, with points on the intersections (think a map of streets, people are standing on random corners). Write code to calculate the point on the grid that is the shortest distance from every point on the grid.
- chandeepsingh85 September 26, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 4of 4 votes
AnswersWe are given a set of integers with repeated occurences of elements. For Example, S={1,2,2}.
- sc.shobhit September 14, 2013 in India
We need to print the power set of S ensuring that the repeated elements of the power set are printed only once.
For the above S, the power set will be {NULL, {1}, {2}, {2}, {1,2}, {1,2}, {2,2}, {1,2,2}}. So, as per the question requirements, we need to print {NULL, {1}, {2}, {1,2}, {2,2}, {1,2,2}}| Report Duplicate | Flag | PURGE
Facebook Intern Algorithm Coding Trees and Graphs - -1of 1 vote
Answerswrite a program to find sum of any path from root to leaf such that the sum of all nodes along the PATH is max compared to all other path,,
- samy August 30, 2013 in United States| Report Duplicate | Flag | PURGE
Trees and Graphs - 0of 0 votes
AnswersWrite a routine to verify if a given tree is a BST (Binary Search Tree).
- Eugene August 21, 2013 in United States| Report Duplicate | Flag | PURGE
Trees and Graphs - 3of 3 votes
AnswersA standard chess knight (it moves in its standard way i.e. L shaped OR 2.5 moves) is sitting at the position a1 on an N x N chess board. What is the minimum number of moves it will take to reach the diagonally opposite corner?
- Saurabh Singhal August 17, 2013 in India
P.S. - If it were a 8 x 8 chess board, the final destination for the knight would be h8| Report Duplicate | Flag | PURGE
Goldman Sachs Intern Algorithm Coding Data Structures Trees and Graphs - 1of 1 vote
AnswersGiven a BST convert it into new Data Structure that satisfies following conditions:
- saran August 13, 2013 in India
1. every leaf node's left ptr point to its parent and right ptr points to the next leaf
2. every non leaf node's left ptr points to its parent and right ptr is NULL
3. return the head and print the new DS
example:
7
/ \
5 9
/ \ \
4 6 10
output:
head->4->5->7
|
->6->5->7
|
->10->9-7
with optimal time and space complexity| Report Duplicate | Flag | PURGE
Groupon Intern Trees and Graphs - 1of 1 vote
Answerscreate the mirror tree for the given BST, provided with the root node of the tree
- saran August 10, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Intern Trees and Graphs - 2of 2 votes
AnswersWAP to create a mirror of a binary tree. Extend the code or write a new code if not possible to do mirroring at alternate levels . Here in the second part , if the two trees are placed in front of each other , then odd levels should be exact mirror as a whole and even levels should be exactly same . Then write the iterative version for the above codes.
- Kavish Dwivedi July 15, 2013 in India for Bangalore| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 0of 0 votes
Answersconsider a full tree.Every node at odd level has 3 children and every node at even level has 4 children. If root is at level one, derive number of nodes if the leaf nodes are at level k.
- theultimatevella July 14, 2013 in India| Report Duplicate | Flag | PURGE
Trees and Graphs - 0of 4 votes
AnswersConstruct a BST from inorder and preorder traversal string. Write code for it.
- yolo July 11, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - -11of 11 votes
AnswersGiven a tree, verify if it contains a subtree.
- yolo July 11, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 0of 0 votes
AnswersGiven a binary tree with each node having a pointer to its parent, Write a function that can find the immediate right neighbor of a given node. Don't use BFS.
- JSDUDE June 27, 2013 in United States
Node* RightNeighbor(Node* node)
Note: Root of the tree is not given| Report Duplicate | Flag | PURGE
Ebay SDE1 Trees and Graphs - 0of 0 votes
AnswersWrite a program to check if one tree is a subtree of other or not.
- getprith June 24, 2013 in India| Report Duplicate | Flag | PURGE
Applications Developer Trees and Graphs - 2of 2 votes
AnswersGiven a family tree for a few generations for the entire population and two people write a routine that will find out if they are blood related. Siblings are blood related since they have the same parents. Cousins are blood related since one of their parents have the same parents etc. Design the data structure first and then write the routine.
- hsantosh71 June 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersN nodes, each node consists of a couple fields and methods. These are:
- JSDUDE June 13, 2013 in United States
int id; //every node has an ID. All of these IDs are sequential, and begin with 0. I.e. all ids are uniquely in the range of 0 t N-1
int val; //every node has a value
int max; //max = N. Every node knows how many nodes are in the system.
void send(int idTo, int payload)
int recv(int idFrom)
Write a single piece of code which runs on every node simultaneously, such that when it is finished running every node in the system knows the sum of the values of all the nodes in the system.| Report Duplicate | Flag | PURGE
Ebay Software Engineer / Developer Trees and Graphs - 5of 5 votes
AnswersGiven a binary tree.
Print nodes of extreme corners of each level but in alternate order.10 5 11 9 20 - 15 14 - - - 25 30
then output should be 10,11,9,25,30
- SK June 09, 2013 in India
left most of 0th level
right most of 1st level
left most of 2nd level
& like this| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm Trees and Graphs - -5of 7 votes
Answersneed to implement a weather report functionality. user will provide the city name , need to return the weather report.
- gopi.komanduri May 29, 2013 in India
if weather station exists n functioning properly , will return the weather report of that station .
else ,
will return the nearest available weather station report.
interviewer looking for optimized manner.
looking for datastructures to stores the cities n algo to return the report.| Report Duplicate | Flag | PURGE
Mentor Graphics Analyst Algorithm Arrays Bit Manipulation Brain Teasers C C# C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures Dynamic Programming General Questions and Comments Graphics Hash Table Ideas Linked Lists Math & Computation Object Oriented Design Problem Solving Sets Sorting Stacks String Manipulation Terminology & Trivia Threads Trees and Graphs XML - 0of 0 votes
AnswersMax distance between two nodes of binary tree. Distance is # of branches.
- Huwanda May 10, 2013 in United States| Report Duplicate | Flag | PURGE
VMWare Inc Member Technical Staff Algorithm Data Structures Trees and Graphs - 0of 0 votes
Answerswrite a program to serialize and deserialize a Binary tree
- VJ May 06, 2013 in India| Report Duplicate | Flag | PURGE
VMWare Inc Member Technical Staff Algorithm Arrays Data Structures Trees and Graphs - 0of 0 votes
Answerswrite a program to return the highest value from a binary tree (note: not BST)
- VJ May 06, 2013 in India| Report Duplicate | Flag | PURGE
VMWare Inc Member Technical Staff Algorithm Data Structures Trees and Graphs - 0of 0 votes
Answerswrite a program to validate a BST and state the complexity (assume payload is integer values)
- VJ May 06, 2013 in India| Report Duplicate | Flag | PURGE
VMWare Inc Member Technical Staff Algorithm Data Structures Trees and Graphs - 2of 2 votes
AnswersGiven a binary tree, print its perimeter:
- JSDUDE May 04, 2013 in United States
node, left->most nodes from top to bottom, leaf nodes from left-> right, right->most nodes from bottom to top
----------------------------1
-----------------------2--------3
------------------4-----5-----6--------7
-------------8------9-----10------11-----12
should print:
1-2-4-8-9-5-10-11-12-7-3
5 because it doesn't have any children. 10 and 11 are children of 6 and 8 & 9 are children of 4.
Apologies for the messy diagram.| Report Duplicate | Flag | PURGE
Microsoft SDE1 Trees and Graphs - 0of 0 votes
AnswersGiven a Binary tree and a node, return it's post-order predecessor
- JSDUDE May 04, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE1 Trees and Graphs - 0of 0 votes
AnswersGiven a BT and 2 nodes, find LowestCommonAncestor
- JSDUDE May 04, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE1 Trees and Graphs - 0of 0 votes
AnswersImplement:
1. a search that will return all the strings that match a sub-string
2. an insert into this datastructure
- JSDUDE May 04, 2013 in United StatesClass { Insert (string str){}; List<strings> Predictions(string subString){}; }
| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 0of 0 votes
AnswersImplement an iterator for a Binary tree. It should have the following things:
- JSDUDE May 04, 2013 in United States
1. bool HasNext()
2. <T> Next()
It should be an in-order traversal.| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 0of 0 votes
AnswersGiven a BST find Ceiling value of given key
8 6 12 2 4 11 14
key = 8 return 11
- JSDUDE April 27, 2013 in United States
key = 1 return 2
key = 16 return Null
Iteration and Recursion both| Report Duplicate | Flag | PURGE
Microsoft SDE1 Trees and Graphs