Ejercicios — Estructuras de Datos y Algoritmos

• f1: $O(n)$ — un bucle de $n$.
• f2: $O(n^2)$ — bucles anidados, ambos $n$.
• f3: $O(\log n)$ — divide $n$ a la mitad cada paso (búsqueda binaria sin acceso a array).
• f4: $O(n \log n)$ — sorted usa Timsort.

A: $1 \cdot 10^{12}$ ops. B: $100 \cdot 10^6 \cdot \log_2(10^6) \approx 100 \cdot 10^6 \cdot 20 = 2 \cdot 10^9$ ops.

B es ~500× más rápido. La constante alta no compensa la diferencia asintótica para $n$ grande.

Lección: Big-O domina para $n$ grandes; las constantes solo importan cuando $n$ es chico.

Manejá tres punteros: prev, actual, siguiente. En cada paso, redirigí actual.next hacia prev.

def invertir(cabeza):
    prev = None
    actual = cabeza
    while actual:
        siguiente = actual.next
        actual.next = prev
        prev = actual
        actual = siguiente
    return prev   # nueva cabeza

Es la pregunta más clásica. Si no la podés escribir en 5 minutos, practicala 10 veces.

def balanceados(s: str) -> bool:
    pila = []
    cierre = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in '([{':
            pila.append(c)
        elif c in ')]}':
            if not pila or pila[-1] != cierre[c]:
                return False
            pila.pop()
    return not pila

Casos críticos: cadena vacía (True), cierre sin apertura (")"), apertura sin cierre ("("), tipos mezclados ("(]").

class ColaConPilas:
    def __init__(self):
        self.entrada = []
        self.salida = []

    def enqueue(self, x):
        self.entrada.append(x)

    def dequeue(self):
        if not self.salida:
            while self.entrada:
                self.salida.append(self.entrada.pop())
        return self.salida.pop() if self.salida else None

Análisis: dequeue puede tardar $O(n)$ cuando salida se vacía, pero cada elemento se mueve una sola vez entre pilas. Amortizado: $O(1)$.

• Preorden (raíz, izq, der): 4, 2, 1, 3, 6, 5, 7.
• Inorden (izq, raíz, der): 1, 2, 3, 4, 5, 6, 7. (En BST, inorden = ordenado.)
• Postorden (izq, der, raíz): 1, 3, 2, 5, 7, 6, 4.

Un nodo no solo debe ser mayor que su hijo izquierdo: debe ser mayor que todo el subárbol izquierdo. Pasá un rango (min, max).

def es_bst(nodo, lo=float('-inf'), hi=float('inf')):
    if nodo is None:
        return True
    if not (lo < nodo.valor < hi):
        return False
    return (es_bst(nodo.izq, lo, nodo.valor) and
            es_bst(nodo.der, nodo.valor, hi))

Trampa común: comparar solo nodo vs. hijos directos falla con árboles como [5, 3, 8, 2, 6] donde el 6 está en el subárbol izquierdo del 5 pero su padre es 3.

def profundidad(nodo):
    if nodo is None:
        return 0
    return 1 + max(profundidad(nodo.izq), profundidad(nodo.der))

$O(n)$ tiempo, $O(h)$ espacio en pila de recursión, donde $h$ es la altura. Un árbol balanceado tiene $h = O(\log n)$.

Para cada número $x$, ¿lo viste antes a $T - x$? Hash table es perfecto para "lo viste antes".

def two_sum(nums, target):
    visto = {}                          # valor → índice
    for i, x in enumerate(nums):
        complemento = target - x
        if complemento in visto:
            return [visto[complemento], i]
        visto[x] = i
    return []

$O(n)$ tiempo, $O(n)$ espacio. La versión brute force con dos bucles es $O(n^2)$.

from collections import Counter

def son_anagrama(a: str, b: str) -> bool:
    return Counter(a) == Counter(b)

Para esos strings: ambos tienen 9 letras y la misma cuenta. Ejemplo: Counter("caracoles") == Counter("escolarac").

Alternativa $O(n \log n)$: sorted(a) == sorted(b). La de Counter es $O(n)$.

Sliding window con un set: expandí el window por la derecha mientras no haya repetidos; cuando aparezca uno, contraé por la izquierda hasta que no.

def longitud_max(s: str) -> int:
    visto = {}
    inicio = 0
    mejor = 0
    for fin, c in enumerate(s):
        if c in visto and visto[c] >= inicio:
            inicio = visto[c] + 1
        visto[c] = fin
        mejor = max(mejor, fin - inicio + 1)
    return mejor

$O(n)$ tiempo, $O(\min(n, |\Sigma|))$ espacio (alfabeto).

def islas(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    visit = [[False] * cols for _ in range(rows)]
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols: return
        if visit[r][c] or grid[r][c] == 0: return
        visit[r][c] = True
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            dfs(r+dr, c+dc)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and not visit[r][c]:
                count += 1
                dfs(r, c)
    return count

$O(R \cdot C)$. LeetCode 200, muy clásico.

from collections import deque

def camino_corto(grid):
    if not grid or grid[0][0] or grid[-1][-1]: return -1
    R, C = len(grid), len(grid[0])
    cola = deque([(0, 0, 1)])              # (r, c, distancia)
    visit = {(0, 0)}
    while cola:
        r, c, d = cola.popleft()
        if (r, c) == (R-1, C-1):
            return d
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r+dr, c+dc
            if (0 <= nr < R and 0 <= nc < C
                and grid[nr][nc] == 0 and (nr,nc) not in visit):
                visit.add((nr, nc))
                cola.append((nr, nc, d+1))
    return -1

BFS encuentra el camino mínimo en aristas porque expande nivel a nivel. $O(R \cdot C)$.

from collections import defaultdict, deque

def orden_materias(n, prereqs):
    graph = defaultdict(list)
    indeg = [0] * n
    for a, b in prereqs:
        graph[b].append(a)            # b → a
        indeg[a] += 1

    cola = deque(i for i in range(n) if indeg[i] == 0)
    orden = []
    while cola:
        v = cola.popleft()
        orden.append(v)
        for w in graph[v]:
            indeg[w] -= 1
            if indeg[w] == 0:
                cola.append(w)

    return orden if len(orden) == n else []

Algoritmo de Kahn. $O(V + E)$. LeetCode 207/210.

Hash + lista doblemente enlazada. La hash da $O(1)$ por key; la doubly-linked list permite mover nodos a la "cabeza" en $O(1)$.

class Node:
    def __init__(self, k, v):
        self.k, self.v = k, v
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}                  # k → Node
        self.head, self.tail = Node(0,0), Node(0,0)   # sentinelas
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, k):
        if k not in self.map: return -1
        node = self.map[k]
        self._remove(node); self._add_front(node)
        return node.v

    def put(self, k, v):
        if k in self.map:
            self._remove(self.map[k])
        elif len(self.map) >= self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.k]
        node = Node(k, v)
        self._add_front(node)
        self.map[k] = node

LeetCode 146, casi obligatorio en entrevistas FAANG.