Amazon Interview Question for SDE-2s


Country: United States




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

I assume you want to traverse the node level order, and store the same in new singly linked list.

We can achieve it using simple queue,

- Maddy September 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not O(1) space as required

- zortlord September 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void connect(Node root) {
	if(root != null)
		connect(root, 0, new Vector<Node>());
	
}

void connect(Node root, int level, Vector<Node> links) {
	
	Node prev = null;
	prev = links.get(level);
	if(prev != null) {
		prev.next = root;
	}
	links.replace(level, root);
	if(!isLeaf(root)) {
		if(root.left != null)
			connect(root.left, level + 1, links);
		if(root.right != null)
			connect(root.right, level + 1, links);
	}

}

- Noobie September 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not O(1) memory. Recursion uses memory too.

- zortlord September 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just do a pre-order or in-order traversal and keep a vector. Time O(n). Space O(log n)

- Obama September 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

not O(1) space as required.

- zortlord September 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi.. I have a doubt on this question.
By 'connect' do you mean that each node must store a reference to all nodes at the same level?

If yes, then this reference storage itself cannot be achieved in O(1) space because as the height of the tree increases, every node will have more number of peers.

It would be helpful to think about this problem if you can explain.

Thanks,
Pravin

- june.pravin September 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in O(n) with O(1) space by doing the following (in java)

class Node{
    int data;
    Node left, right, nextRight;
}

public static void setupLevels(Node leftMost){
    Node lastOnLevel, nextOnLevel, firstOnLevel;
    //while still computing levels
    while(leftMost != null){
        //while there are still Nodes in the parent level
        while(leftMost != null){
            //if there is a new left child to consider
            nextOnLevel = leftMost.left;
            if(nextOnLevel != null){
                //if there is a previous child, attach the last child to the new one
                if(lastOnLevel != null){
                    lastOnLevel.nextRight = nextOnLevel;
                }
                lastOnLevel = nextOnLevel;
            }
            //capture the first non-null child
            if(lastOnLevel != null && firstOnLevel == null){
                firstOnLevel = lastOnLevel;
            }

            //if there is a new right child
            nextOnLevel = leftMost.right;
            if(nextOnLevel != null){
                //if there is a previous child, attach the last child to the new one
                if(lastOnLevel != null){
                   lastOnLevel.nextRight = nextOnLevel;
                }
                lastOnLevel = nextOnLevel;
            }
            //capture the first non-null child
            if(lastOnLevel != null && firstOnLevel == null){
               firstOnLevel = lastOnLevel;
            }
            
            //move to the next parent
            leftMost = leftMost.nextRight;
        }
        //prep for the next level
        leftMost = firstOnLevel;
        firstOnLevel = null;
        lastOnLevel = null;
    }
}

- zortlord September 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Node
{
	int value;
	Node left;
	Node right;
	Node next;
}
public void connectNodes(Node n)
{
	if(n==null)
	{
		return;
	}
	Node rightSibling=getNextSiblingChild(n.next);//Iteratively visit the right sibling of n until we find a node that has at least one child.
	if(n.left!=null && n.left!=null)
	{
		n.left.next=n.right;
		n.right.next=rightSibling;
	}else if (n.left!=null && n.right==null)
	{
		n.left.next=rightSibling;
	}else if (n.right!=null && n.left==null)
	{
		n.right.next=rightSibling;
	}
	connectNodes(n.left);
	connectNodes(n.right);
	
}

private Node getNextSiblingChild(Node n)
{
	while(n!=null)
	{
		if(n.left!=null)
		{
			return n.left;
		}else if(n.right!=null)
		{
			return n.right;
		}
		n=n.next;
	}
}

//O(n) time. O(1) space.

- divm01986 September 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not O(1) memory. You are using recursion and that requires memory too.

- zortlord September 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void connectSameLevelNodes() {

        if (root == null) {
            return;
        }

        int maxDepth = findMaxDepth(root, 0);
        System.out.println("MAX DEPTH " + maxDepth);

        for (int i = 1; i < maxDepth; i++) {
            connectNodesOnSameLevel(root, 0, i, null); 
        }
    }

    private Node connectNodesOnSameLevel(Node root, int currentDepth, int level, Node previousNode) {
        if (root == null) {
            return previousNode;
        }

        if (currentDepth == level) {
            if (previousNode == null) {
                return root;
            } else {
                previousNode.nextRight = root;
                return root;
            }
        } else {
            Node left = connectNodesOnSameLevel(root.left, currentDepth + 1, level, previousNode);
            previousNode = connectNodesOnSameLevel(root.right, currentDepth + 1, level, left == null ? previousNode : left);
        }

        return previousNode;
    }

    private int findMaxDepth(Node root, int depth) {
        if (root == null) {
            return depth;
        }

        return Math.max(findMaxDepth(root.left, depth + 1), findMaxDepth(root.right, depth + 1));
    }

- Ryan October 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void connectSameLevelNodes() {

        if (root == null) {
            return;
        }

        int maxDepth = findMaxDepth(root, 0);
        System.out.println("MAX DEPTH " + maxDepth);

        for (int i = 1; i < maxDepth; i++) {
            connectNodesOnSameLevel(root, 0, i, null); 
        }
    }

    private Node connectNodesOnSameLevel(Node root, int currentDepth, int level, Node previousNode) {
        if (root == null) {
            return previousNode;
        }

        if (currentDepth == level) {
            if (previousNode == null) {
                return root;
            } else {
                previousNode.nextRight = root;
                return root;
            }
        } else {
            Node left = connectNodesOnSameLevel(root.left, currentDepth + 1, level, previousNode);
            previousNode = connectNodesOnSameLevel(root.right, currentDepth + 1, level, left == null ? previousNode : left);
        }

        return previousNode;
    }

    private int findMaxDepth(Node root, int depth) {
        if (root == null) {
            return depth;
        }

        return Math.max(findMaxDepth(root.left, depth + 1), findMaxDepth(root.right, depth + 1));
    }

- Ryan October 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A little deviation from the above approach, I am also using recursion to link the nodes at the same level.
Approach is to use recursion to reach the desired level and if the left child and right child both are not null then running through the next pointers of the left child until we reach the end and then linking it with the right child.
Returning left child as long as it is not null otherwise we return the right child.

public void associateNextPtr(){
		// need to associate pointers starting from the root
		int level = 2;
		while(associateNextPtrAtLevel(root,level)!=null){
			level++;
		}
		System.out.println("total levels are: " + level-1);
	}

	private Node associateNextPtrAtLevel(Node root, int level) {
		Node retVal;
		if (root == null) {
			retVal = null;
		} else if (level == 1) {
			retVal = root;
		} else {
			Node leftChild = associateNextPtrAtLevel(root.left, level - 1);
			Node rightChild = associateNextPtrAtLevel(root.right, level - 1);
			if (leftChild != null && rightChild != null) {
				Node scanNode = leftChild;
				while(scanNode.nextNode != null){
					scanNode = scanNode.nextNode;
				}
				scanNode.nextNode = rightChild;
				retVal = leftChild;
			} else if (leftChild != null) {
				retVal = leftChild;
			} else {
				retVal = rightChild;
			}
		}
		return retVal;
	}

- parvin.singh October 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void connect(Node root) {
		if (root != null) connect(root.left, root.right);
	}

	static void connect(Node root, Node next) {
		if (root == null) return;
		root.nextRight = next;	
		connect(root.left, root.right);	
		if (next != null) connect(root.right, next.left);
	}

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

1st pass - DFS to initialize node.data to the height of this node in a tree.

private static int DFSSetHeight(Node n, int h) {
		if (n == null) return h - 1;
		n.value = h;
		return Math.max(DFSSetHeight(n.left, h+1), DFSSetHeight(n.right, h+1));
	}

then iterate over the height, each iteration spawn a new DFS. so we iteratively go deeper and deeper. during each pass remember to first go to the left son then the right one. also remember the last visited node at the maximum level (per this iteration). when you find a new one at the correct level, connect it with the previous one.

private static void DFSSetNextRight(Node n, int toLevel) {
		if (n == null) return;
		if (n.value == toLevel) {
			if (lastAtLevel != null) {
				lastAtLevel.nextRight = n;	
			}
			lastAtLevel = n;
			return; //we don't need to go deeper
		}
		DFSSetNextRight(n.left, toLevel);
		DFSSetNextRight(n.right, toLevel);
	}

initialize like this:

private static Node lastAtLevel;
	
	public static void main(String[] args) {
		Node root = null ; //init tree
		int maxH = DFSSetHeight(root, 0);
		for (int i = 1; i <= maxH ; i ++ ) {
			lastAtLevel = null;
			DFSSetNextRight(root, i);
		}
	}

space O(1); time O(N) - last iteration goes through n elements (full tree), last but one through (n/2) etc .. so in total O(3N) including first DFS pass to set up heights.

- Pawel November 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we want to achieve this in O(1) space, I assume we have to compromise on Time complexity (natural trade-off between memory and time)

Logic : call following method h times on root (where h is height of tree) and increment depth every time
Method checks if current value of depth is 0 (which means desired depth is achieved) and then attach backup node to current node.

(Please comment for any bug)

static prevNode = null;

connectNode(Node root , int depth){
	if(root == null)
		return;

	if(depth == 0){
		if(prevNode == null){
			prevNode = root;
		}
		else{
			prevNode.nextRight = root;
		}
	}
	else{
		connectNode(root.left , depth -1);
		connectNode(root.right , depth -1);
	}

}

- pankaj March 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we want to achieve this in O(1) space, I assume we have to compromise on Time complexity (natural trade-off between memory and time)

Logic : call following method h times on root (where h is height of tree) and increment depth every time
Method checks if current value of depth is 0 (which means desired depth is achieved) and then attach backup node to current node.

(Please comment for any bug)

static prevNode = null;

connectNode(Node root , int depth){
	if(root == null)
		return;

	if(depth == 0){
		if(prevNode == null){
			prevNode = root;
		}
		else{
			prevNode.nextRight = root;
		}
	}
	else{
		connectNode(root.left , depth -1);
		connectNode(root.right , depth -1);
	}

}

- pankaj March 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static class Node {
		int data;
		Node left;
		Node right;
		Node nextRight;
	}
	
	public static void setNextRight(Node root){
		if(root == null)
			return;
		setNextRight(root.left, root.right);
		setNextRight(root.right, null);
	}
	
	public static void setNextRight(Node left, Node nextRight){
		if(left == null)
			return;
		left.nextRight = nextRight;
		if(left.left != null)
			setNextRight(left.left, left.right);
		if(left.right != null)
			setNextRight(left.right, nextRight == null ? null : nextRight.left);
	}

- HectorLagos June 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def connect(self, root):
        import Queue
        q = Queue.Queue()
        q.put(root)
        while not q.empty():
            size = q.qsize()
            head=None
            while size > 0:
                r = q.get()
                if head:
                    head.next=r
                head=r
                if r.left:
                    q.put(r.left)
                if r.right:
                    q.put(r.right)
                size -= 1
                
        return root

- sumitgaur.iiita December 19, 2016 | 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