Algorithms for Interviews

Interviewers rarely judge only whether you reach the answer. They watch how you think: whether you clarify the task, start from something that works, and improve it deliberately. Silence for ten minutes followed by perfect code scores worse than reasoning aloud and arriving at a good solution. Six steps make that process visible.

1. ClarifyRestate the task in your own words. Ask about the edges: can the array be empty? Are there negatives or duplicates? Is the input sorted? Each answer can change the solution.
2. Work an example by handTake a small input and solve it on paper. This is where you notice the pattern — and catch a misunderstanding before writing a line of code.
3. Say the brute forceDescribe the obvious solution and its complexity, even if it is slow. It proves you understand the task and gives a baseline to improve on.
4. Find the bottleneckAsk what work is repeated. Usually it is a nested loop re-scanning data you have already seen — the classic place where a dictionary, two pointers or a running sum helps.
5. Write the codeClear names, small steps, comments where intent is not obvious. Readable code is part of the grade, not decoration.
6. Test it yourselfWalk through your example line by line, then the edges: empty input, one element, all equal values. Finding your own bug is a plus; the interviewer finding it is a minus.

The section above is about how to behave in the interview; this one is about where the idea itself comes from. Most easy problems are not hard because of the code — they are hard because it is not clear where to start. This section gives you a start that always works: solve a tiny example by hand, notice what you had to keep in your head, and turn that into variables. After that the code almost writes itself. Below are the method, a catalogue of the six kinds of “memory” that cover nearly every easy problem, and six families taken apart slowly — including run-length encoding, counting characters and the missing number. The explanations are written so that they make sense even if you skip the code.

1. What goes in, what comes out? Write two small examples with their answers, plus one edge case — usually the empty input. If you cannot write the answer for an example, you do not understand the task yet: ask.
2. Solve a tiny example by hand — slowly. Do it the way you would on paper and say out loud what you are doing: “I look at the letter, it is the same as before, so I add one…”. That sentence is the algorithm.
3. What did you have to keep in your head? A count, the previous letter, the names you had already seen, the best value so far. Whatever you were holding becomes the variables you create before the loop. This is the most important question on the page.
4. What did you do with each new element? Usually one decision: “same as before → add one, otherwise → write it down and start again”. Say it as one sentence with “if … otherwise …”. That sentence becomes the body of the loop.
5. What is left at the end? When the data runs out, is the answer ready, or is something still “in your hands” — an unfinished run, a table you still have to read? And what happens on the edges: empty input, one element, everything equal?
6. Check with a trace. Walk through your code on the example in a small table: one row per element, one column per variable. The row that surprises you is the bug.

Questions 3, 4 and 5 map onto three parts of the code, and on this page they are coloured. state — what you kept in your head, created before the loop. step — what happens to each element. end — how the state becomes the answer. edge — an edge case handled on purpose. Once you see the parts, every solution reads the same way.

def solve(data):
    memory = ...                 # STATE: what you kept in your head
    for x in data:
        ...                      # STEP: what you did with each new element
    return ...                   # END: how the memory becomes the answer

Ask question 3 and you will almost always get one of the answers below. Each one is a family of problems with its own skeleton. Learn the six, and most easy problems turn into recognising which one you are looking at.

Four kinds of practice. First, recognise the family from the wording — the skill that unlocks the code. Then read code the way an interviewer does: find the bug in a script that returns the wrong answer, predict what code prints, and fill in the missing piece of a solution. Every answer was checked by running the code.

def compress(s):
    if not s:
        return ""
    parts = []
    current, count = s[0], 1
    for ch in s[1:]:
        if ch == current:
            count += 1
        else:
            parts.append(f"{count}{current}")
            current, count = ch, 1
    return "".join(parts)

def count_chars(s):
    counts = {}
    for ch in s:
        counts[ch] += 1
    return "".join(f"{n}{ch}" for ch, n in counts.items())

def largest(nums):
    best = 0
    for x in nums:
        if x > best:
            best = x
    return best

def missing_number(nums):
    expected = sum(range(len(nums)))
    return expected - sum(nums)

def first_uniq_char(s):
    seen = set()
    for i, ch in enumerate(s):
        if ch not in seen:
            return i
        seen.add(ch)
    return -1

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        seen[x] = i
        if target - x in seen:
            return [seen[target - x], i]
    return []

def median(nums):
    n = len(nums)
    mid = n // 2
    if n % 2 == 1:
        return nums[mid]
    return (nums[mid - 1] + nums[mid]) / 2

def unique_sorted(items):
    result = list(set(items))
    result = result.sort()
    return result

def compress(s):
    parts = []
    current, count = s[0], 1
    for ch in s[1:]:
        if ch == current:
            count += 1
        else:
            parts.append(f"{count}{current}")
            current, count = ch, 1
    parts.append(f"{count}{current}")
    return "".join(parts)

print(compress("abab"))

counts = {}
for ch in "abca":
    counts[ch] = counts.get(ch, 0) + 1
print(counts)

seen = set()
for x in [2, 5, 1, 5, 2]:
    if x in seen:
        print(x)
        break
    seen.add(x)

best, count, prev = 0, 0, None
for ch in "aabbbab":
    count = count + 1 if ch == prev else 1
    best = max(best, count)
    prev = ch
print(best)

cheapest, best = float("inf"), 0
for p in [7, 6, 4, 3, 1]:
    cheapest = min(cheapest, p)
    best = max(best, p - cheapest)
print(best)

nums = [0, 1, 2, 3]
n = len(nums)
print(n * (n + 1) // 2 - sum(nums))

out, digits = [], ""
for ch in "12z3a":
    if ch.isdigit():
        digits += ch
    else:
        out.append(ch * int(digits))
        digits = ""
print(len("".join(out)))

def count_chars(s):
    counts = {}
    for ch in s:
        counts[ch] = ???
    return "".join(f"{n}{ch}" for ch, n in counts.items())

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if ??? in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

def missing_number(nums):
    n = len(nums)
    expected = ???
    return expected - sum(nums)

def compress(s):
    if not s:
        return ""
    parts = []
    current, count = s[0], 1
    for ch in s[1:]:
        if ch == current:
            count += 1
        else:
            parts.append(f"{count}{current}")
            current, count = ch, 1
    ???
    return "".join(parts)

def max_profit(prices):
    cheapest, best = float("inf"), 0
    for p in prices:
        cheapest = min(cheapest, p)
        best = max(best, ???)
    return best

Knowing the code by heart does not help when the task is worded slightly differently. What transfers is the reasoning. Three topics come up at almost every analyst interview — strings and counting, sorting, and two pointers — so here they are taken apart slowly, with the questions you should be asking yourself at each step.

1. Does order matter? "Count the letters" and "count letters in a row" are different tasks.
2. What must I remember while walking through the data? A counter, the previous element, the best value so far, what I have already seen.
3. When does what I remember change? This moment — "the run broke", "the sum got too big" — is the heart of the algorithm.
4. What is left over at the end? Many bugs live here: the last group is never written because the loop ended first.

1 · Strings and counting characters

A string is a sequence of characters, just like a list. You can loop over it, take s[i] by position and look back at the previous character with s[i - 1]. One difference matters: strings cannot be changed in place. So the result is collected in a list and glued together once at the end with "".join(parts).

The most frequent string problem at analyst interviews: print how many times each character appears, as "count + character". The count is the total for the whole string, so abab gives 2a2b — the two a's are counted together even though they are not neighbours. Characters go in the order they first appear.

1. Order of neighbours does not matter — only "how many of each". So we need a place to keep a running tally per character: a dictionary character → count.
2. Walk through the string once. For each character: take its current count, or 0 if it is new, and add one — counts.get(ch, 0) + 1.
3. A dictionary remembers the order in which keys were first added (Python 3.7+). So walking through it gives the characters in order of first appearance — no extra work needed.
4. Build the answer from the dictionary: for every pair write "count + character" and join.

Look at the row with i = 2: the second a is not next to the first one, yet its count simply goes from 1 to 2. Neighbours never matter — only the running total for each character.

def count_chars(s):
    """'aabbccc' -> '2a2b3c', 'abab' -> '2a2b': how many times each char appears
    in total, in the order chars first appear."""
    counts = {}                       # a dict remembers insertion order (Python 3.7+)
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    return "".join(f"{n}{ch}" for ch, n in counts.items())

The same dictionary answers a whole family of questions — only the last step changes. Sort its keys for alphabetical order; sort its items by count for "most frequent first"; filter by n > 1 for the characters that repeat; take max for the single most frequent one. Learn the tally once and every variant is one line.

Counter from the collections module does the tally in one word and also keeps first-appearance order. Interviewers often ask for the version without imports first — show the dictionary, then mention Counter as the shortcut.

from collections import Counter

counts = Counter("abab")
print(counts)
print("".join(f"{n}{ch}" for ch, n in counts.items()))

A different, rarer task — run-length encoding — counts only neighbouring repeats: abab becomes 1a1b1a1b. For aabbccc both tasks print the same 2a2b3c, so test your solution on abab to make sure you solved the one that was asked. If the wording is ambiguous, ask.

Here the dictionary is replaced by a single counter that resets whenever the character changes — and the last run has to be written after the loop ends.

2 · Mean, median and mode — by hand

An analyst's favourite warm-up: "compute the average, the median and the most frequent value without NumPy". It checks three things at once — that you know what each statistic means, that you handle the edge cases, and that you know which one to trust.

The definition is the algorithm: add everything up, divide by how many there are. The only trap is the empty list — dividing by zero crashes, so return None first.

def mean(nums):
    if not nums:
        return None                   # an empty list has no mean (and avoids / 0)
    return sum(nums) / len(nums)

Sort first — the median of unsorted data is meaningless. With an odd number of values there is one middle element. With an even number there are two, and the median is their average. The index of the middle is n // 2.

Row 1 has five values: the single middle one is the median. Row 2 adds one more value, so there are two middles and the median is their average.

def median(nums):
    if not nums:
        return None
    s = sorted(nums)                  # the median only makes sense on sorted data
    n = len(s)
    mid = n // 2
    if n % 2 == 1:                    # odd length: one middle element
        return s[mid]
    return (s[mid - 1] + s[mid]) / 2  # even length: average of the two middles

The mode is the counting pattern from the strings section applied to numbers: tally every value, find the highest count, return the values that have it. Return a list — two values can tie, and silently picking one would hide that.

def mode(nums):
    """All most frequent values, sorted (there can be several)."""
    if not nums:
        return []
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
    top = max(counts.values())
    return sorted(x for x, c in counts.items() if c == top)

3 · Sorting: when it helps and how to control it

Sorting is rarely the answer by itself — it is the step that makes the answer easy. After sorting, similar things stand next to each other: duplicates sit in a row, close values become neighbours, and the smallest and largest are at the two ends. That is what makes two pointers and "compare with the neighbour" work. The price is O(n log n), so it pays off when it removes an O(n²) search.

sorted(x) returns a new sorted list and leaves x untouched. x.sort() sorts the list itself and returns None. So x = x.sort() silently replaces your data with None — one of the most frequent mistakes in live coding.

data = [3, 1, 2]
result = sorted(data)
print(result, data)    # a new list; data is unchanged

result = data.sort()
print(result, data)    # None — and data itself is now sorted

The key argument is a function that turns each element into "what to compare". If it returns a tuple, Python compares the first values, and only on a tie looks at the second. A minus sign flips a number into descending order. So key=lambda kv: (-kv[1], kv[0]) reads as: "most frequent first; on a tie — alphabetically".

from collections import Counter

counts = Counter("mississippi")
ranked = sorted(counts.items(), key=lambda kv: (-kv[1], kv[0]))
print(ranked)
print("".join(f"{n}{ch}" for ch, n in ranked))

Look at i and s: both appear 4 times, so the first part of the key is equal. The tie is broken by the second part — the letter itself — and i comes before s.

Insertion sort is the easiest to explain, because it is how people sort cards in their hand. The left part is always sorted. Take the next card and slide it left past every bigger card until it fits. It is O(n²), so in real work you use sorted() — Python's built-in algorithm is O(n log n). But being able to state the rule "the left part stays sorted" is exactly what the interviewer is checking.

def insertion_sort(nums):
    nums = nums[:]
    for i in range(1, len(nums)):
        current = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > current:   # shift bigger values one step right
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = current                 # drop current into the gap
    return nums

The shaded cells are the part that is already sorted — it grows by one on every row. ▲ marks where the new element landed.

4 · Two pointers and duplicates

Two indexes move through the data by a rule, instead of a loop inside a loop. Every step moves at least one pointer, so the whole walk takes at most n steps — O(n). Everything depends on the rule: which pointer moves, and why that move can never skip the right answer. If you can say that sentence out loud, you understand the solution.

One pointer at each end, moving inwards. Works on sorted data and on symmetric questions (palindromes, reversing). Take a sorted list and a target sum. If the sum of the two ends is too small, the left number cannot be part of any answer — even paired with the largest remaining number it falls short. So we drop it and move left. If the sum is too big, the same logic drops the right number.

def two_sum_sorted(nums, target):
    """Sorted list: positions of two numbers that add up to target (opposite pointers)."""
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1                 # need a bigger sum: only moving left can give one
        else:
            right -= 1                # need a smaller sum: only moving right can give one
    return []

Each row throws away one number that provably cannot be in the answer. Five steps instead of fifteen pair checks.

Both pointers start on the left. F (fast) reads every element. S (slow) marks where the "good" part of the array ends. When fast finds something worth keeping, it is copied to the slow position and slow moves on. This is how you clean an array in place without a second list: removing duplicates, moving zeroes to the end, compressing.

def remove_duplicates(nums):
    """Sorted list: keep unique values at the front, return how many."""
    if not nums:
        return 0
    slow = 0                          # last position of the unique part
    for fast in range(1, len(nums)):  # fast scans everything
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

The shaded part is the clean result growing on the left. When F sees a value equal to the one at S, it is a duplicate and simply skipped.

Shape B above removes duplicates in place from a sorted array — that is a LeetCode-style constraint. The everyday interview version is simpler and more common: "return the list without duplicates". Then order matters. list(set(x)) removes repeats but does not keep the original order: a set makes no promise about order. In the example below it even happens to come out sorted — a coincidence of how small numbers are stored, not something to rely on. To keep the first occurrence of each value, walk once and remember what you have already taken.

The set seen answers "have I taken this already?" instantly; the list result keeps the order. Two structures, each doing what it is good at.

def dedup_keep_order(items):
    """[3, 1, 3, 2, 1] -> [3, 1, 2]: drop repeats, keep the first occurrence."""
    seen = set()                      # what we have already taken
    result = []
    for x in items:
        if x not in seen:
            seen.add(x)
            result.append(x)
    return result

When two sorted lists have to be combined or compared, give each its own pointer. At every step compare the two current elements, use the right one, and move only that pointer. Merging sorted lists, checking whether one string is a subsequence of another, and finding common elements all follow this shape.

def is_subsequence(s, t):
    i = 0                             # how much of s is already matched
    for ch in t:
        if i < len(s) and s[i] == ch:
            i += 1
    return i == len(s)

Big-O answers one question: when the input grows, how fast does the work grow? It does not measure seconds — those depend on the computer. It describes the shape of growth. O(n) means "twice the data, twice the work". O(n²) means "twice the data, four times the work".

The chart shows why this matters more than any micro-optimisation. On small inputs every approach is fast. As the data grows, O(n²) leaves the others behind — and that is the curve your interviewer wants you to avoid.

Both functions below solve Two Sum. I timed them on arrays of growing length, on the worst case where no answer exists and every element must be checked. The numbers are measured, not modelled.

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):   # every pair
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

Most interview problems are variations of a small set of patterns. The skill is recognising the pattern from the wording. This table is the cheat sheet: a signal in the problem statement, and the technique it points to.

Most analyst interviews use short, simple problems — the point is to watch how you think, not to stump you. Each problem below has its line of reasoning hidden separately from the solution: open it if you are stuck, but try to reach the idea yourself first.

Strings and characters 13

def count_chars(s):
    """'aabbccc' -> '2a2b3c', 'abab' -> '2a2b': how many times each char appears
    in total, in the order chars first appear."""
    counts = {}                       # a dict remembers insertion order (Python 3.7+)
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    return "".join(f"{n}{ch}" for ch, n in counts.items())

count_chars("aabbccc")
count_chars("abab")
count_chars("")

from collections import Counter


def count_chars_counter(s):
    return "".join(f"{n}{ch}" for ch, n in Counter(s).items())

def count_chars_count(s):
    unique = dict.fromkeys(s)              # distinct chars, in first-appearance order
    return "".join(f"{s.count(ch)}{ch}" for ch in unique)

def count_chars_sorted(s):
    """'cabbac' -> '2a2b2c': the same totals, but in alphabetical order."""
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    return "".join(f"{counts[ch]}{ch}" for ch in sorted(counts))

count_chars_sorted("cabbac")
count_chars_sorted("banana")

from collections import Counter


def count_chars_sorted_counter(s):
    counts = Counter(s)
    return "".join(f"{counts[ch]}{ch}" for ch in sorted(counts))

from itertools import groupby


def count_chars_sorted_groupby(s):
    # sorting puts equal chars side by side; groupby then measures each run
    return "".join(f"{len(list(run))}{ch}" for ch, run in groupby(sorted(s)))

def count_by_frequency(s):
    """'aabbccc' -> '3c2a2b': most frequent first; ties keep first-appearance order."""
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    ranked = sorted(counts.items(), key=lambda kv: -kv[1])   # sorted() is stable
    return "".join(f"{n}{ch}" for ch, n in ranked)

count_by_frequency("aabbccc")
count_by_frequency("abab")

from collections import Counter


def count_by_frequency_counter(s):
    return "".join(f"{n}{ch}" for ch, n in Counter(s).most_common())

def count_by_frequency_key(s):
    # the tie rule is spelled out: more frequent first, then the one seen earlier
    order = sorted(set(s), key=lambda ch: (-s.count(ch), s.index(ch)))
    return "".join(f"{s.count(ch)}{ch}" for ch in order)

def count_letters(text):
    """'Hello, World!' -> '1h1e3l2o1w1r1d': ignore case, spaces and punctuation."""
    counts = {}
    for ch in text.lower():
        if ch.isalpha():              # skip everything that is not a letter
            counts[ch] = counts.get(ch, 0) + 1
    return "".join(f"{n}{ch}" for ch, n in counts.items())

count_letters("Hello, World!")

from collections import Counter


def count_letters_counter(text):
    letters = Counter(ch for ch in text.lower() if ch.isalpha())
    return "".join(f"{n}{ch}" for ch, n in letters.items())

from collections import Counter


def count_letters_filter(text):
    letters = Counter(filter(str.isalpha, text.lower()))
    return "".join(f"{n}{ch}" for ch, n in letters.items())

def most_frequent_char(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    return max(counts, key=counts.get)    # on a tie: the one that appeared first

most_frequent_char("abracadabra")
most_frequent_char("aabb")

from collections import Counter


def most_frequent_char_counter(s):
    return Counter(s).most_common(1)[0][0]

def most_frequent_char_max(s):
    return max(s, key=s.count)

def repeated_chars(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    return [ch for ch, n in counts.items() if n > 1]

repeated_chars("programming")

from collections import Counter


def repeated_chars_counter(s):
    return [ch for ch, n in Counter(s).items() if n > 1]

def repeated_chars_count(s):
    return [ch for ch in dict.fromkeys(s) if s.count(ch) > 1]

def word_frequency(text):
    counts = {}
    for word in text.lower().split():
        counts[word] = counts.get(word, 0) + 1
    return counts

word_frequency("The cat and the hat")

from collections import Counter


def word_frequency_counter(text):
    return dict(Counter(text.lower().split()))

from collections import defaultdict


def word_frequency_defaultdict(text):
    counts = defaultdict(int)              # a missing word starts at 0 automatically
    for word in text.lower().split():
        counts[word] += 1
    return dict(counts)

def compress(s):
    """'aabbccc' -> '2a2b3c': count each run of identical neighbours."""
    if not s:
        return ""
    parts = []
    count = 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:          # same as the previous char: the run goes on
            count += 1
        else:                         # the run broke: write it down, start a new one
            parts.append(f"{count}{s[i - 1]}")
            count = 1
    parts.append(f"{count}{s[-1]}")   # the loop never writes the LAST run
    return "".join(parts)

compress("aabbccc")
compress("abab")
compress("aabbcca")

from itertools import groupby


def compress_groupby(s):
    # groupby cuts the string into runs of identical neighbours
    return "".join(f"{len(list(run))}{ch}" for ch, run in groupby(s))

import re


def compress_regex(s):
    # (.)\1* = one character followed by any number of copies of itself
    return "".join(f"{len(m.group())}{m.group(1)}" for m in re.finditer(r"(.)\1*", s, re.S))

def decompress(code):
    """'2a2b3c' -> 'aabbccc'. Counts may have several digits: '12a'."""
    out = []
    digits = ""
    for ch in code:
        if ch.isdigit():
            digits += ch              # keep collecting the number
        else:
            out.append(ch * int(digits))
            digits = ""
    return "".join(out)

decompress("2a2b3c")
decompress("12z")

import re


def decompress_regex(code):
    # findall returns (number, letter) pairs; \d+ also catches counts like 12
    return "".join(ch * int(n) for n, ch in re.findall(r"(\d+)(\D)", code))

def first_uniq_char(s):
    counts = Counter(s)               # pass 1: how many of each
    for i, ch in enumerate(s):        # pass 2: the first one seen exactly once
        if counts[ch] == 1:
            return i
    return -1

first_uniq_char("leetcode")
first_uniq_char("loveleetcode")
first_uniq_char("aabb")

def first_uniq_char_dict(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    for i, ch in enumerate(s):
        if counts[ch] == 1:
            return i
    return -1

def first_uniq_char_next(s):
    return next((i for i, ch in enumerate(s) if s.count(ch) == 1), -1)

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    return Counter(s) == Counter(t)

is_anagram("anagram", "nagaram")
is_anagram("rat", "car")

def is_anagram_sorted(s, t):
    return sorted(s) == sorted(t)

def is_anagram_balance(s, t):
    if len(s) != len(t):
        return False
    balance = {}
    for a, b in zip(s, t):
        balance[a] = balance.get(a, 0) + 1      # +1 for each letter of s
        balance[b] = balance.get(b, 0) - 1      # -1 for each letter of t
    return all(v == 0 for v in balance.values())

def reverse_words(s):
    return " ".join(word[::-1] for word in s.split(" "))

reverse_words("Let's take LeetCode contest")

def reverse_words_twice(s):
    # reverse everything: each word comes out reversed, but the word order is wrong — fix the order
    return " ".join(s[::-1].split(" ")[::-1])

def reverse_words_reversed(s):
    return " ".join("".join(reversed(word)) for word in s.split(" "))

def longest_common_prefix(words):
    if not words:
        return ""
    prefix = words[0]
    for word in words[1:]:
        while not word.startswith(prefix):
            prefix = prefix[:-1]      # shorten until it fits ("" always fits)
    return prefix

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

def longest_common_prefix_columns(words):
    prefix = []
    for column in zip(*words):             # 1st letters of all words, then 2nd letters, …
        if len(set(column)) != 1:          # the letters in this column differ: stop
            break
        prefix.append(column[0])
    return "".join(prefix)

def longest_common_prefix_minmax(words):
    if not words:
        return ""
    lo, hi = min(words), max(words)         # alphabetically first and last
    for i, ch in enumerate(lo):
        if ch != hi[i]:
            return lo[:i]
    return lo

import os


def longest_common_prefix_stdlib(words):
    return os.path.commonprefix(words)     # works letter by letter, despite the name

Duplicates 5

def dedup_keep_order(items):
    """[3, 1, 3, 2, 1] -> [3, 1, 2]: drop repeats, keep the first occurrence."""
    seen = set()                      # what we have already taken
    result = []
    for x in items:
        if x not in seen:
            seen.add(x)
            result.append(x)
    return result

dedup_keep_order([3, 1, 3, 2, 1])
dedup_keep_order(["b", "a", "b"])
dedup_keep_order([])

def dedup_keep_order_dict(items):
    return list(dict.fromkeys(items))

def dedup_keep_order_slow(items):
    return [x for i, x in enumerate(items) if x not in items[:i]]

def unique_sorted(items):
    return sorted(set(items))         # a set drops repeats but forgets the order

unique_sorted([3, 1, 3, 2, 1])

from itertools import groupby


def unique_sorted_groupby(items):
    # after sorting, equal values stand together: keep one from each run
    return [value for value, _ in groupby(sorted(items))]

def only_unique(items):
    """Values that appear exactly once: [3, 1, 3, 2, 1] -> [2]."""
    counts = {}
    for x in items:
        counts[x] = counts.get(x, 0) + 1
    return [x for x in items if counts[x] == 1]

only_unique([3, 1, 3, 2, 1])

from collections import Counter


def only_unique_counter(items):
    counts = Counter(items)
    return [x for x in items if counts[x] == 1]

def only_unique_count(items):
    return [x for x in items if items.count(x) == 1]

def find_duplicates(items):
    """Which values repeat, each listed once: [3, 1, 3, 2, 1] -> [3, 1]."""
    counts = {}
    for x in items:
        counts[x] = counts.get(x, 0) + 1
    return [x for x, n in counts.items() if n > 1]

find_duplicates([3, 1, 3, 2, 1])
find_duplicates([1, 2, 3])

from collections import Counter


def find_duplicates_counter(items):
    return [x for x, n in Counter(items).items() if n > 1]

def find_duplicates_count(items):
    return list(dict.fromkeys(x for x in items if items.count(x) > 1))

def dedup_string(s):
    """'banana' -> 'ban'."""
    seen = set()
    out = []
    for ch in s:
        if ch not in seen:
            seen.add(ch)
            out.append(ch)
    return "".join(out)

dedup_string("banana")
dedup_string("mississippi")

def dedup_string_dict(s):
    return "".join(dict.fromkeys(s))

Mean, median, mode 3

def mean(nums):
    if not nums:
        return None                   # an empty list has no mean (and avoids / 0)
    return sum(nums) / len(nums)

mean([120, 80, 340, 55, 80, 2000])
mean([])

from statistics import fmean


def mean_stdlib(nums):
    return fmean(nums) if nums else None    # fmean raises an error on an empty list

def median(nums):
    if not nums:
        return None
    s = sorted(nums)                  # the median only makes sense on sorted data
    n = len(s)
    mid = n // 2
    if n % 2 == 1:                    # odd length: one middle element
        return s[mid]
    return (s[mid - 1] + s[mid]) / 2  # even length: average of the two middles

median([340, 55, 120, 80, 80])
median([340, 55, 120, 80, 80, 2000])

from statistics import median as stats_median


def median_stdlib(nums):
    return stats_median(nums) if nums else None

def mode(nums):
    """All most frequent values, sorted (there can be several)."""
    if not nums:
        return []
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
    top = max(counts.values())
    return sorted(x for x, c in counts.items() if c == top)

mode([120, 80, 340, 55, 80, 2000])
mode([1, 1, 2, 2, 3])

from collections import Counter


def mode_counter(nums):
    if not nums:
        return []
    counts = Counter(nums)
    top = max(counts.values())
    return sorted(x for x, n in counts.items() if n == top)

from statistics import multimode


def mode_stdlib(nums):
    return sorted(multimode(nums))         # multimode already returns every tied value

Two pointers 6

def reverse_string(chars):
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return chars

reverse_string(list("hello"))

def reverse_string_builtin(chars):
    chars.reverse()                        # the same swaps, in place, done in C
    return chars

def reverse_string_slice(chars):
    chars[:] = chars[::-1]                 # build a reversed copy, write it back into the same list
    return chars

def remove_duplicates(nums):
    """Sorted list: keep unique values at the front, return how many."""
    if not nums:
        return 0
    slow = 0                          # last position of the unique part
    for fast in range(1, len(nums)):  # fast scans everything
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

a = [1, 1, 2, 3, 3, 3, 4]; k = remove_duplicates(a); print(k, a[:k])

def remove_duplicates_dict(nums):
    unique = list(dict.fromkeys(nums))     # the list is sorted, so this stays sorted
    nums[:len(unique)] = unique
    return len(unique)

def move_zeroes(nums):
    slow = 0                          # where the next non-zero should go
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1
    return nums

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

def move_zeroes_sort(nums):
    nums.sort(key=lambda x: x == 0)        # False (non-zero) sorts before True (zero)
    return nums

def move_zeroes_rebuild(nums):
    nums[:] = [x for x in nums if x != 0] + [0] * nums.count(0)
    return nums

def merge_sorted(nums1, m, nums2, n):
    """nums1 has m values followed by n empty slots. Fill from the END."""
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    return nums1

merge_sorted([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3)

def merge_sorted_sort(nums1, m, nums2, n):
    nums1[m:] = nums2                      # drop nums2 into the empty slots
    nums1.sort()
    return nums1

import heapq


def merge_sorted_heapq(nums1, m, nums2, n):
    nums1[:] = heapq.merge(nums1[:m], nums2)   # merges two sorted sequences in one pass
    return nums1

def sorted_squares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    for pos in range(n - 1, -1, -1):  # the biggest square is at one of the ends
        if abs(nums[left]) > abs(nums[right]):
            result[pos] = nums[left] ** 2
            left += 1
        else:
            result[pos] = nums[right] ** 2
            right -= 1
    return result

sorted_squares([-4, -1, 0, 3, 10])

def sorted_squares_sort(nums):
    return sorted(x * x for x in nums)

def is_subsequence(s, t):
    i = 0                             # how much of s is already matched
    for ch in t:
        if i < len(s) and s[i] == ch:
            i += 1
    return i == len(s)

is_subsequence("abc", "ahbgdc")
is_subsequence("axc", "ahbgdc")

def is_subsequence_iter(s, t):
    it = iter(t)
    return all(ch in it for ch in s)       # "in" moves the iterator forward and never goes back

def is_subsequence_find(s, t):
    pos = -1
    for ch in s:
        pos = t.find(ch, pos + 1)          # next occurrence after the previous match
        if pos == -1:
            return False
    return True

Sorting 3