reveal-md

### Taller de resolución de problemas para entrevistas técnicas

Mariano Goldman \
(marianogoldman@gmail.com)

---

# Clase 2

---

## Repaso de clase anterior

- Abordaje para resolver problemas
- Importancia de la comunicación
- ¿Cómo les fue en la semana?

---

## Esta clase

- Búsquedas: lineal O(n) vs binaria O(log n).
- Recursión: caso base + paso recursivo.
- Backtracking.
- Problemas típicos.
- Práctica sugerida.

---

## Búsqueda

- Variantes de búsquedas:
    - Encontrar un elemento y devolverlo
    - Encontrar un elemento y devolver su índice
    - Determinar si un elemento existe
- El resultado es algo bien concreto: un valor

---

## Búsqueda

- Más variantes:
    - Encontrar todos los elemento que cumplen una condición
    - Contar los elementos que cumplen una condición
    - Determinar si existe un elemento que cumple una condición

---

## Recursión

- Función que se llama a sí misma
- Caso base
- Paso (o pasos) recursivo(s)
- Pila de llamadas (call stack)

---

## Fibonacci Number (LC #509)

- Recursivo
- Complejidad: O(2^n)
- ¿Alguna idea de cómo mejorarlo?

---

##  Práctica en parejas

Problema: Reverse Linked List (LC #206)

---

## Backtracking

- Es un algoritmo de fuerza bruta
- Explora todas las posibilidades
- Se usa para problemas de combinatoria (entre otros)
- Se representa como un árbol de decisiones
- Se puede optimizar con poda

---

## Backtracking

- State Space Tree: es el árbol que representa todas las posibles soluciones a un problema de backtracking.
- Bounded function: es una función que ayuda a podar ramas del árbol de decisiones que no pueden conducir a una solución válida.

---

## Backtracking

Ejemplo: Generar todas las formas de sentar a tres personas: [V1, V2, M1]

```mermaid
graph TD
    A(("*")) --> B(("V1")) & C(("V2")) & D(("M1"))
    B(("V1")) --> E(("V2")) & F(("M1"))
    E(("V2")) --> G(("M1"))
    F(("M1")) --> H(("V2"))
    
    C(("V2")) --> I(("V1")) & J(("M1"))
    I(("V1")) --> K(("M1"))
    J(("M1")) --> L(("V1"))
    
    D(("M1")) --> M(("V1")) & N(("V2"))
    M(("V1")) --> O(("V2"))
    N(("V2")) --> P(("V1"))
```

---

## Backtracking

¿Qué complejidad tiene el algoritmo anterior?

---

## Backtracking

Ejemplo: Mismo problema, pero de manera que una mujer nunca se pueda sentar en el medio.

```mermaid
graph TD
    classDef Rose stroke-width:1px, stroke-dasharray:none, stroke:#FF5978, fill:#FFDFE5, color:#8E2236
    
    A(("*")) --> B(("V1")) & C(("V2")) & D(("M1"))
    B(("V1")) --> E(("V2")) & F(("M1"))
    E(("V2")) --> G(("M1"))
    F(("M1")) --> H(("V2"))
    F:::Rose
    H:::Rose

C(("V2")) --> I(("V1")) & J(("M1"))
    I(("V1")) --> K(("M1"))
    J(("M1")) --> L(("V1"))
    J:::Rose
    L:::Rose
    
    D(("M1")) --> M(("V1")) & N(("V2"))
    M(("V1")) --> O(("V2"))
    N(("V2")) --> P(("V1"))
```

---

## Backtracking

**Ejemplo: Permutations (LC #46)**

- Generar todas las permutaciones de [1,2,3]
- Árbol de decisiones
- Poda para optimizar

---

##  Práctica en parejas

Problema: Permutations (LC #46)

---

##  Práctica en parejas

Problema: Generate Parentheses (LC #22)

---

##  Práctica en parejas

Problema: Sum of All Subset XOR Totals (LC #1863)

---

##  Práctica en parejas

Problema: Subsets (LC #78)

---

##  Práctica en parejas

Problema: Combination Sum (LC #39)

---

##  Práctica en parejas

Problema: Word Search (LC #79)