## unknown Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

``````public class Solution {

public static class Node {
int value;
Node left;
Node right;
}

public int timeTilBurns(Node root, Node start) {
if (root == null || start == null) return 0;

Map<Node, Node> nodesAndParents = new HashMap();
findParensForAllNodes(root, null, nodesAndParents);

int time = 0; // current moment

List<Node> currentBurningNodes = new ArrayList() {{ add(start); }};

while (!nodesAndParents.isEmpty()) {

List<Node> newCurrentBurningNodes = new ArrayList();

// infect neighbours
while (!currentBurningNodes.isEmpty()) {

Node currentBurning = currentBurningNodes.remove(0);

Node parent = nodesAndParents.get(currentBurning);

nodesAndParents.remove(currentBurning);
}

time++;
currentBurningNodes = newCurrentBurningNodes;
}

return time;
}

public void findParensForAllNodes(Node node, Node parent, Map<Node, Node> map) {
if (node != null) {
map.put(node, parent);
findParensForAllNodes(node.left, node, map);
findParensForAllNodes(node.right, node, map);
}
}
}``````

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

O(n) approach -

``````public static void main(String[] args){

T N10 = new T(12, null, null);
T N9 = new T(11, null, null);
T N8 = new T(3, N10, null);
T N7 = new T(10, null, null);
T N6 = new T(9, null, null);
T N5 = new T(8, null, null);
T N4 = new T(7, N8, N9);
T N3 = new T(6, N6, N7);
T N2 = new T(5, N4, N5);
T N1 = new T(4, N2, N3);

int startFire = 9;
height(N1);
int left = catchFire(N1.left, startFire, -1);
if(left == -1)
left = N1.leftHt-1;
else
left = N1.leftHt - left;

int right = catchFire(N1.right, startFire, -1);
if(right == -1)
right = N1.rightHt-1;
else
right = N1.rightHt - right;

System.out.println((left+right+1));

}

public static int catchFire(T node, int startFire, int fireHt){
if(node == null)
return fireHt;

fireHt = catchFire(node.left, startFire, fireHt);
fireHt = catchFire(node.right, startFire, fireHt);

if(node.left != null && node.left.val == startFire)
fireHt = node.height-1;
if(node.right != null && node.right.val == startFire)
fireHt = node.height-1;

return fireHt;
}

public static void height(T node){
if(node == null)
return;
height(node.left);
height(node.right);

if(node.left != null && node.right != null){
node.height = Math.max(node.left.height, node.right.height) +1;
node.rightHt = node.right.height +1;
node.leftHt = node.left.height +1;
}
else if(node.left != null){
node.height = node.left.height+1;
node.leftHt = node.left.height+1;
}
else if(node.right != null){
node.height = node.right.height+1;
node.rightHt = node.right.height+1;
}
}

static class T{
int val;
T left;
T right;
int height;
int rightHt;
int leftHt;

public T(int val, T left, T right){
this.val = val;
this.left = left;
this.right = right;
}
}``````

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

probably there is no parent pointer in the node, since the problem would be trivial that way (as mentioned in the question).

Maybe some observations are interesting:
- If the fire starts at the root, it takes the trees hight time. to burn down the whole tree.
- If the fire starts on the left branch of the root, it takes max(height of the left branch, 2 + height of right branch)
- we can recursively formulate the problem for each root:

``````if it starts the fire:
burn-time = max(height(left) + 1, height(right) + 1)

if it doesn't start fire, but one of it's sub-trees start the fire:
burn-time = max(burn-time-fire-starting sub-tree, height other sub-tree + 1 + distance from fires-tarting node + 1)
if it doesn't start the fire and neither the left nor the right subtree starts the fire:
return the height (max left-height, right-height)``````

in code, if I didn't miss a count, that's the kind of things one should better check carefully, but i actually only wanted to post the idea

``````struct BurnDownState {
int height; // height of (sub)tree
int distFromFireStart; // if tree starts fire, distance to the fire starting node
int burnDownTime; // time needed to burn that tree
};
BurnDownState burnDownTimeRec(Node* root, Node* fireStart)
{
if(root == nullptr) return {0, -1, -1};
auto ls = burnDownTime(root->left, fireStart);
auto rs = burnDownTime(root->right, fireStart);
if(root == fireStart) {
return {1 + max(ls.height, rs.height), 0, max(ls.height, rs.height)};
}
if(rs.distFromFireStart >= 0) swap(ls, rs); // avoid redundant code below for rs
if(ls.distFromFireStart >= 0) {
return {1 + max(ls.height, rs.height), ls.distFromFireStart + 1,
max(ls.burnDownTime, ls.distFromFireStart + 1 + rs.height)};
}
return {1 + max(ls.height, rs.height), -1, -1};
}

int burnDownTime(Node* root, Node* fireStart)
{
return burnDownTimeRec(root, fireStart).burnDownTime;
}``````

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

I would solve this problem using recursion. I haven't tested the code but I think it should illustrate the idea.

``````const timeToCatchFire = (stack, cycle = 1, visited = new Set()) => {
const newGen = [];
for(node of stack) {
}
if(newGen.length > 0)
return timeToCatchFire(newGen, cycle + 1, visited);
else
return cycle;
}

if(node.parent && !visited.has(node.parend))
stack.push(node.parent);
if(node.parent && !visited.has(node.parend))
stack.push(node.parent);
if(node.parent && !visited.has(node.parend))
stack.push(node.parent);
}``````

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.

### 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.