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

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.

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.

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

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.

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

Given a string and a list of (index, source, target) replacement operations, you must apply only the operations whose source substring actually matches at the given index, without letting earlier replacements shift the positions used by later ones. The clean approach is to sort or process operations by index and build the result in a single left-to-right pass, applying replacements only where they validate. It's mainly a simulation/indexing problem that tests careful, bug-free handling of string offsets under a specific ordering constraint rather than a named algorithm.

You must pick exactly k cards from either end of an array to maximize their sum. The standard trick is to reframe it as finding the minimum-sum contiguous window of size (n - k) in the middle of the array, then subtracting that from the total — turning a two-ended selection problem into a straightforward sliding window. It's a good test of whether a candidate can spot a non-obvious reformulation that reduces a seemingly two-pointer problem to a single fixed-size window.

Given a list of words, you need to find the longest chain where each word is formed by inserting exactly one letter into the previous word. It's solved with dynamic programming: sort words by length, and for each word try removing one character at a time to look up the best chain length ending at that shorter predecessor in a hash map. It tests whether a candidate can combine sorting, hashing, and a DP-over-strings formulation rather than brute-forcing all pairs.

Given a set of 2D points, find the minimum-area axis-aligned rectangle that can be formed using four of them as corners. The standard approach hashes points by column (or stores all points in a set) and checks pairs of points sharing the same x-coordinates as potential right-left edges, verifying the other two corners exist and tracking the minimum area. It's a solid signal for geometric reasoning combined with efficient hashing/lookups instead of a naive O(n^4) corner search.

This is a design problem: you add points one at a time and must answer queries asking how many axis-aligned squares can be formed using a given point as one corner and three previously added points as the others. It's solved with a hash map counting occurrences of each point, then for a query, iterating over points sharing the query's x or y coordinate and checking whether the remaining two corners exist. It tests the ability to design an incremental data structure with fast add/count operations rather than recomputing from scratch on every query.

You need to count triplets of indices i < j < k such that nums[i], nums[j], and nums[k] are all pairwise distinct values. A hash map counting frequency of each value lets you compute the count combinatorially (for each distinct value, multiply how many valid choices exist before/at/after it) instead of the brute-force O(n^3) triple loop. It's a lighter, easy-tier problem mainly testing comfort with frequency counting and combinatorics.

A terrain-simulation problem: water droplets are poured one at a time onto an array representing heights, and each droplet flows left or right toward the lowest reachable point before settling (with left preferred as a tiebreak). It requires careful, step-by-step array simulation rather than a shortcut formula, and Google/Airbnb use it as a check of whether a candidate can correctly implement a stateful physical process with several interacting edge cases (flat ground, walls, no valid drop point).

Given a grid where 1s mark people's houses, find the point that minimizes the total Manhattan distance everyone has to travel to meet there. The key insight is that Manhattan distance is separable into independent x and y components, and the point minimizing total distance along each axis is the median of that axis's coordinates — so you sort the row and column indices separately and sum distances to their medians. It's a strong signal for whether a candidate recognizes when a 2D optimization decomposes into two independent 1D median problems.

A stack-based string-processing problem: decode a nested, run-length-encoded string like "3[a2[c]]" into its expanded form, where the nesting can go arbitrarily deep. The standard approach pushes the current string and repeat count onto a stack whenever a '[' is seen and pops/multiplies/concatenates on ']'. It's a clean test of stack-based parsing and correctly handling nested state, which is exactly why it's used across companies as a string-processing check.

Given a researcher's citation counts, compute their h-index — the largest h such that at least h papers have at least h citations each. It tests whether a candidate can sort the array (or use counting sort for a linear-time variant) and reason precisely about the threshold condition, including edge cases where no papers or all papers qualify. It's a good signal for translating a somewhat abstract, real-world-sounding metric definition into a precise algorithmic condition.

Each day you paint an interval on a number line, and you need to report how much of that day's interval was newly painted (i.e., not already painted by a previous day). It's typically solved with a Union-Find structure where each position points to the next unpainted position, letting you "jump over" already-painted ranges in near-constant amortized time instead of re-scanning them, or alternatively with a segment tree tracking the maximum unpainted position in a range. It's a hard interval-processing problem that tests whether a candidate can apply Union-Find outside its typical connectivity use case.

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.

A classic topological-sort problem: given courses and prerequisite pairs, return a valid ordering (or detect that no valid ordering exists due to a cycle). It tests whether a candidate can build an adjacency list, track in-degrees, and run Kahn's BFS algorithm (or DFS with visited/in-progress marking) to order and cycle-detect simultaneously. Its broad company reach reflects how often real systems need this exact shape of problem — resolving build or package dependency order, or task scheduling graphs — making it a reliable signal for graph traversal fluency.

A classic tree-validation problem: determine whether a binary tree satisfies the BST property (every node's value strictly between the min/max bounds implied by its ancestors). The clean solution recurses while passing down valid (low, high) bounds, or does an in-order traversal and checks the sequence is strictly increasing. It's a common warm-up problem that quickly reveals whether a candidate falls into the common trap of only comparing a node to its immediate children instead of the full ancestor range.

A hard tree problem: find the maximum sum of any path between any two nodes in a binary tree, where the path need not pass through the root. It tests whether a candidate can write a DFS that returns the best single-branch sum upward to a parent (for the recursive contract) while separately tracking a global maximum that considers both branches meeting at the current node. It's a well-known hard-tier tree-recursion problem precisely because those two concerns are easy to conflate.

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.

You're given a reference to a node in a connected undirected graph and must produce a deep copy of the entire graph. The standard solution does a DFS or BFS traversal while maintaining a hash map from original nodes to their clones, so previously cloned nodes are reused instead of duplicated when revisited through a cycle. It's a strong, widely-used signal for graph traversal fundamentals plus correct handling of cycles and already-visited state — a very common building-block interview problem across big tech.

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 list of accounts, each with a name and a set of emails, you must merge accounts that share at least one email into a single account. This is a textbook Union-Find (disjoint set union) application: union accounts whenever they share an email, then group all emails by their root account and sort them. It's a good signal for whether a candidate recognizes a merging/grouping problem as Union-Find rather than reaching for a slower graph-traversal approach.

You're given equations like a / b = k and must answer queries of the form c / d using those relationships, including through chains of intermediate variables. It's modeled as a weighted graph (or weighted Union-Find) where an edge a→b has weight k, and each query is answered via a DFS/BFS path search accumulating the product of edge weights along the way. It tests whether a candidate can translate an algebraic relationship into a graph-traversal problem rather than trying to solve it purely with equations.

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

Given a list of friendship events with timestamps, find the earliest time at which everyone in the group is connected (directly or transitively) to everyone else. The solution sorts events by timestamp and processes them through a Union-Find structure, checking after each union whether all people now belong to a single connected component. It's a clean test of combining sorting with incremental Union-Find to detect the moment a graph becomes fully connected.

Given a graph with weighted edges and a batch of queries asking "is there a path between two nodes using only edges of weight less than some limit?", you need to answer all queries efficiently. The standard approach sorts both edges and queries by weight/limit, then processes them in increasing order while incrementally unioning edges into a Union-Find structure as their weight threshold is met, answering each query using the current connectivity state. It's a hard problem testing whether a candidate can combine offline query processing with incremental Union-Find rather than solving each query independently.

Given a binary tree and two node values, produce the step-by-step directions (Left/Right/Up) to navigate from the start node to the destination node. The approach finds the paths from the root to each node via DFS, locates their lowest common ancestor as the point where the paths diverge, then emits "Up" moves for the remaining path to the LCA followed by the downward path to the destination. It tests comfort combining root-to-node path tracking with LCA reasoning into a single directional-path construction.

You're given an elevation grid and water that rises over time; you need the minimum time at which a path exists from the top-left to the bottom-right where every cell on the path has elevation at or below the current water level. It's commonly solved with a Dijkstra-style priority queue that always expands the lowest-elevation-so-far frontier cell, or with binary search on the answer combined with a BFS/DFS reachability check. It's a strong signal for recognizing a "minimize the maximum value along a path" problem as a variant of shortest-path search rather than plain grid BFS.

Given a grid of heights, find a path from the top-left to bottom-right that minimizes the maximum absolute height difference between consecutive cells along the path. Like Swim in Rising Water, it's typically solved with a Dijkstra-style priority queue tracking the minimum possible "effort" to reach each cell, or with binary search on the answer paired with a BFS/DFS feasibility check. It's a good test of recognizing the same minimax-path pattern across superficially different problem framings.

You must repeatedly remove all leaf nodes from a binary tree and record each removed "layer" as a separate list, until the tree is empty. The efficient solution computes each node's height via DFS and buckets nodes into output lists by that height (nodes with height 0 are leaves removed first, and so on), avoiding literal repeated leaf removal. It tests whether a candidate can reframe an iterative removal process as a single DFS pass using computed depth/height values.

Given a grid of heights representing an island bordered by the Pacific on two sides and the Atlantic on the other two, find all cells from which water can flow to both oceans (water flows to equal or lower neighboring cells). The efficient approach runs multi-source BFS or DFS inward from each ocean's border cells separately, then intersects the two reachable sets, rather than testing every cell individually outward. It's a strong signal for recognizing when reversing the direction of search (from the boundaries inward) turns an expensive per-cell search into two linear passes.

Given a list of words, find the longest word that can be built one character at a time by other words also present in the list (i.e., every prefix of the answer must also be a word in the dictionary). It's solved either by sorting words and using a hash set to track which prefixes are "buildable," or by inserting all words into a trie and DFS-ing to find the deepest fully-valid path. It tests string/data-structure design for prefix-based validity, a common precursor to more advanced trie problems.

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.

The classic Levenshtein distance problem: compute the minimum number of insert/delete/replace operations to transform one string into another. It's solved with a 2D dynamic programming table where dp[i][j] represents the edit distance between the first i and j characters of each string, built from the standard recurrence over matching/non-matching characters. It's one of the most canonical DP-on-two-strings problems in interviewing and a strong signal for whether a candidate can derive a DP recurrence from first principles rather than recalling it by rote.

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.

Given an integer array, find the length of the longest strictly increasing subsequence. It tests whether a candidate can move from the straightforward O(n^2) dynamic-programming solution to the O(n log n) approach using binary search over a maintained array of smallest tail values for increasing subsequences of each length. It's a well-known bar for whether a candidate can optimize a DP solution using an auxiliary data structure rather than stopping at the first correct-but-slower approach.

A hard problem: find the length of the longest strictly increasing path in a matrix, moving in four directions. It tests whether a candidate can combine DFS with memoization — treating each cell's longest path as a subproblem cached to avoid recomputation — effectively turning the matrix into a DAG (since values only increase along a path) that supports dynamic programming. It's a good signal for recognizing when grid traversal needs memoization to avoid exponential blowup.

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 an array and an integer m, split the array into m contiguous subarrays to minimize the largest sum among them. The standard technique is binary search on the answer (the candidate "largest sum" value), paired with a greedy check that verifies whether the array can be split into at most m parts without exceeding that candidate sum. It's a strong test of the less-obvious "binary search on the answer" pattern rather than a direct DP or greedy-only solution.

Given an array and a target difference, find the length of the longest subsequence that forms an arithmetic sequence with exactly that common difference. It's solved with dynamic programming using a hash map keyed by value, where dp[v] stores the longest chain ending in value v, updated as dp[v] = dp[v - difference] + 1 while scanning left to right. It's a clean test of recognizing that a subsequence-chain DP can be indexed by value instead of by index when the required relationship (constant difference) makes that more efficient.

Given a grid of points where you must pick exactly one cell per row, and moving from column c in one row to column c' in the next row costs |c - c'| (subtracted from your score), maximize total points collected. A naive DP is O(rows * cols^2); the efficient solution computes running left-to-right and right-to-left maximums of (previous row's DP value adjusted for distance) to bring each row down to O(cols), yielding O(rows * cols) overall. It's a strong signal for whether a candidate can optimize an already-correct DP by restructuring the transition rather than settling for a suboptimal complexity.

Given a binary matrix, count how many square submatrices consist entirely of 1s. It uses a dynamic programming approach nearly identical to the "Maximal Square" problem: dp[i][j] represents the side length of the largest all-ones square with its bottom-right corner at (i, j), computed as 1 + min of the three neighboring dp values when the cell is 1, and the answer is the sum of all dp values (since each dp[i][j] also counts every smaller square rooted there). It's a good follow-up-style problem for testing whether a candidate can extend a known DP pattern to a counting variant.

A binary-search problem: find a target value's index in a rotated sorted array in O(log n) time. It tests whether a candidate can identify which half of the array around the midpoint is properly sorted at each step, then decide whether the target falls within that sorted half or the other one. Its wide reach across companies reflects how well it isolates genuine binary-search intuition from candidates who only know the textbook sorted-array version.

A binary-search-on-the-answer problem: find the minimum eating speed that lets Koko finish all banana piles within h hours. Because a higher speed always finishes in fewer-or-equal hours (a monotonic relationship), the candidate binary searches over possible speeds and uses an O(n) greedy check (summing ceil(pile/speed) for each pile) to test feasibility at each candidate speed. It's a frequently reused pattern-recognition test for spotting monotonic feasibility problems that don't look like a search problem on the surface.

A hard problem: find the median of two sorted arrays in O(log(min(m,n))) time. It tests whether a candidate can go beyond the trivial O(m+n) merge approach to a binary-search-on-partitions technique, correctly reasoning about partition boundaries and edge cases like empty arrays or odd/even combined length. It's one of the most well-known hard-tier binary search problems and a strong filter for candidates who can handle intricate boundary logic under pressure.

A foundational data-structure design problem: implement insert, search, and startsWith operations for a prefix tree, typically using nested hash maps or fixed-size child arrays per node. It tests whether a candidate understands how tries achieve O(L) lookups (L = word length) independent of dictionary size, and can reason cleanly about node structure and end-of-word marking. It's a common warm-up before harder trie-based follow-ups like wildcard search or autocomplete, and is frequently used to gauge comfort with recursive tree-like structures.

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

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.

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.

A design problem: implement a logger that only allows a given message to be printed once every 10 seconds, ignoring duplicate calls within that window. The straightforward solution is a hash map from message to the last timestamp it was allowed through, checked and updated on each call. It's a lightweight design problem mainly testing clean state management for a rate-limiting rule rather than any advanced algorithm.

You need a data structure supporting both point updates to an array and efficient sum queries over arbitrary ranges. The standard solutions are a Binary Indexed Tree (Fenwick tree) or a segment tree, both of which support update and range-sum queries in O(log n) instead of the O(n) an update-then-recompute or naive-array approach would require. It's a foundational test of whether a candidate knows and can implement one of these classic range-query structures.

Given an array, count the number of contiguous subarrays whose sum falls within a given [lower, upper] range. It's a hard problem typically solved by computing prefix sums and then counting, for each prefix, how many earlier prefixes fall within the corresponding range — done efficiently via a modified merge sort or a Binary Indexed Tree over coordinate-compressed prefix sums, since brute force is O(n^2). It's a strong signal for combining prefix-sum reasoning with an advanced counting structure like merge sort's divide-and-conquer counting trick or a BIT.