Amazon Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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.
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));
}
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.
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
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.
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));
}
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));
}
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));
}
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;
}
}
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
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;
}
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;
}
- babesh March 17, 2015