Lesson 1: Programs 1-5: Strings and Numbers

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 1: Reverse a String

Question. Write a function that returns a string reversed.

Examples.

• "Kathmandu" → "udnamhtaK"
• "" → ""

Approach. The shortest way is a slice with step -1. Interviewers often also want to see you do it by hand, with two pointers swapping characters from both ends (strings cannot be changed in place, so use a list).

def reverse_string(s):
    return s[::-1]

def reverse_two_pointers(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

for text in ["Kathmandu", "", "a", "ab"]:
    print(repr(reverse_string(text)), repr(reverse_two_pointers(text)))

Output:

'udnamhtaK' 'udnamhtaK'
'' ''
'a' 'a'
'ba' 'ba'

Complexity. Both run in O(n) time and use O(n) extra space (a new string or list).

Follow-up an interviewer may ask. How would you reverse the words in a sentence but not the letters? (Split, reverse the list, join.)

Problem 2: Check for a Palindrome

Question. Return True if a string reads the same forwards and backwards, ignoring case, spaces and punctuation.

Examples.

• "A man, a plan, a canal: Panama" → True
• "race a car" → False

Approach. First keep only letters and digits in lower case, then compare from both ends with two pointers (or compare with the reverse). Two pointers can stop early at the first difference.

def is_palindrome(s):
    chars = [c.lower() for c in s if c.isalnum()]
    left, right = 0, len(chars) - 1
    while left < right:
        if chars[left] != chars[right]:
            return False
        left += 1
        right -= 1
    return True

for text in ["A man, a plan, a canal: Panama", "race a car", "", "a", "No lemon, no melon", "ab"]:
    print(repr(text), is_palindrome(text))

Output:

'A man, a plan, a canal: Panama' True
'race a car' False
'' True
'a' True
'No lemon, no melon' True
'ab' False

Complexity. O(n) time, O(n) space for the cleaned list. You can reach O(1) extra space by moving two indexes past non-alphanumeric characters instead of building a list.

Follow-up an interviewer may ask. Can you do it without creating a new string? (Skip non-alphanumeric characters with the two indexes.)

Problem 3: FizzBuzz

Question. For the numbers 1 to n: print "Fizz" for multiples of 3, "Buzz" for multiples of 5, "FizzBuzz" for multiples of both, otherwise the number.

Examples.

• n = 15 → 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz

Approach. Check the multiple-of-both case first (or build the word from two parts). The classic mistake is testing 3 and 5 before 15, which prints only "Fizz".

def fizzbuzz(n):
    result = []
    for i in range(1, n + 1):
        word = ""
        if i % 3 == 0:
            word += "Fizz"
        if i % 5 == 0:
            word += "Buzz"
        result.append(word or str(i))
    return result

print(", ".join(fizzbuzz(15)))
print(fizzbuzz(0), fizzbuzz(1))

Output:

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz
[] ['1']

Complexity. O(n) time and O(n) space for the result list.

Follow-up an interviewer may ask. How would you add a third rule, such as "Bazz" for multiples of 7? (The word-building version just gains one more if.)

Problem 4: Check for a Prime Number

Question. Return True if a number is prime (greater than 1 and divisible only by 1 and itself).

Examples.

• 7 → True
• 1 → False
• 91 → False (7 x 13)

Approach. Numbers below 2 are not prime. Otherwise try dividing by 2, then only odd numbers up to the square root: if a number has a factor larger than its square root, it also has a smaller one, so you never need to look further.

import math

def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    for d in range(3, math.isqrt(n) + 1, 2):
        if n % d == 0:
            return False
    return True

print([n for n in range(-2, 30) if is_prime(n)])
print(is_prime(91), is_prime(97), is_prime(1_000_000_007))

Output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
False True True

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

Follow-up an interviewer may ask. How would you list all the primes up to a million? (The Sieve of Eratosthenes: O(n log log n).)

Problem 5: Factorial

Question. Compute n! = n x (n-1) x ... x 1, where 0! = 1. Reject negative numbers.

Examples.

• 5 → 120
• 0 → 1

Approach. A loop that multiplies is simplest and cannot overflow the call stack. The recursive version, n * factorial(n - 1), shows you understand recursion, but Python limits recursion depth (about 1000), so it fails for large n.

import math

def factorial(n):
    if n < 0:
        raise ValueError("factorial is not defined for negative numbers")
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

def factorial_recursive(n):
    return 1 if n <= 1 else n * factorial_recursive(n - 1)

print([factorial(n) for n in range(8)])
print(factorial(20), factorial(20) == math.factorial(20), factorial_recursive(10))
try:
    factorial(-1)
except ValueError as e:
    print("error:", e)

Output:

[1, 1, 2, 6, 24, 120, 720, 5040]
2432902008176640000 True 3628800
error: factorial is not defined for negative numbers

Complexity. O(n) time (the numbers get large, so each multiplication costs more for big n), O(1) space for the loop and O(n) stack for recursion.

Follow-up an interviewer may ask. How would you count the trailing zeros of n! without computing it? (Count the factors of 5: n//5 + n//25 + ...)