Linear Coding Interview Questions
25 Linear coding interview problems with full optimal solutions — 8 easy, 12 medium, 5 hard. Every problem ships with multiple approaches (brute-force first, then the optimal), complexity tables for each, company-specific tips on what an Linear interviewer values, and a FAQ section.
- #1easyfrequently asked
1. Two Sum
Find two numbers in an array that add to a target. Linear asks this as a warm-up to see if you reach for the O(n) hash-map solution immediately or stumble through O(n²) brute force first.
- #3mediumfrequently asked
3. Longest Substring Without Repeating Characters
Find the length of the longest substring with no repeated characters. Linear uses this to test the sliding-window pattern — maintaining a valid window by shrinking the left pointer when a duplicate enters.
- #4hardcommonly asked
4. Median of Two Sorted Arrays
Find the median of two sorted arrays in O(log(m+n)). Linear asks this to see if you understand the binary-search-on-partition technique — a problem where the O(m+n) merge approach is obvious but the O(log) solution requires genuine insight.
- #15mediumfrequently asked
15. 3Sum
Find all unique triplets in an array that sum to zero. Linear asks this to see if you know the 'anchor + two-pointer' pattern and can handle duplicate elimination cleanly — a level above Two Sum that exposes real interview preparation.
- #20easyfrequently asked
20. Valid Parentheses
Determine whether a string of brackets is balanced. Linear uses this to see if you naturally reach for a stack and can explain the push/pop invariant clearly — a proxy for how you communicate data-structure choices.
- #21easyfrequently asked
21. Merge Two Sorted Lists
Merge two sorted linked lists into one sorted list. Linear asks this as a foundational pointer problem — it directly primes the harder follow-up (Merge K Sorted Lists) and reveals whether you use a dummy head to simplify edge cases.
- #23hardfrequently asked
23. Merge K Sorted Lists
Merge k sorted linked lists into one. Linear uses this to see if you know the min-heap approach and can articulate why it's O(n log k) — a natural step up from the easy 'Merge Two Sorted Lists' problem.
- #42hardfrequently asked
42. Trapping Rain Water
Calculate the total water trapped between elevation bars. Linear asks this to see whether you progress through the intuitions — brute force → precomputed max arrays → two pointers — and can articulate why the two-pointer approach is O(1) space.
- #49mediumfrequently asked
49. Group Anagrams
Group strings that are anagrams of each other. Linear uses this to see if you can design a canonical key for grouping — sorted string vs. character frequency array — and articulate the trade-off between the two.
- #53easyfrequently asked
53. Maximum Subarray
Find the contiguous subarray with the largest sum. Linear uses this to see if you know Kadane's algorithm by name and can articulate the 'restart if running sum goes negative' intuition before writing a single line of code.
- #56mediumfrequently asked
56. Merge Intervals
Given a list of intervals, merge all overlapping ones. Linear asks this to test sorting-as-preprocessing and clean interval comparison logic — a practical problem that maps directly to scheduling and event systems, fitting for a project management tool company.
- #70easycommonly asked
70. Climbing Stairs
Count the number of distinct ways to climb n stairs taking 1 or 2 steps at a time. Linear asks this to see if you recognize it as Fibonacci DP and can articulate why memoization beats plain recursion — a proxy for how you think about repeated subproblems.
- #98mediumfrequently asked
98. Validate Binary Search Tree
Check that every node in a binary tree satisfies the BST property. Linear uses this to see if you avoid the common trap of only comparing a node to its direct parent — the BST constraint is global, not local.
- #121easyfrequently asked
121. Best Time to Buy and Sell Stock
Find the maximum profit from a single buy-then-sell transaction. Linear uses this to see if you recognize the 'running minimum' pattern — iterating once while tracking the cheapest buy price seen so far.
- #127hardcommonly asked
127. Word Ladder
Find the shortest transformation sequence from beginWord to endWord, changing one letter at a time, using only dictionary words. Linear asks this to test whether you model it as BFS on an implicit graph — and whether you know the wildcard-key optimization to build adjacency lists efficiently.
- #139mediumcommonly asked
139. Word Break
Determine if a string can be segmented into words from a dictionary. Linear uses this DP problem to see if you can formulate dp[i] = 'can I form s[0..i-1] from the wordDict?' and handle the substring check efficiently.
- #146mediumfrequently asked
146. LRU Cache
Design a cache that evicts the least-recently-used item when it's full. Linear asks this because it's a real design problem embedded in a coding question — you need to compose a hash map and a doubly-linked list to hit O(1) get and put.
- #200mediumfrequently asked
200. Number of Islands
Count connected components of '1's in a 2D grid. Linear uses this as a graph traversal benchmark — both DFS and BFS are accepted, but the interviewer wants to hear you name the approach and explain the visited-cell marking strategy.
- #206easyfrequently asked
206. Reverse Linked List
Reverse a singly-linked list. Linear uses this to probe pointer manipulation fundamentals and to see whether you can explain both the iterative and recursive versions — and articulate which is preferred in production.
- #207mediumfrequently asked
207. Course Schedule
Detect whether a set of course prerequisites forms a cycle. Linear asks this to test directed-graph cycle detection — can you reach for DFS with three-color marking or Kahn's topological sort, and explain the difference?
- #238mediumfrequently asked
238. Product of Array Except Self
Return an array where each element is the product of all other elements, without using division and in O(n). Linear asks this to see if you can find the 'prefix and suffix product' insight — a classic example of precomputed auxiliary arrays.
- #297hardcommonly asked
297. Serialize and Deserialize Binary Tree
Design a codec that converts a binary tree to a string and back. Linear asks this to probe system design thinking in a coding context — can you design a self-describing format and implement both encode/decode symmetrically?
- #322mediumfrequently asked
322. Coin Change
Find the minimum number of coins to make a given amount. Linear asks this as a benchmark DP problem — it separates candidates who pattern-match 'unbounded knapsack' from those who just try greedy and hit the wrong answer.
- #347mediumfrequently asked
347. Top K Frequent Elements
Return the k most frequent elements in an array. Linear uses this to probe your knowledge of heaps vs. bucket sort — both O(n log k) and O(n) solutions exist, and the interviewer wants to see if you know both.
- #704easycommonly asked
704. Binary Search
Search a sorted array in O(log n). Linear asks this to verify you can write a correct binary search without off-by-one bugs — a small problem that reveals a lot about coding precision.