PART 4 · DSA AND COMPLEXITY · PRACTICE

Practice set 3: DSA with complexity

FreeLesson 55 of 78

Every answer ends with its time and space cost. Saying those two out loud is half the score in a DSA round.

Q16Order ids should be 1 to n with exactly one missing. Find it.DEEASY

Approach: The expected total is n(n+1)/2; subtract what is there. O(n) time, O(1) space.

def missing(ids):
    n = len(ids) + 1
    return n * (n + 1) // 2 - sum(ids)

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

Output

3 4

Q17Find the k-th largest order amount without sorting the whole list.DEMEDIUM

Approach: Keep a min-heap of size k; its top is the answer. O(n log k) time, O(k) space.

import csv, heapq
amounts = [float(r["amount"])
           for r in csv.DictReader(open("orders.csv"))]
def kth_largest(xs, k):
    heap = xs[:k]
    heapq.heapify(heap)
    for x in xs[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)
    return heap[0]
print(kth_largest(amounts, 3), sorted(amounts, reverse=True)[2])

Output

1999.0 1999.0

Q18Return the longest common prefix of these S3 paths.DEEASY

Approach: Compare characters column by column until one path differs. O(total characters) time, O(1) extra.

paths = ["s3://raw/orders/2025/04/01/part-0.csv",
         "s3://raw/orders/2025/04/02/part-0.csv",
         "s3://raw/orders/2025/03/31/part-1.csv"]
def common_prefix(strs):
    first, last = min(strs), max(strs)   # compare only these
    i = 0
    while i < len(first) and first[i] == last[i]:
        i += 1
    return first[:i]
print(common_prefix(paths))

Output

s3://raw/orders/2025/0

Q19For each day, the product of every other day's growth factor, without division.DEMEDIUM

Approach: Prefix products from the left, suffix products from the right, multiplied. O(n) time, O(1) extra besides the output.

def product_except_self(xs):
    out = [1] * len(xs)
    left = 1
    for i in range(len(xs)):
        out[i] = left; left *= xs[i]
    right = 1
    for i in reversed(range(len(xs))):
        out[i] *= right; right *= xs[i]
    return out

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

Output

[60, 40, 30, 24]

Q20Find files in a folder that have exactly the same content, even under different names.DEMEDIUM

Approach: Group by a hash of the bytes (P3 with a different key). O(total bytes) time, O(number of files) space.

import hashlib, pathlib, shutil
from collections import defaultdict

shutil.copy("orders.csv", "backup.csv")    # plant a duplicate
groups = defaultdict(list)
for p in sorted(pathlib.Path(".").glob("*.csv")):
    digest = hashlib.sha256(p.read_bytes()).hexdigest()
    groups[digest].append(p.name)
print([names for names in groups.values() if len(names) > 1])

Output

[['backup.csv', 'orders.csv']]

Practice before you move on

Solve Q16 to Q20 in the Try it editor, and say the time and space complexity before you run each one.
Change Q17 to return the k-th smallest amount instead of the largest.