Cheat sheet de Python para entrevistas
O Python que o entrevistador espera: custo das estruturas, ordenação, strings, itertools, armadilhas e dez templates, com a saída real de cada trecho.
Atualizado em 54 trechos, todos executados10 templatesPronta para imprimir — use a impressão do seu navegador
Cada trecho desta página foi executado exatamente como está impresso, e a saída abaixo dele é o que o Python imprimiu. Escrito para Python 3.9 ou superior; as poucas linhas que exigem uma versão mais nova avisam. Os custos são os do CPython: pior caso, a menos que marcado como avg (médio) ou amortized (amortizado).
Estruturas de dados e seus custos
Os built-ins e os tipos de collections com que uma resposta é construída. Cada card leva à linha da cheat sheet de Big-O da estrutura por trás dele.
list
Um array dinâmico: rápido no fim, lento no início.
list: custo das operações Operação Tempo 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) scanSaída
[9, 3, 1, 4, 1] 1 9 True
Tirar do início dentro de um loop custa O(n²) no total — use um
deque.- Big-O
- Array dinâmico
- Aula
- O básico de arrays · Arrays
dict
Um hash map. As chaves precisam ser hashable; a iteração segue a ordem de inserção.
dict: custo das operações Operação Tempo d[k], d[k] = v, del d[k] O(1) avgO(n) worst k in d, d.get(k, default) O(1) avg percorrer chaves / itens 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 orderSaída
0 True {'b': 2, 'a': 1, 'c': [3]} ['b', 'a', 'c']d[k]com uma chave ausente lança KeyError;getesetdefaultnão.- Aula
- O básico de tabelas hash · Tabelas hash
set
“Já vi isso?” em O(1). Sem ordem, sem duplicatas.
set: custo das operações Operação Tempo add, remove, x in s O(1) avg a | b, a & b, a - b (tamanhos 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))Saída
True 3 [2, 3] [1, 2, 3, 4] [1] [1, 4]
Imprima um conjunto passando por
sorted— a ordem dele não faz parte da linguagem.{}é um dict vazio; um conjunto vazio éset().- Aula
- O básico de tabelas hash · Tabelas hash
deque
from collections import deque
A fila: O(1) nas duas pontas. A estrutura da BFS.
deque: custo das operações Operação Tempo append, appendleft O(1) pop, popleft O(1) q[i] no meio 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)Saída
0 3 deque([1, 2]) deque([2, 3, 4], maxlen=3)
maxlendescarta pela outra ponta: uma janela de tamanho fixo de graça.- Big-O
- Fila / deque
- Aula
- O básico de filas · Pilhas e filas
heapq
import heapq
Um MIN-heap binário sobre uma lista comum. Para um max-heap, insira os valores negativos.
heapq: custo das operações Operação Tempo heapify(a) O(n) heappush, heappop O(log n) a[0] (ver o 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])Saída
0 1 [1, 3] 8
Insira tuplas
(priority, count, item)para que um empate nunca compare dois itens.- Big-O
- Heap binário
- Aula
- O básico de heaps · Heaps
Counter
from collections import Counter
Um dict de contagens: frequências, anagramas, “top k mais comuns”.
Counter: custo das operações Operação Tempo Counter(iterable) O(n) c[x] (0 se ausente) 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"))Saída
Counter({'a': 3, 'n': 2, 'b': 1}) 3 0 [('a', 3), ('n', 2)] True- Aula
- Contagem de frequência · Tabelas hash
defaultdict
from collections import defaultdict
Um dict que cria o valor ausente na primeira leitura — agrupamento em uma linha.
defaultdict: custo das operações Operação Tempo d[k] (cria se ausente) O(1) avg todo o resto 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))Saída
{'aet': ['eat', 'tea'], 'ant': ['tan']} [] 3Só de ler
groups["zzz"], a chave foi inserida. Teste a presença comin.- Aula
- Group Anagrams · Tabelas hash
OrderedDict
from collections import OrderedDict
Um dict com reordenação em O(1): o cache LRU em poucas linhas.
OrderedDict: custo das operações Operação Tempo move_to_end(k) O(1) popitem(last=False) O(1) todo o resto 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()))Saída
[('c', 'C'), ('a', 'A')]Um dict comum também mantém a ordem de inserção (3.7+), mas não tem
move_to_end.- Aula
- Cache LRU · Low-level design
Fatiamento e comprehensions
a[start:stop:step] nunca lança erro com um limite fora do intervalo e sempre cria uma lista nova — O(k) de tempo e memória para k itens. Uma comprehension é o loop idiomático que cria uma lista, um dict ou um set; uma expressão geradora (generator expression) não cria nada.
Fatias
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 IndexErrorSaída
[1, 2, 3] [4, 5] [0, 1] [0, 2, 4] [5, 4, 3, 2, 1, 0] [] []
Uma fatia é uma cópia
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)Saída
[1, 2, 3] [1, 2, 3, 4] weivretni ter [1, 7]
A cópia é rasa: listas aninhadas são compartilhadas (veja Armadilhas comuns).
Comprehensions de lista, dict e set
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)) # generatorSaída
[64, 36] {3: 0, 8: 2, 1: 1, 6: 0} [0, 1, 2] [3, 8, 0, 6] 18O filtro
ifvai depois do loop; a escolhaa if c else bvai antes dele.Grids: montar, achatar, transpor
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)])Saída
[[1, 0, 0], [0, 0, 0]] [1, 0, 0, 0, 0, 0] [[1, 0], [0, 0], [0, 0]]
Loops aninhados são lidos da esquerda para a direita, o externo primeiro — a ordem em que você os escreveria.
Ordenação
Timsort: O(n log n) no pior caso, O(n) em dados que já estão ordenados, e ESTÁVEL — chaves iguais mantêm a ordem da entrada, e é isso que faz ordenações em várias passadas funcionarem. sorted() aceita qualquer iterável e retorna uma lista nova; list.sort() ordena in-place e retorna 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)))Saída
[3, 1, 2] [1, 2, 3] [1, 2, 3] None ['a', 'b', 'c'] [1, 3]
a = a.sort()é o bug clássico: agoraaé None.key= e reverse=
words = ["kiwi", "fig", "banana", "apple"] print(sorted(words, key=len)) print(sorted(words, key=len, reverse=True)) print(max(words, key=len))Saída
['fig', 'kiwi', 'apple', 'banana'] ['banana', 'apple', 'kiwi', 'fig'] banana
A chave é calculada uma vez por item, não uma vez por comparação.
Várias chaves, direções mistas
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)))Saída
[('ana', 31), ('cy', 31), ('ben', 25)] [('ben', 25), ('ana', 31), ('cy', 31)]Troque o sinal de um número para inverter a direção dele dentro de uma chave em tupla; strings não têm sinal — ordene duas vezes no lugar disso.
Estabilidade: ordene duas vezes, a chave secundária primeiro
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)Saída
[('a', 1), ('d', 1), ('b', 2), ('c', 2)] [('d', 1), ('a', 1), ('c', 2), ('b', 2)]Empates mantêm a ordem da entrada, então a segunda passada preserva a ordem da primeira dentro de cada número.
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))Saída
9534330
Para uma ordem que nenhuma chave consegue expressar (“largest number”). Negativo significa a primeiro, positivo b primeiro, 0 iguais.
Strings
Strings são imutáveis: toda “mudança” cria uma nova. Monte a saída como uma lista de pedaços e faça join uma vez só; transforme a string em lista quando precisar editá-la 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]))Saída
abc a-b-c 1,2,3
+=em um loop pode ser O(n²): o CPython às vezes estende in-place, mas nada garante isso.joiné uma única passada 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=}")Saída
'ana' scored 2.33 [ ana] [ana ] [00042] 11111111 ff 1,234,567 x=5, x * 2=10
{x=}imprime a expressão e o valor dela — útil para depurar quando você executa o código no quadro.Os métodos que o entrevistador espera
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)Saída
hello, world ['a', 'b', '', 'c'] ['a', 'b', 'c'] True True True 2 -1 2 abc ababab
split()sem argumento divide em sequências de espaços em branco e descarta pedaços vazios.findretorna -1;indexlança ValueError.Caracteres como números; editar uma 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))Saída
97 c [2, 1, 1] immutable bat
Ferramentas de iteração
Percorra valores, não índices. enumerate quando você também precisa do índice, zip para percorrer várias sequências juntas e itertools para a combinatória que você escreveria como recursão. As funções do itertools são preguiçosas (lazy): envolva-as em list() para ver o resultado.
enumerate e 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)))Saída
1 a 2 b [('ana', 31), ('ben', 25)] {'ana': 31, 'ben': 25}zippara em silêncio na entrada mais curta.zip(..., strict=True)lança erro no lugar disso, mas só a partir da 3.10.Transpor e pares vizinhos
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:])])Saída
[(1, 4), (2, 5), (3, 6)] [3, 5, 7]
itertools.pairwisefaz a segunda linha a partir da 3.10;zip(a, a[1:])funciona em qualquer versão.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)))))Saída
[('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! permutações e C(n, k) combinações: tudo bem para n ≤ 10, nunca para n = 30.
accumulate: somas, máximos e produtos 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)))Saída
[3, 4, 8, 9, 14] [3, 3, 4, 4, 5] [3, 3, 12, 12, 60] [0, 3, 4, 8, 9, 14]
initial=0dá o array de somas de prefixos com o zero inicial.groupby: sequências de chaves iguais
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))Saída
[('a', 3), ('b', 1), ('c', 2), ('d', 2)] 2 ['al'] 3 ['amy'] 4 ['bill'] 3 ['bob']Ele agrupa só itens ADJACENTES:
3aparece duas vezes porque a lista foi ordenada por nome, não por tamanho. Ordene pela mesma chave usada para agrupar.
Limites de recursão e memoização
O CPython não otimiza chamadas de cauda e interrompe uma recursão em cerca de mil frames com um RecursionError. Uma DFS sobre um caminho de 10⁵ nós, ou uma DP memoizada com 10⁴ de profundidade, precisa de uma pilha explícita ou de uma tabela bottom-up — não de um limite maior.
O limite, atingido
def depth(n): return 0 if n == 0 else 1 + depth(n - 1) print(depth(500)) try: depth(100_000) except RecursionError: print("RecursionError")Saída
500 RecursionError
O padrão é 1000 frames no CPython; o número exato é detalhe de implementação, então não o imprima numa resposta.
sys.setrecursionlimit — com cuidado
import sys sys.setrecursionlimit(3_000) def depth(n): return 0 if n == 0 else 1 + depth(n - 1) print(depth(2_000))Saída
2000
Ele aumenta o contador do Python, não a pilha de C por baixo dele. Na máquina Windows em que esta cheat sheet foi executada, a mesma função com 3.000 de profundidade derrubou o processo com um estouro de pilha (stack overflow) — sem RecursionError para capturar. Diga isso e ofereça a versão 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 casesSaída
23416728348467685 CacheInfo(hits=78, misses=81, maxsize=None, currsize=81)
81 chamadas distintas em vez de cerca de 8 × 10¹⁶.
@functools.cacheé a mesma coisa, com nome mais curto, a partir da 3.9.Argumentos em cache precisam ser hashable
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 tupleSaída
list: unhashable 3
Converta listas em tuplas (ou índices) antes que elas cheguem a uma função com cache.
AulasO básico de recursãoA pilha de chamadasSua própria pilha de chamadasChamadas de cauda e loops
Pegadinhas com inteiros e floats
// e % do Python arredondam em direção a menos infinito, não em direção a zero como em C, Java e JavaScript. Inteiros nunca dão overflow, e floats são doubles IEEE — compare-os com uma tolerância.
// e % com 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) # ceilSaída
3 -4 -3 1 (-4, 1) 4 4
-7 // 2é -4 (piso);int(-7 / 2)é -3 (trunca, passando por um float — errado para números grandes). As formas idiomáticas de teto (ceil) não saem dos inteiros.Inteiros nunca dão overflow
print(2 ** 100) print(10 ** 18 + 1 == 10 ** 18) MOD = 10 ** 9 + 7 print(2 ** 64 % MOD) print(pow(3, 200, MOD)) # fast modular powSaída
1267650600228229401496703205376 False 582344008 136318165
Quando um problema diz “retorne o resultado módulo 10⁹+7”, reduza ao longo do caminho mesmo assim: aritmética com inteiros grandes não é O(1).
math.inf como sentinela
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)Saída
3 True True nan False
math.infé um float: retorne-1(ou um int) quando a resposta precisar ser inteira.Igualdade de floats e arredondamento
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)Saída
False 0.30000000000000004 True 2 4 2.67 45 1.0
roundarredonda metades para o par, e 2.675 na verdade é 2.67499…./sempre retorna um float.
Truques com bits
Inteiros do Python não têm largura fixa, então ~x é -x - 1 e não existe overflow com que contar. Quando um problema supõe inteiros de 32 bits, aplique você mesmo a máscara 0xFFFFFFFF.
Os truques essenciais
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 bitsSaída
0b10110 0 11 88 0b10100 2 3
x.bit_count()conta os bits ligados (set bits) a partir da 3.10;bin(x).count("1")funciona em qualquer versão.Potências de dois e 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 0Saída
[1, 2, 4, 8, 16] 0b1001 1 0b1000
No Python,
&tem precedência maior que==— o oposto de C e Java —, entãon & (n - 1) == 0funciona. Use parênteses mesmo assim: quem lê pode estar pensando em C.XOR e todos os 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)Saída
4 ['', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']
x ^ x = 0 cancela cada par. As máscaras 0 … 2ⁿ−1 são os 2ⁿ subconjuntos.
Números negativos e visões de 32 bits
print(~5, -5 >> 1) print(bin(-5 & 0xFFFFFFFF)) print((5).bit_length(), (255).bit_length())Saída
-6 -3 0b11111111111111111111111111111011 3 8
-5 >> 1é -3: o deslocamento à direita arredonda para baixo, como//.
AulasBinário e operações bit a bitMáscaras e potência de doisTruques com XORBitmask como conjunto
Armadilhas comuns
Os bugs que o entrevistador de Python está procurando. Cada um imprime algo surpreendente; a correção está nas linhas logo abaixo.
Argumentos padrão mutáveis
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))Saída
[1, 2] [1, 2] [1] [2]
O padrão é avaliado uma vez, quando o
defroda. Use None e crie a lista dentro da função.Closures com late binding
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])Saída
[2, 2, 2] [0, 1, 2]
Uma closure lê a variável quando é CHAMADA. Fixe o valor atual como argumento padrão.
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 isSaída
True False [1, 2, 3] True True
ispergunta “é o mesmo objeto?”. Pode parecer certo com ints pequenos e strings curtas só porque o CPython os mantém em cache — nunca compare valores com ele.Cópias rasas e [[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)Saída
[[1, 0], [1, 0]] [[1, 9], [2]] [[1], [2]]
Monte grids com uma comprehension.
a[:],list(a)ea.copy()copiam só a lista externa.A ordem do dict é garantida; a do set, não
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"}))Saída
['b', 'c', 'a'] ['b', 'a', 'c'] ['a', 'b', 'c']
A ordem de inserção faz parte da linguagem a partir da 3.7. Atualizar uma chave existente mantém o lugar dela; remover e inserir outra vez a leva para o fim.
Alterar um dict enquanto você o percorre
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)Saída
RuntimeError {}Uma lista não lança erro — ela pula itens em silêncio. Percorra uma cópia ou crie uma coleção nova.
Os 10 templates de entrevista
Os esqueletos sobre os quais a maioria das respostas é construída, em Python idiomático — cada um com sua aula e um problema para praticar. A cheat sheet de padrões de entrevista tem os sinais que dizem qual deles o problema pede.
Dois ponteiros
Um array ordenado e um par, uma partição ou um palíndromo decidido pelas duas pontas.
Custo: O(n) de tempo, O(1) de espaço
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))Saída
(0, 4)
- Aula
- Dois ponteiros · Arrays
- Prática
Janela deslizante
A resposta é um trecho contíguo, e mover uma das pontas atualiza o estado de forma barata.
Custo: O(n) de tempo, O(k) de espaço
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"))Saída
3
- Aula
- Janela deslizante · Arrays
- Prática
BFS com deque
Menos passos em um grafo ou grid sem pesos; nível por nível.
Custo: O(V + E) de tempo, O(V) de espaço
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))Saída
{1: 0, 2: 1, 3: 1, 4: 2}list.pop(0)deixaria isto em O(V²). Marque um nó quando ele entra na fila, não quando sai.- Aula
- Busca em largura · Grafos
- Prática
DFS, recursiva e iterativa
Alcançar tudo o que está conectado: flood fill, ilhas, verificação de ciclos, caminhos.
Custo: O(V + E) de tempo, O(V) de espaço
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))Saída
[1, 2, 4, 3] [1, 2, 4, 3]
Empilhar os vizinhos em ordem inversa faz a pilha visitá-los na mesma ordem da versão recursiva.
- Aula
- Busca em profundidade · Grafos
- Prática
Busca binária com bisect
Uma lista ordenada: posição de inserção, primeira/última ocorrência, contagem em um intervalo.
Custo: O(log n) por busca
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)Saída
2 5 3 False [1, 2, 4, 4, 4, 5, 7]
bisect_left: primeiro índice com a[i] ≥ x; bisect_right: primeiro com a[i] > x. O argumento
key=exige a 3.10.- Aula
- Busca binária · Busca
- Prática
Somas de prefixos
Muitas somas de intervalo sobre um array, ou subarrays que somam k.
Custo: O(n) para montar, 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))Saída
[0, 2, 6, 7, 10] 5 3
O 0 inicial é o que faz
pre[j] - pre[i]ser a soma dea[i:j]sem caso especial.- Aula
- Somas de prefixos · Arrays
- Prática
Pilha monotônica
Próximo elemento maior / menor, spans, o maior retângulo.
Custo: O(n) de tempo, O(n) de espaço
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]))Saída
[4, 2, 4, -1, -1]
Cada índice é empilhado uma vez e desempilhado no máximo uma vez: O(n) apesar do while interno.
- Aula
- Pilha monotônica · Pilhas e filas
- Prática
Top-k com heap
Os k maiores, menores, mais próximos ou mais frequentes de n itens.
Custo: O(n log k) de tempo, O(k) de espaço
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]))Saída
[9, 7, 5] [9, 7, 5]
Para manter os k MAIORES, remova de um MIN-heap: o topo dele é o mais fraco dos k mantidos.
- Aula
- Top-k elementos · Heaps
- Prática
Union-find
Componentes conexos que só se fundem; detecção de ciclo em um grafo não direcionado.
Custo: ≈ O(1) por operação, O(n) de espaço
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)}))Saída
True True False 3
findé iterativo de propósito: um recursivo bate no limite de recursão em uma cadeia longa.- Aula
- O básico de conjuntos disjuntos · Union-Find
- Prática
DP com memoizaçãoPython 3.9+
Subproblemas sobrepostos: escreva a recorrência e depois coloque um cache nela.
Custo: O(estados × escolhas) de tempo, O(estados) de espaço
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))Saída
3 2
A profundidade é o próprio valor: passando de alguns milhares, converta para bottom-up (veja Limites de recursão).
- Aula
- Memoização · Recursão
- Prática
bytepatterns.com/cheatsheets/python — lá, cada linha leva a uma aula animada.