Python Programming Questions
Python as an interview language: core syntax, data types and built-in collections, comprehensions, iterators and generators, idiomatic style, and the standard library, extending into data-oriented and automation use of the language and its common libraries. Covers writing correct, Pythonic code and reasoning about the language's semantics. The most heavily exercised language surface in this category across engineering and data roles.
Write a function merge_sorted_iterables(iters, key=None) that merges multiple sorted iterables (which may be generators) into a single generator yielding elements in sorted order. Use only standard library modules. Explain memory characteristics.
Sample Answer
Approach: Use a min-heap (a min-heap is a tree-shaped data structure that always keeps its smallest element accessible at the top/root, retrievable in O(1), and restores that property in O(log n) after every push or pop; that is what lets this algorithm always grab the smallest available head-of-iterable next without rescanning every input from scratch) to pull the smallest next element from heads of each iterable. Support key by pushing (key(val), idx, val, iterator). Works with generators and streams and only holds one item per input plus heap overhead.
Implementation:
import heapq
import itertools
def merge_sorted_iterables(iters, key=None):
key = (lambda x: x) if key is None else key
heap = []
for idx, it in enumerate(map(iter, iters)):
try:
val = next(it)
heapq.heappush(heap, (key(val), idx, val, it))
except StopIteration:
continue
while heap:
_, idx, val, it = heapq.heappop(heap)
yield val
try:
nxt = next(it)
heapq.heappush(heap, (key(nxt), idx, nxt, it))
except StopIteration:
continue
Worked example, verified on CPython 3.12:
print(list(merge_sorted_iterables([[1, 4, 7], [2, 3, 9]])))
# [1, 2, 3, 4, 7, 9]
Tracing the heap: it starts holding one entry per input, (1, 0, 1, iter1) and (2, 1, 2, iter2), the smallest head of each list. Popping the smaller one yields 1 and immediately pushes that same iterator's next value, 4, back in, so the heap always holds exactly one "candidate next value" per iterable that still has values left. Popping the current minimum of that small set is always correct because every value not yet pulled from a given iterable is guaranteed to be >= the value currently sitting in the heap for it, since each input is already sorted; the full sequence of pops is 1, 2, 3, 4, 7, 9, matching the printed output exactly.
Key points:
- Memory: O(m) where m = number of input iterables (one element per iterator + heap metadata).
- Works with infinite streams and generators.
- Stable per iterator due to idx tie-breaker.
Edge cases: empty iterables, differing element types (ensure key handles them), expensive key (consider caching keys).
Implement a function top_k_frequent(iterable, k) that returns the k most frequent items and their counts. Your solution must handle very large iterables (possibly streaming) and have O(n) expected time with O(k) additional memory where possible. Use Python.
Sample Answer
Goal: return k most frequent items from a possibly streaming iterable using O(k) extra memory where possible.
Approach: Use Misra-Gries (frequent algorithm) for streaming approximate top-k with O(k) memory; for exact top-k when feasible, use counting with a hashmap and a min-heap of size k (memory O(u) where u unique). For very large universes, prefer Misra-Gries. This is a genuinely advanced, fairly obscure streaming algorithm, most engineers have never needed it; skip straight to "hashmap + heap, exact counts" below unless the interviewer specifically probes for a single-pass, bounded-memory answer.
The core intuition, in plain language, before any code: Misra-Gries tracks at most k candidate items with counts. When a new, not-yet-tracked item arrives and there is no room left (k candidates already exist), instead of dropping the new item and keeping the old ones untouched, EVERY existing candidate's counter is decremented by one, as if the new item had "cancelled out" one occurrence of each current candidate, and the new item itself is not added. Any item that truly appears more than roughly n/k times (n being the total stream length) cannot be fully cancelled away by this process, no matter how the decrements land, so it is guaranteed to still be a candidate at the end; the guarantee is one-sided, though, some less-frequent items may also survive as candidates (false positives), which is exactly why the code takes a second pass over the real data to compute true counts for whatever candidates survived, rather than trusting the approximate counters directly.
Misra-Gries implementation (approximate, deterministic guarantees):
from collections import defaultdict
def top_k_frequent(stream, k):
if k < 1:
return []
counters = {}
for x in stream:
if x in counters:
counters[x] += 1
elif len(counters) < k:
counters[x] = 1
else:
# decrement all
to_del = []
for y in list(counters):
counters[y] -= 1
if counters[y] == 0:
del counters[y]
# counters are candidates; to get actual counts, re-scan
true_counts = defaultdict(int)
for x in stream:
if x in counters:
true_counts[x] += 1
return sorted(true_counts.items(), key=lambda t: -t[1])[:k]
Worked trace, verified on CPython 3.12: an 8-item stream with k=2 (so the true top item, 'a', appears 5 out of 8 times, far more than the other three items, each appearing once):
stream = ['a', 'a', 'b', 'c', 'a', 'd', 'a', 'a']
print(top_k_frequent(stream, 2))
# [('a', 5), ('d', 1)]
Tracing counters step by step: a (candidate, table has room) -> {'a': 1}. Second a (already tracked, increment) -> {'a': 2}. b (room) -> {'a': 2, 'b': 1}. c arrives with the table full (2 candidates already, k=2): every existing candidate is decremented, a drops to 1, b drops to 0 and is deleted, and c itself is never added -> {'a': 1}. Third a (tracked, increment) -> {'a': 2}. d (room again, since b was just evicted) -> {'a': 2, 'd': 1}. Fourth and fifth a (tracked, increment twice) -> {'a': 4, 'd': 1}. Final candidates: a and d. The second pass then counts each candidate's REAL frequency across the whole stream (a: 5, d: 1) and returns them sorted by that real count.
This trace also shows the false-positive behavior honestly: b and c both had a true count of 1, identical to d's true count of 1, but only d happened to survive as a candidate, purely because of when it arrived relative to the decrement-all events. The algorithm's real guarantee is only about the dominant item: a, at 5 out of 8 occurrences, appears far more often than roughly n/k = 4, and it survives every decrement round intact enough to still be tracked at the end. Nothing is guaranteed about which of the equally-infrequent items happen to survive alongside it, which is precisely why a second, exact pass over the real data is required before trusting any reported count, the approximate candidate set is a correct superset guarantee for truly frequent items, not a precise answer on its own.
Notes: The algorithm uses O(k) memory and one or two passes (approximate single-pass; exact requires second pass over data or storing counts). Choose Misra-Gries for streaming huge data; use Counter+heap for exact counts when unique items fit memory.
Write a short Python function detect_deadlocks(thread_dump) that, given a list of thread lock acquisition traces (each trace is a list of lock ids a thread holds and then requests), detects whether a circular deadlock is possible. Provide algorithmic complexity and a brief correctness argument.
Sample Answer
Approach: build a directed graph of lock waits and detect cycles. Represent each lock as node; for each thread that holds locks A then requests B, add edges A -> B. A cycle implies possible deadlock.
def detect_deadlocks(thread_dump):
# thread_dump: list of tuples (holds:list, wants:list)
from collections import defaultdict, deque
g=defaultdict(list)
for holds, wants in thread_dump:
for h in holds:
for w in wants:
g[h].append(w)
# detect cycle via DFS
visited=set(); stack=set()
def dfs(u):
if u in stack: return True
if u in visited: return False
visited.add(u); stack.add(u)
for v in g.get(u, []):
if dfs(v): return True
stack.remove(u); return False
return any(dfs(node) for node in g)
Note (a correction to the traversal, verified by actually running both versions): the loop reads g.get(u, []) rather than plain g[u]. Since g is a defaultdict(list), g[u] for a lock u that is only ever requested and never itself a holds key would silently insert a new empty entry for u into g the first time it is visited, mutating the dictionary while the outer for node in g is still iterating over it. Run directly, that raises RuntimeError: dictionary changed size during iteration on any thread_dump containing such a lock, for example the two-thread chain in the worked example just below. .get(u, []) reads the same list without ever creating a new key, so the traversal cannot perturb the structure it is iterating over.
Worked example, verified on CPython 3.12:
# Deadlock: A holds a lock and wants B's; B holds a lock and wants A's -> circular wait.
print(detect_deadlocks([(['A'], ['B']), (['B'], ['A'])]))
# True
# No deadlock: A wants what B holds, B wants what C holds -> a chain, not a cycle.
print(detect_deadlocks([(['A'], ['B']), (['B'], ['C'])]))
# False
For the deadlock case, the edge-building loop adds A -> B (from the first tuple) and B -> A (from the second), so g = {'A': ['B'], 'B': ['A']}. dfs('A') marks A visited and on-stack, follows the edge to B, marks B visited and on-stack, then follows B's edge back to A; since A is already on the current recursion stack, dfs returns True immediately, that revisit of an on-stack node is the cycle. For the no-deadlock case, g = {'A': ['B'], 'B': ['C']}; dfs('A') walks A -> B -> C, and C has no outgoing edges (g.get('C', []) returns [], since C never holds anything in this example) and is never back on the stack, so every branch returns False and no cycle is found.
Complexity: building edges O(E) where E = sum(hands*wants); cycle detection O(V+E).
Correctness: an edge A -> B means "a thread holding A is waiting to acquire B", i.e. that thread cannot proceed until whoever holds B releases it. Sufficiency (a cycle really does mean a stuck circular wait): if A -> B -> C -> A is a real cycle, the thread waiting on the A -> B edge cannot proceed until B frees up, but whoever holds B is itself stuck on the B -> C edge waiting for C, and whoever holds C is stuck on the C -> A edge waiting for A, which is held by the very first thread that is blocked; every thread on the cycle is waiting on the next one, forever, none of them can be the one to break the chain. Necessity (a stuck circular wait always shows up as a cycle here): if a set of threads really is deadlocked in a circular wait, then by definition each thread in that set holds one lock and is blocked wanting another lock in the same set, which is exactly one holds -> wants edge per thread; following those edges from any thread in the set must eventually revisit a thread already seen, since there are only finitely many threads in the set and every one of them has an outgoing edge to another member of the set, and a finite directed graph where every node in some subset has an outgoing edge back into that same subset necessarily contains a cycle. So "cycle in this graph" and "circular wait is possible" imply each other, given the model that a thread's current wait state is fully captured by its (holds, wants) entry.
Explain how to structure a Python package to make it easy to test and maintain: where to place tests, use of init.py, how to expose a stable public API, and how to run tests in CI. Include best practices for type stubs and documentation.
Sample Answer
Project layout
- mypackage/
- src/mypackage/init.py # package implementation
- src/mypackage/module.py
- tests/ # unit tests
- test_module.py
- pyproject.toml / setup.cfg
Where to place tests
Keep tests outside package source (e.g., tests/ at repo root). This prevents accidental import of tests and mirrors CI test discovery.
init.py & public API
Use init.py to expose a stable public API with explicit imports and all. Keep implementation modules internal (e.g., mypackage._internal).
A concrete worked example of what that __init__.py and its module actually contain:
# src/mypackage/module.py
def process(data):
return [x * 2 for x in data]
def _internal_helper(): # leading underscore: not part of the public API
pass
# src/mypackage/__init__.py
from .module import process
__all__ = ["process"]
A caller then does from mypackage import process, process is the stable public name, while mypackage.module._internal_helper stays a private implementation detail nobody outside the package should import directly; __all__ also controls exactly what from mypackage import * pulls in.
Testing in CI
- Use pytest, run in CI (GitHub Actions) with matrix for Python versions. Run mypy (checks your type hints without actually running the code) and unit tests; fail on coverage thresholds.
A minimal CI job doing exactly that:
# .github/workflows/test.yml
jobs:
test:
strategy:
matrix:
python-version: ["3.11", "3.12"]
steps:
- uses: actions/checkout@v4
- uses: actions/setup-python@v5
with:
python-version: ${{ matrix.python-version }}
- run: pip install -e .[dev]
- run: pytest --cov=mypackage --cov-fail-under=80
- run: mypy src/mypackage
Type stubs & docs
- Add type hints in code; supply .pyi stubs (a
.pyifile is a type-hint-only file, holding no real code, for code Python itself cannot read type hints from directly, such as a compiled C extension) for compiled extensions. - Use Sphinx or MkDocs (both turn your docstrings into a browsable documentation website) for docs; generate API reference from docstrings. Include CI job to build docs.
Which of these matter most for a first working setup versus are polish added later: the src/ layout, an explicit __init__.py public API, and pytest running in CI are the essentials, without them the package is neither testable nor safely importable by other code. mypy, coverage thresholds, .pyi stubs, and generated documentation sites are all valuable, genuinely worth doing, but they are follow-up hardening once the basic package structure and test suite already exist, not blockers to a first working, publishable package.
Best practices: pin dev deps, run linters, and keep public surface minimal and documented.
Design an experiment to compare memory usage and speed of three methods to join two large tables (both fit on disk but not memory): (1) pandas.merge on chunked reads, (2) using SQLite on-disk join, (3) using Dask. Describe metrics to collect, how to ensure fairness, and how to present results.
Sample Answer
Goal: compare memory and wall-clock of three join methods on two large disk-resident tables.
A concrete illustrative scale, to make the deliverable tangible (placeholder numbers for the experiment's INPUT sizes, not a claimed result; the actual measured numbers only come from running it): joining a 5,000,000-row table to a 50,000,000-row table on a shared user_id column, on a machine with 8 GB of RAM available to the process. That size difference (10x) is deliberately chosen so a hash join (build an in-memory lookup table keyed by the join column from the SMALLER side, then scan the larger side and look up each row's match against it, rather than one built from the bigger side) has an obvious "small side" to build its lookup table from.
Metrics:
- Peak RAM (process) via psutil
- Total wall-clock and CPU time
- I/O throughput and disk usage
- Return correctness (row counts, spot checksums)
Fairness:
- Same machine, same storage medium, same join keys/indexes
- Fixed dataset snapshots and repeat runs per method
- Use warm/cold cache measurements (warm cache: the operating system already has the file's data sitting in memory from a previous read, so the next read is fast; cold cache: the OS has to actually go to disk, which is slower and closer to a fresh, worst-case run; measuring both matters because a method that looks fast on a warm cache can look very different the first time it touches a cold file)
Experiment plan:
- Prepare synthetic datasets with controlled sizes and cardinalities, using the illustrative 5M/50M scale above (or whatever scale matches the real workload) as a concrete starting point
- Method (1): pandas: read table A in chunks, build index on join key for B or stream smaller table and use dict-based hash join (build an in-memory Python dict keyed by the join column from the smaller table, then scan the larger table row by row and look each row's key up in that dict, an O(n+m) approach instead of an O(n⋅m) nested comparison)
- Method (2): SQLite: load both tables into temp DB, create indexes, run JOIN
- Method (3): Dask (a library that mirrors the Pandas API but splits data into partitions and runs the same operations, including merge/join, across them in parallel, so a join too large for one machine's memory can still complete by processing partitions and spilling intermediate results to disk when needed): persist datasets on disk, execute dask.dataframe.merge with appropriate partitions
Presentation:
- Plot peak memory vs runtime per method (error bars from repeats)
- Table with throughput, disk I/O, and CPU
- Discuss trade-offs: simplicity, indexing cost, parallelism, disk spill behavior (disk spill: what happens when an operation's intermediate data no longer fits in RAM and the engine starts writing partial results to disk to keep going instead of crashing with an out-of-memory error, trading speed for the ability to finish at all)
Success criteria: lowest peak memory with acceptable runtime; reproducible scripts + configs
Unlock Full Question Bank
Get access to all 46 Python Programming interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.