## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

``````static int mixDif = Integer.MIN_VALUE;
public static int maxDifNodes(TreeNode root,TreeNode node){

if(root==node){
return 0;
}

inorder(root,node);
return maxDif;
}

public static TreeNode inorder(TreeNode root,TreeNode node){
if(root==null){
return null;
}
if(root==node){

maxDif = Math.max(maxDif,Math.abs(root.val-node.val));
return node;
}

TreeNode left = inorder(root.left,node);
TreeNode right = inorder(root.right,node);
if(left==null&&right==null){
return null;
}else{
maxDif = Math.max(maxDif,Math.abs(root.val-node.val));
return node;
}
}``````

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

``````package random;

import java.util.HashMap;
import java.util.Map;

public class MaxDiffTree {

public static void main(String[] args) {

TreeNode leafOne = new TreeNode(2, null, null);
TreeNode leafTwo = new TreeNode(3, null, null);
TreeNode oneLevelOne = new TreeNode(5, leafOne, leafTwo);
TreeNode root = new TreeNode(2, oneLevelOne, null);

MaxDiffTree maxDiffTreeSolver = new MaxDiffTree();
System.out.println(maxDiffTreeSolver.findMaxDiff(root));

}

public int findMaxDiff(TreeNode root) {
if (root == null) {
System.out.println("don't fuck with me");
return -1;
}

Integer currentBest = -2;
Map<TreeNode, Integer> maxMap = new HashMap<>();
Map<TreeNode, Integer> minMap = new HashMap<>();

createMaxMap(root, maxMap);
createMinMap(root, minMap);
currentBest = findMaxDifference(root, maxMap, minMap);
System.out.println("Best difference is " + currentBest);
return currentBest;
}

private int findMaxDifference(TreeNode node, Map<TreeNode, Integer> maxChild, Map<TreeNode, Integer> minChild) {

int currentBest = -2;

if (node.left != null) {
currentBest = findMaxDifference(node.left, maxChild, minChild);
}

if (node.right != null) {
currentBest = findMaxDifference(node.right, maxChild, minChild);
}

if (Math.abs(maxChild.get(node) - node.value) > currentBest) {
currentBest = Math.abs(maxChild.get(node) - node.value);
}
if (Math.abs(node.value - minChild.get(node)) > currentBest) {
currentBest = Math.abs(node.value - minChild.get(node));
}
return currentBest;

}

private int createMinMap(TreeNode node, Map<TreeNode, Integer> minMap) {
int min = node.value;
if (node.left != null) {
int minLeft = createMinMap(node.left, minMap);
if (minLeft < min) {
min = minLeft;
}
}

if (node.right != null) {
int minRight = createMaxMap(node.right, minMap);
if (minRight < min) {
min = minRight;
}
}

minMap.put(node, min);
return min;
}

private int createMaxMap(TreeNode node, Map<TreeNode, Integer> maxMap) {
int max = node.value;
if (node.left != null) {
int maxLeft = createMaxMap(node.left, maxMap);
if (maxLeft > max) {
max = maxLeft;
}
}

if (node.right != null) {
int maxRight = createMaxMap(node.right, maxMap);
if (maxRight > max) {
max = maxRight;
}
}

maxMap.put(node, max);
return max;
}
}

class TreeNode {
int value;
TreeNode left;
TreeNode right;

public boolean isLeaf() {
if (left == null && right == null) {
return true;
}
return false;
}

public TreeNode(int val, TreeNode left, TreeNode right) {
this.value = val;
this.left = left;
this.right = right;
}
}``````

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

package random;

import java.util.HashMap;
import java.util.Map;

public class MaxDiffTree {

public static void main(String[] args) {

TreeNode leafOne = new TreeNode(2, null, null);
TreeNode leafTwo = new TreeNode(3, null, null);
TreeNode oneLevelOne = new TreeNode(5, leafOne, leafTwo);
TreeNode root = new TreeNode(2, oneLevelOne, null);

MaxDiffTree maxDiffTreeSolver = new MaxDiffTree();
System.out.println(maxDiffTreeSolver.findMaxDiff(root));

}

public int findMaxDiff(TreeNode root) {
if (root == null) {
System.out.println("don't fuck with me");
return -1;
}

Integer currentBest = -2;
Map<TreeNode, Integer> maxMap = new HashMap<>();
Map<TreeNode, Integer> minMap = new HashMap<>();

createMaxMap(root, maxMap);
createMinMap(root, minMap);
currentBest = findMaxDifference(root, maxMap, minMap);
System.out.println("Best difference is " + currentBest);
return currentBest;
}

private int findMaxDifference(TreeNode node, Map<TreeNode, Integer> maxChild, Map<TreeNode, Integer> minChild) {

int currentBest = -2;

if (node.left != null) {
currentBest = findMaxDifference(node.left, maxChild, minChild);
}

if (node.right != null) {
currentBest = findMaxDifference(node.right, maxChild, minChild);
}

if (Math.abs(maxChild.get(node) - node.value) > currentBest) {
currentBest = Math.abs(maxChild.get(node) - node.value);
}
if (Math.abs(node.value - minChild.get(node)) > currentBest) {
currentBest = Math.abs(node.value - minChild.get(node));
}
return currentBest;

}

private int createMinMap(TreeNode node, Map<TreeNode, Integer> minMap) {
int min = node.value;
if (node.left != null) {
int minLeft = createMinMap(node.left, minMap);
if (minLeft < min) {
min = minLeft;
}
}

if (node.right != null) {
int minRight = createMaxMap(node.right, minMap);
if (minRight < min) {
min = minRight;
}
}

minMap.put(node, min);
return min;
}

private int createMaxMap(TreeNode node, Map<TreeNode, Integer> maxMap) {
int max = node.value;
if (node.left != null) {
int maxLeft = createMaxMap(node.left, maxMap);
if (maxLeft > max) {
max = maxLeft;
}
}

if (node.right != null) {
int maxRight = createMaxMap(node.right, maxMap);
if (maxRight > max) {
max = maxRight;
}
}

maxMap.put(node, max);
return max;
}
}

class TreeNode {
int value;
TreeNode left;
TreeNode right;

public boolean isLeaf() {
if (left == null && right == null) {
return true;
}
return false;
}

public TreeNode(int val, TreeNode left, TreeNode right) {
this.value = val;
this.left = left;
this.right = right;
}
}

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

/*
* Traverse Tree
* Keep Track of MaxSoFar and MaxDiff
*
*/

``````public class BinaryTreeMaxDiffBetweenAndNodeAncestor {

public static int getMaxDiffNodeAndAncestor(Node root, int maxSoFar, int maxDiff){
if(root==null){
return maxDiff;
}else{
maxDiff=Math.max(maxDiff, maxSoFar-root.data);
maxSoFar=Math.max(maxSoFar, root.data);

return Math.max(getMaxDiffNodeAndAncestor(root.leftChild,maxSoFar,maxDiff),
getMaxDiffNodeAndAncestor(root.rightChild, maxSoFar, maxDiff));
}

}

public static void main(String[] args) {

Node root = new Node(8);
root.rightChild=new Node(10);
root.rightChild.rightChild=new Node(14);
root.rightChild.rightChild.leftChild=new Node(13);

root.leftChild=new Node(3);
root.leftChild.leftChild=new Node(1);

root.leftChild.rightChild=new Node(6);
root.leftChild.rightChild.rightChild=new Node(7);
root.leftChild.rightChild.leftChild=new Node(4);

int maxDiff = getMaxDiffNodeAndAncestor(root,0,0);
System.out.println(maxDiff);
}

static class Node{
int data;
Node leftChild;
Node rightChild;
Node(int data){
this.data = data;
}
}
}``````

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.

### 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.