🧠 Amazon Interview Experience — Binary Trees, Backtracking, and Greedy Algorithms

Overview

This case study examines a candidate's experience during an interview process at Amazon. The technical assessment focused on a range of algorithmic topics, including binary trees, backtracking, and greedy algorithms. The interview comprised several rounds, each designed to evaluate the candidate's proficiency in problem-solving and coding.

Interview Rounds

Round 1: Initial Assessment

This round involved algorithmic questions related to data structures, specifically binary trees.

Problem 1: Maximum Average Subtree

The candidate was asked to find the maximum average subtree in a given binary tree.

Approach:

A post-order traversal approach was used. For each node, the algorithm calculates:

• The sum of the subtree
• The number of nodes in the subtree
• The average, which is then used to update the global maximum average.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function maximumAverageSubtree(root) {
  let maxAvg = -Infinity;

  function dfs(node) {
    if (!node) return { sum: 0, count: 0 };

    const left = dfs(node.left);
    const right = dfs(node.right);

    const sum = node.val + left.sum + right.sum;
    const count = 1 + left.count + right.count;
    const avg = sum / count;

    maxAvg = Math.max(maxAvg, avg);
    return { sum, count };
  }

  dfs(root);
  return maxAvg;
}

Problem 2: Backtracking on Array (Subset Sum)

The candidate faced a classic backtracking problem, specifically the Subset Sum problem.

function subsetSum(arr, target) {
  const result = [];

  function backtrack(start, path, sum) {
    if (sum === target) {
      result.push([...path]);
      return;
    }

    if (sum > target) return;

    for (let i = start; i < arr.length; i++) {
      path.push(arr[i]);
      backtrack(i + 1, path, sum + arr[i]);
      path.pop();
    }
  }

  backtrack(0, [], 0);
  return result;
}

Round 2: Face-to-Face (Amazon Chime)

This round was conducted via Amazon Chime.

Problem 1: Zigzag Tree Traversal

The task was to implement a zigzag (level-order) traversal of a binary tree.

function zigzagTraversal(root) {
  if (!root) return []; // If the tree is empty, return an empty array

  const result = [];           // This will store the final zigzag traversal
  const queue = [root];        // Use a queue for level-order traversal
  let leftToRight = true;      // Toggle direction at each level

  while (queue.length) {
    const size = queue.length; // Number of nodes at the current level
    const level = [];          // Temporarily store values for this level

    // Traverse all nodes at the current level
    for (let i = 0; i < size; i++) {
      const node = queue.shift(); // Get the front node from the queue

      // Add the node's value in the appropriate order
      if (leftToRight) {
        level.push(node.val);     // Insert at the end for left-to-right
      } else {
        level.unshift(node.val);  // Insert at the beginning for right-to-left
      }

      // Add children of the current node to the queue (for next level)
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    // Add this level's values to the result
    result.push(...level);

    // Flip the traversal direction for the next level
    leftToRight = !leftToRight;
  }

  return result;
}

Problem 2: Print Path Between Two Nodes in Binary Tree

The candidate was required to find and print the path between two given nodes in a binary tree.

Approach:

The solution involves finding the paths from the root to each of the two nodes. The algorithm identifies the last common node (Lowest Common Ancestor - LCA) in both paths. The final path is constructed by reversing the path from the first node to the LCA and then appending the path from the LCA to the second node.

function findPath(root, path, k) {
  if (!root) return false; // Base case: null node means path not found

  path.push(root.val); // Add current node to path

  if (root.val === k) return true; // Found the node we are looking for

  // Recursively search left and right subtrees
  if (findPath(root.left, path, k) || findPath(root.right, path, k)) {
    return true; // If found in either subtree, return true
  }

  // If not found in this path, backtrack: remove the current node
  path.pop();
  return false; // Return false to indicate this path doesn't contain 'k'
}
function pathBetweenNodes(root, n1, n2) {
  const path1 = [], path2 = [];

  // Get paths from root to n1 and n2
  findPath(root, path1, n1); // path1 will store nodes from root to n1
  findPath(root, path2, n2); // path2 will store nodes from root to n2

  // Find the last common node (Lowest Common Ancestor - LCA)
  let i = 0;
  while (i < path1.length && i < path2.length && path1[i] === path2[i]) {
    i++;
  }

  // Build the final path:
  // 1. Reverse path from n1 to LCA
  // 2. Append path from LCA to n2 (excluding LCA to avoid duplication)
  const result = path1.slice(i - 1).reverse().concat(path2.slice(i));
  return result;
}

Round 3: Face-to-Face (Amazon Chime)

This round continued via Amazon Chime, focusing on greedy algorithms and sorting techniques.

Problem 1: Chocolate Distribution Problem

Given an array representing the number of chocolates in each packet, the goal is to distribute m packets to m students such that the difference between the maximum and minimum number of chocolates in the distributed packets is minimized.

// JavaScript program to solve chocolate distribution
// problem using Sliding Window

function findMinDiff(arr, m) {
    let n = arr.length;

    // Sort the given packets
    arr.sort((a, b) => a - b);

    let minDiff = Number.MAX_SAFE_INTEGER;

    for (let i = 0; i + m - 1 < n; i++) {

        // calculate difference of current window
        let diff = arr[i + m - 1] - arr[i];

        // if current difference is smaller
        // then update the minimum difference
        if (diff < minDiff)
            minDiff = diff;
    }
    return minDiff;
}

let arr = [7, 3, 2, 4, 9, 12, 56];
let m = 3;

console.log(findMinDiff(arr, m));

Problem 2: Nuts and Bolts Problem (Lock-Key Matching)

The candidate was presented with the Nuts and Bolts problem, which involves matching n nuts and n bolts where each nut has a corresponding bolt. Direct comparison between nuts or bolts is disallowed; only nut-to-bolt comparisons are permitted.

function matchPairs(nuts, bolts, low, high) {
  if (low < high) {
    // Use the last bolt as pivot to partition nuts
    var pivot = partition(nuts, low, high, bolts[high]);

    // Use the matched nut to partition bolts
    partition(bolts, low, high, nuts[pivot]);

    // Recursively match the left and right subarrays
    matchPairs(nuts, bolts, low, pivot - 1);
    matchPairs(nuts, bolts, pivot + 1, high);
  }
}

function partition(arr, low, high, pivot) {
  var i = low;
  var temp1, temp2;

  for (var j = low; j < high; j++) {
    if (arr[j] < pivot) {
      // Swap arr[i] and arr[j]
      temp1 = arr[i];
      arr[i] = arr[j];
      arr[j] = temp1;
      i++;
    } else if (arr[j] == pivot) {
      // Move pivot to the end temporarily
      temp1 = arr[j];
      arr[j] = arr[high];
      arr[high] = temp1;
      j--; // Recheck this index in next iteration
    }
  }

  // Move pivot to its correct position
  temp2 = arr[i];
  arr[i] = arr[high];
  arr[high] = temp2;

  return i; // Return index of pivot
}

Problem 3: Left View of Binary Tree

This problem wasn't fully detailed, but likely involved implementing an algorithm to return the left view of a binary tree.

Key Takeaways

• Amazon's interview process emphasizes strong problem-solving skills and a deep understanding of fundamental data structures and algorithms.
• Candidates should be prepared to implement solutions in a live coding environment.
• A solid grasp of binary trees, backtracking, greedy algorithms, and sorting techniques is crucial for success.
• The ability to clearly explain the reasoning behind chosen approaches and the time/space complexity of solutions is highly valued.