Amazon Interview Questions

Given an array and a target, find the two indices whose values sum to the target, typically solved in a single pass using a hash map that stores each value's complement as it's seen. It requires no advanced technique, which is exactly the point — it's a fast, low-friction warm-up used to confirm a candidate can reach for a hash map instead of defaulting to a brute-force O(n^2) nested loop.

Given a collection of intervals, merge all overlapping ones. The standard approach sorts intervals by start time, then does a single linear pass, extending the current merged interval whenever the next one overlaps and starting a new one otherwise. It's a foundational interval problem that shows up across many companies because interval merging underlies a large family of harder scheduling and calendar-style questions.

Given a list of strings, group the ones that are anagrams of each other. The typical solution hashes each string to a canonical key (either its sorted characters or a fixed-length character-count signature) and groups strings sharing a key in a hash map. It's a straightforward but reliable test of whether a candidate reaches for the right canonicalization strategy and understands the tradeoffs between sorting-based and counting-based keys.

Compute, for each index, the product of all array elements except the one at that index, without using division. The standard O(1)-extra-space solution builds a running prefix product and running suffix product in two passes, multiplying them together for the final answer. It tests array manipulation and space-optimization thinking — specifically whether a candidate can avoid the naive division-based shortcut and still hit optimal time and space.

Find the contiguous subarray with the largest sum, the textbook application of Kadane's algorithm: track the best sum ending at the current index (either extend the previous subarray or start fresh at the current element) alongside a running global maximum. It's one of the most fundamental dynamic-programming-style problems in interviewing, testing whether a candidate has the core DP intuition of 'best solution ending here' down cold.

Rotate an n x n matrix 90 degrees clockwise in place. The common technique is to transpose the matrix (swap elements across the diagonal) and then reverse each row, though a layer-by-layer four-way swap also works. It's a compact test of in-place matrix manipulation and geometric/index reasoning without needing any extra data structure.

Find all unique triplets in an array that sum to zero. The standard approach sorts the array, then for each element uses a two-pointer sweep over the remaining elements, carefully skipping duplicate values to avoid repeated triplets in the output. It extends the simpler two-pointer/two-sum pattern into a triplet setting and tests whether a candidate can handle the deduplication logic correctly, which is where most candidates lose points.

Given an elevation map, compute how much water it can trap after rain — the water trapped at each index equals the shorter of the tallest bars to its left and right, minus its own height. It's solvable with two pointers in O(1) extra space, with a monotonic stack, or with two precomputed max-prefix/max-suffix arrays, making it a great vehicle for comparing multiple valid techniques in one interview. Its breadth of companies asking it reflects that it's one of the most widely used checks of two-pointer/array reasoning in the entire interview circuit.

Convert a non-negative integer into its English words representation (e.g. 1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"). The approach breaks the number into groups of three digits, converts each group using lookup tables for ones/teens/tens and hundreds, then appends the appropriate scale word (thousand, million, billion) per group. It's not algorithmically deep, but it's implementation-heavy with many easy-to-miss edge cases (zero, teens, trailing zero groups), making it a good test of careful, methodical coding under a large but mechanical spec.

Count the number of contiguous subarrays that sum to exactly k. The efficient solution uses a running prefix sum alongside a hash map counting how many times each prefix-sum value has occurred, since a subarray sums to k exactly when the difference between two prefix sums equals k. It's a strong test of the prefix-sum-plus-hash-map pattern, a technique that generalizes to many other subarray-counting problems.

You may choose one contiguous subarray and one integer x, then add x to every element in that subarray exactly once, and must return the maximum possible frequency of a given target value k in the resulting array. The standard technique considers each candidate source value v that could be shifted into k (i.e. x = k - v), transforms the array into a scoring array (+1 where an element equals v, -1 where it already equals k, since shifting it away loses a k), then finds the best-scoring subarray with a Kadane's-style max-subarray-sum scan; the answer is k's original count plus the best score found across all choices of v. It tests whether a candidate can reduce an unfamiliar-sounding operation into a known max-subarray-sum pattern, which is the harder conceptual leap rather than the implementation itself.

Given an integer, you must pick a digit and replace every occurrence of it with another digit twice — once to maximize the resulting number and once to minimize it — then return the difference. Both are greedy digit-replacement problems: for the maximum, replace the first non-9 digit found with 9 everywhere it occurs; for the minimum, if the leading digit isn't already 1, replace all its occurrences with 1, otherwise scan the remaining digits for the first one that is neither 0 nor 1 and replace all its occurrences with 0 (skipping 0 and 1 avoids either a no-op or creating a leading zero). It tests careful case analysis on digit strings rather than any deep algorithm, and the leading-zero edge case is where most mistakes happen.

Given a log of (username, timestamp, website) visits, find the 3-website sequence (in chronological order) that was visited by the largest number of distinct users, breaking ties lexicographically. The approach groups visits by user and sorts each user's visits by timestamp, generates all distinct 3-length subsequences per user, and tallies how many unique users each subsequence appears for across everyone. It tests combining grouping/hashing with combinatorial subsequence generation and precise tie-breaking logic, rather than any single well-known algorithm.

Given a sorted array, find the first and last index of a target value in O(log n) time. The standard solution runs two separate binary searches — one biased to find the leftmost occurrence, one biased to find the rightmost — rather than a single search followed by linear scanning, which would break the required time complexity on arrays with many duplicates. It's a precise test of binary search boundary handling, a skill many candidates get subtly wrong under time pressure.

Given a set of points on a 2D plane, find the maximum number that lie on the same straight line. The typical approach fixes each point as a pivot and computes the slope to every other point, using a hash map keyed by a reduced-fraction (or normalized) slope representation to avoid floating-point precision errors, then takes the largest bucket size across all pivots. It tests geometric reasoning combined with hashing, plus careful handling of vertical lines and duplicate/overlapping points, which are easy to mishandle.

Find the length of the longest substring without repeating characters, the canonical sliding-window problem: maintain a window with two pointers and a hash map/set tracking the last-seen index of each character, jumping the left pointer forward whenever a repeat is found. It's one of the most fundamental sliding-window problems in interviewing and is often used to confirm a candidate can move beyond brute-force substring enumeration to a linear-time two-pointer approach.

Find the smallest substring of a string s that contains every character of another string t (respecting character multiplicities). The solution is a variable-size sliding window with a hash map of required character counts and a counter tracking how many distinct required characters are currently satisfied, expanding the right pointer until the window is valid and then greedily shrinking from the left. It's a step up from basic sliding-window problems because of the 'expand until valid, then shrink while still valid' two-phase logic, which trips up candidates who haven't internalized the pattern.

Given an array of heights, find two lines that, together with the x-axis, form the container holding the most water. The optimal solution uses two pointers starting from both ends, always moving the pointer at the shorter line inward (since moving the taller one can never increase the area), tracking the best area seen. It tests two-pointer greedy reasoning and, more importantly, whether a candidate can articulate why the greedy move is provably safe rather than just applying it by rote.

Given a string and an integer k, find the length of the longest substring that can be made to consist of a single repeated character by changing at most k characters. The solution is a sliding window that tracks the count of the most frequent character within the window; the window is valid as long as (window size - count of most frequent character) <= k, shrinking from the left otherwise. It's a meaningful step up from basic sliding-window problems since it requires tracking a running frequency count inside the window rather than just window boundaries.

This problem asks for the maximum value in every fixed-size window as it slides across an array, and the naive per-window scan is O(nk), so the real test is whether you can get to O(n) using a monotonic deque that stores candidate indices in decreasing order of value. You need to correctly pop from the back whenever a new element invalidates smaller values still in the deque, and pop from the front whenever the window's leftmost index expires. It's a strong signal for whether a candidate can reason about amortized complexity and maintain a non-obvious data-structure invariant under a moving constraint, rather than just knowing the deque trick by rote.

A grid graph-traversal problem: count connected components of '1' cells using DFS, BFS, or Union-Find, being careful with boundary checks and marking visited cells so you don't recount. It's one of the most common entry points into grid-based graph problems and is often used as a warm-up before harder multi-source or Union-Find variants. The core signal is whether a candidate can translate a 2D grid into an implicit graph and correctly implement flood-fill without off-by-one or infinite-loop bugs.

Given prerequisite pairs, this problem asks whether all courses can be finished, which is equivalent to detecting a cycle in a directed graph. Candidates typically solve it with Kahn's algorithm (in-degree tracking and a queue) for topological sort, or with DFS using a three-color (unvisited/visiting/visited) scheme to catch back edges. It tests fundamental graph modeling skills — representing prerequisites as an adjacency list and correctly distinguishing cycle detection from simple reachability.

This is a multi-source BFS problem: all initially rotten oranges are enqueued simultaneously, and the grid is processed level by level to find the minimum number of minutes until no fresh orange remains (or -1 if some are unreachable). It tests whether a candidate can generalize single-source BFS to multiple simultaneous sources and correctly track elapsed time via BFS levels rather than per-cell distance tracking. A common trap is starting BFS from a single source or forgetting to check for oranges that can never rot.

Word Ladder models words as nodes in an implicit graph, connecting two words if they differ by exactly one letter, and asks for the shortest transformation sequence from a start word to an end word via BFS. Because the graph isn't given explicitly, candidates must generate neighboring words on the fly (e.g., by trying all 26 letter substitutions at each position) and use a word dictionary/set for O(1) membership checks and visited tracking. Its practical relevance in interviews often ties to NLP transformations — reasoning about minimal edit-style paths between text tokens — which is one reason it recurs in ML-adjacent interview loops.

A harder follow-up to Number of Islands: first label each existing island via DFS/BFS and record its size, then for every water cell, check which distinct island labels are adjacent to it and sum their sizes plus one to see if flipping that cell creates a larger island. The key subtlety is deduplicating island labels around a single water cell so the same island isn't counted twice. It's a good test of whether a candidate can compose two passes of grid traversal — component labeling followed by a targeted second scan — rather than trying to solve everything in one pass.

This asks for the lowest common ancestor of two nodes in a general (non-BST) binary tree, solved with a recursive DFS that returns the found node upward once either target is located in a subtree. The elegant part is recognizing that if both left and right recursive calls return non-null, the current node is the LCA. It's a clean test of recursive tree thinking and correctly propagating and combining results from subtree calls.

A BFS-based level-order traversal where alternating levels are read left-to-right and right-to-left. The core work is standard queue-based BFS, with an added twist of tracking level parity and either reversing every other level's output or using a deque to build each level in the correct direction directly. It checks whether a candidate can extend a familiar BFS pattern with a small but easy-to-fumble stateful rule.

The diameter is the longest path between any two nodes, which may or may not pass through the root, so this problem requires computing subtree heights via DFS while simultaneously tracking a running maximum of left-height + right-height at every node. The common mistake is only considering paths through the root or recomputing height separately for each diameter check, leading to O(n^2). It's a good, low-difficulty test of whether a candidate can carry extra state through a standard recursive height computation.

A design problem: encode a binary tree into a string and reconstruct an identical tree from that string, typically via a preorder traversal with explicit null markers, or a BFS-based level encoding. The candidate must design a format that's unambiguous enough for deserialization to rebuild structure without extra information. Interview relevance frequently maps to data persistence — serializing structured data for storage or transmission and reliably reconstructing it — which is why it shows up across companies handling tree-like or hierarchical data on disk or over the wire.

Given a grid of letters and a list of target words, find every word that can be traced as a path of adjacent cells. The efficient solution builds a Trie from all target words, then does a DFS/backtracking search from every cell, using the Trie to prune paths that can't possibly extend into any remaining word. It's a strong signal problem because it requires combining two separate techniques — Trie construction and grid backtracking — rather than applying either in isolation.

Given a list of words sorted according to an unknown alphabet's ordering, the task is to reconstruct a valid character ordering: build a directed graph of precedence constraints from adjacent word comparisons, then topologically sort it (Kahn's algorithm or DFS-based), detecting cycles as an invalid/impossible ordering. The task is conceptually similar to inferring a token ordering from partial, pairwise evidence, which is plausibly why it resonates with companies doing tokenizer/vocabulary-adjacent ML work. It's a solid test of translating a word-comparison problem into a graph and correctly handling topological sort edge cases (cycles, ties, unreachable characters).

A classic backtracking problem: search a 2D letter grid for a given word by trying each cell as a starting point and exploring adjacent cells via DFS, marking cells visited during the current path and unmarking them (backtracking) before trying alternate paths. It tests whether a candidate can correctly manage mutable visited state across a recursive search and prune paths early when a character mismatch occurs. It's a strong signal for general backtracking competence, a technique that generalizes to many other constraint-search problems.

This problem can be solved with a fixed-size min-heap of size k (keeping the k largest elements seen so far) for O(n log k), or with quickselect — a partition-based approach related to quicksort — for expected O(n). It's frequently used to gauge whether a candidate knows more than one approach and can reason about the time/space tradeoffs between a heap-based streaming solution and an in-place partitioning one. Handling duplicate values and off-by-one indexing during partition are common places candidates slip up.

Requires counting element frequencies with a hash map, then selecting the k most frequent using either a heap (O(n log k)) or bucket sort by frequency (O(n)). It's a common building block for ML preprocessing workflows — identifying the most frequent tokens, features, or events in a dataset before further processing — which is part of why it recurs in ML-adjacent interview loops. The bucket-sort approach in particular tests whether a candidate recognizes that frequency is bounded by array length and can exploit that to avoid a full sort.

Merging k sorted linked lists efficiently requires either a min-heap holding the current head of each list (repeatedly popping the smallest and pushing its successor) or a divide-and-conquer pairwise merge, both achieving O(N log k). It tests whether a candidate can extend the two-list merge pattern to k lists and reason about the resulting complexity rather than defaulting to an O(Nk) linear scan across lists. Correct pointer management across multiple linked lists under time pressure is the practical difficulty.

A streaming-median design problem solved with two heaps: a max-heap holding the smaller half of seen values and a min-heap holding the larger half, rebalanced after each insertion so the median is always derivable from the heaps' tops in O(log n) per insert and O(1) per query. It tests whether a candidate can design a data structure that supports an evolving statistic under continuous insertion, a pattern that generalizes to other streaming-aggregate problems. Correctly maintaining the size invariant between the two heaps is the main source of bugs.

This asks whether a string's characters can be rearranged so no two adjacent characters are the same, and if so, to produce one such arrangement. The standard approach counts character frequencies, checks the feasibility condition (no character exceeds (n+1)/2 occurrences), and then greedily places the most frequent remaining characters using a max-heap. It tests the combination of a feasibility argument with a greedy, heap-driven construction, rather than pure search.

Given tasks with a cooldown period between identical tasks, this problem asks for the minimum total time (including idle slots) to complete them all. It can be solved with a closed-form formula based on the most frequent task's count and the number of tasks tied for that frequency, or simulated with a greedy max-heap approach. It tests whether a candidate can derive and justify a mathematical bound rather than only brute-force simulating the schedule.

Given parallel arrays x and y, this problem asks for three indices with pairwise-distinct x-values that maximize the sum of their corresponding y-values. Since only one index can ever be chosen per distinct x-value, the key insight is to keep only the maximum y for each x (via a hash map), then pick the three largest of those per-group maxima; if fewer than three distinct x-values exist, no valid triplet exists. It's a fairly recent LeetCode addition that tests clean hash-map grouping combined with a simple top-3 selection, rather than heavier algorithmic machinery.

This is a Huffman-coding-style greedy problem: repeatedly combine the two shortest sticks (using a min-heap), add their combined length back to the pool, and sum the costs of each combination until one stick remains. It tests whether a candidate recognizes the greedy-with-heap pattern for minimizing cumulative combination cost, a pattern that shows up in several other 'repeatedly merge the two smallest' problems. The proof that always merging the two smallest is optimal is a useful thing to be able to articulate.

A classic hard problem: given a set of building outlines (left edge, right edge, height), compute the skyline formed by their union as a sequence of key points. The standard approach uses a sweep line over building edges combined with a max-heap that supports lazy deletion — heights are pushed on left edges and only truly removed from consideration once the sweep passes their right edge, deferring actual heap cleanup. It's a strong signal for whether a candidate can combine event-based sweep-line reasoning with a non-trivial heap variant.

For each element, this asks how many elements to its right are strictly smaller than it — a problem that resists brute force at scale (O(n^2)) and instead calls for an order-statistics structure. Common approaches are a modified merge sort that counts cross-inversions during the merge step, or a Binary Indexed Tree (Fenwick tree) over coordinate-compressed values. It's a solid test of whether a candidate can adapt a familiar algorithm (merge sort) to simultaneously answer a counting query, or apply a Fenwick tree correctly with coordinate compression.

This asks for the longest contiguous palindromic substring, typically solved by expanding around each possible center (accounting for both odd- and even-length palindromes) in O(n^2), or via dynamic programming over substring start/end pairs, with Manacher's algorithm as the O(n) approach for candidates who know it. It's a common medium-difficulty string problem that tests careful index handling and awareness of the difference between substrings and subsequences. Interviewers often use it to see whether a candidate can identify and handle the odd/even-length edge case cleanly.

A canonical unbounded-knapsack dynamic programming problem: given coin denominations and a target amount, find the minimum number of coins needed to make that amount (or determine it's impossible). The standard solution builds a bottom-up DP array where each amount's answer depends on smaller amounts reduced by each coin denomination. It's often used to gauge whether a candidate can correctly set up and reason about a 1D DP recurrence and its base cases, a foundational skill for many other DP problems.

Unlike the maximum-sum subarray problem, this requires tracking both the running maximum and running minimum product ending at each index, because multiplying by a negative number can flip a very negative product into the new maximum. It's a good test of whether a candidate notices this sign-flip subtlety rather than naively adapting Kadane's algorithm for sums. Handling zeros, which reset both running values, is another common edge case.

Given an array of maximum jump lengths from each position, this asks whether the last index is reachable from the first. The efficient solution is a single greedy left-to-right pass tracking the farthest index reachable so far, rather than exploring all possible jump sequences. It's a clean test of whether a candidate can replace an exponential search-space approach with a greedy O(n) argument and justify why the greedy choice is safe.

This asks for the maximum profit from a single buy and sell of one share, given a sequence of daily prices. The optimal solution is a single pass that tracks the minimum price seen so far and the best profit achievable by selling at the current price. Despite being an easy problem, it's a useful check for whether a candidate defaults to an unnecessary O(n^2) pairwise comparison or immediately sees the one-pass greedy/DP formulation.

A harder variant of Word Break that asks not just whether a string can be segmented into dictionary words, but for all possible segmentations as space-separated sentences. It requires combining dynamic programming (or memoized recursion) with backtracking to build and return every valid sentence, and memoization is essential to avoid exponential blowup on inputs with many overlapping valid segmentations. It tests whether a candidate can extend a decision-problem DP into an enumeration problem while still controlling complexity.

A well-known hard interval dynamic programming problem: given balloons with values, bursting a balloon yields coins based on its neighbors at the time of bursting, and the goal is to maximize total coins from bursting all balloons. The key insight is to think in reverse — deciding which balloon is burst last within a subrange — which turns an order-dependent problem into a clean interval DP over subranges bounded by two virtual balloons of value 1. It's a strong signal for whether a candidate can find a non-obvious DP state definition when the naive greedy or ordering-based approach fails.

Given a string of digits representing an encoded message (where 'A'=1 through 'Z'=26), this asks for the number of ways it can be decoded, solved with a 1D DP similar in structure to climbing stairs but with extra validity checks for one- and two-digit groupings (including the '0' edge case, which can only appear as the second digit of a valid two-digit code). It tests careful handling of string-parsing edge cases within an otherwise standard DP recurrence.

Given a string and a dictionary of words, this asks whether the string can be segmented into a space-separated sequence of dictionary words. The standard solution is DP where dp[i] indicates whether the prefix of length i can be segmented, checking all dictionary words as potential suffixes ending at each position. It's a foundational string-DP problem and often a stepping stone to the harder Word Break II, testing whether a candidate can define and fill a boolean DP array correctly.

A design problem requiring O(1) get and put operations with least-recently-used eviction, implemented by combining a hash map (for O(1) lookup) with a doubly linked list (for O(1) reordering and eviction from either end). This exact structure underlies real inference key-value caches — it's reportedly one of the most frequently asked design questions at companies building LLM inference systems, since eviction policy for a bounded cache maps directly onto managing GPU memory for attention KV caches. It's a strong test of whether a candidate can compose two data structures to get O(1) across every required operation, not just some of them.

This design problem requires insert, remove, and getRandom to all run in O(1) average time, which rules out a plain hash set (no O(1) random access) or a plain array (no O(1) removal by value). The standard solution pairs an array (for O(1) indexed random access) with a hash map from value to array index, and handles removal by swapping the target element with the last array element before popping, keeping the array dense. It tests whether a candidate can identify which single data structure fails which requirement and combine two structures to satisfy all three simultaneously.

A harder relative of LRU Cache: eviction is based on least frequency of use (with least-recently-used as a tiebreaker), requiring O(1) get and put. The standard solution uses a hash map from key to value/frequency plus a second structure — typically frequency buckets implemented as doubly linked lists, tracked with a pointer to the current minimum frequency — to keep every operation O(1). This is a genuinely advanced caching pattern relevant to systems needing usage-aware eviction beyond simple recency, which is why it appears in interview loops as a step up from LRU Cache once a candidate has demonstrated that baseline.

This design problem asks for a simplified in-memory file system supporting operations like ls, mkdir, addContentToFile, and readContentFromFile. It's typically modeled as a tree (or trie-like structure) of nodes representing directories and files, where each node tracks its children and, for files, accumulated content. It tests whether a candidate can design a coherent object model for a hierarchical namespace and correctly implement path parsing and traversal across multiple related operations.

This design problem asks for a system that, as a user types characters one at a time, returns the top 3 historical sentences matching the current prefix, ranked by frequency (and lexicographically to break ties). It's commonly implemented with a trie augmented with sentence frequency counts at terminal nodes, combined with a traversal or small heap to extract the top matches at each keystroke. It's a good test of whether a candidate can combine a trie for prefix matching with a ranking mechanism, and manage incremental state across a sequence of calls.

This design problem asks for a counter that records hits with timestamps and can report the number of hits in the past 300 seconds. It's typically implemented with a queue (or a fixed-size circular buffer of timestamp/count pairs) that evicts entries falling outside the trailing time window as new hits arrive. It tests whether a candidate can design a data structure for a sliding time window under both single-hit and (in a common follow-up) batched-hit conditions.

This asks for reordering a linked list so nodes are interleaved from the front and back (L0, Ln, L1, Ln-1, ...) in place, without using extra array storage for full random access. The standard solution finds the middle with slow/fast pointers, reverses the second half, and then merges the two halves alternately. It's a good test of whether a candidate can compose three separate linked-list techniques — midpoint finding, in-place reversal, and merge — into one coherent solution.