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.
Showing 19 problems of 25
- #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.
- #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.
- #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.
- #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.
- #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.