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);
                
                // add infected nodes
                Node parent = nodesAndParents.get(currentBurning);
                if (parent != null) newCurrentBurningNodes.add(parent);
                if (currentBurning.left != null) newCurrentBurningNodes.add(currentBurning.left);
                if (currentBurning.right != null) newCurrentBurningNodes.add(currentBurning.right);

                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); 
        }
    }
}

- sandak October 10, 2017 | Flag Reply
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;
	    }
	  }

- sudip.innovates October 11, 2017 | Flag Reply
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;
}

- ChrisK October 11, 2017 | Flag Reply
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) {
        addAdjacents(node, newGen, visited);
    }
    if(newGen.length > 0)
        return timeToCatchFire(newGen, cycle + 1, visited);
    else
        return cycle;
}

const addAdjacents = (node, stack, visited)  => {
    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);
}

- Anonymous October 15, 2017 | 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