Amazon Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

import java.util.*;

public class Unival {
    private static class Node {
	private int n;
	private Node left;
	private Node right;

	public Node(int n, Node left, Node right) {
	    this.n = n;
	    this.left = left;
	    this.right = right;
	}

	public boolean isUnival() {
	    if (this.left != null) {
		if (this.left.n != this.n) {
		    return false;
		}
		if (!this.left.isUnival()) {
		    return false;
		}
	    }

	    if (this.right != null) {
		if (this.right.n != this.n) {
		    return false;
		}
		if (!this.right.isUnival()) {
		    return false;
		}
	    }

	    return true;
	}

	public int countUnival() {
	    int count = 1;
	    if (this.left != null) {
		if (this.left.n == this.n) {
		    count++;
		}
		count += this.left.countUnival();
	    }
	    if (this.right != null) {
		if (this.right.n == this.n) {
		    count++;
		}
		count += this.right.countUnival();
	    }
	    if (this.left != null && this.right != null && this.left.n == this.n && this.right.n == this.n) {
		count++;
	    }
	    return count;
	}
    }

    public static void main(String args[]) {
	Node left = new Node(1, null, null);
	Node right = new Node(2, null, null);
	Node root = new Node(2, left, right);
	System.out.println(root.isUnival());
	System.out.println(root.countUnival());
    }
}

- babesh March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming it is a binary tree

int CountUnival(node* pNode, int curVal = 0x80000000)
{
	if (!pNode) return 0;
	return (pNode->val != curVal) + CountUnival(pNode->pLeft, pNode->val)
						        + CountUnival(pNode->pRight, pNode->val);
}

- tjcbs2 March 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. for 1st scenario :

For binary tree:

public static boolean isTreeUnivalRoot(Node root) {		
	if (root == null) {
		return true;
	}
	
	return isTreeUnival(root.left, root.val) && isTreeUnival(root.right, root.val); 			
}

public static boolean isTreeUnival(Node n, int val) {		
	if (n == null) {
		return true;
	}
	if (n.val != val) {
		return false;
	}
	
	return isTreeUnival(n.left, val) && isTreeUnival(n.right, val);		
}

In case for an N-ary tree

public static boolean isTreeUnivalRoot(Node root) {		
	if (root == null) {
		return true;
	}

	boolean isUnival = true;		
	if (root.children != null && !root.children.isEmpty()) {
		for (Node c : root.children) {
			isUnival = isTreeUnival(c, root.val);
		}			
	}			
	
	return isUnival;			
}

public static boolean isTreeUnival(Node n, int val) {		
	if (n == null) {
		return true;
	}
	if (n.val != val) {
		return false;
	}
	
	boolean unival = true;
	if (n.children != null && !n.children.isEmpty()) {			
		for (Node c : n.children) {
			unival = isTreeUnival(c, val);
		}
	}
	return unival;		
}

2. for 2nd on a binary tree count the number of unival subtrees:

There will be at least N subtrees of size 1 unival trees.
Then again inside a bigger unival subtree there will be several smaller unival subtrees, each from a possible combination of the nodes of the bigger tree.

- guilhebl March 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is no minimum size. You need to return all the subtrees. And it is a binary tree for both cases.

- tbag March 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

For the follow up question, just need to count the occurrences where the current node and child nodes values are the same but not equal to the current node's parent's value.

public class CountUnivalSubtrees {
	
	public static int countUnivalSubtrees(Node root, Node parent) {
		if(root == null) return 0;
		
		if(parent != null && root.getLeft() != null && root.getRight() != null &&
				root.getVal() != parent.getVal() &&
				root.getVal() == root.getLeft().getVal() &&
				root.getVal() == root.getRight().getVal())
			return 1 + countUnivalSubtrees(root.getLeft(), root) + countUnivalSubtrees(root.getRight(), root);
		else
			return countUnivalSubtrees(root.getLeft(), root) + countUnivalSubtrees(root.getRight(), root);
	}
	
	public static class Node{ 
		private int val;
		private Node left;
		private Node right;
		public Node(int val) {
			this.val = val;
		}
		public int getVal() {
			return val;
		}
		public void setVal(int val) {
			this.val = val;
		}
		public Node getLeft() {
			return left;
		}
		public void setLeft(Node left) {
			this.left = left;
		}
		public Node getRight() {
			return right;
		}
		public void setRight(Node right) {
			this.right = right;
		}
	}
	
	public static void main(String[] args) {
		/**
		 *              1
		 *           /       \
		 *         2           3
		 *        /  \       /   \
		 *       2    2     3     3
		 *     /   \       / \   / \
		 *    5     5     4   4  3  3
		 */
		Node root = new Node(1);
		Node n1 = new Node(2);
		Node n2 = new Node(3);
		Node n3 = new Node(2);
		Node n4 = new Node(2);
		Node n5 = new Node(5);
		Node n6 = new Node(5);
		Node n7 = new Node(3);
		Node n8 = new Node(3);
		Node n9 = new Node(4);
		Node n10 = new Node(4);
		Node n11 = new Node(3);
		Node n12 = new Node(3);
		
		root.setLeft(n1);
		root.setRight(n2);
		n1.setLeft(n3);
		n1.setRight(n4);
		n3.setLeft(n5);
		n3.setRight(n6);
		n2.setLeft(n7);
		n2.setRight(n8);
		n7.setLeft(n9);
		n7.setRight(n10);
		n8.setLeft(n11);
		n8.setRight(n12);
		
		System.out.println(countUnivalSubtrees(root, null));
	}

- Anonymous March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How about the subtrees inside the unival subtrees ? Like for example the trees below derived from your example:

/**
		 *              
		 *         2         3
		 *        /            \
		 *       2             3
		 *                      / \
		 *                     3  3
		 */

These are also unival trees as well.

- guilhebl March 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think in the tree you considered as an example, there is only 1 Unival subtree.
That is,
3
* / \
* 3 3

Others are not subtrees

- bharat March 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

We can use simple DFS approach ...

private static int count = 0;
	
	private static void dfs(Node root) {
		dfs(root, null);
	}
	
	private static void dfs(Node root, Node parent) {
		if(root == null) return;
		if((root.getLeft() != null && root.getLeft().getVal() == root.getVal()) && (root.getRight() != null && root.getRight().getVal() == root.getVal()) ){
			//To check are we expending existing UnivalTree tree or found new one
			if(parent == null){
				count++;
			}
			parent = root;
		} else if(root.getLeft() != null && root.getRight() == null && root.getLeft().getVal() == root.getVal()){
			//Found tree with single child - Left child
			if(parent == null){
				count++;
			}
			parent = root;
		} else if(root.getRight() != null && root.getLeft() == null && root.getRight().getVal() == root.getVal()){
			//Found tree with single child - Right child
			if(parent == null){
				count++;
			}
			parent = root;
		} else{
			parent = null;
		}
		dfs(root.left, parent);
		dfs(root.right, parent);
	}

After dfs(root) operation, count will be equal to number of UnivalTree.

- Ajeet March 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int function f(node, parent)
{
	if(node == null) 
	{
		return 0;
	}

	if( parent == null || node.val == parent.val)
	{
		return f(node.left, node) + f(node.right, node);
	}

	if(node.val != parent.val)
	{
		return 1 + f(node.left, node) + f(node.right, node);

	}
}

void main()
{
	if(root == null)
		console.log('zero');
	else
	    console.log(1+f(node, null));
}

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

int function f(node, parent)
{
if(node == null)
{
return 0;
}

if( parent == null || node.val == parent.val)
{
return f(node.left, node) + f(node.right, node);
}

if(node.val != parent.val)
{
return 1 + f(node.left, node) + f(node.right, node);

}
}

void main()
{
if(root == null)
console.log('zero');
else
console.log(1+f(node, null));
}

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

For the first:

isSame(Node n) {

	if (n == null) {
		
		return true;
	}

	Node l = n.left;
	Node r = n.right;

	boolean a, b, c;

	a = (l == null) ? true : (l.value == n.value) ? true : false;
	b = (r == null) ? true : (r.value == n.value) ? true : false;
	c = (l == null) ? true : (r.value == l.value) ? true : false;

	return (a && b && c && isSame(l) && isSame(r));
}

- SK March 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System.IO;
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    static void Main()
    {
       
        var root = new TestNode(1);
		var n1 = new TestNode(2);
		var n2 = new TestNode(3);
		var n3 = new TestNode(2);
		var n4 = new TestNode(2);
		var n5 = new TestNode(5);
		var n6 = new TestNode(5);
		var n7 = new TestNode(3);
		var n8 = new TestNode(3);
		var n9 = new TestNode(4);
		var n10 = new TestNode(4);
		var n11 = new TestNode(3);
		var n12 = new TestNode(3);
		
		root.addNode(n1);
		root.addNode(n2);
		n1.addNode(n3);
		n1.addNode(n4);
		n3.addNode(n5);
		n3.addNode(n6);
		n2.addNode(n7);
		n2.addNode(n8);
		n7.addNode(n9);
		n7.addNode(n10);
		n8.addNode(n11);
		n8.addNode(n12);
        int count = CountUnivalSubtrees(root);
        Console.WriteLine("Hello, World!{0}",count);
    }
    
    private static int CountUnivalSubtrees(TestNode node)
    {
        int intReturn = 0;
        if(node.children.All(c=>c.val == node.children.FirstOrDefault().val))  
           intReturn = 1;
           
         return intReturn + node.children.Sum(c=>CountUnivalSubtrees(c));
    }
    
    public class TestNode
    {
        public TestNode(int val1)
        {
            val = val1;
            children = new List<TestNode>();
        }
        
        public void addNode(TestNode node)
        {
            node.parent = this;
            children.Add(node);
        }
        
        public int val;
        public List<TestNode> children;
        public TestNode parent;
    }
    
}

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

Remember that a subtree is defined as a node and *all* its descendants, down to the leaves. To count the number of unival subtrees in a binary tree, we can use the following recursive approach:

If the current node matches its two children in value, and each of its children is the root of a unival subtree, then the current node is the root of a unival subtree.

The base case occurs with a leaf node -- every leaf node is the root of its own unival subtree. (Note that you might want to tweak the definition of subtree so that root nodes don't count, but technically this is correct.)

Untested Python:

def count_unival(tree):
	count = 0

	def is_unival(tree):
		if not tree.left and not tree.right:
			count += 1
			return True

		if is_unival(tree.left) and is_unival(tree.right) and \
		   tree.value == tree.left.value and tree.value == tree.right.value:
			count += 1
			return True

		return False

	is_unival(tree)
	return count

- nilkn April 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

2nd part of problem

int unival_grp(struct tree *root){
	if(NULL == root) return 0; //if tree is empty
	if(root->left == NULL  && root->right == NULL) //leaf node
		return 1;
	int l =unival_grp(root->left);
	int r = unival_grp(root->right);
	if(root->data == root->left->data && root->data == root->right->data){
		if(l == 1 & r == 1)
			return 1;
	}
	else
		return l+r;
}

- krrish April 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

correcting typo error if(l == 1 && r == 1)

- krrish April 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

int unival_grp(struct tree *root){
	if(NULL == root) return 0; //if tree is empty
	if(root->left == NULL  && root->right == NULL) //leaf node
		return 1;
	int l =unival_grp(root->left);
	int r = unival_grp(root->right);
	if(l == 0 || r == 0) //handle internal single node
			return l?l:r;
		
	if(root->data == root->left->data && root->data == root->right->data){
		if(l == 1 && r == 1)
			return 1;
	}
	else
		return l+r;
}

- krrishn April 07, 2015 | Flag


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