🧠 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;
}