Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

the ans is: 1ms * height of binary tree

- ise2016013@iiita.ac.in August 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
The tree will burn in k ms, where k is the diameter of the tree.
The below is not a formal proof ( and may be wrong!)

Find the diameter (k) of the tree and let the sequence of nodes
{N0, N1, N2,..Nj, Nj+1, ..,Nk} lie on the diameter (path).
Let us consider the following possibilities how the fire could be
started

Case (1):
The fire could be lit at node N0 or Nk and would take the
maximum hops to reach the other end of the diameter.
Also, think of the intermediate burnt state of the tree
where the fire has reached node Nj. Now the remaining part
of the diameter left intact is k-j. Can there exist any reachable
node at a distance greater than k-j from Nj ? The answer is no.
Because, this would be contradict the definition of diameter.
If such a node existed, then it would be included on/in the diameter
path. We can safely conclude that all nodes reachable from Nj will
burn before the fire reaches the other end of the diameter, Nk.
It is clear in this case that the fire would consume the tree in
just k ms

Case (2):
The fire is started at a leaf node, Nx, not in {N0, N1, N2,..Nj, Nj+1, ..,Nk}
In this case, the fire has to eventually reach a node on the diameter path.
Let the fire with source at Nx reach Nj on the diameter path. Let the difference
between path length (N0..Nj) and path length (Nx...Nj) be D'.
After reaching Nj, the fire will continue towards Nk will will take
path length ( Nj.. Nk) ms. So the tree will be consumed in (k MINUS D') ms

*/

- Makarand August 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maximum would be 1ms * 2 * hight_of_the_Tree

In a perfectly balanced tree, we can start from the most far right leaf, it burns up to the root, then goes down to the far most left leaf.

- IB August 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming we are given parent pointer in the tree:
Apply DFS from the leaf node (including the parent), add 1 ms for all nodes in your path until you reach end and recurse back to node where you started. Node keeps max cost after recursive return to itself, and returns that to its calling node. Once reached back to the leaf node, returned cost is the answer.

- gumanji August 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it will be equal to the distance from the starting leafnode(from the start point of fire) to the farthest leafnode in the tree. You can easily find that by doing a BFS from the leafNode and the lastNode visited during the BFS will be the farthest leafnode.

- Anonymous October 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It will be equal to the l + s where l and s are the longest and shortest paths from the root to leaf node respectively. No need for bfs. As there is only one path in the tree to reach from one node to another. The proof is obvious.

- vijaykumar.csenitj January 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The time required : - maximum distance of a node from the starting node.

- Narendra July 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <bits/stdc++.h>
using namespace std;

struct Node {
int data;
Node *left, *right;
};

Node* newNode(int data) {
Node *temp = new Node();
temp->data = data;
temp->left = NULL;
temp->right = NULL;

return temp;
}

int minTimeUtil(unordered_map<Node*, int> &minTime ,Node *root) {
if(root) {
minTimeUtil(minTime, root->left);
minTimeUtil(minTime, root->right);

if(root->left == NULL && root->right == NULL)
minTime[root] = 1;
else {
minTime[root] = min(root->left!=NULL?minTime[root->left]:INT_MAX, root->right!=NULL?minTime[root->right]:INT_MAX) + 1;
}
}
}

int main()
{
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->right = newNode(8);
root->left->left->left = newNode(6);
root->left->left->right = newNode(7);

unordered_map<Node*, int> minTime;
minTimeUtil(minTime, root);

int ans = 0;
for(auto n:minTime) {
cout<<n.first<<" "<<n.second<<endl;
ans = max(ans, n.second);
}
cout<<ans<<endl;

return 0;
}

- manjuransari143 September 07, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we are giving particular node(leaf) from which it is starting to burn.............Then total time required to burn whole tree will be equal to
" Max distance of another leaf from that node "
In worst case, it will be equal to 2* Height(Binary tree)

- Abhijeet Singh September 17, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More