Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 77 ยท Python Interview Questions

Python: Classic Coding Questions

Solve classic Python interview problems: anagrams, two-sum, LRU cache, flatten, Counter tricks, plus the time complexity of built-in operations.

Most Python screens include a few short coding problems. They are small on purpose: the interviewer wants to see that you know the standard library, pick the right data structure, and can state the cost of what you wrote. This lesson walks through six classics with a clear method each time: state the idea, write the code, test one edge case, and give the complexity.

Background lessons: Dictionaries, Collections and Generators. For the algorithm families behind these problems, see the DSA tutorial.

A routine for every problem

Clarify Inputs, edge cases, size.
Idea Say the approach before typing.
Code Short and readable.
Cost Time and space, out loud.
1 / 2

Anagrams

Q: Check whether two strings are anagrams. Two strings are anagrams when they have the same letters with the same counts. Sorting both works in O(n log n). Counting characters works in O(n) time and uses collections.Counter. Ask whether case and spaces matter; here we ignore both.

Python Anagram check and grouping

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sorted word is a canonical key: all anagrams map to the same key, so a dictionary groups them. This is a pattern worth naming.

Two-sum

Q: Given a list and a target, return the indices of two numbers that add up to it. The brute force tries every pair, O(nยฒ). The standard answer keeps a dictionary of values seen so far, and for each number looks up its complement (target - n). One pass, O(n) time, O(n) space.

Python Two-sum with a dictionary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The [3, 3] case is the edge case interviewers ask about: because we look up before storing, the same element is never used twice, but two equal values still work.

Counter tricks

Q: Find the most common element, or the first non-repeating character. Counter is a dictionary subclass for counting; most_common(k) returns the top k pairs. Counters also support arithmetic: + adds counts and - subtracts, dropping results that are zero or less.

Python Counter in practice

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Flatten a nested list

Q: Flatten arbitrarily nested lists. Recursion is the natural fit. With a generator you produce items lazily and never build intermediate lists. Mention the limits: deep nesting can hit the recursion limit, and strings need care because a string is iterable and its characters are strings again (infinite recursion if you test "is it iterable?").

Python Recursive generator and an iterative version

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The iterative version uses an explicit stack, so depth is no longer limited by Python's recursion limit. Both run in O(n) for n total items.

LRU cache

Q: Implement a least-recently-used cache with O(1) get and put. You need fast lookup (hash map) and fast "move to most recent" and "remove oldest" (a linked list). In Python, collections.OrderedDict is exactly that combination: move_to_end and popitem(last=False) are O(1).

Python LRU cache with OrderedDict

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The follow-up is usually "now do it without OrderedDict". The answer is a dictionary from key to node plus a doubly linked list. For caching function results, the standard library already ships functools.lru_cache; see Itertools and Functools.

Time complexity of built-ins

Interviewers love "what is the cost of that line?" Know these (CPython, average case):

Operation Cost
list[i], list.append(x) O(1) (append is amortized)
list.insert(0, x), list.pop(0), x in list O(n)
list.sort(), sorted(x) O(n log n)
dict[k], k in dict, set.add(x), x in set O(1) average
s += t for strings in a loop O(nยฒ) overall: use "".join(parts)
collections.deque.appendleft / popleft O(1)
Slicing a[i:j] O(j - i), it copies
Python Why membership in a list is slow

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Never quote exact timings in an interview. Say "O(n) scan versus O(1) average hash lookup" and, if asked, mention that worst-case dictionary behavior is O(n) with pathological hash collisions.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the time complexity of the dictionary-based two-sum solution?

    One pass over the list with O(1) average lookups; the dictionary may store up to n values.
  2. 2. Which structure gives O(1) get and put for an LRU cache in Python's standard library?

    OrderedDict keeps insertion order and can move or remove ends in constant time.
  3. 3. Why does list.pop(0) have a performance problem?

    Lists are arrays; removing from the front moves every other element.
  4. 4. What is a good canonical key for grouping anagrams?

    All anagrams of a word contain the same letters, so sorting them yields identical keys.

Summary

  • Name the idea first, then code, then test an edge case and state the complexity.
  • Anagrams: compare Counters or group by the sorted-letters key.
  • Two-sum: one pass with a dictionary of values seen, looking up the complement.
  • Flatten with a recursive generator, or an explicit stack to avoid recursion limits.
  • LRU cache: OrderedDict gives O(1) updates; know the dict plus linked list version.
  • Know the costs: list front operations and list membership are O(n); dict and set lookups are O(1) on average.

Next: Java: OOP, Strings and the Object Contract.