DSA Coding Interview Questions and Answers

10 questions

How do you find the maximum profit from buying and selling a stock once?
Track the lowest price so far; each day's best sale is price - lowest, and you keep the maximum. O(n) time, O(1) space.
Python
def max_profit(prices): lowest = float("inf") best = 0 for p in prices: lowest = min(lowest, p) best = max(best, p - lowest) return best print(max_profit([7, 1, 5, 3, 6, 4])) print(max_profit([7, 6, 4, 3, 1]))
If prices only fall, the answer is 0, not a negative number. Follow-up: unlimited transactions? Add up every positive day-to-day increase.
Practice it: Best Time to Buy and Sell Stock
How do you find the majority element (more than n/2 occurrences) in O(1) space?
Use Boyer-Moore voting: keep a candidate and a counter; when the counter is 0 take the current element, then add 1 on a match and subtract 1 otherwise. Other elements can cancel at most one copy each, so the majority survives. O(n) time, O(1) space.
Python
def majority(nums): candidate, count = None, 0 for x in nums: if count == 0: candidate = x count += 1 if x == candidate else -1 return candidate print(majority([2, 2, 1, 1, 1, 2, 2]))
If a majority might not exist, verify the candidate in a second pass.
Practice it: Majority Element
How do you find the longest substring without repeating characters?
Use a sliding window and a map from each character to its last index. When the character at right was seen inside the window, jump left past it. O(n).
Python
def longest_unique(s): last = {} left = best = 0 for right, ch in enumerate(s): if ch in last and last[ch] >= left: left = last[ch] + 1 last[ch] = right best = max(best, right - left + 1) return best for s in ["abcabcbb", "bbbbb", "pwwkew", "abba"]: print(s, longest_unique(s))
"abba" catches the classic bug: without last[ch] >= left, the second a moves left backwards.
Practice it: Longest Substring Without Repeating Characters, Longest Repeating Character Replacement, Minimum Window Substring
How do you merge overlapping intervals?
Sort by start; if the next interval starts at or before the last merged end, extend that end, otherwise start a new interval. O(n log n) for the sort.
Python
def merge(intervals): merged = [] for start, end in sorted(intervals): if merged and start <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], end) else: merged.append([start, end]) return merged print(merge([[1, 3], [8, 10], [2, 6], [15, 18], [17, 20]])) print(merge([[1, 4], [2, 3]]))
The max matters because [1, 4] contains [2, 3]. Ask whether touching intervals like [1, 2] and [2, 3] merge; <= says yes.
Practice it: Merge Intervals, Insert Interval, Meeting Rooms II

How do you find all unique triplets that sum to zero?

Sort, fix one number at a time, and find pairs that sum to its negative with two pointers over the rest. Skip equal values for the fixed number and after each match to avoid duplicate triplets. O(n²).

Python

def three_sum(nums):
    nums = sorted(nums)
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                result.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
                hi -= 1
    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))

Practice it: 3Sum, Two Sum II: Sorted Input

How do you solve trapping rain water in O(n) time and O(1) space?

Water above a bar is the lower of the tallest bars on its left and right, minus the bar. Move two pointers inward with running maximums, always moving the lower side: the other side has a bar at least as tall, so the water here depends only on this side's maximum.

Python

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = water = 0
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water

print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

Two arrays of running maximums also work, at O(n) space.

Practice it: Trapping Rain Water, Container With Most Water

How do you generate all subsets or permutations of an array?
Backtracking: add a choice, recurse, then undo it. For subsets each element is in or out, so there are 2^n subsets and O(n × 2^n) work; permutations give n! results.
Python
def subsets(nums): result, path = [], [] def go(i): if i == len(nums): result.append(path[:]) # copy, path keeps changing return path.append(nums[i]) # take nums[i] go(i + 1) path.pop() # undo go(i + 1) # skip nums[i] go(0) return result print(subsets([1, 2, 3]))
The common bug is appending path instead of path[:]: every entry then points to the same list, which is empty by the end.
Practice it: Subsets, Permutations, Combination Sum, N-Queens II
How do you find the maximum of every window of size k in O(n)?
Keep a deque of indexes with decreasing values. For each element, pop smaller values from the back, push its index, and drop the front once it leaves the window; the front is the maximum. Each index is pushed and popped once: O(n), against O(n × k).
Python
from collections import deque def window_max(nums, k): dq, result = deque(), [] for i, x in enumerate(nums): while dq and nums[dq[-1]] <= x: dq.pop() dq.append(i) if dq[0] <= i - k: dq.popleft() if i >= k - 1: result.append(nums[dq[0]]) return result print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
The deque is a monotonic queue, the queue version of the monotonic stack.
Practice it: Sliding Window Maximum
How do you merge two sorted arrays into one sorted array?
Walk both with two pointers, always taking the smaller head, then append what is left of the other. O(n + m) time, against O((n + m) log(n + m)) for joining and sorting.
Python
def merge(a, b): i = j = 0 out = [] while i < len(a) and j < len(b): if a[i] <= b[j]: # <= keeps equal items in order (stable) out.append(a[i]) i += 1 else: out.append(b[j]) j += 1 out.extend(a[i:]) out.extend(b[j:]) return out print(merge([1, 4, 7], [2, 3, 8, 9]))
It is the merge step of merge sort, and the same loop merges two sorted linked lists by relinking nodes. To merge in place into an array with spare room at its end, fill from the back.
Practice it: Merge Sorted Array, Merge Two Sorted Lists

How do you rotate a square matrix by 90 degrees clockwise in place?

Transpose it (swap m[i][j] with m[j][i]), then reverse each row. O(n²) time and O(1) extra space.

Python

def rotate(m):
    n = len(m)
    for i in range(n):
        for j in range(i + 1, n):   # upper triangle only, or each swap is undone
            m[i][j], m[j][i] = m[j][i], m[i][j]
    for row in m:
        row.reverse()

grid = [[1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]]
rotate(grid)
for row in grid:
    print(row)

It prints [7, 4, 1], [8, 5, 2], [9, 6, 3]. For counterclockwise, transpose and then reverse each column instead.

Practice it: Rotate Image, Transpose Matrix

How do you find the maximum profit from buying and selling a stock once?

How do you find the majority element (more than n/2 occurrences) in O(1) space?

How do you find the longest substring without repeating characters?

How do you merge overlapping intervals?

How do you find all unique triplets that sum to zero?

How do you solve trapping rain water in O(n) time and O(1) space?

How do you generate all subsets or permutations of an array?

How do you find the maximum of every window of size k in O(n)?

How do you merge two sorted arrays into one sorted array?

How do you rotate a square matrix by 90 degrees clockwise in place?

Learn to code with Coddy