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ón Tiempo 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) scanSalida
[9, 3, 1, 4, 1] 1 9 True
Hacer pop del principio dentro de un bucle cuesta O(n²) en total: usa un
deque.- Big-O
- Array dinámico
- 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ón Tiempo 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 / items O(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 orderSalida
0 True {'b': 2, 'a': 1, 'c': [3]} ['b', 'a', 'c']d[k]con una clave que no existe lanza KeyError;getysetdefaultno.- 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ón Tiempo add, remove, x in s O(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 esset().- 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ón Tiempo append, appendleft O(1) pop, popleft O(1) q[i] en el medio O(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)
maxlendescarta por el otro extremo: una ventana de tamaño fijo sin esfuerzo.- Big-O
- Cola / deque
- 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ón Tiempo heapify(a) O(n) heappush, heappop O(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.- Big-O
- Heap binario
- 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ón Tiempo 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ón Tiempo d[k] (lo crea si no existe) O(1) avg todo lo demás as 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']} [] 3Con solo leer
groups["zzz"]se insertó. Comprueba la pertenencia conin.- 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ón Tiempo move_to_end(k) O(1) popitem(last=False) O(1) todo lo demás as 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 IndexErrorSalida
[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)) # generatorSalida
[64, 36] {3: 0, 8: 2, 1: 1, 6: 0} [0, 1, 2] [3, 8, 0, 6] 18El
ifque filtra va después del bucle; la eleccióna if c else bva 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.
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: ahoraaes 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.joines 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.finddevuelve -1;indexlanza 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
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}zipse 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.pairwisehace 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)] 120n! 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=0da 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:
3aparece dos veces porque la lista se ordenó por nombre, no por longitud. Ordena por la misma clave con la que agrupas.
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 casesSalida
23416728348467685 CacheInfo(hits=78, misses=81, maxsize=None, currsize=81)
81 llamadas distintas en lugar de unas 8 × 10¹⁶.
@functools.cachees 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 tupleSalida
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) # ceilSalida
3 -4 -3 1 (-4, 1) 4 4
-7 // 2es -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 powSalida
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.infes 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
roundredondea las mitades al par, y 2.675 en realidad es 2.67499…./siempre devuelve un float.
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 bitsSalida
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 0Salida
[1, 2, 4, 8, 16] 0b1001 1 0b1000
En Python
&tiene más precedencia que==(al revés que en C y Java), así quen & (n - 1) == 0funciona. 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 >> 1es -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 isSalida
True False [1, 2, 3] True True
ispregunta “¿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)ya.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
- Práctica
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
- Práctica
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
- Práctica
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
- Práctica
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
- Práctica
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 dea[i:j]sin casos especiales.- Lección
- Sumas de prefijos · Arrays
- Práctica
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
- Práctica
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
- Práctica
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
findes iterativo a propósito: uno recursivo choca con el límite de recursión en una cadena larga.- Lección
- Fundamentos de conjuntos disjuntos · Union-Find
- Práctica
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
- Práctica
bytepatterns.com/cheatsheets/python: cada fila enlaza ahí a una lección animada.