λDSA Learning Hubpart of DSA Atlas

Python Foundations

Beginner~3h · 8 lessons0 practice problems

The Python building blocks every DSA solution is written with: collections, functions, classes, iterators, and the math that shows up in interviews.

0 of 8 lessons checked off

Introduction

What it is

  • This topic is a fast, interview-focused refresher of the Python you will use in every other lesson: variables and types, loops and conditionals, functions, classes, and the built-in collections (list, tuple, dict, set, deque).
  • It also covers the small math toolkit interviews assume silently: logarithms, modulo arithmetic, and bitwise operators.

Why it matters

  • Interviewers judge fluency. If you pause to remember how enumerate or dict.get works, you lose time and confidence that should go into the algorithm.
  • Almost every optimal Python solution leans on the right built-in: a dict for O(1) lookup, a deque for O(1) pops from the left, a heap for repeated minimums. Knowing what exists is half the battle.

How it works

  • Python's core collections are thin wrappers over classic data structures: list is a dynamic array, dict and set are hash tables, collections.deque is a doubly linked ring buffer, and heapq turns a list into a binary min-heap.
  • Functions are first-class values, iteration is protocol-based (__iter__/__next__), and generators produce values lazily with yield — which lets you traverse huge search spaces without storing them.

Where it's used

  • The same primitives run production systems: dicts back caches and configuration, deques back task queues, and generators back streaming pipelines that process files larger than memory.

In interviews

  • Choosing the right built-in container is often the entire answer to a warm-up question ('deduplicate this list', 'count word frequency').
  • Call-stack mechanics explain recursion limits and why iterative rewrites are sometimes required.
Analogy: Think of Python's built-ins as a well-organised toolbox: you can build a cabinet with only a knife, but the person who reaches straight for the screwdriver finishes first — and interviews are timed.

Interactive diagram

Every call pushes a frame; every return pops one. Recursion is just this mechanism feeding itself.

Python runs main()

Every function call pushes a frame (its local variables and return address) onto the call stack.

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Variables and data types

    Names bind to objects; int, float, str, bool; mutability vs immutability and why it matters for function arguments.

    15 min
  2. Loops and conditionals

    for/while, range, enumerate, zip, break/continue/else — the traversal vocabulary used in every algorithm.

    15 min
  3. Functions

    Parameters, return values, default-argument pitfalls, *args/**kwargs, and closures.

    15 min
  4. Classes and objects

    Defining ListNode/TreeNode-style classes, __init__, attributes, and dunder methods interviews expect.

    20 min
  5. Python collections

    list, tuple, dict, set, deque, Counter, defaultdict, heapq — what each costs and when to reach for it.

    25 min
  6. Iterators and generators

    The iteration protocol, yield, lazy evaluation, and generator expressions for memory-light pipelines.

    20 min
  7. Recursion and the call stack

    How Python tracks nested calls, the ~1000-frame default limit, and stack overflow.

    15 min
  8. Math foundations: logs, modulo, bitwise

    Why halving means log₂ n, how % wraps values into a range, and the &, |, ^, <<, >> operators.

    25 min

Operations

Choosing the right collection

The four containers that solve 90% of interview subproblems, with the operation costs that justify them.

Choosing the right collection
from collections import Counter, defaultdict, dequeimport heapqnums = [3, 1, 4, 1, 5, 9, 2, 6]# dict / set: O(1) average lookup — membership and frequencyfreq = Counter(nums)              # {1: 2, 3: 1, ...}seen: set[int] = set()graph: defaultdict[int, list[int]] = defaultdict(list)# deque: O(1) append/pop at BOTH ends — BFS queues, sliding windowsqueue: deque[int] = deque([1, 2, 3])queue.append(4)                   # rearfirst = queue.popleft()           # front, O(1) (list.pop(0) is O(n)!)# heapq: O(log n) push/pop of the SMALLEST — top-k, schedulingheap = list(nums)heapq.heapify(heap)               # O(n)smallest = heapq.heappop(heap)    # O(log n)# sorted / sort: O(n log n), stable — the workhorse preprocessing stepordered = sorted(nums, key=lambda x: -x)
Time: O(1)–O(n log n) per operation (see table)Space: O(n)

Edge cases

  • dict/set need hashable keys — lists can't be keys, tuples can.
  • heapq is a min-heap only; push negated values for max-heap behaviour.
  • list.pop(0) silently costs O(n); use deque.popleft() instead.

Common mistakes

  • Using `in` on a list inside a loop (O(n) each) when a set gives O(1).
  • Mutable default arguments (def f(x, acc=[])) sharing state across calls.

Iterators and generators

yield pauses a function and resumes it on demand — sequences are produced one element at a time instead of being materialised.

Iterators and generators
def countdown(n: int):    """Generate n, n-1, ..., 1 lazily."""    while n > 0:        yield n          # pause here; resume on next()        n -= 1gen = countdown(3)print(next(gen))         # 3print(next(gen))         # 2print(list(gen))         # [1]  — continues from where it paused# Generator expression: sum of squares without a temporary listtotal = sum(x * x for x in range(1_000_000))
Time: O(1) per value producedSpace: O(1) beyond the values you keep

Edge cases

  • A generator can be consumed only once; convert to list() if you need to re-iterate.
  • next() on an exhausted generator raises StopIteration.

Common mistakes

  • Building a full list just to loop over it once — a generator does it in O(1) memory.
  • Returning inside a generator body ends it; use yield for every value.

Logarithms, modulo, and bitwise operators

The three pieces of math interviews assume: log₂ counts halvings, % wraps into a range, and bit operators manipulate integers directly.

Logarithms, modulo, and bitwise operators
import math# Logarithm: how many times can 64 be halved before reaching 1?print(math.log2(64))      # 6.0  → binary search on 64 items ≈ 6 probes# Modulo: wrap an index around a circular structurering_size = 5index = (4 + 3) % ring_size    # 2 — circular queue arithmeticprint(-7 % 5)                  # 3 — Python keeps modulo non-negative# Bitwise: integers as arrays of bitsa, b = 12, 10                  # 1100, 1010print(a & b)   # 8  (1000)  both bits setprint(a | b)   # 14 (1110)  either bit setprint(a ^ b)   # 6  (0110)  bits differprint(a << 1)  # 24 — ×2      a >> 1 → 6 — //2print(a & (a - 1))  # 8 — clears lowest set bit (bit-count trick)
Time: O(1)Space: O(1)

Edge cases

  • Python's % always returns a value with the sign of the divisor: -7 % 5 == 3 (unlike C/Java).
  • Python ints are arbitrary precision — no overflow, but bit tricks assuming 32 bits need masking with 0xFFFFFFFF.

Common mistakes

  • Confusing logical `and`/`or` with bitwise `&`/`|`.
  • Assuming log means natural log; complexity analysis uses log base 2, though the base only changes a constant factor.

Complexity analysis

OperationBestAverageWorstSpace
list index / appendO(1)O(1)*O(1) amortised—
list insert / delete at frontO(n)O(n)O(n)—
dict / set get, put, inO(1)O(1)O(n)O(n)
deque append / popleftO(1)O(1)O(1)O(n)
heapq push / popO(log n)O(log n)O(log n)O(n)
sorted() / list.sort()O(n)O(n log n)O(n log n)O(n)

*append is amortised O(1): occasional resizes cost O(n) but average out. These costs are the vocabulary the rest of the course is written in.

Python implementation

Production-quality code with type hints, validation, and docstrings.

A TreeNode/ListNode starter kit (the classes interviews hand you)
from __future__ import annotationsfrom typing import Optionalclass ListNode:    """Singly linked list node, as used in LeetCode-style problems."""    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):        self.val = val        self.next = nextclass TreeNode:    """Binary tree node."""    def __init__(        self,        val: int = 0,

What interviewers expect you to know

Definitions you must be able to state

  • Mutable vs immutable: lists/dicts/sets mutate in place; ints/strings/tuples never do — 'modifying' a string builds a new one in O(n).
  • Hashable: an object with a stable hash — required for dict keys and set members.
  • Amortised cost: expensive occasional operations (list resize) averaged over many cheap ones.

Common follow-up questions

  • "Why is list.pop(0) slow?" — every remaining element shifts left; deque.popleft() is O(1) because it's a linked structure.
  • "What happens with a mutable default argument?" — it is created once at definition time and shared across calls.
  • "How would you make a max-heap with heapq?" — push negated values, or push (−priority, item) tuples.

How to talk about it in interviews

  • Name the container and its cost as you reach for it: 'I'll use a set here so membership checks are O(1).'
  • When constraints allow ~10⁵ operations, say out loud that an O(n²) approach (~10¹⁰ steps) won't run in time — this shows you connect constraints to tools.

Common mistakes

Using a list where a set/dict belongs

`if x in my_list` is O(n). Inside a loop that's O(n²) — the single most common accidental slowdown in Python interviews.

Mutable default arguments

def solve(nums, memo={}) shares one dict across every call of the function — including separate test cases. Use memo=None and create inside.

String concatenation in a loop

s += ch copies the whole string each time: O(n²) total. Collect parts in a list and ''.join(parts) once.

Shadowing built-ins

Naming variables list, dict, sum, or max silently breaks later calls to those functions.

Confusing is with ==

is compares identity, == compares value. Small-int caching makes `a is b` 'work' in tests and fail in production.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

No practice problems are configured for this topic yet.

Browse the full problem atlas →

Topic quiz

5 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Code output1. What does this print?
    def add(item, bag=[]):    bag.append(item)    return bagprint(add(1))print(add(2))
  2. Complexity2. What is the average-case cost of `x in s` when s is a set, and when s is a list?
  3. Concept3. You need a queue with fast removals from the front. Which container is correct?
  4. Code output4. What does `print(-7 % 5)` output in Python?
  5. Scenario5. You must process a 10 GB log file line by line on a laptop with 8 GB RAM. Which Python feature makes this feasible?
0 of 5 answered

Frequently asked questions

Do I need to master all of Python before starting DSA?

No. You need the subset on this page: collections, functions, classes, iteration, and basic math operators. Everything else can be learned as it appears.

Is Python too slow for coding interviews?

No — interviewers evaluate algorithmic complexity, not language speed, and Python's concise syntax is an advantage under time pressure. Only competitive programming with strict time limits sometimes favours C++.

Should I use type hints in interviews?

They're optional but cheap signal: `def two_sum(nums: list[int], target: int) -> list[int]` reads clearly and shows engineering habits. Don't let them slow you down.

Summary & cheat sheet

Key takeaways

  • list = dynamic array, dict/set = hash table, deque = O(1) both ends, heapq = min-heap — pick by operation cost.
  • The call stack explains recursion: one frame per active call, ~1000-frame default limit.
  • Generators produce values lazily — constant memory for streaming work.
  • log₂ n counts halvings; % wraps into a range; ^ finds differing bits.

Formulas & cheat sheet

  • log₂(n) = number of times n can be halved before reaching 1
  • (a + b) % m wraps sums into 0..m−1 (Python result is always non-negative for m > 0)
  • n & (n − 1) clears the lowest set bit

Interview checklist

  • I can state the cost of every list/dict/set/deque/heapq operation.
  • I can write ListNode and TreeNode classes from memory.
  • I can explain mutable default arguments and why they bite.
  • I can explain what yield does to a function's execution.