Coding Interview Questions and Answers

Slicing is the normal way to do it in Python. Without it, build the result from the end or swap characters from both ends of a list.

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

def reverse_manual(s):
    chars = list(s)
    i, j = 0, len(chars) - 1
    while i < j:
        chars[i], chars[j] = chars[j], chars[i]
        i += 1; j -= 1
    return "".join(chars)

print(reverse("hello"), reverse_manual("hello"))   # olleh olleh

Strings are immutable, so a copy is needed. Complexity: O(n) time, O(n) space.

What they are checking: Basic string handling and awareness of immutability

Compare the cleaned string with its reverse, or use two pointers moving inward to avoid the extra copy. For sentences, ignore case and non-alphanumeric characters.

def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if not s[i].isalnum(): i += 1
        elif not s[j].isalnum(): j -= 1
        else:
            if s[i].lower() != s[j].lower(): return False
            i += 1; j -= 1
    return True

print(is_palindrome("A man, a plan, a canal: Panama"), is_palindrome("hello"))   # True False

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

What they are checking: Two pointer basics and edge cases (case, punctuation)

Print numbers 1 to n; multiples of 3 print Fizz, multiples of 5 print Buzz, multiples of both print FizzBuzz. Check the combined case first (or build the string).

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

print(fizzbuzz(15))

Complexity: O(n) time. The common mistake is testing 3 and 5 before 15, so 15 prints only Fizz.

What they are checking: Basic control flow and ordering of conditions

Use a hash map from value to index. For each number, check whether target - x has been seen. One pass instead of a nested loop.

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

print(two_sum([2, 7, 11, 15], 9))   # [0, 1]

Complexity: O(n) time, O(n) space. Brute force is O(n^2) time and O(1) space. If the array is sorted, two pointers give O(n) time with O(1) space.

What they are checking: The classic hash map optimisation

Two strings are anagrams if they have the same characters with the same counts. Compare sorted strings, or compare character counts (faster).

from collections import Counter

def is_anagram(a, b):
    return Counter(a) == Counter(b)

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

print(is_anagram("listen", "silent"), is_anagram("abc", "abd"))   # True False

Counter: O(n) time, O(k) space for k distinct characters. Sorting: O(n log n). Clarify with the interviewer whether case and spaces matter.

What they are checking: Frequency counting

The naive recursion repeats work and is O(2^n). Use iteration with two variables, or memoization.

from functools import lru_cache

def fib(n):                       # iterative
    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(10), fib_memo(10))   # 55 55

Iterative: O(n) time, O(1) space. Memoized: O(n) time and space. A matrix or fast-doubling method gives O(log n).

What they are checking: Recursion, repeated subproblems and DP awareness

Track the largest and second largest in one pass, no sorting needed. Handle duplicates by requiring a strictly smaller value.

def second_largest(nums):
    first = second = float("-inf")
    for x in nums:
        if x > first:
            first, second = x, first
        elif first > x > second:
            second = x
    return None if second == float("-inf") else second

print(second_largest([5, 9, 2, 9, 7]))   # 7

Complexity: O(n) time, O(1) space. Sorting works but costs O(n log n). Edge cases: fewer than two distinct values.

What they are checking: One-pass thinking and edge cases

Use a set to remember what you have seen. A value already present is a duplicate.

def find_duplicates(nums):
    seen, dups = set(), set()
    for x in nums:
        if x in seen: dups.add(x)
        else: seen.add(x)
    return list(dups)

print(sorted(find_duplicates([1, 2, 3, 2, 4, 1])))   # [1, 2]

Complexity: O(n) time, O(n) space. Alternatives: sort and compare neighbours (O(n log n), O(1) extra space), or if values are 1..n, use index marking in place.

What they are checking: Set usage and space-time trade-off

Use a stack. Push opening brackets; on a closing bracket, the top of the stack must be its matching opener. At the end the stack must be empty.

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

print(is_valid("{[()]}"), is_valid("(]"))   # True False

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

What they are checking: Stack usage

Use two pointers, always taking the smaller current element. Append what remains.

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

print(merge([1, 3, 5], [2, 4, 6, 8]))   # [1, 2, 3, 4, 5, 6, 8]

Complexity: O(m + n) time, O(m + n) space. This is the merge step of merge sort. If one array has spare room at the end (merge in place), fill from the back.

What they are checking: Two pointers and merge sort foundation

A prime has no divisors other than 1 and itself. You only need to test divisors up to the square root.

Use a dictionary (or Counter) mapping each item to its count.

Keep lo and hi bounds; compare the middle value and throw away half each time. The array must be sorted.

Walk the list while reversing each next pointer, keeping track of the previous node.

Floyd's tortoise and hare: move one pointer by 1 and another by 2. If there is a cycle they meet; otherwise the fast pointer reaches the end.

The expected sum of 1..n is n(n+1)/2. Subtract the actual sum. XOR also works and avoids overflow in fixed-width languages.

Count characters in the first pass, then return the first character whose count is 1 in a second pass.

Use a write pointer: copy each non-zero value forward, then fill the rest with zeros. This works in place.

Take k modulo n, then use slicing for clarity, or three reversals for O(1) extra space.

Split on whitespace, reverse the list, join with a single space. Using split() without arguments also collapses extra spaces.

Euclid's algorithm: gcd(a, b) = gcd(b, a % b) until b is 0. LCM follows from lcm = a * b / gcd.

• Sorting with a comparison sort (sorted, Arrays.sort): O(n log n) time.
• Hash map or set lookup, insert, delete: O(1) on average, O(n) worst case.
• Single loop over the array: O(n).
• Two nested loops over the array: O(n^2).
• Binary search on sorted data: O(log n).
• Generating all subsets: O(2^n); all permutations: O(n!).

x in some_list scans the list: O(n). x in some_set hashes x and looks it up: O(1) on average. For repeated membership tests, first turn the list into a set (O(n) once). This changes an O(n * m) algorithm into O(n + m).

Walk the string once. Keep the current character and its run length. When the run ends, add the character and the count to the result. Use a list and join at the end, because repeated string concatenation is slower.

Use recursion when the depth is small. Use your own stack when the nesting could be very deep and you want to avoid the recursion limit.

Use a dictionary keyed by customer and update it in one pass. This is O(n) and does not need sorting.

Put one array into a set and keep elements of the other that are in it. For duplicates counted multiple times, use Counter.

Sliding window with a map of the last seen index of each character. When a repeat is inside the window, move the left edge past the previous occurrence.

At each element, either extend the current subarray or start fresh, whichever is larger. Track the best seen.

Use a canonical key for each word: its sorted letters. Words with the same key are anagrams.

Sort by start. Then walk through: if the next interval starts before or at the end of the last merged one, extend the end. Otherwise, start a new interval.

The number of ways to reach step n is the sum of the ways to reach n-1 and n-2. This is the Fibonacci pattern.

Bottom-up DP: dp[a] is the minimum coins for amount a. For each amount try every coin. Greedy fails for some coin sets (for example coins 1, 3, 4 and amount 6).

For each index, the answer is the product of everything to its left times everything to its right. Compute prefix products going forward, then multiply by suffix products going back.

Sort the array. For each index i, use two pointers on the rest to find pairs that sum to -a[i]. Skip duplicates to keep results unique.

Scan once, tracking the lowest price so far and the best profit if you sold today.

Use BFS with a queue. Process one level at a time by reading the queue length before looping.

Both are short recursions: depth is 1 + max of child depths; inversion swaps children at every node.

Pass down the allowed range for each node. Checking only the immediate children is a common bug, because a deep node must obey every ancestor.

Count with a Counter. Then take the K most common using a heap (O(n log k)), or a bucket sort by frequency (O(n)).

Scan the grid. When you find an unvisited 1, count one island and flood fill it (DFS or BFS) marking all connected land.

Boyer-Moore voting: keep a candidate and a counter. Matching element increments, different one decrements; when the counter hits zero pick a new candidate. A true majority always survives.

Expand around every possible centre (n odd-length and n-1 even-length centres) and keep the longest.

Modified binary search: at each step one half is always sorted. Check whether the target lies in the sorted half. If not, throw that half away.

Patience sorting with binary search: keep tails[i], the smallest possible tail of an increasing subsequence of length i + 1. For each number, replace the first tail that is greater or equal, or append.

Combine a hash map (O(1) lookup) with a structure that tracks recency. In Python, OrderedDict is a hash map plus doubly linked list, with move_to_end and popitem.

Keep a second stack (or store pairs) that tracks the minimum at each depth. Every push records the smaller of the new value and the current minimum.

Use an input stack for pushes and an output stack for pops. When the output stack is empty, move everything over, which reverses the order to FIFO.

Use a sliding window log per user: keep the timestamps of recent requests in a deque. Drop the ones older than the window. Allow the request if fewer than N remain.

Treat AI output like code from a new teammate: useful, but unreviewed. I never merge what I cannot explain line by line.

Keep two heaps: a max-heap for the lower half and a min-heap for the upper half, sizes balanced within one. The median is the top of the larger heap, or the average of both tops.

Store timestamps in a deque (hits arrive in time order). On each query, drop entries older than 300 seconds and return the length. For very high traffic, count into per-second buckets in a fixed array of 300 slots.

Store (value, expires_at) in a dict. Check expiry lazily on reads. A background sweep (or heap ordered by expiry) removes dead entries so memory does not grow without bound.

Give each URL an auto-increment ID (from a database sequence or a distributed ID generator). Then encode the ID in base62 (0-9, a-z, A-Z). Decoding reverses it. This avoids collisions and gives short codes: 7 characters cover 62^7, about 3.5 trillion IDs.

Work in the smallest currency unit (integer cents or paisa), so there is no floating point error. Work out each share with integer division. Then give out the leftover units one by one, so the shares add up exactly to the total. This is the largest remainder method.