Guía para Entrevistas Técnicas: Algoritmos y Estructuras

EXPLICACIÓN DEL CÓDIGO

Este pseudocódigo ilustra el algoritmo BFS, destacando el uso de una cola para gestionar los nodos a visitar y un conjunto para rastrear los nodos ya visitados, evitando ciclos infinitos.

Hash Tables (Tablas Hash)

Las tablas hash (o hash maps/dictionaries) proporcionan un acceso casi constante para la búsqueda, inserción y eliminación de elementos, lo que las hace increíblemente eficientes para problemas que requieren un mapeo rápido de claves a valores. Comprender las funciones hash, las colisiones y las estrategias de resolución (encadenamiento, sondeo lineal) es vital.

Ejemplo de Uso de Hash Table

Un problema común es encontrar si un arreglo contiene duplicados. Con una tabla hash, esto se puede resolver en tiempo lineal.

import java.util.HashSet;
import java.util.Set;

public class Duplicados {
    public boolean contieneDuplicados(int[] nums) {
        Set<Integer> vistos = new HashSet<>();
        for (int num : nums) {
            if (vistos.contains(num)) {
                return true;
            }
            vistos.add(num);
        }
        return false;
    }

    public static void main(String[] args) {
        Duplicados d = new Duplicados();
        int[] arr1 = {1, 2, 3, 1};
        System.out.println(d.contieneDuplicados(arr1)); // true
        int[] arr2 = {1, 2, 3, 4};
        System.out.println(d.contieneDuplicados(arr2)); // false
    }
}

int busquedaBinaria(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;

        // Si x está en el medio
        if (arr[m] == x)
            return m;

        // Si x es mayor, ignorar la mitad izquierda
        if (arr[m] < x)
            l = m + 1;

        // Si x es menor, ignorar la mitad derecha
        else
            r = m - 1;
    }
    // Si el elemento no está presente
    return -1;
}

// Uso
// int arr[] = {2, 3, 4, 10, 40};
// int n = sizeof(arr) / sizeof(arr[0]);
// int x = 10;
// int resultado = busquedaBinaria(arr, 0, n - 1, x);
// if (resultado == -1) ...

1. Comprende el Problema

Clarificación — Haz preguntas hasta que entiendas completamente el problema. ¿Hay restricciones en los datos de entrada? ¿Qué tipo de salida se espera? ¿Hay casos especiales? ¿Cuál es el rango de los valores? Un entrevistador espera que hagas preguntas para aclarar, no que adivines.

Ejemplos — Propón ejemplos de entrada y salida para verificar tu comprensión. Si el entrevistador proporciona uno, úsalo y crea uno o dos más (un caso base, un caso borde, un caso general).

2. Planifica la Solución

Ideas iniciales — Empieza con una solución «bruta» si es necesario. No te preocupes por la optimización al principio. Simplemente busca una manera de resolver el problema.

Optimización — Una vez que tengas una solución funcional, piensa en cómo mejorarla. ¿Puedes usar una estructura de datos diferente (ej. tabla hash para búsquedas rápidas)? ¿Puedes reducir la complejidad temporal o espacial? Analiza la complejidad Big O de tu solución propuesta.

Discusión — Comunica tus pensamientos al entrevistador. Explica por qué una solución es mejor que otra. Esto demuestra tus habilidades de resolución de problemas y comunicación.

3. Escribe el Código

Claridad — Escribe código limpio, legible y bien estructurado. Usa nombres de variables descriptivos. Comenta si es necesario, pero el código debe ser autoexplicativo.

Enfoque — Céntrate en un módulo o función a la vez. Si el problema es grande, divídelo en subproblemas y resuélvelos uno a uno.

4. Prueba tu Código

Casos de prueba — Usa los ejemplos que discutiste al principio. También piensa en casos borde (listas vacías, un solo elemento, valores mínimos/máximos, etc.) y casos nulos.

Paso a paso — Simula la ejecución de tu código con un caso de prueba en tu mente o en un papel. Esto te ayuda a encontrar errores lógicos que no son obvios.

5. Evalúa y Refina

Complejidad — Reconfirma la complejidad temporal y espacial de tu solución final. ¿Hay alguna mejora adicional que se pueda hacer?

Discusión — Si el tiempo lo permite, discute posibles extensiones del problema o cómo tu solución manejaría diferentes escalas o restricciones.