Saltar al contenido

Cheat sheet de Python para entrevistas

El Python que espera un entrevistador: costos de estructuras, ordenamiento, strings, itertools, trampas y diez plantillas, cada fragmento con su salida real.

Actualizado el 54 fragmentos, todos ejecutados10 plantillasSe imprime limpia: usa la impresión de tu navegador

Cada fragmento de esta página se ejecutó tal como aparece, y la salida de abajo es lo que imprimió Python. Escrito para Python 3.9 o posterior; las pocas líneas que necesitan una versión más nueva lo indican. Los costos son los de CPython: peor caso salvo que diga avg o amortized.

Estructuras de datos y sus costos

Los built-ins y los tipos de collections con los que se arma una respuesta. Cada tarjeta enlaza a la fila de la cheat sheet de Big-O de la estructura que hay debajo.

  • list

    Un array (arreglo) dinámico: rápido al final, lento al principio.

    list: costos de las operaciones
    OperaciónTiempo
    a[i], a[i] = x, len(a)O(1)
    append(x), pop()O(1) amortized
    insert(0, x), pop(0)O(n)
    x in a, a.index(x)O(n)
    a[i:j] (copia)O(k)
    sort(), sorted(a)O(n log n)
    a = [3, 1, 4]
    a.append(1)      # O(1) amortized
    a.insert(0, 9)   # O(n): shifts every item
    print(a)
    print(a.pop(), a.pop(0))  # O(1), O(n)
    print(4 in a)    # O(n) scan

    Salida

    [9, 3, 1, 4, 1]
    1 9
    True

    Hacer pop del principio dentro de un bucle cuesta O(n²) en total: usa un deque.

    Lección
    Fundamentos de arrays · Arrays
  • dict

    Un hash map. Las claves deben ser hashables; la iteración sigue el orden de inserción.

    dict: costos de las operaciones
    OperaciónTiempo
    d[k], d[k] = v, del d[k]O(1) avgO(n) worst
    k in d, d.get(k, default)O(1) avg
    recorrer claves / itemsO(n)
    d = {"b": 2}
    d["a"] = 1
    print(d.get("z", 0), "a" in d)
    d.setdefault("c", []).append(3)
    print(d)
    print(list(d))    # insertion order

    Salida

    0 True
    {'b': 2, 'a': 1, 'c': [3]}
    ['b', 'a', 'c']

    d[k] con una clave que no existe lanza KeyError; get y setdefault no.

    Lección
    Fundamentos de la tabla hash · Tablas hash
  • set

    “¿Ya vi esto?” en O(1). Sin orden y sin duplicados.

    set: costos de las operaciones
    OperaciónTiempo
    add, remove, x in sO(1) avg
    a | b, a & b, a - b (tamaños m, n)O(m + n)
    seen = {3, 1}
    seen.add(2)
    print(2 in seen, len(seen))
    a, b = {1, 2, 3}, {2, 3, 4}
    print(sorted(a & b), sorted(a | b))
    print(sorted(a - b), sorted(a ^ b))

    Salida

    True 3
    [2, 3] [1, 2, 3, 4]
    [1] [1, 4]

    Imprime un conjunto pasándolo por sorted: su orden no forma parte del lenguaje. {} es un diccionario vacío; un conjunto vacío es set().

    Lección
    Fundamentos de la tabla hash · Tablas hash
  • deque

    from collections import deque

    La cola: O(1) en ambos extremos. La estructura del BFS.

    deque: costos de las operaciones
    OperaciónTiempo
    append, appendleftO(1)
    pop, popleftO(1)
    q[i] en el medioO(n)
    from collections import deque
    q = deque([1, 2])
    q.appendleft(0)
    q.append(3)
    print(q.popleft(), q.pop(), q)
    last3 = deque(maxlen=3)
    for x in range(5):
        last3.append(x)
    print(last3)

    Salida

    0 3 deque([1, 2])
    deque([2, 3, 4], maxlen=3)

    maxlen descarta por el otro extremo: una ventana de tamaño fijo sin esfuerzo.

    Lección
    Fundamentos de la cola · Pilas y colas
  • heapq

    import heapq

    Un MIN-heap binario sobre una lista común. Para un max-heap, inserta los valores negados.

    heapq: costos de las operaciones
    OperaciónTiempo
    heapify(a)O(n)
    heappush, heappopO(log n)
    a[0] (ver el mínimo)O(1)
    nsmallest(k, a), nlargest(k, a)O(n log k)
    import heapq
    h = [5, 1, 8, 3]
    heapq.heapify(h)
    heapq.heappush(h, 0)
    print(heapq.heappop(h), h[0])
    print(heapq.nsmallest(2, [5, 1, 8, 3]))
    m = []                   # max-heap
    for x in [5, 1, 8]:
        heapq.heappush(m, -x)
    print(-m[0])

    Salida

    0 1
    [1, 3]
    8

    Inserta tuplas (priority, count, item) para que un empate nunca compare dos elementos.

    Lección
    Fundamentos del heap · Heaps
  • Counter

    from collections import Counter

    Un diccionario de conteos: frecuencias, anagramas, “los k más comunes”.

    Counter: costos de las operaciones
    OperaciónTiempo
    Counter(iterable)O(n)
    c[x] (0 si no existe)O(1) avg
    most_common(k)O(n log k)
    from collections import Counter
    c = Counter("banana")
    print(c)
    print(c["a"], c["z"])     # missing -> 0
    print(c.most_common(2))
    print(Counter("listen") == Counter("silent"))

    Salida

    Counter({'a': 3, 'n': 2, 'b': 1})
    3 0
    [('a', 3), ('n', 2)]
    True
    Lección
    Conteo de frecuencias · Tablas hash
  • defaultdict

    from collections import defaultdict

    Un diccionario que crea el valor que falta en la primera lectura: agrupar en una sola línea.

    defaultdict: costos de las operaciones
    OperaciónTiempo
    d[k] (lo crea si no existe)O(1) avg
    todo lo demásas dict
    from collections import defaultdict
    groups = defaultdict(list)
    for w in ["eat", "tea", "tan"]:
        groups["".join(sorted(w))].append(w)
    print(dict(groups))
    print(groups["zzz"], len(groups))

    Salida

    {'aet': ['eat', 'tea'], 'ant': ['tan']}
    [] 3

    Con solo leer groups["zzz"] se insertó. Comprueba la pertenencia con in.

    Lección
    Group Anagrams · Tablas hash
  • OrderedDict

    from collections import OrderedDict

    Un diccionario que se reordena en O(1): la caché LRU en pocas líneas.

    OrderedDict: costos de las operaciones
    OperaciónTiempo
    move_to_end(k)O(1)
    popitem(last=False)O(1)
    todo lo demásas dict
    from collections import OrderedDict
    lru = OrderedDict()
    for k in "abc":
        lru[k] = k.upper()
    lru.move_to_end("a")      # a is now newest
    lru.popitem(last=False)   # evict the oldest
    print(list(lru.items()))

    Salida

    [('c', 'C'), ('a', 'A')]

    Un diccionario común también conserva el orden de inserción (3.7+), pero no tiene move_to_end.

    Lección
    Caché LRU · Diseño de bajo nivel

Slices y comprensiones

a[start:stop:step] nunca lanza un error por un límite fuera de rango y siempre construye una lista nueva: O(k) de tiempo y memoria para k elementos. Una comprensión (comprehension) es el bucle idiomático que construye una lista, un diccionario o un conjunto; una expresión generadora no construye nada.

  • Slices

    a = [0, 1, 2, 3, 4, 5]
    print(a[1:4], a[-2:], a[:2])
    print(a[::2], a[::-1])
    print(a[10:], a[4:1])   # no IndexError

    Salida

    [1, 2, 3] [4, 5] [0, 1]
    [0, 2, 4] [5, 4, 3, 2, 1, 0]
    [] []
  • Un slice es una copia

    a = [1, 2, 3]
    b = a[:]          # new list, O(n)
    b.append(4)
    print(a, b)
    s = "interview"
    print(s[::-1], s[2:5])
    a[1:3] = [7]      # slice assignment
    print(a)

    Salida

    [1, 2, 3] [1, 2, 3, 4]
    weivretni ter
    [1, 7]

    La copia es superficial: las listas anidadas se comparten (ver Trampas comunes).

  • Comprensiones de listas, diccionarios y conjuntos

    nums = [3, 8, 1, 6]
    print([x * x for x in nums if x % 2 == 0])
    print({x: x % 3 for x in nums})
    print(sorted({x % 3 for x in nums}))
    print([x if x > 2 else 0 for x in nums])
    print(sum(x for x in nums))  # generator

    Salida

    [64, 36]
    {3: 0, 8: 2, 1: 1, 6: 0}
    [0, 1, 2]
    [3, 8, 0, 6]
    18

    El if que filtra va después del bucle; la elección a if c else b va antes.

  • Cuadrículas: construir, aplanar, transponer

    rows, cols = 2, 3
    grid = [[0] * cols for _ in range(rows)]
    grid[0][0] = 1
    print(grid)
    print([v for row in grid for v in row])
    print([list(c) for c in zip(*grid)])

    Salida

    [[1, 0, 0], [0, 0, 0]]
    [1, 0, 0, 0, 0, 0]
    [[1, 0], [0, 0], [0, 0]]

    Los bucles anidados se leen de izquierda a derecha, el externo primero: en el orden en que los escribirías.

LeccionesFundamentos de arraysInversión in-place

Ordenamiento

Timsort: O(n log n) en el peor caso, O(n) con datos que ya están ordenados, y ESTABLE: las claves iguales conservan su orden de entrada, y eso es lo que permite ordenar en varias pasadas. sorted() acepta cualquier iterable y devuelve una lista nueva; list.sort() ordena in-place y devuelve None.

  • sorted() vs .sort()

    a = [3, 1, 2]
    b = sorted(a)     # new list
    print(a, b)
    r = a.sort()      # in place
    print(a, r)
    print(sorted("cab"), sorted((3, 1)))

    Salida

    [3, 1, 2] [1, 2, 3]
    [1, 2, 3] None
    ['a', 'b', 'c'] [1, 3]

    a = a.sort() es el bug clásico: ahora a es None.

  • key= y reverse=

    words = ["kiwi", "fig", "banana", "apple"]
    print(sorted(words, key=len))
    print(sorted(words, key=len, reverse=True))
    print(max(words, key=len))

    Salida

    ['fig', 'kiwi', 'apple', 'banana']
    ['banana', 'apple', 'kiwi', 'fig']
    banana

    La clave se calcula una vez por elemento, no una vez por comparación.

  • Varias claves, en distinto sentido

    people = [("ana", 31), ("ben", 25),
              ("cy", 31)]
    # age descending, then name ascending
    key = lambda p: (-p[1], p[0])
    print(sorted(people, key=key))
    from operator import itemgetter
    print(sorted(people, key=itemgetter(1)))

    Salida

    [('ana', 31), ('cy', 31), ('ben', 25)]
    [('ben', 25), ('ana', 31), ('cy', 31)]

    Niega un número para invertir su sentido dentro de una clave de tupla; un string no se puede negar: en ese caso, ordena dos veces.

  • Estabilidad: ordena dos veces, primero por la clave secundaria

    rows = [("b", 2), ("a", 1), ("c", 2),
            ("d", 1)]
    print(sorted(rows, key=lambda r: r[1]))
    rows.sort(key=lambda r: r[0], reverse=True)
    rows.sort(key=lambda r: r[1])
    print(rows)

    Salida

    [('a', 1), ('d', 1), ('b', 2), ('c', 2)]
    [('d', 1), ('a', 1), ('c', 2), ('b', 2)]

    Los empates conservan el orden de entrada, así que la segunda pasada mantiene, dentro de cada número, el orden de la primera.

  • functools.cmp_to_key

    from functools import cmp_to_key
    def cmp(a, b):
        if a + b > b + a:
            return -1          # a goes first
        return 1 if a + b < b + a else 0
    nums = ["3", "30", "34", "5", "9"]
    nums.sort(key=cmp_to_key(cmp))
    print("".join(nums))

    Salida

    9534330

    Para un orden que ninguna clave puede expresar (“largest number”). Negativo significa que va primero a; positivo, que va primero b; 0, que son iguales.

LeccionesFundamentos del ordenamiento¿Qué ordenamiento usar y cuándo?

Strings

Los strings (cadenas) son inmutables: cada “cambio” construye uno nuevo. Arma la salida como una lista de partes y haz join una sola vez; convierte un string en lista cuando necesites editarlo in-place.

  • join vs. +=

    parts = ["a", "b", "c"]
    s = ""
    for p in parts:
        s += p        # may copy s every time
    print(s, "-".join(parts))
    print(",".join(str(n) for n in [1, 2, 3]))

    Salida

    abc a-b-c
    1,2,3

    += en un bucle puede ser O(n²): CPython a veces extiende in-place, pero nada lo garantiza. join es una sola pasada O(n).

  • f-stringsPython 3.8+

    name, score = "ana", 7 / 3
    print(f"{name!r} scored {score:.2f}")
    print(f"[{name:>6}] [{name:<6}] [{42:05d}]")
    print(f"{255:b} {255:x} {1234567:,}")
    x = 5
    print(f"{x=}, {x * 2=}")

    Salida

    'ana' scored 2.33
    [   ana] [ana   ] [00042]
    11111111 ff 1,234,567
    x=5, x * 2=10

    {x=} imprime la expresión y su valor: útil para depurar cuando ejecutas a mano en la pizarra.

  • Los métodos que espera un entrevistador

    s = "  Hello, World  "
    print(s.strip().lower())
    print("a,b,,c".split(","), "a b  c".split())
    print("abc123".isalnum(), "123".isdigit())
    print("level".startswith("le"))
    print("banana".count("an"))
    print("banana".find("x"), "banana".index("n"))
    print("a-b-c".replace("-", ""), "ab" * 3)

    Salida

    hello, world
    ['a', 'b', '', 'c'] ['a', 'b', 'c']
    True True
    True
    2
    -1 2
    abc ababab

    split() sin argumento divide por tramos de espacios en blanco y descarta las partes vacías. find devuelve -1; index lanza ValueError.

  • Caracteres como números; editar un string

    print(ord("a"), chr(ord("a") + 2))
    counts = [0] * 26
    for ch in "abca":
        counts[ord(ch) - ord("a")] += 1
    print(counts[:3])
    s = "cat"
    try:
        s[0] = "b"
    except TypeError:
        print("immutable")
    chars = list(s)
    chars[0] = "b"
    print("".join(chars))

    Salida

    97 c
    [2, 1, 1]
    immutable
    bat

LeccionesFundamentos de stringsInvertir palabras

Herramientas de iteración

Recorre valores, no índices. enumerate cuando también necesitas el índice, zip para recorrer varias secuencias a la vez e itertools para la combinatoria que de otro modo escribirías con recursión. Las funciones de itertools son perezosas (lazy): envuélvelas en list() para ver lo que producen.

  • enumerate y zip

    for i, ch in enumerate("ab", start=1):
        print(i, ch)
    names, ages = ["ana", "ben", "cy"], [31, 25]
    print(list(zip(names, ages)))  # shortest wins
    print(dict(zip(names, ages)))

    Salida

    1 a
    2 b
    [('ana', 31), ('ben', 25)]
    {'ana': 31, 'ben': 25}

    zip se detiene sin avisar en la entrada más corta. zip(..., strict=True) lanza un error en su lugar, pero solo desde 3.10.

  • Transponer y pares consecutivos

    m = [[1, 2, 3], [4, 5, 6]]
    print(list(zip(*m)))       # transpose
    a = [1, 4, 9, 16]
    print([y - x for x, y in zip(a, a[1:])])

    Salida

    [(1, 4), (2, 5), (3, 6)]
    [3, 5, 7]

    itertools.pairwise hace lo de la segunda línea desde 3.10; zip(a, a[1:]) funciona en todas las versiones.

  • product, permutations, combinations

    import itertools as it
    print(list(it.product("ab", repeat=2)))
    print(list(it.permutations([1, 2, 3], 2)))
    print(list(it.combinations([1, 2, 3], 2)))
    print(len(list(it.permutations(range(5)))))

    Salida

    [('a', 'a'), ('a', 'b'), ('b', 'a'), ('b', 'b')]
    [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
    [(1, 2), (1, 3), (2, 3)]
    120

    n! permutaciones y C(n, k) combinaciones: bien para n ≤ 10, nunca para n = 30.

  • accumulate: sumas, máximos y productos acumuladosPython 3.8+

    from itertools import accumulate
    import operator
    a = [3, 1, 4, 1, 5]
    print(list(accumulate(a)))
    print(list(accumulate(a, max)))
    print(list(accumulate(a, operator.mul)))
    print(list(accumulate(a, initial=0)))

    Salida

    [3, 4, 8, 9, 14]
    [3, 3, 4, 4, 5]
    [3, 3, 12, 12, 60]
    [0, 3, 4, 8, 9, 14]

    initial=0 da el array de sumas de prefijos con su cero inicial.

  • groupby: tramos de claves iguales

    from itertools import groupby
    s = "aaabccdd"
    print([(k, len(list(g)))
           for k, g in groupby(s)])
    words = ["bob", "amy", "bill", "al"]
    for k, g in groupby(sorted(words), key=len):
        print(k, list(g))

    Salida

    [('a', 3), ('b', 1), ('c', 2), ('d', 2)]
    2 ['al']
    3 ['amy']
    4 ['bill']
    3 ['bob']

    Solo agrupa elementos ADYACENTES: 3 aparece dos veces porque la lista se ordenó por nombre, no por longitud. Ordena por la misma clave con la que agrupas.

LeccionesPermutaciones vs. combinacionesSubconjuntos

Límites de recursión y memoización

CPython no optimiza las llamadas de cola y corta una recursión a unos mil stack frames (marcos de pila) con un RecursionError. Un DFS sobre un camino de 10⁵ nodos, o una DP memoizada de 10⁴ niveles, necesita una pila explícita o una tabla bottom-up (de abajo hacia arriba), no un límite más alto.

  • El límite, alcanzado

    def depth(n):
        return 0 if n == 0 else 1 + depth(n - 1)
    print(depth(500))
    try:
        depth(100_000)
    except RecursionError:
        print("RecursionError")

    Salida

    500
    RecursionError

    El valor por defecto en CPython es de 1000 frames; el número exacto es un detalle de implementación, así que no lo imprimas en una respuesta.

  • sys.setrecursionlimit, con cuidado

    import sys
    sys.setrecursionlimit(3_000)
    def depth(n):
        return 0 if n == 0 else 1 + depth(n - 1)
    print(depth(2_000))

    Salida

    2000

    Sube el contador de Python, no la pila de C que hay debajo. En la máquina Windows donde se ejecutó esta cheat sheet, la misma función con 3000 niveles de profundidad mató el proceso con un desbordamiento de pila (stack overflow), sin ningún RecursionError que atrapar. Dilo y ofrece la versión iterativa.

  • functools.lru_cache

    from functools import lru_cache
    @lru_cache(maxsize=None)
    def fib(n):
        if n < 2:
            return n
        return fib(n - 1) + fib(n - 2)
    print(fib(80))
    print(fib.cache_info())
    fib.cache_clear()   # between test cases

    Salida

    23416728348467685
    CacheInfo(hits=78, misses=81, maxsize=None, currsize=81)

    81 llamadas distintas en lugar de unas 8 × 10¹⁶. @functools.cache es lo mismo, escrito más corto, desde 3.9.

  • Los argumentos en caché deben ser hashables

    from functools import lru_cache
    @lru_cache(maxsize=None)
    def total(items):
        return sum(items)
    try:
        total([1, 2])
    except TypeError:
        print("list: unhashable")
    print(total((1, 2)))   # pass a tuple

    Salida

    list: unhashable
    3

    Convierte las listas en tuplas (o en índices) antes de que lleguen a una función con caché.

LeccionesFundamentos de la recursiónLa pila de llamadasTu propia pila de llamadasLlamadas de cola y bucles

Trampas con enteros y floats

// y % de Python redondean hacia menos infinito, no hacia cero como en C, Java y JavaScript. Los enteros nunca se desbordan, y los floats son doubles IEEE: compáralos con una tolerancia.

  • // y % con negativos

    print(7 // 2, -7 // 2)
    print(int(-7 / 2), -7 % 2)
    print(divmod(-7, 2))
    a, b = 7, 2
    print(-(-a // b), (a + b - 1) // b)  # ceil

    Salida

    3 -4
    -3 1
    (-4, 1)
    4 4

    -7 // 2 es -4 (piso); int(-7 / 2) es -3 (trunca, pasando por un float: falla con números grandes). Las formas idiomáticas de calcular el techo se quedan en enteros.

  • Los enteros nunca se desbordan

    print(2 ** 100)
    print(10 ** 18 + 1 == 10 ** 18)
    MOD = 10 ** 9 + 7
    print(2 ** 64 % MOD)
    print(pow(3, 200, MOD))     # fast modular pow

    Salida

    1267650600228229401496703205376
    False
    582344008
    136318165

    Cuando un problema dice “devuélvelo módulo 10⁹+7”, reduce igual sobre la marcha: la aritmética con enteros grandes no es O(1).

  • math.inf como centinela

    import math
    best = math.inf
    for x in [5, 3, 8]:
        best = min(best, x)
    print(best, -math.inf < -10 ** 100)
    print(float("inf") == math.inf)
    nan = math.inf - math.inf
    print(nan, nan == nan)

    Salida

    3 True
    True
    nan False

    math.inf es un float: devuelve -1 (o un int) cuando la respuesta tiene que ser un entero.

  • Igualdad y redondeo de floats

    import math
    print(0.1 + 0.2 == 0.3, 0.1 + 0.2)
    print(math.isclose(0.1 + 0.2, 0.3))
    print(round(2.5), round(3.5), round(2.675, 2))
    print(int("42") + int(3.9), 7 / 7)

    Salida

    False 0.30000000000000004
    True
    2 4 2.67
    45 1.0

    round redondea las mitades al par, y 2.675 en realidad es 2.67499…. / siempre devuelve un float.

LeccionesAritmética modularExponenciación rápida

Trucos con bits

Los enteros de Python no tienen un ancho fijo, así que ~x es -x - 1 y no hay un desbordamiento con el que contar. Cuando un problema asume enteros de 32 bits, aplica tú la máscara 0xFFFFFFFF.

  • Los trucos básicos

    x = 0b10110
    print(bin(x), x & 1, x >> 1, x << 2)
    print(bin(x & (x - 1)))  # drop lowest 1
    print(x & -x)             # lowest set bit
    print(bin(x).count("1"))  # set bits

    Salida

    0b10110 0 11 88
    0b10100
    2
    3

    x.bit_count() cuenta los bits encendidos desde 3.10; bin(x).count("1") funciona en todas las versiones.

  • Potencias de dos y máscaras de bits

    def is_pow2(n):
        return n > 0 and n & (n - 1) == 0
    print([n for n in range(1, 20) if is_pow2(n)])
    mask = 0
    for i in [0, 3]:
        mask |= 1 << i           # set bit i
    print(bin(mask), (mask >> 3) & 1)
    print(bin(mask & ~1))        # clear bit 0

    Salida

    [1, 2, 4, 8, 16]
    0b1001 1
    0b1000

    En Python & tiene más precedencia que == (al revés que en C y Java), así que n & (n - 1) == 0 funciona. Pon paréntesis igual: quien lee puede estar pensando en C.

  • XOR y todos los subconjuntos

    from functools import reduce
    from operator import xor
    print(reduce(xor, [4, 1, 2, 1, 2]))
    items = ["a", "b", "c"]
    n = len(items)
    subsets = []
    for m in range(1 << n):
        picked = [items[i] for i in range(n)
                  if m >> i & 1]
        subsets.append("".join(picked))
    print(subsets)

    Salida

    4
    ['', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']

    x ^ x = 0 cancela cada par. Las máscaras 0 … 2ⁿ−1 son los 2ⁿ subconjuntos.

  • Números negativos y vistas de 32 bits

    print(~5, -5 >> 1)
    print(bin(-5 & 0xFFFFFFFF))
    print((5).bit_length(), (255).bit_length())

    Salida

    -6 -3
    0b11111111111111111111111111111011
    3 8

    -5 >> 1 es -3: el desplazamiento a la derecha redondea hacia abajo, como //.

LeccionesBinario y operaciones a nivel de bitsMáscaras y potencias de dosTrucos con XORLa máscara de bits como conjunto

Trampas comunes

Los bugs que busca un entrevistador de Python. Cada uno imprime algo sorprendente; la solución está en las líneas de abajo.

  • Argumentos por defecto mutables

    def add(x, into=[]):     # one list, shared
        into.append(x)
        return into
    print(add(1), add(2))
    def add_fixed(x, into=None):
        into = [] if into is None else into
        into.append(x)
        return into
    print(add_fixed(1), add_fixed(2))

    Salida

    [1, 2] [1, 2]
    [1] [2]

    El valor por defecto se evalúa una sola vez, cuando se ejecuta def. Usa None y crea la lista adentro.

  • Closures y enlace tardío

    fs = [lambda: i for i in range(3)]
    print([f() for f in fs])  # all see last i
    fs = [lambda i=i: i for i in range(3)]
    print([f() for f in fs])

    Salida

    [2, 2, 2]
    [0, 1, 2]

    Un closure lee la variable cuando se lo LLAMA. Fija el valor actual como argumento por defecto.

  • is vs. ==

    a = [1, 2]
    b = [1, 2]
    print(a == b, a is b)  # equal, not same
    c = a
    c.append(3)
    print(a, a is c)
    x = None
    print(x is None)        # the right use of is

    Salida

    True False
    [1, 2, 3] True
    True

    is pregunta “¿es el mismo objeto?”. Puede parecer correcto con ints pequeños y strings cortos solo porque CPython los guarda en caché: nunca compares valores con él.

  • Copias superficiales y [[0] * n] * m

    import copy
    grid = [[0] * 2] * 2     # two refs, ONE row
    grid[0][0] = 1
    print(grid)
    a = [[1], [2]]
    b = a[:]         # = list(a) = a.copy()
    c = copy.deepcopy(a)
    a[0].append(9)
    print(b, c)

    Salida

    [[1, 0], [1, 0]]
    [[1, 9], [2]] [[1], [2]]

    Construye las cuadrículas con una comprensión. a[:], list(a) y a.copy() solo copian la lista externa.

  • El orden de un dict está garantizado; el de un set, no

    d = {}
    for k in ["b", "c", "a"]:
        d[k] = True
    print(list(d))          # insertion order
    d.pop("c")
    d["c"] = 1              # now last
    print(list(d))
    print(sorted({"b", "c", "a"}))

    Salida

    ['b', 'c', 'a']
    ['b', 'a', 'c']
    ['a', 'b', 'c']

    El orden de inserción forma parte del lenguaje desde 3.7. Actualizar una clave existente conserva su lugar; borrarla y volver a agregarla la mueve al final.

  • Modificar un dict mientras lo recorres

    d = {"a": 1, "b": 2}
    try:
        for k in d:
            del d[k]
    except RuntimeError:
        print("RuntimeError")
    d = {"a": 1, "b": 2}
    for k in list(d):       # loop over a copy
        del d[k]
    print(d)

    Salida

    RuntimeError
    {}

    Una lista no lanza un error: se salta elementos sin avisar. Recorre una copia o construye una colección nueva.

Las 10 plantillas de entrevista

Los esqueletos sobre los que se arma la mayoría de las respuestas, en Python idiomático, cada uno con su lección y un problema para practicarlo. La cheat sheet de patrones de entrevista tiene las señales que te dicen cuál pide un problema.

  • Dos punteros

    Un array ordenado y un par, una partición o un palíndromo que se decide desde ambos extremos.

    Costo: O(n) de tiempo, O(1) de espacio

    def pair_sum(a, target):    # a is sorted
        i, j = 0, len(a) - 1
        while i < j:
            s = a[i] + a[j]
            if s == target:
                return i, j
            if s < target:
                i += 1
            else:
                j -= 1
        return None
    print(pair_sum([1, 3, 4, 6, 9], 10))

    Salida

    (0, 4)
    Lección
    Dos punteros · Arrays
  • Ventana deslizante

    La respuesta es un tramo contiguo, y mover uno de sus extremos actualiza el estado con poco costo.

    Costo: O(n) de tiempo, O(k) de espacio

    def longest_unique(s):
        last = {}
        start = best = 0
        for i, ch in enumerate(s):
            if last.get(ch, -1) >= start:
                start = last[ch] + 1
            last[ch] = i
            best = max(best, i - start + 1)
        return best
    print(longest_unique("abcabcbb"))

    Salida

    3
    Lección
    Ventana deslizante · Arrays
  • BFS con un deque

    La menor cantidad de pasos en un grafo o una cuadrícula sin pesos; nivel por nivel.

    Costo: O(V + E) de tiempo, O(V) de espacio

    from collections import deque
    def bfs(graph, src):
        dist = {src: 0}
        q = deque([src])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if v not in dist:  # on push
                    dist[v] = dist[u] + 1
                    q.append(v)
        return dist
    g = {1: [2, 3], 2: [4], 3: [4], 4: []}
    print(bfs(g, 1))

    Salida

    {1: 0, 2: 1, 3: 1, 4: 2}

    list.pop(0) haría esto O(V²). Marca un nodo cuando entra en la cola, no cuando sale.

    Lección
    Búsqueda en anchura · Grafos
  • DFS, recursivo e iterativo

    Alcanzar todo lo conectado: flood fill, islas, detección de ciclos, caminos.

    Costo: O(V + E) de tiempo, O(V) de espacio

    g = {1: [2, 3], 2: [4], 3: [4], 4: []}
    def dfs(u, seen, order):
        seen.add(u)
        order.append(u)
        for v in g[u]:
            if v not in seen:
                dfs(v, seen, order)
        return order
    print(dfs(1, set(), []))
    def dfs_iter(src):   # no depth limit
        seen, order, stack = set(), [], [src]
        while stack:
            u = stack.pop()
            if u in seen:
                continue
            seen.add(u)
            order.append(u)
            stack.extend(reversed(g[u]))
        return order
    print(dfs_iter(1))

    Salida

    [1, 2, 4, 3]
    [1, 2, 4, 3]

    Apilar los vecinos en orden inverso hace que la pila los visite en el mismo orden que la versión recursiva.

    Lección
    Búsqueda en profundidad · Grafos
  • Búsqueda binaria con bisect

    Una lista ordenada: posición de inserción, primera/última aparición, conteo en un rango.

    Costo: O(log n) por búsqueda

    from bisect import bisect_left, bisect_right
    from bisect import insort
    a = [1, 2, 4, 4, 4, 7]
    print(bisect_left(a, 4), bisect_right(a, 4))
    print(bisect_right(a, 4) - bisect_left(a, 4))
    i = bisect_left(a, 5)
    print(i < len(a) and a[i] == 5)  # found?
    insort(a, 5)                # O(n) insert
    print(a)

    Salida

    2 5
    3
    False
    [1, 2, 4, 4, 4, 5, 7]

    bisect_left: primer índice con a[i] ≥ x; bisect_right: primero con a[i] > x. El argumento key= requiere 3.10.

    Lección
    Búsqueda binaria · Búsqueda
  • Sumas de prefijos

    Muchas sumas por rango sobre un mismo array, o subarrays que suman k.

    Costo: O(n) para construir, O(1) por consulta

    from itertools import accumulate
    a = [2, 4, 1, 3]
    pre = [0, *accumulate(a)]  # sum(a[:i])
    print(pre, pre[3] - pre[1])  # sum(a[1:3])
    def count_k(nums, k):  # sums equal to k
        seen = {0: 1}
        total = count = 0
        for x in nums:
            total += x
            count += seen.get(total - k, 0)
            seen[total] = seen.get(total, 0) + 1
        return count
    print(count_k([1, 2, 1, -1, 2], 3))

    Salida

    [0, 2, 6, 7, 10] 5
    3

    El 0 inicial es lo que hace que pre[j] - pre[i] sea la suma de a[i:j] sin casos especiales.

    Lección
    Sumas de prefijos · Arrays
  • Pila monótona

    Siguiente elemento mayor / menor, spans, el rectángulo más grande.

    Costo: O(n) de tiempo, O(n) de espacio

    def next_greater(a):
        ans = [-1] * len(a)
        stack = []   # indices, values falling
        for i, x in enumerate(a):
            while stack and a[stack[-1]] < x:
                ans[stack.pop()] = x
            stack.append(i)
        return ans
    print(next_greater([2, 1, 2, 4, 3]))

    Salida

    [4, 2, 4, -1, -1]

    Cada índice entra en la pila una vez y sale como mucho una vez: O(n) a pesar del while interno.

    Lección
    Pila monótona · Pilas y colas
  • Top-k con un heap

    Los k mayores, menores, más cercanos o más frecuentes de n elementos.

    Costo: O(n log k) de tiempo, O(k) de espacio

    import heapq
    def top_k(nums, k):
        h = []            # min-heap, <= k
        for x in nums:
            heapq.heappush(h, x)
            if len(h) > k:
                heapq.heappop(h)
        return sorted(h, reverse=True)
    print(top_k([5, 1, 9, 3, 7, 2], 3))
    print(heapq.nlargest(3, [5, 1, 9, 3, 7, 2]))

    Salida

    [9, 7, 5]
    [9, 7, 5]

    Para quedarte con los k MAYORES, saca elementos de un MIN-heap: su tope es el más débil de los k que guardas.

    Lección
    Los top-k elementos · Heaps
  • Union-find

    Componentes conexos que solo se fusionan; detección de ciclos en un grafo no dirigido.

    Costo: ≈ O(1) por operación, O(n) de espacio

    parent = list(range(5))
    size = [1] * 5
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # halve
            x = parent[x]
        return x
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return False       # already joined
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        size[ra] += size[rb]
        return True
    print(union(0, 1), union(1, 2), union(0, 2))
    print(len({find(x) for x in range(5)}))

    Salida

    True True False
    3

    find es iterativo a propósito: uno recursivo choca con el límite de recursión en una cadena larga.

  • DP con memoizaciónPython 3.9+

    Subproblemas superpuestos: escribe la recurrencia y después guárdala en caché.

    Costo: O(estados × opciones) de tiempo, O(estados) de espacio

    from functools import cache
    coins = (1, 2, 5)
    @cache
    def fewest(amount):
        if amount == 0:
            return 0
        best = float("inf")
        for c in coins:
            if c <= amount:
                best = min(best,
                           fewest(amount - c) + 1)
        return best
    print(fewest(11), fewest(3))

    Salida

    3 2

    La profundidad es el monto: más allá de unos pocos miles, pásala a bottom-up (ver Límites de recursión).

    Lección
    Memoización · Recursión

bytepatterns.com/cheatsheets/python: cada fila enlaza ahí a una lección animada.