Lesson 4: Programs 16-20: Matrices, Search, Stacks and Words

How to use this lesson. Read the question and try it yourself for ten minutes before you read the approach. In a real interview, say your idea out loud, mention the edge cases (empty input, one item, duplicates, negative numbers), then code, then test with an example.

Problem 16: Transpose a Matrix

Question. Swap the rows and columns of a matrix (a list of lists).

Examples.

• [[1, 2, 3], [4, 5, 6]] → [[1, 4], [2, 5], [3, 6]]

Approach. Element (row, column) moves to (column, row). zip(*matrix) does this in one step: the star spreads the rows into separate arguments and zip pairs up their first items, second items and so on.

def transpose(matrix):
    return [list(row) for row in zip(*matrix)]

def transpose_loops(matrix):
    rows, cols = len(matrix), len(matrix[0])
    return [[matrix[r][c] for r in range(rows)] for c in range(cols)]

m = [[1, 2, 3], [4, 5, 6]]
print(transpose(m))
print(transpose_loops(m))
print(transpose([[7]]))
print(transpose([]))

Output:

[[1, 4], [2, 5], [3, 6]]
[[1, 4], [2, 5], [3, 6]]
[[7]]
[]

Complexity. O(r x c) time and space for an r x c matrix.

Follow-up an interviewer may ask. Rotate a square matrix 90 degrees clockwise. (Transpose, then reverse each row.)

Problem 17: Binary Search

Question. Given a sorted list, return the position of a target, or -1 if it is not there.

Examples.

• [1, 3, 5, 7, 9], 7 → 3
• [1, 3, 5, 7, 9], 4 → -1

Approach. Look at the middle item. If it is the target you are done; if the target is smaller, discard the right half; otherwise discard the left half. Each step halves the search space. Write the loop carefully: low <= high and mid = (low + high) // 2.

def binary_search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

data = [1, 3, 5, 7, 9]
print([binary_search(data, t) for t in [1, 7, 9, 4, 0, 10]])
print(binary_search([], 3), binary_search([5], 5))

Output:

[0, 3, 4, -1, -1, -1]
-1 0

Complexity. O(log n) time, O(1) space. (The list must already be sorted.)

Follow-up an interviewer may ask. How would you find the first occurrence in a list with duplicates? (Keep searching left after a match, or use bisect_left.)

Problem 18: Valid Parentheses

Question. Given a string of brackets ()[]{}, return True if every opening bracket is closed by the right kind, in the right order.

Examples.

• "()[]{}" → True
• "(]" → False
• "([)]" → False

Approach. Use a stack. Push each opening bracket. For a closing bracket, the top of the stack must be its matching opener; pop it. At the end the stack must be empty.

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs.values():
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

for text in ["()[]{}", "(]", "([)]", "{[]}", "", "((", "))", "a(b)c"]:
    print(repr(text), is_valid(text))

Output:

'()[]{}' True
'(]' False
'([)]' False
'{[]}' True
'' True
'((' False
'))' False
'a(b)c' True

Complexity. O(n) time, O(n) space for the stack.

Follow-up an interviewer may ask. How would you find the length of the longest valid substring? (Track indexes on the stack.)

Problem 19: Merge Two Sorted Lists

Question. Merge two sorted lists into one sorted list.

Examples.

• [1, 4, 7], [2, 3, 9] → [1, 2, 3, 4, 7, 9]

Approach. Keep one pointer in each list. Repeatedly take the smaller of the two current items, then move that pointer. When one list runs out, add what is left of the other. This is the merge step of merge sort.

import heapq

def merge_sorted(a, b):
    i = j = 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

print(merge_sorted([1, 4, 7], [2, 3, 9]))
print(merge_sorted([], [1, 2]))
print(merge_sorted([1, 1], [1]))
print(list(heapq.merge([1, 4, 7], [2, 3, 9])))

Output:

[1, 2, 3, 4, 7, 9]
[1, 2]
[1, 1, 1]
[1, 2, 3, 4, 7, 9]

Complexity. O(m + n) time and O(m + n) space.

Follow-up an interviewer may ask. How would you merge k sorted lists? (A min-heap holding the next item of each list: O(N log k).)

Problem 20: Word Frequency: The Most Common Words

Question. Given a text, return the n most frequent words, ignoring case and punctuation.

Examples.

• "the cat and the hat and the bat", n = 2 → [('the', 3), ('and', 2)]

Approach. Lower-case the text, pull out the words with a regular expression, count them with a Counter, and ask for most_common(n). Words with equal counts keep the order in which they first appeared.

import re
from collections import Counter

def top_words(text, n):
    words = re.findall(r"[a-z']+", text.lower())
    return Counter(words).most_common(n)

text = "The cat and the hat. And the bat! It's the cat's hat."
print(top_words(text, 3))
print(top_words("", 3))
print(top_words("One fish, two fish.", 5))

Output:

[('the', 4), ('and', 2), ('hat', 2)]
[]
[('fish', 2), ('one', 1), ('two', 1)]

Complexity. O(n) time to count; most_common(n) adds O(k log n) for k distinct words.

Follow-up an interviewer may ask. How would you do it for a file too big for memory? (Count in chunks and merge, or use a streaming approximate counter.)

What to do next

• Re-solve each problem tomorrow without looking, then explain it out loud.
• Write a few extra test cases for each: empty input, one item, duplicates, very large values.
• Practise related problems on sites such as LeetCode and HackerRank, starting with the "easy" ones in each topic.
• Take the JavaScript: 20 Interview Programs course to practise the same ideas in a second language.

Good luck with your interviews. Understanding the pattern behind each problem matters more than memorising code.