Meta Interview Questions

A stack-based string problem: you scan the string tracking indices of unmatched parentheses (pushing open-paren indices onto a stack and popping when a matching close is found), then remove any indices left on the stack or any close parens with no matching open. It tests whether a candidate can correctly track and later reference input positions rather than just counting balance, since simple counter-based approaches miss which specific characters to remove. It's a well-known Meta-favorite string/stack problem, frequently paired with a follow-up about restoring the closest valid string.

A two-pointer palindrome problem with a twist: after finding the first mismatched pair moving inward from both ends, you must check whether skipping either the left or right character produces a valid palindrome for the remainder. It tests whether a candidate can extend a straightforward two-pointer palindrome check into a one-off greedy branch, and correctly reason that only one deletion is ever allowed. It's frequently used as a natural follow-up after the plain Valid Palindrome problem in the same interview.

A classic two-pointer string problem: you compare characters from both ends moving inward, skipping non-alphanumeric characters and normalizing case along the way. It's a fast check of whether a candidate can handle input-cleaning logic and pointer bookkeeping correctly, and it's frequently used as a warm-up before harder palindrome variants like Valid Palindrome II. Its simplicity makes it a good gauge of coding speed and precision under time pressure rather than algorithmic depth.

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.

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.

An in-place array problem: you move all non-zero elements to the front in their original relative order while pushing zeroes to the end, ideally in a single pass using a slow/fast pointer pair and minimizing swaps or writes. It tests whether a candidate can reason about in-place array mutation without extra space while maintaining relative order, a common building block for larger array manipulation problems. It's typically used as a fast confidence-building problem early in an interview.

A stack-and-string-parsing problem: evaluate an expression containing +, -, *, / (no parentheses) while respecting standard operator precedence. The typical approach scans left to right, pushing signed numbers onto a stack and immediately resolving * and / against the last pushed value, then summing the stack at the end. It's a solid check of careful state-machine parsing and edge-case handling (multi-digit numbers, whitespace, consecutive operators) under time pressure.

An array problem best solved by scanning from right to left while tracking the maximum height seen so far, keeping any building taller than everything to its right (since those are the ones with an unobstructed ocean view). It tests whether a candidate can find the right traversal direction to turn what looks like an O(n²) comparison problem into a single O(n) pass, similar in spirit to a monotonic stack problem. It's a good signal for recognizing when a reversed scan simplifies a 'compare against everything to one side' problem.

A counting/hash map problem: you tally the frequency of each character in the string to be sorted, then output characters in the order specified by the custom-order string (consuming counts as you go), and append any leftover characters not mentioned in the order at the end. It tests basic but precise hash map or counting-array manipulation and careful handling of characters absent from the custom order. It's typically a fast, low-friction problem confirming string/hash map fluency early in an interview.

Given an array and an integer k, determine whether the array has a contiguous subarray of size at least two whose sum is a multiple of k. It tests whether a candidate can use the prefix-sum-modulo trick — storing the first index at which each remainder (prefix sum mod k) occurs in a hash map, since two prefixes sharing the same remainder means the subarray between them sums to a multiple of k. It's a classic example of turning a divisibility condition into a hash-map lookup problem, a pattern that appears in several subarray-sum variants.

A string-simulation problem that reimplements grade-school addition: you walk both number strings from the least significant digit, add corresponding digits plus a running carry, and prepend each result digit, without converting the strings to native integers (real interview variants extend to numbers larger than fit in standard integer types). It tests careful handling of differing string lengths, the trailing carry, and off-by-one indexing. It's a good signal for meticulous, low-abstraction coding rather than algorithmic insight.

A greedy digit-array problem: to maximize a number with at most one swap, you want to move the largest available later digit as far left as possible, which you can find efficiently by tracking, for each digit position, the rightmost occurrence of each digit 0-9. It tests whether a candidate can reformulate 'try every pair of swaps' (an O(n²) brute force) into a single-pass greedy solution using precomputed last-occurrence indices. It's a solid Medium-tier signal for translating a brute-force intuition into an optimized one.

A two-pointer string-parsing problem: you walk the word and its abbreviation simultaneously, matching literal characters directly and consuming runs of digits in the abbreviation to skip that many characters in the word, while enforcing rules like no leading zeros in a number. It tests careful edge-case handling in parsing logic rather than any advanced algorithm. It's commonly used to check attention to detail and defensive coding under multiple validation constraints at once.

A straightforward two-pointer string problem: you build the result by alternating characters from each input string and appending whatever remains once the shorter string is exhausted. It mainly tests careful index management and clean handling of unequal string lengths rather than any deep algorithmic insight. It's typically used as a fast warm-up problem to confirm basic string-manipulation fluency.

A matrix-traversal simulation problem: you output elements along each diagonal, alternating traversal direction (up-right, then down-left) between successive diagonals, which requires careful boundary handling whenever a diagonal walk hits the top, bottom, left, or right edge of the matrix. It tests whether a candidate can simulate a non-trivial 2D traversal pattern correctly across many edge cases without an elegant closed-form shortcut. It's a solid signal for meticulous index bookkeeping under a moderately complex traversal rule.

A classic in-place array algorithm: find the rightmost position where the sequence stops strictly increasing (scanning from the right), swap that element with the smallest element to its right that's still larger than it, then reverse the suffix to get the smallest lexicographic arrangement greater than the current one. It tests whether a candidate knows or can derive this specific non-obvious three-step algorithm, since a naive approach (generating and sorting all permutations) doesn't scale. It's a strong signal for algorithmic pattern recognition, since the technique itself, not just the coding, is the crux of the problem.

A two-pointer problem over two separately-sorted lists of intervals: you advance through both lists simultaneously, computing the overlap of the current pair of intervals when one exists, and advance whichever interval ends first. It tests whether a candidate can correctly reason about interval overlap conditions and pointer advancement logic without missing or double-counting intersections. It's a good Medium-tier signal for interval-based two-pointer technique, a pattern that recurs across many scheduling-style problems.

A string-parsing and validation problem: you must determine whether an input string is a valid IPv4 address, valid IPv6 address, or neither, which requires splitting on the right delimiter and checking format-specific rules (e.g. no leading zeros and ranges 0-255 for IPv4; valid hex digit groups of correct length for IPv6). It tests meticulous, defensive parsing across many edge cases rather than any real algorithmic technique. It's a strong signal for how a candidate handles a long list of finicky validation rules without missing one under time pressure.

A stack-based string problem: you maintain a stack of (character, count) pairs, incrementing the count when the next character matches the stack top and popping the entry once its count reaches k, then reconstructing the remaining string. It tests whether a candidate can generalize the simpler 'remove adjacent duplicate pairs' pattern to an arbitrary k using a stack that tracks run-lengths rather than repeatedly rescanning the string. It's a good signal for extending a known stack pattern to a parameterized version under time pressure.

A string problem with a number-theory core: two strings have a valid 'GCD string' only if concatenating them in both orders gives the same result, and if so, the answer is the prefix of length gcd(len1, len2). It tests whether a candidate can find and justify a non-obvious mathematical characterization rather than brute-forcing over all possible candidate substrings. It's a good signal for mathematical reasoning applied to a string problem, a less common combination than typical string/array interview questions.

A simple matrix-traversal problem: a matrix is Toeplitz if every diagonal from top-left to bottom-right has the same value, which you can check by comparing each cell to its lower-right neighbor across the whole matrix. It's a fast, low-friction signal for correct 2D indexing and boundary handling, with a natural follow-up about handling a matrix too large to fit in memory (processed as a row-by-row stream). It's typically used as a quick early-interview problem.

A problem that can be solved either with a trie (inserting every prefix of every number in one array as digit sequences, then querying the longest matching prefix against numbers in the other array) or with a hash set of all prefixes for fast lookup. It tests whether a candidate recognizes 'longest common prefix across many numbers' as a trie-shaped problem rather than doing pairwise comparisons, which would be far too slow at scale. It's a solid Medium-tier signal for trie fluency, a data structure many candidates only know in theory.

A sliding window problem using a hash map to track character counts within the current window: you expand the window's right edge, and shrink from the left whenever the number of distinct characters in the map exceeds k, tracking the maximum valid window length throughout. It tests the general 'sliding window plus frequency map' pattern that recurs across many string problems (e.g. longest substring without repeating characters, minimum window substring). It's a strong Medium-tier signal for whether a candidate can manage window state and shrink conditions correctly.

A design problem built around a 2D prefix-sum table: you precompute cumulative sums so that any rectangular sub-region's sum can be answered in O(1) using inclusion-exclusion over four prefix-sum lookups, after an O(rows × cols) preprocessing step. It tests whether a candidate can correctly derive and index the 2D prefix-sum formula, which trips up many candidates on the exact off-by-one boundary terms. It's a good signal for whether someone has internalized prefix sums beyond the simpler 1D case.

A Hard-tier array problem solved with an in-place, index-as-hash-table technique: you place each positive number ≤ n at its correct index (value v goes to index v-1) via swaps, then scan for the first index whose value doesn't match, all within O(n) time and O(1) extra space. It tests whether a candidate can find a genuinely non-obvious optimal solution rather than the natural but disallowed approach (a hash set), since the O(1)-space constraint is the entire point of the problem. It's a strong signal for algorithmic creativity under a tight space constraint, commonly used to differentiate strong candidates in a Hard-tier slot.

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.

A foundational linked-list problem: you merge two sorted linked lists into one sorted list by walking both simultaneously and re-linking nodes in order, typically using a dummy head node to simplify edge cases. It's a fast check of basic linked-list pointer manipulation and the dummy-node technique, both of which recur throughout harder linked-list problems (merge k lists, sort list). It's commonly used as a warm-up before a harder linked-list or merge-based follow-up.

A linked-list problem where each node has both a next pointer and a random pointer that can point to any node in the list (or null), and you must produce a fully independent deep copy. The efficient O(1)-extra-space approach interleaves cloned nodes directly into the original list (original, clone, original, clone...) so each clone's random pointer can be set from its predecessor's random pointer, then the interleaved list is split back apart; a simpler O(n)-space alternative uses a hash map from original nodes to cloned nodes. It tests whether a candidate can reason precisely about pointer relationships when a node references arbitrary other nodes, not just its neighbor.

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.

A linked-list problem testing careful edge-case handling rather than algorithmic complexity: you must insert a new value into a sorted circular linked list while correctly handling an empty list, a list where all values are equal, and the wraparound point where the maximum value connects back to the minimum. It tests whether a candidate can enumerate and handle every structural edge case of a circular list rather than just the straightforward 'insert between two ascending values' case. It's a good signal for defensive linked-list coding under a deceptively simple prompt.

A linked-list problem solved with the two-pointer 'fast and slow' technique: you advance a lead pointer n nodes ahead, then move both pointers together until the lead reaches the end, leaving the trailing pointer just before the node to remove, all in a single pass using a dummy head to simplify removing the actual head node. It tests whether a candidate can solve a problem that looks like it needs the list's length (a two-pass approach) with a cleaner one-pass technique instead. It's a common, fast Medium-tier signal for linked-list pointer fluency.

A tree problem combining BFS with a hash map keyed by horizontal column index: as you traverse level by level, you track each node's column offset from the root (left child is column-1, right child is column+1) and group node values by column, then output columns left to right, top to bottom within each column. It tests whether a candidate can track auxiliary coordinate state alongside a standard traversal and handle correct ordering both across columns and among same-column nodes at different depths (and tie-breaking when nodes share both column and depth). It's a good signal for combining a standard traversal with non-trivial bookkeeping.

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 tree problem usually solved with level-order BFS, taking the last node visited at each level (or a DFS that visits right-before-left and records the first node seen at each depth). It tests whether a candidate can adapt a standard traversal to extract a specific per-level property rather than just performing a generic traversal, and whether they choose the more natural BFS framing or a slightly trickier depth-tracked DFS. It's a common, fast Medium-tier signal for level-order-traversal fluency.

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.

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

This is a shortest-path search on a grid where movement is allowed in all eight directions, so it's solved with BFS from the top-left cell, expanding layer by layer until the bottom-right cell is reached. The core skill being tested is recognizing that BFS (not DFS) guarantees the shortest path in an unweighted graph, plus careful handling of blocked cells and grid boundaries. It's a good warm-up signal for whether a candidate can model a 2D grid as a graph and correctly track visited state to avoid revisiting cells.

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.

A straightforward recursive tree traversal that asks for the sum of all node values falling within a given range. The interesting part is using the binary search tree's ordering property to prune entire subtrees that can't contain values in range, rather than visiting every node like a plain tree sum would. It's often used as an easy confidence-builder that also checks whether a candidate actually exploits BST structure instead of brute-forcing.

Each node here has a pointer to its parent, which reframes the lowest-common-ancestor problem as finding the intersection point of two upward paths -- conceptually the same two-pointer trick used to find the intersection of two linked lists. Candidates need to spot that walking both nodes toward the root and switching paths when one pointer reaches the top converges them at the LCA without extra memory. It's a nice signal for pattern transfer: recognizing a linked-list technique hiding inside a tree problem.

Binary trees only have parent-to-child pointers, but this problem needs distance-k neighbors in every direction, so the standard trick is to first do a pass adding parent pointers (or building an adjacency map), converting the tree into an undirected graph. From there it's a straightforward BFS from the target node up to depth k. It tests whether a candidate can recognize that a tree-shaped input sometimes needs to be reframed as a general graph before the right algorithm applies.

This problem asks candidates to rewire a BST in place into a sorted circular doubly linked list, which requires an in-order traversal while threading `prev`/`next` pointers as nodes are visited. It tests comfort with in-order traversal order (since it naturally yields sorted output for a BST) plus careful pointer bookkeeping to link the first and last nodes into a circle at the end. The in-place, O(1) extra space constraint is what separates a clean solution from a sloppy one.

A classic "top-k" selection problem: find the k points closest to the origin out of a larger set. It can be solved with a max-heap of size k (evict the farthest point whenever a closer one is found) for an O(n log k) solution, or with a quickselect-style partition for expected O(n). It's commonly used to see whether a candidate defaults to sorting everything (O(n log n)) or recognizes the more efficient heap/quickselect approaches suited to "top-k" style questions.

Given a binary tree where each root-to-leaf path represents a number (digits along the path), sum all such numbers. It tests standard DFS/preorder traversal skills, specifically carrying an accumulated value down each recursive call and only adding to the total once a leaf is reached. It's a good check on whether a candidate handles tree recursion state correctly rather than conflating per-node and per-path values.

A grid flood-fill problem: for each unvisited land cell, run DFS or BFS to measure the connected island's size and track the maximum across all islands. It's a direct, well-known application of grid traversal with visited-tracking, generally used as an accessible warm-up to confirm a candidate can implement flood fill cleanly (including edge and boundary handling) before moving to a harder graph or DP follow-up.

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.

Given a jagged (ragged) 2D list, the task is to return all elements ordered by ascending diagonal (row + column index), which is typically solved by bucketing elements into a hashmap or array-of-lists keyed by that diagonal sum and then flattening. It's a solid test of index bookkeeping and of noticing that elements within the same diagonal must be ordered by decreasing row (or increasing column) to get the traversal right. The irregular row lengths make naive nested-loop diagonal traversal error-prone, which is exactly what the problem is probing.

A classic backtracking problem: given a string of digits, you recursively build every possible letter combination by exploring one digit's mapped letters at a time and backtracking after each branch. It tests whether a candidate can correctly manage recursive state (the current partial string, the index into the digit string) and reason about the branching factor and time complexity of the resulting exponential search space. It's frequently used as a canonical intro-to-backtracking problem before harder combinatorial follow-ups like N-Queens or word search.

A classic backtracking problem: generate all permutations of a list of distinct integers. It tests whether a candidate can build a recursive decision tree — choosing one unused element at each level, recursing, then undoing the choice (backtracking) — and manage a visited/used-elements structure correctly. It's frequently used as an accessible entry point into recursion and backtracking before harder constrained-search problems.

A classic backtracking problem asking for the power set of a list of distinct integers, solvable either through recursive include/exclude backtracking or an iterative bitmask approach. It's frequently used to check whether a candidate can articulate and code a clean backtracking template -- choose, recurse, un-choose -- since that same skeleton generalizes to combinations, permutations, and partition problems. Because the state space is small and well understood, it's often a fast signal-check before moving to a harder combinatorial follow-up.

Given a string with extra parentheses, the goal is to find all ways to remove the minimum number of characters to make it valid, which is typically solved with BFS over strings (level by level, removing one character at a time) or backtracking with aggressive pruning. The problem tests whether a candidate can reason about search-space minimality -- proving a given removal count is truly minimal -- while also writing a correct, efficient parentheses-validity checker. It's a strong signal for handling exponential search spaces responsibly instead of generating all subsequences and filtering.

This asks for all ways to insert +, -, and * between digits of a string so the resulting expression evaluates to a target, solved via DFS/backtracking that tracks a running value and a separate "last multiplied term" so multiplication precedence can be correctly undone and reapplied. It also requires guarding against invalid leading zeros in multi-digit operands. It's a genuinely tricky combinatorics-plus-arithmetic problem that reveals whether a candidate can manage multiple pieces of backtracking state (partial expression, current value, previous operand) simultaneously.

The task is to generate all strobogrammatic numbers (numbers that look the same rotated 180 degrees) of a given length, built recursively from the innermost digits outward using the valid mirrored digit pairs (0-0, 1-1, 6-9, 8-8, 9-6). It tests recursive construction with a shrinking subproblem and awareness of edge cases like disallowing a leading zero except when the whole number is "0". It's a less common pattern than typical backtracking, so it also checks whether a candidate can build a solution from first principles rather than pattern-matching to a memorized template.

This is a weighted random sampling design problem: given an array of weights, repeatedly return an index with probability proportional to its weight. The standard solution builds a prefix-sum array and then binary searches a random value into that prefix-sum range, so it tests whether a candidate can connect probability weighting to cumulative sums and then apply binary search correctly on that derived array. It's a common signal for services that need weighted load distribution or randomized selection, such as routing or recommendation systems.

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.

Despite the array being unsorted, a peak (an element greater than its neighbors) can still be found in O(log n) using binary search by comparing the midpoint to its neighbor and moving toward the side that's still increasing. It's a good test of whether a candidate understands why binary search applies here even without global sortedness -- the key insight is that the search space always contains a peak in the direction of the ascending neighbor. This is often used to probe binary-search intuition beyond the standard "find target in sorted array" template.

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.

This asks for an efficient implementation of x^n, solved with binary (fast) exponentiation that halves the exponent each recursive/iterative step to run in O(log n) instead of O(n). Correctly handling a negative exponent (by inverting the base and negating n) and integer-overflow edge cases around the minimum exponent value are what typically separate a passing from a buggy solution. It's a compact but effective test of numeric edge-case discipline as much as algorithmic knowledge.

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.

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.

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.

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.

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

A design problem where the input vectors are mostly zeros, so the expected solution stores only non-zero (index, value) pairs rather than the full array, then computes the dot product by merging the two sparse representations (e.g. via a two-pointer walk or hashmap lookup). It tests whether a candidate thinks about the actual data distribution rather than defaulting to a dense O(n) approach that wastes time and space on zeros. This kind of representation-choice judgment is a common signal for systems that deal with sparse or high-dimensional data.

This is a design problem: implement a Tic-Tac-Toe board that reports a winner in O(1) per move instead of rescanning the whole board after every play. The standard trick is maintaining running counters per row, per column, and for each diagonal, incrementing or decrementing them per player's move so a win can be detected by checking whether any counter hits the board size. It's a solid signal for whether a candidate can convert an O(n) check into an O(1) amortized one by choosing the right incremental state.

Given a nested list of integers (lists can contain integers or further nested lists), compute the sum of all integers weighted by their depth of nesting. It's solved with straightforward recursive DFS, passing down the current depth and multiplying each integer found by it. It's a simpler recursion/tree-traversal-style problem, good for verifying comfort with recursive structures that aren't literal trees.