Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 225 ยท Getting Started

Python You Need for DSA

Python review for DSA: lists, dicts, sets, slicing, comprehensions, classes, recursion, generators, sorted with key, and the traps that bite in interviews.

You do not need to be a Python expert to learn data structures, but a handful of features show up in almost every lesson. This page is a fast tour of exactly those, with the traps that cost beginners hours: shared mutable lists, shallow copies, and mutable default arguments.

If something here is brand new, follow the link to the full Python tutorial and come back. If it is all familiar, skim the traps and move on to Memory and Data Layout.

Lists, tuples, dicts and sets

These four built-ins are the raw material for almost every solution.

Type Looks like Ordered Mutable Duplicates Typical use
list [3, 1, 3] yes yes yes sequence you change
tuple (3, 1) yes no yes fixed record, dictionary key
dict {"a": 1} insertion order yes unique keys key to value lookup
set {3, 1} no yes no membership, removing duplicates
Python The four built-in containers

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.

Two habits matter for DSA. First, x in my_list scans the list, while x in my_set and key in my_dict jump straight to the answer; the lesson on hash tables explains how. Second, never print a set of strings and rely on its order, because it can differ between runs. Use sorted(...) first.

Indexing and slicing

Indexes start at 0. Negative indexes count from the end, so -1 is the last item. A slice a[start:stop:step] includes start and excludes stop, and it copies that part into a new list.

TEXT
index:    0    1    2    3    4
        +----+----+----+----+----+
a =     | 10 | 20 | 30 | 40 | 50 |
        +----+----+----+----+----+
negative: -5   -4   -3   -2   -1

a[1:4]  -> [20, 30, 40]
a[:2]   -> [10, 20]
a[-2:]  -> [40, 50]
a[::-1] -> [50, 40, 30, 20, 10]
Python Slicing and copying

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.

Because a slice copies, a[1:] costs time proportional to its length. Taking a slice inside a loop or a recursive call can quietly turn a fast algorithm into a slow one. Pass indexes (low, high) instead of slices when you care about speed. You will see this again in binary search.

Comprehensions

A comprehension builds a list, set or dict in one expression. They are short, and interviewers like them.

Python Comprehensions

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.

Functions, parameters and type hints

Functions take positional and keyword arguments, can have defaults, and can return several values as a tuple. Type hints do not change how code runs; they document what each function expects, which is helpful in a subject full of lists of lists and optional nodes.

Python
def clamp(value: int, low: int = 0, high: int = 100) -> int:
    return max(low, min(value, high))

def min_and_max(items: list[int]) -> tuple[int, int]:
    return min(items), max(items)

def find_index(items: list[int], target: int) -> int | None:
    for i, x in enumerate(items):
        if x == target:
            return i
    return None

int | None means "an int or None". We use it for "found or not found" results. Compare with is None, never == None.

Sorting with key

sorted(items) returns a new sorted list; items.sort() sorts in place and returns None. Both accept key=, a function that turns each item into the value to compare, and reverse=True. Sorting is stable: items that compare equal keep their original order.

Python sorted and key

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 sorting chapter, starting at Sorting Basics, builds these algorithms from scratch; here you only need to know sorted exists and costs about n log n steps.

Classes in one page

You will build nodes and structures as classes. The pieces you need: __init__ creates the object, attributes hold data, methods work on it, and self is the object itself.

Python A tiny node class

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.

Notice Node points at another Node. That chain of references is how linked lists work, and Linked Lists is built on exactly this class.

Recursion basics

A recursive function calls itself on a smaller problem. Every recursive function needs a base case that stops the calls and a recursive case that moves toward it. Python allows about 1,000 nested calls by default, so a function that recurses once per item breaks on long inputs; the full story is in Recursion.

Python Recursion with a base case

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.

Generators and iterators

A generator produces values one at a time instead of building a whole list. A function with yield becomes a generator. It is memory-friendly and perfect for "walk through a structure" code, such as tree traversals later.

Python A generator with yield

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.

Useful idioms

  • Swap without a temporary: a, b = b, a. List items too: a[i], a[j] = a[j], a[i].
  • Chained comparison: 0 <= i < len(a) is a bounds check.
  • Infinity as a starting minimum: best = float("inf").
  • Integer division and remainder: //, %, or divmod(17, 5) which gives (3, 2).
  • Counting: collections.Counter("banana") and collections.defaultdict(list) save a lot of if key in d code.
  • Truthiness: empty lists, strings, dicts and 0 are false, so if not items: tests for emptiness.
  • any(...) and all(...) test a condition across a whole iterable.
Python Idioms you will use constantly

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.

Traps that bite

Trap 1: shared rows

[[0] * 3] * 2 does not make two independent rows; it makes two references to the same row.

Trap 2: shallow copies

b = a[:] and a.copy() copy only the outer list. Inner lists are still shared. Use copy.deepcopy when you need a fully independent copy.

Trap 3: mutable default arguments

A default value is created once, when the function is defined. If it is a list, every call shares it.

Python The three classic traps

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 reason behind all three is the same: variables in Python hold references to objects, not the objects themselves. The next lesson, Memory and Data Layout, explains that model properly.

Modifying a list while looping over it (for x in a: a.remove(x)) skips items. Loop over a copy (for x in a[:]) or build a new list instead.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a[1:4] return for a = [10, 20, 30, 40, 50]?

    A slice includes the start index and excludes the stop index, so indexes 1, 2 and 3 give 20, 30 and 40.
  2. 2. After grid = [[0] * 3] * 2 and grid[0][0] = 1, what is grid?

    The multiplication repeats a reference to the same inner list, so both rows are one object and the change shows in both.
  3. 3. Why is slicing inside a recursive function often a performance problem?

    Each slice builds a new list. Copying on every call adds up to far more work than passing index bounds.
  4. 4. What does words.sort() return?

    list.sort changes the list in place and returns None. Use sorted(words) when you want a new list.
  5. 5. What is wrong with def add(x, bucket=[]):?

    Default values are evaluated once at definition time. Use None as the default and create a new list inside the function.

Summary

  • Know list, tuple, dict and set; use sets and dicts for fast membership and lookup, and sort sets before printing.
  • Slices a[start:stop:step] exclude stop and copy; avoid them in hot loops and recursion.
  • Comprehensions, enumerate, zip, sorted(key=...), divmod, Counter and defaultdict are the everyday tools.
  • Classes bundle data and methods; a node that points to another node is the seed of linked structures.
  • Recursion needs a base case, and Python's default depth limit is about 1,000 calls.
  • Beware shared inner lists, shallow copies and mutable default arguments. All come from variables being references.

Next: Memory and Data Layout, where you will learn what a reference really is and why contiguous memory is fast.