LinkedIn Interview Questions

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.

A variant of Nested List Weight Sum where the weighting is inverted: integers at shallower depth get a higher weight (weight = maxDepth - depth + 1) instead of a lower one. Since max depth isn't known in advance, an efficient one-pass solution tracks a running "unweighted" total across depths and adds it cumulatively at each level, avoiding the need for two full passes (one to find max depth, one to sum). It's a good follow-up to the original problem that tests whether a candidate can adapt a straightforward recursive solution when the weighting direction flips.

A design problem asking for a stack that supports push, pop, top, peekMax, and popMax — the difficulty is popMax, which must remove the maximum element from anywhere in the stack while preserving relative order of the rest. Efficient solutions typically pair a doubly linked list (for O(1) removal from the middle) with an ordered map or balanced structure keyed by value to locate the max quickly. It's a strong test of composing multiple data structures to hit better-than-O(n) time on every operation, not just the easy ones.

This design problem requires inc(key), dec(key), getMaxKey(), and getMinKey() to all run in O(1) — ruling out a plain hashmap plus heap, since heaps don't give O(1) max/min removal alongside arbitrary key updates. The standard solution buckets keys by their current count in a doubly linked list of count-buckets, combined with a hashmap from key to its bucket, so incrementing or decrementing a key just moves it to an adjacent bucket. It's a genuinely hard composition of a hash map with a linked structure, and a strong signal for whether a candidate can design toward a strict complexity bound rather than a merely-workable one.

A design problem: given a list of words with repeats, preprocess it so that many subsequent queries for the shortest distance between two given words can each be answered efficiently. The solution precomputes a hash map from each word to a sorted list of its indices, then answers each query with a two-pointer merge over the two words' index lists to find the minimum gap. It tests the ability to separate one-time preprocessing cost from per-query cost when a query is expected to run many times, unlike the single-query version of this problem.

A design problem: build a data structure supporting adding words and searching with a wildcard '.' that can match any single letter. It tests whether a candidate can extend a trie with DFS-based search that branches over all children when a wildcard is encountered, rather than requiring an exact-match traversal. It's a natural harder follow-up to the basic Trie problem and checks whether a candidate can adapt a known structure to a new requirement.

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.

Design a data structure supporting insert, remove, and getRandom (returning a uniformly random existing element) all in average O(1) time, where the same value may be inserted multiple times. The solution pairs a dynamic array (for O(1) random access by index) with a hash map from value to the set of indices where it currently appears, using a swap-with-last-element trick on removal to keep the array compact. It's a step up from the no-duplicates version of this problem and tests careful bookkeeping when multiple indices must be tracked per value.

Design a system that issues time-limited authentication tokens, supports renewing an unexpired token's expiration, and can count how many tokens are currently unexpired at a given time. A straightforward solution uses a hash map from token ID to its expiration time, removing or ignoring expired entries as needed; countUnexpiredTokens can be implemented directly by scanning the map. It's a design problem focused on correctly modeling time-based expiration and renewal semantics rather than requiring an advanced algorithm.

You need to encode a binary search tree into a string and decode that string back into an identical tree. Because it's specifically a BST (not just any binary tree), a preorder traversal alone is enough to reconstruct the tree unambiguously — the decode step rebuilds it by recursively partitioning the preorder sequence using each value's implied lower/upper bounds, without needing explicit null markers the way the general binary-tree version of this problem does. It's a good test of whether a candidate exploits the BST ordering property to produce a more compact and efficient solution than the general-tree case.

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.

Among n people, a "celebrity" is someone everyone else knows but who knows no one else; you're only given a knows(a, b) API and must identify the celebrity (or determine none exists) using as few calls as possible. The efficient solution does a single elimination pass to find one candidate (if a knows b, a can't be the celebrity, so move on; otherwise b can't be), then verifies that candidate against everyone else in a second pass, achieving O(n) calls instead of the naive O(n^2). It's a strong signal for recognizing an elimination-based linear-time approach over a brute-force pairwise check.

This problem tests whether you understand how to exploit the binary search tree invariant rather than treating the tree as a generic binary tree. Because left and right subtree values are ordered, you can determine at each node whether both targets lie left, both lie right, or the node itself is the split point, giving an O(h) solution without needing to track full root-to-node paths. It's a good signal for whether a candidate distinguishes BST-specific optimizations from the generic LCA algorithm (which needs parent pointers or path tracking) used on unordered binary trees.

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.

This is a math-and-probability problem: candidates need to know that sampling angle and radius independently and uniformly does not produce a uniform distribution over the disk, because area scales with the square of the radius. The correct approach samples the squared radius uniformly then takes its square root (or uses rejection sampling over the bounding square) alongside a uniform angle. It tests whether a candidate can reason about geometric probability rather than pattern-matching to a standard data structure technique, which sets it apart from most array/tree/graph problems in an interview loop.

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 greedy array-scanning problem: you walk the flowerbed left to right and plant a flower in any position where the current, left, and right neighbors are all empty, then check whether enough flowers were planted. It's a solid signal for whether a candidate can reason correctly about edge cases at the array boundaries and convince themselves that the local greedy choice never blocks a better global solution. It's usually treated as a quick warm-up problem rather than a deep signal on its own.

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.

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.

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.

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.

An extension of the classic House Robber DP where houses are arranged in a circle, so the first and last house can't both be robbed. The standard solution runs the original linear DP twice — once excluding the first house, once excluding the last — and takes the max of the two results. It's a good test of recognizing how a small structural change (circular vs. linear) can be handled by decomposing into two instances of a known subproblem rather than inventing new DP state.

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 problem tests hash map usage for enforcing a bijective (one-to-one and onto) character mapping between two strings. The common pitfall is mapping characters in only one direction, which misses cases where two different source characters map to the same target character, so it's a good check for whether a candidate thinks through both directions of the constraint. It's typically a fast, low-friction problem used to confirm basic hash map fluency.

Given a binary array and an integer k, find the length of the longest subarray of 1s obtainable after flipping at most k zeros. It's a classic variable-size sliding-window problem: expanding the window while tracking the count of zeros inside it, and shrinking from the left once that count exceeds k. It's a reliable signal for sliding-window fluency, a pattern that recurs across many array and string problems in interviews.

A sliding window problem over a binary array: you maintain a window that contains at most one zero (k zeros in the general version) and track the maximum window length as you expand and contract it. It tests whether a candidate can correctly manage a two-pointer window with a violation counter and shrink the window only when the constraint is actually broken. It's a good stepping stone toward more general 'longest substring/subarray with at most k of something' sliding window problems.

A dynamic programming problem with three dimensions of state: house index, color chosen, and number of neighborhoods formed so far, where painting a house a different color than its predecessor starts a new neighborhood. It tests whether a candidate can define a DP state and transition correctly under multiple simultaneous constraints, while handling some houses being pre-painted and unchangeable. It's a strong signal for comfort with multi-dimensional DP under real interview time pressure, since a naive implementation is easy to get wrong on the neighborhood-counting transition.

A dynamic programming problem combined with the insight that the optimal mailbox location for a contiguous group of houses is the median of that group, which minimizes total absolute distance. Candidates need to precompute the cost of servicing every contiguous subarray of houses with one mailbox, then run a DP over how to partition the houses into k such groups to minimize total cost. It tests both a mathematical insight (median minimizes sum of absolute deviations) and the ability to combine it with interval-partition DP, making it a strong hard-tier signal.

A binary search problem: rather than computing a square root directly, you binary search over the integer range to find whether some integer squared equals the target, taking care to use a data type wide enough to avoid overflow on the multiplication. It's a straightforward check of whether a candidate can set up binary search bounds and a termination condition correctly rather than reaching for a library sqrt function. It's typically used as a quick warm-up before deeper binary-search-on-answer problems.

A two-pointer problem: because the input array is sorted but can contain negative numbers, the largest squared values come from either end of the array, so you fill the result array from the back using pointers starting at both ends. It tests whether a candidate recognizes that squaring breaks the original sort order and can still produce a sorted output in linear time instead of resorting to an O(n log n) sort. It's a common warm-up for two-pointer technique in an interview loop.

A classic easy-level stack problem: determine whether a string of brackets is validly matched and nested. It tests the fundamental insight that a stack naturally models nested, last-in-first-out matching — pushing opening brackets and popping/comparing on closing ones. Despite its simplicity, it's a reliable early-round filter for whether a candidate reaches for the right data structure immediately rather than over-engineering a solution.