Amazon Frontend Engineer II Interview Prep | Generated: June 2026
- 🔢 Array
- Two Sum · Best Time to Buy/Sell Stock · Contains Duplicate · Product of Array Except Self · Maximum Subarray · Maximum Product Subarray · Find Minimum in Rotated Sorted Array · Search in Rotated Sorted Array · 3Sum · Container With Most Water
- ⚡ Binary
- Sum of Two Integers · Number of 1 Bits · Counting Bits · Missing Number · Reverse Bits
- 🧠 Dynamic Programming
- Climbing Stairs · Coin Change · Longest Increasing Subsequence · Longest Common Subsequence · Word Break · Combination Sum IV · House Robber · House Robber II · Decode Ways · Unique Paths · Jump Game
- 🕸️ Graph
- Clone Graph · Course Schedule · Pacific Atlantic Water Flow · Number of Islands · Longest Consecutive Sequence · Alien Dictionary · Graph Valid Tree · Number of Connected Components
- 📅 Interval
- Insert Interval · Merge Intervals · Non-overlapping Intervals · Meeting Rooms · Meeting Rooms II
- 🔗 Linked List
- Reverse a Linked List · Detect Cycle · Merge Two Sorted Lists · Merge K Sorted Lists · Remove Nth Node From End · Reorder List
- 📊 Matrix
- Set Matrix Zeroes · Spiral Matrix · Rotate Image · Word Search
- 🔤 String
- Longest Substring Without Repeating Characters · Longest Repeating Character Replacement · Minimum Window Substring · Valid Anagram · Group Anagrams · Valid Parentheses · Valid Palindrome · Longest Palindromic Substring · Palindromic Substrings · Encode and Decode Strings
- 🌲 Tree
- Maximum Depth · Same Tree · Invert Binary Tree · Binary Tree Maximum Path Sum · Level Order Traversal · Serialize/Deserialize · Subtree of Another Tree · Construct from Preorder+Inorder · Validate BST · Kth Smallest in BST · Lowest Common Ancestor · Implement Trie · Add and Search Word · Word Search II
- 🏔️ Heap
- Merge K Sorted Lists · Top K Frequent Elements · Find Median from Data Stream
- ⭐ Amazon Frontend Engineer II — Must Know
Problem: Given an array of integers and a target, return indices of the two numbers that add up to target.
function twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) return [i, j];
}
}
}function twoSum(nums, target) {
const map = new Map(); // value → index
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) return [map.get(complement), i];
map.set(nums[i], i);
}
}Problem: Find the maximum profit from buying on one day and selling on a later day.
function maxProfit(prices) {
let max = 0;
for (let i = 0; i < prices.length; i++)
for (let j = i + 1; j < prices.length; j++)
max = Math.max(max, prices[j] - prices[i]);
return max;
}function maxProfit(prices) {
let minPrice = Infinity, maxProfit = 0;
for (const price of prices) {
minPrice = Math.min(minPrice, price);
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
}Problem: Return true if any value appears at least twice.
function containsDuplicate(nums) {
for (let i = 0; i < nums.length; i++)
for (let j = i + 1; j < nums.length; j++)
if (nums[i] === nums[j]) return true;
return false;
}function containsDuplicate(nums) {
const seen = new Set();
for (const n of nums) {
if (seen.has(n)) return true;
seen.add(n);
}
return false;
}Problem: Return an array where each element is the product of all other elements. No division allowed.
function productExceptSelf(nums) {
const result = [];
for (let i = 0; i < nums.length; i++) {
let product = 1;
for (let j = 0; j < nums.length; j++)
if (i !== j) product *= nums[j];
result[i] = product;
}
return result;
}function productExceptSelf(nums) {
const n = nums.length;
const result = new Array(n).fill(1);
// Left pass: result[i] = product of all elements to the left
let prefix = 1;
for (let i = 0; i < n; i++) {
result[i] = prefix;
prefix *= nums[i];
}
// Right pass: multiply by product of all elements to the right
let suffix = 1;
for (let i = n - 1; i >= 0; i--) {
result[i] *= suffix;
suffix *= nums[i];
}
return result;
}Problem: Find the contiguous subarray with the largest sum (Kadane's Algorithm).
function maxSubArray(nums) {
let max = -Infinity;
for (let i = 0; i < nums.length; i++) {
let sum = 0;
for (let j = i; j < nums.length; j++) {
sum += nums[j];
max = Math.max(max, sum);
}
}
return max;
}function maxSubArray(nums) {
let maxSum = nums[0], current = nums[0];
for (let i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
maxSum = Math.max(maxSum, current);
}
return maxSum;
}Problem: Find the contiguous subarray that has the largest product.
function maxProduct(nums) {
let max = -Infinity;
for (let i = 0; i < nums.length; i++) {
let product = 1;
for (let j = i; j < nums.length; j++) {
product *= nums[j];
max = Math.max(max, product);
}
}
return max;
}// Track both max and min because a negative * negative = positive
function maxProduct(nums) {
let maxProd = nums[0], minProd = nums[0], result = nums[0];
for (let i = 1; i < nums.length; i++) {
const candidates = [nums[i], maxProd * nums[i], minProd * nums[i]];
maxProd = Math.max(...candidates);
minProd = Math.min(...candidates);
result = Math.max(result, maxProd);
}
return result;
}Problem: Find the minimum element in a rotated sorted array.
function findMin(nums) {
return Math.min(...nums);
}function findMin(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] > nums[hi]) lo = mid + 1; // min is in right half
else hi = mid; // min is in left half (including mid)
}
return nums[lo];
}Problem: Search for a target in a rotated sorted array. Return its index or -1.
function search(nums, target) {
return nums.indexOf(target);
}function search(nums, target) {
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] === target) return mid;
// Left half is sorted
if (nums[lo] <= nums[mid]) {
if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // Right half is sorted
if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}Problem: Find all unique triplets that sum to zero.
function threeSum(nums) {
const result = new Set();
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++)
for (let j = i + 1; j < nums.length; j++)
for (let k = j + 1; k < nums.length; k++)
if (nums[i] + nums[j] + nums[k] === 0)
result.add(JSON.stringify([nums[i], nums[j], nums[k]]));
return [...result].map(JSON.parse);
}function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicates
let lo = i + 1, hi = nums.length - 1;
while (lo < hi) {
const sum = nums[i] + nums[lo] + nums[hi];
if (sum === 0) {
result.push([nums[i], nums[lo], nums[hi]]);
while (lo < hi && nums[lo] === nums[lo + 1]) lo++;
while (lo < hi && nums[hi] === nums[hi - 1]) hi--;
lo++; hi--;
} else if (sum < 0) lo++;
else hi--;
}
}
return result;
}Problem: Find two lines that together with the x-axis form a container holding the most water.
function maxArea(height) {
let max = 0;
for (let i = 0; i < height.length; i++)
for (let j = i + 1; j < height.length; j++)
max = Math.max(max, (j - i) * Math.min(height[i], height[j]));
return max;
}function maxArea(height) {
let lo = 0, hi = height.length - 1, max = 0;
while (lo < hi) {
max = Math.max(max, (hi - lo) * Math.min(height[lo], height[hi]));
if (height[lo] < height[hi]) lo++;
else hi--;
}
return max;
}Problem: Calculate sum of two integers without using + or -.
function getSum(a, b) {
while (b !== 0) {
const carry = (a & b) << 1; // carry bits
a = a ^ b; // sum without carry
b = carry;
}
return a;
}Problem: Return the number of '1' bits in the binary representation (Hamming weight).
function hammingWeight(n) {
let count = 0;
while (n !== 0) {
count += n & 1;
n >>>= 1; // unsigned right shift
}
return count;
}function hammingWeight(n) {
let count = 0;
while (n !== 0) {
n &= n - 1; // removes lowest set bit
count++;
}
return count;
}Problem: For every number from 0 to n, return the count of 1 bits.
function countBits(n) {
const result = [];
for (let i = 0; i <= n; i++) {
let count = 0, num = i;
while (num) { count += num & 1; num >>= 1; }
result.push(count);
}
return result;
}function countBits(n) {
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++)
dp[i] = dp[i >> 1] + (i & 1); // i>>1 drops last bit; add 1 if last bit is set
return dp;
}Problem: Given an array of n distinct numbers in range [0, n], find the missing number.
function missingNumber(nums) {
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++)
if (nums[i] !== i) return i;
return nums.length;
}// Math approach
function missingNumber(nums) {
const n = nums.length;
const expected = (n * (n + 1)) / 2;
return expected - nums.reduce((a, b) => a + b, 0);
}
// XOR approach
function missingNumberXOR(nums) {
let xor = nums.length;
for (let i = 0; i < nums.length; i++) xor ^= i ^ nums[i];
return xor;
}Problem: Reverse bits of a 32-bit unsigned integer.
function reverseBits(n) {
let result = 0;
for (let i = 0; i < 32; i++) {
result = (result << 1) | (n & 1);
n >>>= 1;
}
return result >>> 0; // convert to unsigned 32-bit
}function reverseBits(n) {
let result = 0;
for (let i = 31; i >= 0; i--) {
result |= (n & 1) << i;
n >>>= 1;
}
return result >>> 0;
}Problem: You can climb 1 or 2 steps. How many distinct ways to reach step n?
function climbStairs(n) {
if (n <= 2) return n;
return climbStairs(n - 1) + climbStairs(n - 2);
}function climbStairs(n) {
if (n <= 2) return n;
let prev = 1, curr = 2;
for (let i = 3; i <= n; i++) [prev, curr] = [curr, prev + curr];
return curr;
}Problem: Find minimum number of coins to make up the amount. Return -1 if not possible.
function coinChange(coins, amount) {
function dp(rem) {
if (rem < 0) return -1;
if (rem === 0) return 0;
let min = Infinity;
for (const c of coins) {
const res = dp(rem - c);
if (res >= 0) min = Math.min(min, res + 1);
}
return min === Infinity ? -1 : min;
}
return dp(amount);
}function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++)
for (const coin of coins)
if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
return dp[amount] === Infinity ? -1 : dp[amount];
}Problem: Find the length of the longest strictly increasing subsequence.
function lengthOfLIS(nums) {
const dp = new Array(nums.length).fill(1);
for (let i = 1; i < nums.length; i++)
for (let j = 0; j < i; j++)
if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
return Math.max(...dp);
}function lengthOfLIS(nums) {
const tails = [];
for (const num of nums) {
let lo = 0, hi = tails.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tails[mid] < num) lo = mid + 1;
else hi = mid;
}
tails[lo] = num;
}
return tails.length;
}Problem: Find the length of the longest common subsequence of two strings.
function lcs(text1, text2, i = 0, j = 0) {
if (i === text1.length || j === text2.length) return 0;
if (text1[i] === text2[j]) return 1 + lcs(text1, text2, i + 1, j + 1);
return Math.max(lcs(text1, text2, i + 1, j), lcs(text1, text2, i, j + 1));
}function longestCommonSubsequence(text1, text2) {
const m = text1.length, n = text2.length;
const dp = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++)
for (let j = 1; j <= n; j++)
dp[i][j] = text1[i-1] === text2[j-1]
? dp[i-1][j-1] + 1
: Math.max(dp[i-1][j], dp[i][j-1]);
return dp[m][n];
}Problem: Given a string and a dictionary, determine if the string can be segmented into dictionary words.
function wordBreak(s, wordDict) {
const set = new Set(wordDict);
function dfs(start) {
if (start === s.length) return true;
for (let end = start + 1; end <= s.length; end++)
if (set.has(s.slice(start, end)) && dfs(end)) return true;
return false;
}
return dfs(0);
}function wordBreak(s, wordDict) {
const set = new Set(wordDict);
const dp = new Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= s.length; i++)
for (let j = 0; j < i; j++)
if (dp[j] && set.has(s.slice(j, i))) { dp[i] = true; break; }
return dp[s.length];
}Problem: Find the number of possible combinations that add up to target.
function combinationSum4(nums, target) {
if (target === 0) return 1;
let count = 0;
for (const n of nums)
if (n <= target) count += combinationSum4(nums, target - n);
return count;
}function combinationSum4(nums, target) {
const dp = new Array(target + 1).fill(0);
dp[0] = 1;
for (let i = 1; i <= target; i++)
for (const n of nums)
if (n <= i) dp[i] += dp[i - n];
return dp[target];
}Problem: Rob houses in a row, but cannot rob adjacent houses. Maximize money.
function rob(nums) {
function dfs(i) {
if (i >= nums.length) return 0;
return Math.max(nums[i] + dfs(i + 2), dfs(i + 1));
}
return dfs(0);
}function rob(nums) {
let prev = 0, curr = 0;
for (const n of nums) [prev, curr] = [curr, Math.max(curr, prev + n)];
return curr;
}Problem: Houses in a circle. Cannot rob adjacent. Maximize.
function rob(nums) {
if (nums.length === 1) return nums[0];
function robRange(start, end) {
let prev = 0, curr = 0;
for (let i = start; i <= end; i++)
[prev, curr] = [curr, Math.max(curr, prev + nums[i])];
return curr;
}
// Either rob [0..n-2] or [1..n-1]
return Math.max(robRange(0, nums.length - 2), robRange(1, nums.length - 1));
}Problem: A message encoded as numbers can be decoded multiple ways. Count distinct decodings.
function numDecodings(s) {
function dfs(i) {
if (i === s.length) return 1;
if (s[i] === '0') return 0;
let ways = dfs(i + 1);
if (i + 1 < s.length && parseInt(s.slice(i, i + 2)) <= 26)
ways += dfs(i + 2);
return ways;
}
return dfs(0);
}function numDecodings(s) {
let prev2 = 1, prev1 = s[0] !== '0' ? 1 : 0;
for (let i = 1; i < s.length; i++) {
let curr = 0;
if (s[i] !== '0') curr = prev1;
const two = parseInt(s.slice(i - 1, i + 1));
if (two >= 10 && two <= 26) curr += prev2;
[prev2, prev1] = [prev1, curr];
}
return prev1;
}Problem: Count unique paths from top-left to bottom-right in an m x n grid.
function uniquePaths(m, n) {
if (m === 1 || n === 1) return 1;
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}function uniquePaths(m, n) {
let dp = new Array(n).fill(1);
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) dp[j] += dp[j - 1];
}
return dp[n - 1];
}Problem: Given jump lengths at each position, determine if you can reach the last index.
function canJump(nums) {
function dfs(i) {
if (i >= nums.length - 1) return true;
for (let j = 1; j <= nums[i]; j++)
if (dfs(i + j)) return true;
return false;
}
return dfs(0);
}function canJump(nums) {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}Problem: Deep clone a connected undirected graph.
function cloneGraph(node, visited = new Map()) {
if (!node) return null;
if (visited.has(node)) return visited.get(node);
const clone = { val: node.val, neighbors: [] };
visited.set(node, clone);
for (const neighbor of node.neighbors)
clone.neighbors.push(cloneGraph(neighbor, visited));
return clone;
}Problem: Can you finish all courses given prerequisites? (Cycle detection in DAG)
function canFinish(numCourses, prerequisites) {
const graph = Array.from({length: numCourses}, () => []);
for (const [a, b] of prerequisites) graph[b].push(a);
// 0=unvisited, 1=visiting, 2=done
const state = new Array(numCourses).fill(0);
function hasCycle(node) {
if (state[node] === 1) return true;
if (state[node] === 2) return false;
state[node] = 1;
for (const nei of graph[node]) if (hasCycle(nei)) return true;
state[node] = 2;
return false;
}
for (let i = 0; i < numCourses; i++) if (hasCycle(i)) return false;
return true;
}Problem: Find cells from which water can flow to both Pacific and Atlantic oceans.
function pacificAtlantic(heights) {
const m = heights.length, n = heights[0].length;
const bfs = (starts) => {
const visited = Array.from({length: m}, () => new Array(n).fill(false));
const queue = [...starts];
starts.forEach(([r, c]) => (visited[r][c] = true));
while (queue.length) {
const [r, c] = queue.shift();
for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
!visited[nr][nc] && heights[nr][nc] >= heights[r][c]) {
visited[nr][nc] = true;
queue.push([nr, nc]);
}
}
}
return visited;
};
const pac = [], atl = [];
for (let r = 0; r < m; r++) { pac.push([r, 0]); atl.push([r, n - 1]); }
for (let c = 0; c < n; c++) { pac.push([0, c]); atl.push([m - 1, c]); }
const pacReach = bfs(pac), atlReach = bfs(atl);
const result = [];
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (pacReach[r][c] && atlReach[r][c]) result.push([r, c]);
return result;
}Problem: Count distinct islands in a 2D grid.
function numIslands(grid) {
let count = 0;
function dfs(r, c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] === '0') return;
grid[r][c] = '0'; // mark visited
dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
}
for (let r = 0; r < grid.length; r++)
for (let c = 0; c < grid[0].length; c++)
if (grid[r][c] === '1') { dfs(r, c); count++; }
return count;
}Problem: Find the length of the longest consecutive sequence. Must run in O(n).
function longestConsecutive(nums) {
nums.sort((a, b) => a - b);
let max = 1, curr = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i-1] + 1) max = Math.max(max, ++curr);
else if (nums[i] !== nums[i-1]) curr = 1;
}
return nums.length ? max : 0;
}function longestConsecutive(nums) {
const set = new Set(nums);
let max = 0;
for (const n of set) {
if (!set.has(n - 1)) { // only start counting from sequence start
let len = 1;
while (set.has(n + len)) len++;
max = Math.max(max, len);
}
}
return max;
}Problem: Given sorted alien words, determine character order.
function alienOrder(words) {
const adj = new Map();
const inDegree = new Map();
for (const c of words.join('')) {
if (!adj.has(c)) adj.set(c, new Set());
if (!inDegree.has(c)) inDegree.set(c, 0);
}
for (let i = 0; i < words.length - 1; i++) {
const [w1, w2] = [words[i], words[i+1]];
const minLen = Math.min(w1.length, w2.length);
if (w1.length > w2.length && w1.startsWith(w2)) return "";
for (let j = 0; j < minLen; j++) {
if (w1[j] !== w2[j]) {
if (!adj.get(w1[j]).has(w2[j])) {
adj.get(w1[j]).add(w2[j]);
inDegree.set(w2[j], inDegree.get(w2[j]) + 1);
}
break;
}
}
}
const queue = [...inDegree.entries()].filter(([,v]) => v === 0).map(([k]) => k);
let result = '';
while (queue.length) {
const c = queue.shift();
result += c;
for (const next of adj.get(c)) {
inDegree.set(next, inDegree.get(next) - 1);
if (inDegree.get(next) === 0) queue.push(next);
}
}
return result.length === inDegree.size ? result : '';
}class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
this.rank = new Array(n).fill(0);
this.components = n;
}
find(x) {
if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(x, y) {
const px = this.find(x), py = this.find(y);
if (px === py) return false;
if (this.rank[px] < this.rank[py]) this.parent[px] = py;
else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
else { this.parent[py] = px; this.rank[px]++; }
this.components--;
return true;
}
}
// Graph Valid Tree: n nodes, edges → tree if connected and no cycle
function validTree(n, edges) {
if (edges.length !== n - 1) return false;
const uf = new UnionFind(n);
for (const [a, b] of edges) if (!uf.union(a, b)) return false;
return true;
}
// Number of Connected Components
function countComponents(n, edges) {
const uf = new UnionFind(n);
for (const [a, b] of edges) uf.union(a, b);
return uf.components;
}Problem: Insert a new interval into a sorted non-overlapping intervals list.
function insert(intervals, newInterval) {
const result = [];
let i = 0, [start, end] = newInterval;
// Add all intervals that end before new interval starts
while (i < intervals.length && intervals[i][1] < start) result.push(intervals[i++]);
// Merge overlapping intervals
while (i < intervals.length && intervals[i][0] <= end) {
start = Math.min(start, intervals[i][0]);
end = Math.max(end, intervals[i][1]);
i++;
}
result.push([start, end]);
// Add remaining
while (i < intervals.length) result.push(intervals[i++]);
return result;
}Problem: Merge all overlapping intervals.
function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const result = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = result[result.length - 1];
if (intervals[i][0] <= last[1]) last[1] = Math.max(last[1], intervals[i][1]);
else result.push(intervals[i]);
}
return result;
}Problem: Find the minimum number of intervals to remove to make the rest non-overlapping.
function eraseOverlapIntervals(intervals) {
intervals.sort((a, b) => a[1] - b[1]); // sort by end time
let count = 0, end = -Infinity;
for (const [s, e] of intervals) {
if (s >= end) end = e; // no overlap
else count++; // overlap: remove current (keep earlier-ending)
}
return count;
}// Meeting Rooms I: can a person attend all meetings?
function canAttendMeetings(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
for (let i = 1; i < intervals.length; i++)
if (intervals[i][0] < intervals[i-1][1]) return false;
return true;
}
// Meeting Rooms II: minimum number of conference rooms required
function minMeetingRooms(intervals) {
const starts = intervals.map(i => i[0]).sort((a,b) => a-b);
const ends = intervals.map(i => i[1]).sort((a,b) => a-b);
let rooms = 0, endPtr = 0;
for (let i = 0; i < starts.length; i++) {
if (starts[i] < ends[endPtr]) rooms++;
else endPtr++;
}
return rooms;
}Time: O(n log n) | Space: O(n)
function reverseList(head) {
let prev = null, curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}function reverseList(head) {
if (!head || !head.next) return head;
const newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}function mergeTwoLists(l1, l2) {
const dummy = { next: null };
let curr = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next;
}
curr.next = l1 || l2;
return dummy.next;
}function mergeKLists(lists) {
const all = [];
for (let node of lists) while (node) { all.push(node.val); node = node.next; }
all.sort((a, b) => a - b);
const dummy = { next: null }; let curr = dummy;
for (const v of all) { curr.next = { val: v, next: null }; curr = curr.next; }
return dummy.next;
}function mergeKLists(lists) {
if (!lists.length) return null;
while (lists.length > 1) {
const merged = [];
for (let i = 0; i < lists.length; i += 2)
merged.push(mergeTwoLists(lists[i], lists[i+1] || null));
lists = merged;
}
return lists[0];
}function removeNthFromEnd(head, n) {
const dummy = { next: head };
let fast = dummy, slow = dummy;
for (let i = 0; i <= n; i++) fast = fast.next;
while (fast) { fast = fast.next; slow = slow.next; }
slow.next = slow.next.next;
return dummy.next;
}Problem: L0→Ln→L1→Ln-1→L2→Ln-2→…
function reorderList(head) {
// 1. Find middle
let slow = head, fast = head;
while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; }
// 2. Reverse second half
let prev = null, curr = slow.next;
slow.next = null;
while (curr) { const next = curr.next; curr.next = prev; prev = curr; curr = next; }
// 3. Merge two halves
let first = head, second = prev;
while (second) {
const [fn, sn] = [first.next, second.next];
first.next = second; second.next = fn;
first = fn; second = sn;
}
}function setZeroes(matrix) {
const m = matrix.length, n = matrix[0].length;
let firstRowZero = matrix[0].includes(0);
let firstColZero = matrix.some(row => row[0] === 0);
// Mark zeros in first row/col
for (let r = 1; r < m; r++)
for (let c = 1; c < n; c++)
if (matrix[r][c] === 0) { matrix[r][0] = 0; matrix[0][c] = 0; }
// Zero out cells
for (let r = 1; r < m; r++)
for (let c = 1; c < n; c++)
if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0;
if (firstRowZero) matrix[0].fill(0);
if (firstColZero) for (let r = 0; r < m; r++) matrix[r][0] = 0;
}function spiralOrder(matrix) {
const result = [];
let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (let c = left; c <= right; c++) result.push(matrix[top][c]); top++;
for (let r = top; r <= bottom; r++) result.push(matrix[r][right]); right--;
if (top <= bottom) { for (let c = right; c >= left; c--) result.push(matrix[bottom][c]); bottom--; }
if (left <= right) { for (let r = bottom; r >= top; r--) result.push(matrix[r][left]); left++; }
}
return result;
}Problem: Rotate an n×n matrix 90° clockwise in-place.
function rotate(matrix) {
const n = matrix.length;
// Step 1: Transpose
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
// Step 2: Reverse each row
for (let row of matrix) row.reverse();
}Problem: Find if a word exists in a grid of characters.
function exist(board, word) {
const m = board.length, n = board[0].length;
function dfs(r, c, i) {
if (i === word.length) return true;
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[i]) return false;
const temp = board[r][c];
board[r][c] = '#'; // mark visited
const found = dfs(r+1,c,i+1) || dfs(r-1,c,i+1) || dfs(r,c+1,i+1) || dfs(r,c-1,i+1);
board[r][c] = temp;
return found;
}
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (dfs(r, c, 0)) return true;
return false;
}function lengthOfLongestSubstring(s) {
let max = 0;
for (let i = 0; i < s.length; i++) {
const set = new Set();
for (let j = i; j < s.length; j++) {
if (set.has(s[j])) break;
set.add(s[j]); max = Math.max(max, j - i + 1);
}
}
return max;
}function lengthOfLongestSubstring(s) {
const map = new Map();
let max = 0, left = 0;
for (let right = 0; right < s.length; right++) {
if (map.has(s[right])) left = Math.max(left, map.get(s[right]) + 1);
map.set(s[right], right);
max = Math.max(max, right - left + 1);
}
return max;
}Problem: Replace at most k characters. Find the longest substring with same letters.
function characterReplacement(s, k) {
const count = new Array(26).fill(0);
let max = 0, maxCount = 0, left = 0;
for (let right = 0; right < s.length; right++) {
maxCount = Math.max(maxCount, ++count[s.charCodeAt(right) - 65]);
while ((right - left + 1) - maxCount > k) count[s.charCodeAt(left++) - 65]--;
max = Math.max(max, right - left + 1);
}
return max;
}Problem: Find the minimum window in s which contains all characters of t.
function minWindow(s, t) {
const need = new Map(), have = new Map();
for (const c of t) need.set(c, (need.get(c) || 0) + 1);
let formed = 0, required = need.size;
let lo = 0, result = [-1, 0, 0];
for (let hi = 0; hi < s.length; hi++) {
const c = s[hi];
have.set(c, (have.get(c) || 0) + 1);
if (need.has(c) && have.get(c) === need.get(c)) formed++;
while (formed === required) {
if (result[0] === -1 || hi - lo + 1 < result[0]) result = [hi - lo + 1, lo, hi];
const lc = s[lo++];
have.set(lc, have.get(lc) - 1);
if (need.has(lc) && have.get(lc) < need.get(lc)) formed--;
}
}
return result[0] === -1 ? '' : s.slice(result[1], result[2] + 1);
}function isAnagram(s, t) {
if (s.length !== t.length) return false;
const count = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - 97]++;
count[t.charCodeAt(i) - 97]--;
}
return count.every(c => c === 0);
}function groupAnagrams(strs) {
const map = new Map();
for (const s of strs) {
const key = [...s].sort().join('');
if (!map.has(key)) map.set(key, []);
map.get(key).push(s);
}
return [...map.values()];
}function isValid(s) {
const stack = [], map = { ')': '(', ']': '[', '}': '{' };
for (const c of s) {
if ('([{'.includes(c)) stack.push(c);
else if (stack.pop() !== map[c]) return false;
}
return stack.length === 0;
}function isPalindrome(s) {
let lo = 0, hi = s.length - 1;
while (lo < hi) {
while (lo < hi && !s[lo].match(/[a-z0-9]/i)) lo++;
while (lo < hi && !s[hi].match(/[a-z0-9]/i)) hi--;
if (s[lo].toLowerCase() !== s[hi].toLowerCase()) return false;
lo++; hi--;
}
return true;
}function longestPalindrome(s) {
let start = 0, maxLen = 0;
function expand(l, r) {
while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
if (r - l - 1 > maxLen) { maxLen = r - l - 1; start = l + 1; }
}
for (let i = 0; i < s.length; i++) { expand(i, i); expand(i, i + 1); }
return s.slice(start, start + maxLen);
}Problem: Count all palindromic substrings.
function countSubstrings(s) {
let count = 0;
function expand(l, r) {
while (l >= 0 && r < s.length && s[l] === s[r]) { count++; l--; r++; }
}
for (let i = 0; i < s.length; i++) { expand(i, i); expand(i, i + 1); }
return count;
}// Encode: prefix each word with its length and a delimiter
function encode(strs) {
return strs.map(s => `${s.length}#${s}`).join('');
}
function decode(s) {
const result = [];
let i = 0;
while (i < s.length) {
let j = i;
while (s[j] !== '#') j++;
const len = parseInt(s.slice(i, j));
result.push(s.slice(j + 1, j + 1 + len));
i = j + 1 + len;
}
return result;
}function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q || p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}function invertTree(root) {
if (!root) return null;
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
return root;
}function maxPathSum(root) {
let maxSum = -Infinity;
function dfs(node) {
if (!node) return 0;
const left = Math.max(0, dfs(node.left));
const right = Math.max(0, dfs(node.right));
maxSum = Math.max(maxSum, node.val + left + right); // path through this node
return node.val + Math.max(left, right); // return max single branch
}
dfs(root);
return maxSum;
}function levelOrder(root) {
if (!root) return [];
const result = [], queue = [root];
while (queue.length) {
const level = [], size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}function serialize(root) {
if (!root) return '';
const queue = [root], result = [];
while (queue.length) {
const node = queue.shift();
if (node) { result.push(node.val); queue.push(node.left, node.right); }
else result.push('null');
}
return result.join(',');
}
function deserialize(data) {
if (!data) return null;
const vals = data.split(',');
const root = { val: parseInt(vals[0]), left: null, right: null };
const queue = [root]; let i = 1;
while (queue.length) {
const node = queue.shift();
if (vals[i] !== 'null') { node.left = { val: parseInt(vals[i]), left: null, right: null }; queue.push(node.left); }
i++;
if (vals[i] !== 'null') { node.right = { val: parseInt(vals[i]), left: null, right: null }; queue.push(node.right); }
i++;
}
return root;
}function isSubtree(root, subRoot) {
if (!root) return false;
if (isSameTree(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q || p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}function buildTree(preorder, inorder) {
const map = new Map(inorder.map((v, i) => [v, i]));
function build(preStart, inStart, inEnd) {
if (preStart >= preorder.length || inStart > inEnd) return null;
const rootVal = preorder[preStart];
const mid = map.get(rootVal);
return {
val: rootVal,
left: build(preStart + 1, inStart, mid - 1),
right: build(preStart + mid - inStart + 1, mid + 1, inEnd)
};
}
return build(0, 0, inorder.length - 1);
}function isValidBST(root, min = -Infinity, max = Infinity) {
if (!root) return true;
if (root.val <= min || root.val >= max) return false;
return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}function kthSmallest(root, k) {
let count = 0, result = 0;
function inorder(node) {
if (!node) return;
inorder(node.left);
if (++count === k) { result = node.val; return; }
inorder(node.right);
}
inorder(root);
return result;
}function lowestCommonAncestor(root, p, q) {
while (root) {
if (p.val < root.val && q.val < root.val) root = root.left;
else if (p.val > root.val && q.val > root.val) root = root.right;
else return root;
}
}class TrieNode {
constructor() { this.children = {}; this.isEnd = false; }
}
class Trie {
constructor() { this.root = new TrieNode(); }
insert(word) {
let node = this.root;
for (const c of word) { if (!node.children[c]) node.children[c] = new TrieNode(); node = node.children[c]; }
node.isEnd = true;
}
search(word) {
let node = this.root;
for (const c of word) { if (!node.children[c]) return false; node = node.children[c]; }
return node.isEnd;
}
startsWith(prefix) {
let node = this.root;
for (const c of prefix) { if (!node.children[c]) return false; node = node.children[c]; }
return true;
}
}class WordDictionary {
constructor() { this.root = {}; }
addWord(word) {
let node = this.root;
for (const c of word) { if (!node[c]) node[c] = {}; node = node[c]; }
node['#'] = true;
}
search(word) {
return this._search(word, 0, this.root);
}
_search(word, i, node) {
if (i === word.length) return !!node['#'];
const c = word[i];
if (c === '.') return Object.keys(node).some(k => k !== '#' && this._search(word, i + 1, node[k]));
return !!node[c] && this._search(word, i + 1, node[c]);
}
}Problem: Find all words from a list that exist in the board (uses Trie for efficiency).
function findWords(board, words) {
// Build Trie
const root = {};
for (const word of words) {
let node = root;
for (const c of word) { if (!node[c]) node[c] = {}; node = node[c]; }
node['$'] = word;
}
const m = board.length, n = board[0].length, result = [];
function dfs(r, c, node) {
if (r < 0 || r >= m || c < 0 || c >= n) return;
const ch = board[r][c];
if (!ch || !node[ch]) return;
const next = node[ch];
if (next['$']) { result.push(next['$']); delete next['$']; }
board[r][c] = 0;
dfs(r+1,c,next); dfs(r-1,c,next); dfs(r,c+1,next); dfs(r,c-1,next);
board[r][c] = ch;
}
for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) dfs(r, c, root);
return result;
}function topKFrequent(nums, k) {
const map = new Map();
for (const n of nums) map.set(n, (map.get(n) || 0) + 1);
return [...map.entries()].sort((a, b) => b[1] - a[1]).slice(0, k).map(e => e[0]);
}function topKFrequent(nums, k) {
const map = new Map();
for (const n of nums) map.set(n, (map.get(n) || 0) + 1);
const buckets = new Array(nums.length + 1).fill(null).map(() => []);
for (const [num, freq] of map) buckets[freq].push(num);
const result = [];
for (let i = buckets.length - 1; i >= 0 && result.length < k; i--)
result.push(...buckets[i]);
return result.slice(0, k);
}// JS doesn't have a built-in heap; use a simple sorted insertion for interviews
// or implement MinHeap/MaxHeap
class MedianFinder {
constructor() {
this.lo = []; // max-heap (lower half)
this.hi = []; // min-heap (upper half)
}
addNum(num) {
// Push to max-heap (negate for min-heap simulation)
this.lo.push(num); this.lo.sort((a, b) => b - a);
// Balance: move max of lo to hi
this.hi.push(this.lo.shift()); this.hi.sort((a, b) => a - b);
// Ensure lo has >= elements
if (this.hi.length > this.lo.length) { this.lo.push(this.hi.shift()); this.lo.sort((a, b) => b - a); }
}
findMedian() {
if (this.lo.length > this.hi.length) return this.lo[0];
return (this.lo[0] + this.hi[0]) / 2;
}
}Note: For production-grade O(log n) insertion, implement a proper heap. The above is interview-friendly JavaScript.
This section covers topics most likely to appear in your Amazon FEI interview tomorrow based on frontend system design patterns, L5 expectations, and Amazon's LP-driven coding rounds.
Amazon FEI interviews typically test:
- JavaScript fundamentals (closures, event loop, prototypes)
- Browser/DOM (event delegation, throttle/debounce)
- Array/String problems (most common in phone screens)
- Trees (DOM is a tree — very relevant for FE roles)
- Dynamic Programming (medium difficulty)
| Problem | Why It Matters | Pattern |
|---|---|---|
| Two Sum | Foundational; always appears | HashMap |
| Valid Parentheses | DOM/JSON parsing analog | Stack |
| Longest Substring Without Repeating Chars | Sliding window; text editors | Sliding Window |
| Climbing Stairs | Intro DP; always asked | DP / Fibonacci |
| Level Order Traversal | Virtual DOM diffing / BFS | BFS |
| Maximum Subarray | Kadane's; analytics dashboards | DP / Greedy |
| Merge Intervals | Calendar features, scheduling | Intervals |
| LRU Cache | Often asked for FE caching | HashMap + DLL |
| Number of Islands | Grid traversal; maps/rendering | DFS/BFS |
| Top K Frequent Elements | Analytics, autocomplete | Heap / Bucket Sort |
function debounce(fn, delay) {
let timer;
return function(...args) {
clearTimeout(timer);
timer = setTimeout(() => fn.apply(this, args), delay);
};
}function throttle(fn, limit) {
let inThrottle;
return function(...args) {
if (!inThrottle) {
fn.apply(this, args);
inThrottle = true;
setTimeout(() => inThrottle = false, limit);
}
};
}class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map(); // maintains insertion order
}
get(key) {
if (!this.map.has(key)) return -1;
const val = this.map.get(key);
this.map.delete(key); this.map.set(key, val); // move to end (most recent)
return val;
}
put(key, value) {
if (this.map.has(key)) this.map.delete(key);
this.map.set(key, value);
if (this.map.size > this.capacity) this.map.delete(this.map.keys().next().value);
}
}function deepClone(obj, seen = new WeakMap()) {
if (obj === null || typeof obj !== 'object') return obj;
if (seen.has(obj)) return seen.get(obj);
const clone = Array.isArray(obj) ? [] : {};
seen.set(obj, clone);
for (const key of Object.keys(obj)) clone[key] = deepClone(obj[key], seen);
return clone;
}class EventEmitter {
constructor() { this.events = {}; }
on(event, cb) { (this.events[event] = this.events[event] || []).push(cb); return this; }
off(event, cb) { this.events[event] = (this.events[event] || []).filter(fn => fn !== cb); }
emit(event, ...args) { (this.events[event] || []).forEach(fn => fn(...args)); }
once(event, cb) {
const wrapper = (...args) => { cb(...args); this.off(event, wrapper); };
this.on(event, wrapper);
}
}When explaining your approach, mention:
- Customer Obsession → "I optimize for the end user by minimizing re-renders"
- Invent and Simplify → "Instead of a complex cache, a Map with O(1) access is elegant"
- Dive Deep → Explain time/space complexity unprompted
| Algorithm | Time | Space |
|---|---|---|
| HashMap lookup | O(1) | O(n) |
| Binary Search | O(log n) | O(1) |
| BFS/DFS on graph | O(V+E) | O(V) |
| Merge Sort | O(n log n) | O(n) |
| Kadane's (Max Subarray) | O(n) | O(1) |
| Sliding Window | O(n) | O(k) |
| Two Pointers | O(n) | O(1) |
| DP (1D) | O(n) | O(n) or O(1) |
- Think out loud — narrate your thought process before coding.
- Brute force first, then optimize — shows structured thinking.
- Clarify edge cases — empty input, single element, negative numbers.
- Amazon uses "bar raiser" — expect one round to be deliberately harder.
- Frontend specifics — you may get DOM, React, or browser API questions alongside DSA.
- Time yourself — aim to solve medium problems in under 20 minutes.
🍀 Good luck tomorrow! You've got this.