Lesson 2: Programs 6-10: Sequences, Anagrams and Counting

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 6: Fibonacci Numbers

Question. Return the n-th Fibonacci number, where F(0)=0, F(1)=1 and each next number is the sum of the previous two.

Examples.

• n = 10 → 55
• n = 0 → 0

Approach. The naive recursive version recomputes the same values again and again and takes exponential time. Keep just the last two numbers in a loop, or cache results with functools.lru_cache.

from functools import lru_cache

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)

print([fib(n) for n in range(11)])
print(fib(50), fib_memo(50), fib(90))

Output:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
12586269025 12586269025 2880067194370816120

Complexity. The loop is O(n) time and O(1) space. The memoized version is O(n) time and O(n) space.

Follow-up an interviewer may ask. Can you do better than O(n)? (Matrix exponentiation or fast doubling gives O(log n).)

Problem 7: Check for Anagrams

Question. Two words are anagrams if they contain the same letters in a different order. Return True if so, ignoring case.

Examples.

• "listen", "silent" → True
• "abc", "abd" → False

Approach. If the lengths differ they cannot be anagrams. Otherwise compare the sorted letters (O(n log n)), or compare letter counts with a Counter (O(n)).

from collections import Counter

def is_anagram(a, b):
    a, b = a.lower(), b.lower()
    return len(a) == len(b) and Counter(a) == Counter(b)

def is_anagram_sorted(a, b):
    return sorted(a.lower()) == sorted(b.lower())

for x, y in [("listen", "silent"), ("Hello", "Olelh"), ("abc", "abd"), ("aab", "abb"), ("", "")]:
    print(repr(x), repr(y), is_anagram(x, y), is_anagram_sorted(x, y))

Output:

'listen' 'silent' True True
'Hello' 'Olelh' True True
'abc' 'abd' False False
'aab' 'abb' False False
'' '' True True

Complexity. Counting is O(n) time and O(k) space (k = number of distinct letters). Sorting is O(n log n).

Follow-up an interviewer may ask. How would you group a list of words into anagram families? (Use the sorted letters as a dictionary key.)

Problem 8: Count Character Frequency

Question. Return how many times each character appears in a string.

Examples.

• "mississippi" → {'m': 1, 'i': 4, 's': 4, 'p': 2}

Approach. Walk through the string once, adding one to a dictionary entry for each character. collections.Counter does exactly this. Dictionaries remember insertion order, so the result is predictable.

from collections import Counter

def char_frequency(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    return counts

print(char_frequency("mississippi"))
print(char_frequency(""))
print(Counter("mississippi").most_common(2))
print(char_frequency("Hello World".replace(" ", "").lower()))

Output:

{'m': 1, 'i': 4, 's': 4, 'p': 2}
{}
[('i', 4), ('s', 4)]
{'h': 1, 'e': 1, 'l': 3, 'o': 2, 'w': 1, 'r': 1, 'd': 1}

Complexity. O(n) time, O(k) space for k distinct characters.

Follow-up an interviewer may ask. How would you find the most frequent character? (max(counts, key=counts.get), or Counter.most_common(1).)

Problem 9: First Non-Repeating Character

Question. Return the first character in a string that appears only once, or None if there is none.

Examples.

• "swiss" → "w"
• "aabb" → None

Approach. Two passes: first count every character, then scan the string again in order and return the first whose count is 1. Scanning the original string (not the dictionary) is what keeps the order right.

from collections import Counter

def first_unique(s):
    counts = Counter(s)
    for ch in s:
        if counts[ch] == 1:
            return ch
    return None

for text in ["swiss", "aabb", "leetcode", "", "z"]:
    print(repr(text), "->", first_unique(text))

Output:

'swiss' -> w
'aabb' -> None
'leetcode' -> l
'' -> None
'z' -> z

Complexity. O(n) time, O(k) space.

Follow-up an interviewer may ask. What if the text is a stream and you cannot read it twice? (Keep the counts plus an ordered structure of the characters seen once.)

Problem 10: Remove Duplicates and Keep the Order

Question. Return a list with the repeated items removed, keeping the first occurrence of each in the original order.

Examples.

• [3, 1, 3, 2, 1] → [3, 1, 2]

Approach. A set(items) removes duplicates but loses the order. Instead remember what you have already seen in a set and append an item only the first time. Since dictionaries keep insertion order, list(dict.fromkeys(items)) is a neat one-liner (items must be hashable).

def unique_in_order(items):
    seen = set()
    result = []
    for item in items:
        if item not in seen:
            seen.add(item)
            result.append(item)
    return result

print(unique_in_order([3, 1, 3, 2, 1]))
print(unique_in_order("banana"))
print(unique_in_order([]))
print(list(dict.fromkeys([3, 1, 3, 2, 1])))

Output:

[3, 1, 2]
['b', 'a', 'n']
[]
[3, 1, 2]

Complexity. O(n) time, O(n) space.

Follow-up an interviewer may ask. What if the items are not hashable, such as lists? (Convert to tuples, or fall back to an O(n squared) check with in on the result list.)