Menu
CoddyTech
Start learning
Learn Python step by stepOnline Python compiler

Array and String Interview Questions

Two pointers, sliding windows, prefix sums and the in-place tricks behind most array and string questions.

By Kevin Spektor, Co-founder & CTO

10 questions

  1. What is the two pointer technique, and when do you use it?

    Two pointers walks an array with two indexes, from both ends inward or both from the left at different speeds, turning many O(n²) pair searches into O(n). Pair sums need a sorted array.

    Python
    def pair_with_sum(nums, target):
    # nums is sorted
    i, j = 0, len(nums) - 1
    while i < j:
        s = nums[i] + nums[j]
        if s == target:
            return nums[i], nums[j]
        if s < target:
            i += 1   # need a bigger sum
        else:
            j -= 1   # need a smaller sum
    return None

print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))

    If nums[i] + nums[j] is too small, nums[i] cannot pair with anything left of j, so i can move.

    Practice it: Two Sum II: Sorted Input, Container With Most Water, Remove Duplicates from Sorted Array

  2. What is the sliding window technique?

    A sliding window keeps a range [left, right] and updates the answer as it moves instead of recomputing. A fixed window adds the entering element and drops the leaving one; a variable window grows right and shrinks left while a condition is broken. O(n).

    Python
    def max_sum_of_k(nums, k):
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]
        best = max(best, window)
    return best

print(max_sum_of_k([2, 1, 5, 1, 3, 2], 3))

    With negative numbers, "sum at least k" breaks a shrinking window; use prefix sums.

    Practice it: Maximum Sum Subarray of Size K, Minimum Size Subarray Sum, Permutation in String

  3. How does Kadane's algorithm find the maximum subarray sum?

    Track the best sum of a subarray ending at the current index: extend the previous one or start fresh here, whichever is larger. The answer is the largest of those. O(n) time, O(1) space.

    Python
    def max_subarray(nums):
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray([-3, -1, -2]))

    Do not start best at 0: with all negatives the answer is -1.

    Practice it: Maximum Subarray, Best Time to Buy and Sell Stock

  4. What is a prefix sum, and what problems does it solve?

    prefix[i] holds the sum of the first i elements, so after O(n) preprocessing any range sum [l, r] is prefix[r + 1] - prefix[l] in O(1). It pays off for many range queries on one array.

    Python
    from itertools import accumulate

nums = [3, 1, 4, 1, 5, 9, 2]
prefix = [0] + list(accumulate(nums))

def range_sum(l, r):
    return prefix[r + 1] - prefix[l]

print(prefix)
print(range_sum(2, 4))  # 4 + 1 + 5

    With a hash map of earlier prefix sums it also counts subarrays summing to k.

    Practice it: Range Sum Query, Find Pivot Index, Running Sum of an Array

  5. How do you move all zeros to the end of an array while keeping the order of the other elements?

    Keep a write index: swap every non-zero value to it, then move it forward. O(n) time, O(1) extra space, and the non-zero values keep their order.

    Python
    def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

print(move_zeroes([0, 1, 0, 3, 12]))

    The same read and write pointers remove duplicates from a sorted array in place.

    Practice it: Move Zeroes, Remove Duplicates from Sorted Array

  6. What happens when you set one cell of a Python grid built with [[0] * 3] * 3?

    Python
    grid = [[0] * 3] * 3
grid[0][0] = 1
print(grid)

    [[0] * 3] * 3 holds three references to the same inner list, so changing one row changes all three. It breaks grid and DP code that looks right. Build each row separately:

    Python
    grid = [[0] * 3 for _ in range(3)]
grid[0][0] = 1
print(grid)

    [0] * 3 alone is fine, because integers are immutable.

  7. How do you rotate an array to the right by k steps in place?

    Reverse the whole array, then the first k elements, then the rest: O(n) time, O(1) extra space. Take k % n first, since rotating by n changes nothing.

    Python
    def reverse(a, i, j):
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

def rotate(a, k):
    n = len(a)
    k %= n
    reverse(a, 0, n - 1)
    reverse(a, 0, k - 1)
    reverse(a, k, n - 1)
    return a

print(rotate([1, 2, 3, 4, 5, 6, 7], 3))

    a[-k:] + a[:-k] is the Python one-liner, but it allocates a new list, O(n) extra space.

  8. How do you sort an array of 0s, 1s and 2s in one pass?

    Use the Dutch national flag algorithm: low is the next slot for a 0, mid the current element, high the next slot for a 2. Swap 0s to low and 2s to high. One pass, O(1) space.

    Python
    def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1   # mid stays: the swapped-in value is unchecked
    return nums

print(sort_colors([2, 0, 2, 1, 1, 0]))

    The usual bug is advancing mid after swapping with high, before checking the value swapped in.

    Practice it: Sort Colors

  9. How do you compute the product of all elements except self without division?

    Make two passes: the left pass stores the product of everything left of each index, the right pass multiplies in everything to its right from one running variable. O(n) time, O(1) extra space besides the output.

    Python
    def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out

print(product_except_self([1, 2, 3, 4]))
print(product_except_self([2, 0, 5]))

    Division would break on zeros.

    Practice it: Product of Array Except Self

  10. How do you find the longest common prefix of a list of strings?

    Compare the strings column by column and stop at the first position where a string ends or a character differs. That is O(S) for S total characters.

    Python
    def longest_common_prefix(words):
    if not words:
        return ""
    for i, ch in enumerate(words[0]):
        for w in words[1:]:
            if i == len(w) or w[i] != ch:
                return words[0][:i]
    return words[0]

print(longest_common_prefix(["flower", "flow", "flight"]))
print(repr(longest_common_prefix(["dog", "car"])))

    When the follow-up is many prefix queries against the same words, use a trie.

    Practice it: Longest Common Prefix

Coddy programming languages illustration

Learn to code with Coddy

Get started