Algorithms in Python — Practice Questions

Implement linear_search(numbers, target) returning the index of target, or -1 if not found.

Implement binary_search(sorted_numbers, target) returning the index of target, or -1 if not found.

Implement bubble_sort(numbers) sorting a list in place using repeated adjacent swaps.

Implement selection_sort(numbers), repeatedly finding the minimum of the unsorted portion and swapping it into place.

Implement insertion_sort(numbers), building up a sorted portion one element at a time.

Write is_sorted(numbers) that checks whether a list is already sorted in ascending order.

Write a recursive factorial(n) as a warm-up before tackling more complex recursive algorithms.

Given numbers = [4, 2, 7, 1, 9], build a set from it and show that membership checks against the set are the hashing-based alternative to a linear scan.

Given a list of words, build a frequency dictionary counting each word's occurrences (a direct application of hashing).

Write two_sum_brute_force(numbers, target) checking every PAIR of numbers with nested loops, returning the pair's indices.

Implement merge_sort(numbers) recursively — split the list in half, sort each half, then merge them back together.

Implement quicksort(numbers) recursively using a simple pivot-partition approach.

Given a SORTED list, write has_pair_with_sum(numbers, target) using two pointers (one from each end) to check if a pair sums to target.

Write reverse_in_place(numbers) using two pointers swapping from both ends toward the middle.

Given numbers = [2, 4, 6, 8, 10], build a prefix-sum array where prefix[i] is the sum of numbers[0..i].

Using a prefix-sum array, answer a "range sum" query (sum of numbers[start:end+1]) in O(1), instead of re-summing each time.

Given a list and a fixed window size k, find the maximum sum of any k consecutive elements using a sliding window (not recomputing the full sum each time).

Given a list of positive numbers and a target sum, find the length of the SMALLEST contiguous subarray whose sum is at least target, using a variable-size sliding window.

Write two_sum_hashed(numbers, target) using a dictionary to solve the two-sum problem in a SINGLE pass (O(n) instead of O(n^2)).

Write first_unique_char(text) using a frequency dictionary to find the first character that appears exactly once.

Given numbers = [1, 2, 4, 5, 6] (one number from 1 to n is missing), find the missing number using the sum formula n*(n+1)/2.

Given numbers = [4, 3, 6, 2, 3, 1], find the FIRST duplicate value using a set for O(n) detection.

Given numbers = [1, 5, 3, 4, 2] and a diff of 2, count how many PAIRS have exactly that absolute difference, using a set for O(n) lookups.

Write longest_substring_without_repeats(text) finding the length of the longest substring with no repeated characters, using a sliding window and a set.

Implement Kadane's algorithm, max_subarray_sum(numbers), finding the largest sum of any contiguous subarray.

Implement merge_intervals(intervals) merging overlapping (start, end) tuples into non-overlapping ones (revisiting the Tuples module as an algorithm).

Write intersection(list1, list2) finding common elements between two lists using sets, in O(n) instead of a nested loop.

Write is_anagram(word1, word2) using character-frequency dictionaries (an O(n) alternative to sorting both strings).

Write find_majority_element(numbers) finding the element that appears MORE than n/2 times, using a frequency dictionary.

Write move_zeroes_to_end(numbers) moving all zeroes to the end IN PLACE while preserving the relative order of non-zero elements, using two pointers.

Implement quicksort_in_place(numbers, low, high) using Lomuto partitioning, sorting the array WITHOUT creating new lists at each step.

Implement sliding_window_maximum(numbers, k) finding the maximum of every window of size k, using a collections.deque to stay efficient.

Write longest_common_prefix(words) finding the longest prefix shared by EVERY word in a list.

Implement three_sum_zero(numbers) finding all UNIQUE triplets that sum to zero, using sorting + two pointers (avoiding the O(n^3) brute force).

Implement trapping_rain_water(heights) computing how much water is trapped between bars of given heights, using two pointers.

Write kth_largest(numbers, k) finding the k-th largest value using sorted(), then explain in a comment why a heap-based approach (not covered here) would scale better for huge inputs.

Implement tower_of_hanoi(n, source, target, auxiliary), printing each move needed to solve the classic puzzle recursively.

Implement generate_permutations(items) recursively, returning every possible ordering of a list.

Implement fibonacci_memoized(n, cache={}), caching previously computed results to avoid the exponential blow-up of plain recursive Fibonacci.

The following binary search has an off-by-one bug that causes an infinite loop for certain inputs. Find and fix it.

def binary_search(numbers, target):
    low, high = 0, len(numbers)
    while low < high:
        mid = (low + high) // 2
        if numbers[mid] == target:
            return mid
        elif numbers[mid] < target:
            low = mid
        else:
            high = mid
    return -1

Build a "Sorting Algorithm Comparator": implement bubble sort, merge sort, and Python's built-in sorted(), running all three on the SAME random list and timing each with timeit.

Build a "Search Benchmark Tool" comparing linear search versus binary search on a large sorted list, timing both with timeit.

Build a "Two-Pointer Toolkit" combining pair-sum detection, in-place reversal, and palindrome checking, all sharing the same two-pointer pattern.

Build a "Sliding Window Toolkit" combining fixed-window max-sum and longest-unique-substring, both using the window pattern.

Build a "Recursion Toolkit" combining factorial, memoized Fibonacci, and permutation generation into one demonstration.

Explain Big-O time complexity for O(1), O(n), O(n log n), and O(n^2), demonstrating each with a concrete, annotated code example.

Revisit the two-sum problem as a classic interview contrast: brute force O(n^2) versus hashing O(n), explaining exactly WHY the hashmap version is faster.

Explain the tradeoffs between recursion and iteration (stack depth limits, memoization opportunities, code clarity), demonstrating with the Fibonacci example.

Explain when to choose which sorting approach: Python's built-in sorted() (Timsort) versus a hand-rolled algorithm, covering stability and real-world performance.

Build an "Algorithms Mastery Report" — the most complete demonstration in this module. Given a random list of numbers, run and print results from: binary search, merge sort, a two-pointer pair-sum check, a prefix-sum range query, a sliding-window max-sum, and a hashing-based duplicate check — all in one labeled report.