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

Two sorted arrays need to be merged in place into the first array, which has extra trailing space to accommodate the second. The efficient approach fills from the back (largest elements first) with three pointers, avoiding the overwrite problem that a naive front-to-back merge would hit. It's a simple but effective test of whether a candidate can reason about in-place array manipulation direction rather than just knowing the merge-step of merge sort.

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.

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 a matrix, any cell containing zero must have its entire row and column zeroed out, and the interesting constraint is doing this in O(1) extra space. The standard trick reuses the matrix's own first row and first column as marker storage for which rows/columns need zeroing, with a couple of extra flags to avoid corrupting the markers themselves. It's a good test of in-place space-optimization thinking, since the brute-force O(m+n) auxiliary-array solution is easy but the constant-space version requires more careful reasoning.

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.

This is the classic Dutch National Flag problem: sort an array containing only three distinct values (commonly 0, 1, 2) in a single pass using three pointers (low, mid, high) that partition the array into three regions as they scan. It tests whether a candidate can implement in-place three-way partitioning correctly, including the subtlety of not advancing the mid pointer after a swap with the high pointer. It's a frequently reused building block in quicksort-style partitioning, so it also signals whether that broader pattern is understood.

Given two strings, determine whether one contains a permutation of the other as a substring, solved with a fixed-size sliding window and character-frequency comparison (arrays or hashmaps) rather than generating and checking permutations directly. It tests whether a candidate recognizes that "contains a permutation of" reduces to "contains a window with the same character-count multiset," and can maintain that count incrementally as the window slides rather than recomputing it from scratch each time. This is a strong signal for general sliding-window fluency, a pattern that recurs across many string and array problems.

A stack-simulation problem: asteroids move left or right, and colliding pairs are resolved by comparing sizes and directions according to a small set of rules. The stack holds asteroids that haven't yet been destroyed, and each new asteroid may trigger a cascade of comparisons against the stack top before it's pushed or discarded. It's a good test of careful, exhaustive case enumeration (which asteroid survives, ties, same-direction pairs) rather than algorithmic complexity.

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

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

The task is to return all elements of a matrix visited in spiral order, typically implemented by maintaining four shrinking boundaries (top, bottom, left, right) and walking each edge in turn before tightening the boundaries inward. It's less about algorithmic complexity and more about careful index management and avoiding off-by-one errors or double-counting the last row/column when the matrix isn't square. It's a common signal for whether a candidate can translate a visual/spatial pattern into precise, boundary-safe loop logic.

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.

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.

Given an array where each element is the maximum jump length from that position, the goal is to find the minimum number of jumps to reach the last index, solved greedily by tracking the farthest reachable index within the current "jump level" (an implicit BFS over reachability ranges rather than over individual indices). It tests whether a candidate can find the greedy invariant that avoids exponential branching from trying every possible jump length at each step. This greedy-versus-brute-force distinction is a common signal for optimization-style array problems.

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.

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.

This is a string-parsing/simulation problem that mimics the C `atoi` function: skip leading whitespace, handle an optional sign, consume digits until a non-digit character, and clamp the result to 32-bit signed integer bounds. There's no complex algorithm involved -- the difficulty is entirely in correctly handling the long list of edge cases (empty string, sign-only input, overflow, trailing garbage) without missing one. It's a strong signal for meticulous, defensive coding under a spec with many corner cases, which mirrors real-world input-validation work.

Two numbers are represented as linked lists of digits in reverse order, and the task is to add them and return the sum as a new linked list, carrying over digit-by-digit the same way manual addition works. It tests basic but precise linked-list manipulation: creating new nodes, propagating a carry, and correctly handling lists of different lengths plus a possible trailing carry node. It's often an early-round problem used to confirm a candidate is comfortable with linked-list pointer mechanics before moving to harder list problems.

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 reversing a linked list in groups of k nodes at a time, leaving any leftover group smaller than k in its original order. It's a meaningfully harder linked-list problem than a plain full-list reversal because it requires reversing each k-sized segment in place while correctly reconnecting the previous segment's tail and the next segment's head, plus a first pass to confirm a full group actually exists before reversing it. It's a strong signal for whether a candidate can manage several simultaneous pointers without corrupting the list.

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 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 standard breadth-first traversal of a binary tree that returns node values grouped by depth level, implemented with a queue and by tracking how many nodes belong to the current level before processing the next one. It's a foundational tree-BFS problem used to confirm a candidate can implement queue-based traversal correctly, including the level-boundary bookkeeping that distinguishes it from a plain flat BFS. It also frequently serves as a building block that gets extended into zigzag or right-side-view variants.

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.

This checks whether a binary tree is a mirror image of itself around its center, solved either recursively by comparing left and right subtrees pairwise (outer-with-outer, inner-with-inner) or iteratively with a queue/stack holding paired nodes. It's a simple but precise test of recursive thinking about tree structure, since a naive left-equals-right value comparison without considering the mirrored structural pairing gives wrong answers. It's commonly used as an easy calibration problem before moving into harder tree-recursion questions.

A shortest-path problem with an added constraint on the number of edges (stops) used: the standard approaches are a bounded Bellman-Ford (relax all edges K+1 times) or a modified Dijkstra/BFS that tracks both cost and stop count as part of the search state. It tests whether a candidate understands why plain Dijkstra can fail here (it doesn't account for the stop limit) and can adapt a shortest-path algorithm to a secondary constraint — a pattern that generalizes to real routing and logistics problems.

Given a tree's preorder and inorder traversal sequences, the task is to rebuild the original tree, using the fact that preorder's first element is always the root and that same value's position in inorder splits the tree into left and right subtrees. An efficient solution uses a hashmap to look up each value's inorder index in O(1) rather than scanning linearly, which keeps the overall reconstruction at O(n). It's a strong signal for whether a candidate can turn a traversal-property insight into a correct recursive divide-and-conquer algorithm.

Given n pairs of parentheses, generate all combinations that are well-formed, solved with backtracking that only opens a new parenthesis if fewer than n have been used and only closes one if it wouldn't outnumber the opens so far. It's a canonical backtracking-with-constraints problem, testing whether a candidate can prune the search tree using simple counters rather than generating all sequences and filtering for validity afterward. It's frequently used as a quick, well-understood check on backtracking fundamentals.

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

Implement regular expression matching supporting `.` (any single character) and `*` (zero or more of the preceding element) against a full string. The standard solution is a 2D dynamic program over (string index, pattern index), where the transition for `*` requires considering both 'match zero occurrences' and 'match one more occurrence' cases. It's widely regarded as one of the trickier string DP problems because the `*` transitions are easy to get subtly wrong, making it a good test of precise DP formulation under pressure.

A classic hard monotonic-stack problem: find the largest rectangular area that can be formed within a histogram's bars. The efficient O(n) solution maintains a stack of increasing bar heights and, whenever a shorter bar is encountered, pops and computes the area of each taller bar using the current index as the right boundary and the new stack top as the left boundary. It's one of the most commonly cited tests of genuine monotonic-stack fluency, since the naive approach is O(n^2) and the stack-based trick isn't obvious without prior exposure to the pattern.

This requires filling a partially completed 9x9 Sudoku board so it satisfies all of Sudoku's row, column, and 3x3-box constraints, solved with backtracking search plus constraint checking (or precomputed row/column/box bitmasks for speed) at each candidate placement. It's a genuinely demanding constraint-satisfaction problem that tests whether a candidate can structure a backtracking search efficiently over a much larger state space than typical interview backtracking problems, including choosing a sensible cell-ordering heuristic to keep it fast in practice. It's a strong signal for handling real combinatorial search under multiple simultaneous constraints.

Given three strings, determine whether the third can be formed by interleaving the first two while preserving each one's internal character order, solved with a 2D dynamic-programming table where each cell tracks whether a prefix of s3 can be built from prefixes of s1 and s2. It tests whether a candidate can correctly define the DP state and transition (matching either the next character of s1 or s2, but not both at once) rather than trying to brute-force all interleavings. It's a good signal for comfort with two-dimensional string DP, a pattern that generalizes to edit distance and longest-common-subsequence-style 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.