You have a long list of readings and a stream of questions about it. What’s the total between positions 3 and 40? Where would 17 go if you inserted it? Scanning the whole list for every question works, but your interviewer will ask whether you can do better. That’s what you’ll practice in this course.
You’ll work through fourteen exercises with two patterns. Prefix sums save running totals once, so any range total becomes a single subtraction. Binary search uses sorted order to throw away half of the remaining values with every step.
You should feel comfortable with functions, loops, lists, dictionaries, and the basics of Big O notation. The previous course in this series, Python Coding Interview Practice: Hashing, Pointers, and Windows, makes a good warm-up, but it isn’t required.
Each pattern section opens with a short introduction and six exercises, and ends with a recap. The mixed practice section leaves out the pattern name, so you get to choose the approach yourself, and then you’ll try a mock interview. For each problem, you’ll clarify, plan, implement, test, and explain:
Before you type, grab a pen and paper and walk a small input through by hand. What should you return for an empty list? Where exactly does a range start, and where does it stop? Off-by-one slips love both of these patterns, so a tiny example pays off quickly.
The time and extra-space bounds in each exercise are requirements. Expect a few red tests along the way. Read each failure message before you change your code, and open one hint at a time when you’re stuck. After your tests pass, use the efficiency review to explain what your code costs, including Python operations such as slicing, which copies part of a list.
Got your pen and paper ready? Have fun practicing!
Free Bonus: Python Time and Space Complexity Cheat Sheet
Get a Python Time and Space Complexity Cheat Sheet (PDF) with the Big O costs of lists, dicts, sets, deques, heaps, sorting, and recursion on one page:
