Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
C#
public class Main
{
private int getMax(Node n, int max)
{
int lMax = max;
int rMax = max;
if (n==null)
return max;
if (n.left!=null)
lMax = getMax(n.left, (n.value+1 == n.left.value ? max + 1 : max));
if (n.right!=null)
rMax = getMax(n.right, (n.value+1 == n.right.value ? max + 1 : max));
return Math.Max(lMax, rMax);
}
public Node root{get;set;}
public Main()
{
Node l = new Node(99, null, null);
Node r = new Node(100, null, null);
l = new Node(5, l, r);
r = new Node(4, null, null);
Node l1 = new Node(68, null, null);
l = new Node(2, l, r);
r = new Node(67, l1, null);
l1 = new Node(1, null,null);
r = new Node(66, l, r);
this.root = new Node(90, l1, r);
}
public int GetMax()
{
return getMax(this.root, 0);
}
}
public class Node{
public int value {get; set;}
public Node left {get; set;}
public Node right {get; set;}
public Node(int v, Node l, Node r)
{
this.value = v;
this.right = r;
this.left = l;
}
}
import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
public class MaxConsecutiveNumbersinBinaryTree
{
public static void main(String args[])
{
MaxConsecutiveNumbersinBinaryTree m = new MaxConsecutiveNumbersinBinaryTree();
TreeNode root = new TreeNode(90);
root.left = new TreeNode(1);
root.left.left = new TreeNode(2);
root.left.left.left = new TreeNode(5);
root.left.left.right = new TreeNode(4);
root.left.left.left.left = new TreeNode(99);
root.left.left.left.right = new TreeNode(100);
root.right = new TreeNode(66);
root.right.left = new TreeNode(67);
root.right.left.left = new TreeNode(68);
Set<List<Integer>> list = new HashSet<>();
m.dfs(root, null, new ArrayList<Integer>(), list);
System.out.println(list);
}
public void dfs(TreeNode root, TreeNode parent, List<Integer> l, Set<List<Integer>> list)
{
if(root == null)
{
list.add(l);
return;
}
if(parent==null)
{
l.add(root.val);
}
else if(Math.abs(root.val - parent.val)==1)
{
l.add(root.val);
}
else if(Math.abs(root.val - parent.val)!=1)
{
list.add(l);
l = new ArrayList<>();
l.add(root.val);
}
dfs(root.left, root, l, list);
dfs(root.right, root, l, list);
}
}
class TreeNode
{
TreeNode left;
TreeNode right;
int val;
TreeNode(int val)
{
this.val = val;
}
}
Using DFS in C#
}
- maksymas March 18, 2017