14 patrones para dominar cualquier pregunta de entrevista de codificación

El proceso de preparación para las entrevistas de codificación genera ansiedad para muchos desarrolladores. Hay tanto material que cubrir y, a menudo, gran parte de él se siente irrelevante para lo que los desarrolladores están haciendo en su trabajo diario, lo que solo aumenta el estrés.

Uno de los resultados de esto es que ahora es común que los desarrolladores pasen semanas revisando cientos de preguntas de entrevistas en sitios como LeetCode. Uno de los puntos más comunes de los desarrolladores de ansiedad con los que he hablado antes de la entrevista es: ¿He resuelto suficientes preguntas de práctica? ¿Podría haber hecho más?

Es por eso que trato de concentrarme en ayudar a los desarrolladores a comprender los patrones subyacentes detrás de cada pregunta, para que no tengan que preocuparse por resolver cientos de problemas y sufrir la fatiga de Leetcode. Si comprende los patrones genéricos, puede usarlos como plantilla para resolver una miríada de otros problemas con ligeras variaciones.

Aquí, he presentado los 14 patrones principales que se pueden usar para resolver cualquier pregunta de la entrevista de codificación, así como también cómo identificar cada patrón y algunas preguntas de ejemplo para cada uno. Esto solo toca la superficie. Recomiendo encarecidamente consultar Grokking the Coding Interview: Patterns for Coding Questions para obtener explicaciones completas, ejemplos y prácticas de codificación.

Los siguientes patrones asumen que ha repasado las estructuras de datos. Si no lo ha hecho, consulte estos cursos de actualización sobre estructuras de datos .

¡Empecemos!

1. Ventana corrediza

El patrón de ventana deslizante se usa para realizar una operación requerida en un tamaño de ventana específico de una matriz determinada o una lista vinculada, como encontrar la subarreglo más larga que contiene todos los 1. Las ventanas deslizantes comienzan desde el primer elemento y continúan desplazándose hacia la derecha un elemento y ajustan la longitud de la ventana de acuerdo con el problema que está resolviendo. En algunos casos, el tamaño de la ventana permanece constante y en otros casos, el tamaño crece o se reduce.

Las siguientes son algunas formas en que puede identificar que el problema dado podría requerir una ventana deslizante :

• La entrada del problema es una estructura de datos lineal, como una lista enlazada, una matriz o una cadena.
• Se le pide que busque la subcadena, el subarreglo o el valor deseado más largo/más corto

Problemas comunes con los que usa el patrón de ventana deslizante:

• Subarreglo de suma máxima de tamaño 'K' (fácil)
• Subcadena más larga con caracteres distintivos 'K' (medio)
• Anagramas de cuerdas (difíciles)

2. Dos punteros o iteradores

Two Pointers es un patrón en el que dos punteros iteran a través de la estructura de datos en tándem hasta que uno o ambos punteros alcanzan una determinada condición. Two Pointers suele ser útil cuando se buscan pares en una matriz ordenada o una lista vinculada; por ejemplo, cuando tiene que comparar cada elemento de una matriz con sus otros elementos.

Se necesitan dos punteros porque con solo el puntero, tendría que recorrer continuamente la matriz para encontrar la respuesta. Este ir y venir con un solo iterador es ineficiente para la complejidad del tiempo y el espacio, un concepto denominado análisis asintótico. Si bien la fuerza bruta o la solución ingenua con 1 puntero funcionaría, producirá algo similar a O (n²). En muchos casos, dos indicadores pueden ayudarlo a encontrar una solución con mejor espacio o complejidad de tiempo de ejecución.

Formas de identificar cuándo usar el método Two Pointer:

• Presentará problemas en los que trate con matrices ordenadas (o listas enlazadas) y necesite encontrar un conjunto de elementos que cumplan con ciertas restricciones
• El conjunto de elementos en el arreglo es un par, un triplete o incluso un subarreglo.

Aquí hay algunos problemas que presentan el patrón de dos punteros:

• Cuadrar una matriz ordenada (fácil)
• Trillizos que suman cero (medio)
• Comparación de cadenas que contienen espacios de retroceso (medio)

3. Punteros rápidos y lentos
El enfoque de puntero rápido y lento, también conocido como el algoritmo Hare & Tortoise , es un algoritmo de puntero que utiliza dos punteros que se mueven a través de la matriz (o secuencia/lista enlazada) a diferentes velocidades. Este enfoque es bastante útil cuando se trata de listas o matrices cíclicas enlazadas.

Al moverse a diferentes velocidades (digamos, en una lista cíclica enlazada), el algoritmo prueba que los dos punteros están obligados a encontrarse. El puntero rápido debería atrapar al puntero lento una vez que ambos punteros estén en un bucle cíclico.

¿Cómo identifica cuándo usar el patrón Rápido y Lento?

• El problema tratará con un bucle en una lista o matriz vinculada
• Cuando necesite saber la posición de un determinado elemento o la longitud total de la lista enlazada.

¿Cuándo debo usarlo sobre el método Two Pointer mencionado anteriormente?

• Hay algunos casos en los que no debe usar el enfoque de dos punteros, como en una lista enlazada individualmente donde no puede moverse hacia atrás. Un ejemplo de cuándo usar el patrón Rápido y Lento es cuando intenta determinar si una lista enlazada es un palíndromo.

Problemas con el patrón de punteros rápidos y lentos:

• Ciclo de lista enlazada (fácil)
• Lista vinculada de Palindrome (mediana)
• Ciclo en una matriz circular (difícil)

4. Combinar intervalos

El patrón Merge Intervals es una técnica eficiente para manejar intervalos superpuestos. En muchos problemas que involucran intervalos, debe encontrar intervalos superpuestos o fusionar intervalos si se superponen. El patrón funciona así:

Dados dos intervalos ('a' y 'b'), habrá seis formas diferentes en que los dos intervalos pueden relacionarse entre sí:

Comprender y reconocer estos seis casos lo ayudará a resolver una amplia gama de problemas, desde la inserción de intervalos hasta la optimización de fusiones de intervalos.

¿Cómo identifica cuándo usar el patrón Merge Intervals?

• Si se le pide que produzca una lista con solo intervalos mutuamente excluyentes
• Si escucha el término "intervalos superpuestos".

Combinar patrones de problemas de intervalo:

• Intersección de intervalos (medio)
• Carga máxima de CPU (dura)

5. Clasificación cíclica

Este patrón describe un enfoque interesante para tratar problemas que involucran arreglos que contienen números en un rango dado. El patrón Ordenación cíclica itera sobre el arreglo un número a la vez, y si el número actual que está iterando no está en el índice correcto, lo intercambia con el número en su índice correcto. Puede intentar colocar el número en su índice correcto, pero esto producirá una complejidad de O (n ^ 2) que no es óptima, de ahí el patrón de clasificación cíclica.

¿Cómo identifico este patrón?

• Serán problemas que involucren una matriz ordenada con números en un rango dado
• Si el problema le pide que encuentre el número faltante/duplicado/más pequeño en una matriz ordenada/girada

Problemas que presentan un patrón de ordenación cíclica:

• Encuentra el número que falta (fácil)
• Encuentre el número positivo faltante más pequeño (medio)

6. Inversión en el lugar de la lista enlazada

En muchos problemas, se le puede pedir que invierta los enlaces entre un conjunto de nodos de una lista enlazada. A menudo, la restricción es que necesita hacer esto en el lugar, es decir, usando los objetos de nodo existentes y sin usar memoria adicional. Aquí es donde el patrón mencionado anteriormente es útil.

Este patrón invierte un nodo a la vez, comenzando con una variable (actual) que apunta al encabezado de la lista vinculada, y una variable (anterior) apuntará al nodo anterior que haya procesado. De manera escalonada, invertirá el nodo actual apuntándolo al anterior antes de pasar al siguiente nodo. Además, actualizará la variable "anterior" para que siempre apunte al nodo anterior que ha procesado.

¿Cómo identifico cuándo usar este patrón?

• Si se le pide que invierta una lista vinculada sin usar memoria adicional

Problemas que presentan la inversión en el lugar del patrón de lista enlazada:

• Invertir una sublista (medio)
• Invierta cada sublista de elementos K (medio)

7. Árbol BFS

Este patrón se basa en la técnica Breadth First Search (BFS) para atravesar un árbol y utiliza una cola para realizar un seguimiento de todos los nodos de un nivel antes de pasar al siguiente nivel. Cualquier problema que involucre el recorrido de un árbol en un orden de nivel por nivel puede resolverse de manera eficiente utilizando este enfoque.

El patrón Tree BFS funciona empujando el nodo raíz a la cola y luego iterando continuamente hasta que la cola está vacía. Para cada iteración, eliminamos el nodo al principio de la cola y "visitamos" ese nodo. Después de eliminar cada nodo de la cola, también insertamos todos sus elementos secundarios en la cola.

Cómo identificar el patrón Tree BFS:

• Si se le pide que recorra un árbol nivel por nivel (o recorrido por orden de nivel)

Problemas con el patrón Tree BFS:

• Recorrido en zigzag (medio)

8. Árbol DFS

Tree DFS se basa en la técnica Depth First Search (DFS) para atravesar un árbol.

Puede usar la recursión (o una pila para el enfoque iterativo) para realizar un seguimiento de todos los nodos anteriores (principales) mientras se atraviesa.

El patrón Tree DFS funciona comenzando en la raíz del árbol, si el nodo no es una hoja, debe hacer tres cosas:

1. Decida si desea procesar el nodo actual ahora (pre-pedido), o entre procesar dos hijos (en orden) o después de procesar ambos hijos (post-pedido).
2. Realice dos llamadas recursivas para que los dos hijos del nodo actual los procesen.

Cómo identificar el patrón Tree DFS:

• Si se le pide que atraviese un árbol con DFS en orden, preorden o postorden
• Si el problema requiere buscar algo donde el nodo esté más cerca de una hoja

Problemas con el patrón Tree DFS:

• Suma de números de ruta (medio)
• Todos los caminos por una suma (medio)

9. Dos montones

En muchos problemas, se nos da un conjunto de elementos tales que podemos dividirlos en dos partes. Para resolver el problema, nos interesa conocer el elemento más pequeño de una parte y el elemento más grande de la otra parte. Este patrón es un enfoque eficiente para resolver tales problemas.

Este patrón utiliza dos montones; Un Min Heap para encontrar el elemento más pequeño y un Max Heap para encontrar el elemento más grande. El patrón funciona almacenando la primera mitad de los números en un Max Heap, esto se debe a que desea encontrar el número más grande en la primera mitad. Luego almacena la segunda mitad de los números en un Min Heap, ya que desea encontrar el número más pequeño en la segunda mitad. En cualquier momento, la mediana de la lista actual de números se puede calcular a partir del elemento superior de los dos montones.

Formas de identificar el patrón Two Heaps:

• Útil en situaciones como Priority Queue, Scheduling
• Si el problema indica que necesita encontrar los elementos más pequeños/más grandes/medianos de un conjunto
• A veces, útil en problemas con una estructura de datos de árbol binario

Problemas que presentan

• Encuentra la mediana de un flujo de números (medio)

10. Subconjuntos

Una gran cantidad de problemas de entrevistas de codificación implican tratar con permutaciones y combinaciones de un conjunto dado de elementos. Los subconjuntos de patrones describen un enfoque eficiente de Breadth First Search (BFS) para manejar todos estos problemas.

El patrón se ve así:

Dado un conjunto de [1, 5, 3]

1. Empezar con un conjunto vacío: [[]]
2. Agregue el primer número (1) a todos los subconjuntos existentes para crear nuevos subconjuntos: [[], [1]];
3. Agregue el segundo número (5) a todos los subconjuntos existentes: [[], [1], [5], [1,5]];
4. Agregue el tercer número (3) a todos los subconjuntos existentes: [[], [1], [5], [1,5], [3], [1,3], [5,3], [1, 5,3]].

Aquí hay una representación visual del patrón Subconjuntos:

Cómo identificar el patrón Subconjuntos:

• Problemas donde necesitas encontrar las combinaciones o permutaciones de un conjunto dado

Problemas con el patrón de subconjuntos:

• Subconjuntos con duplicados (fácil)
• Permutaciones de cadenas cambiando de mayúsculas y minúsculas (medio)

11. Búsqueda binaria modificada

Cada vez que se le proporciona una matriz ordenada, una lista vinculada o una matriz, y se le pide que encuentre un elemento determinado, el mejor algoritmo que puede usar es la búsqueda binaria. Este patrón describe una manera eficiente de manejar todos los problemas relacionados con la búsqueda binaria.

Los patrones se ven así para un conjunto de orden ascendente:

1. Primero, encuentra el punto medio entre el principio y el final. Una manera fácil de encontrar el medio sería: medio = (inicio + final) / 2. Pero esto tiene buenas posibilidades de producir un desbordamiento de enteros, por lo que se recomienda que represente el medio como: medio = inicio + (final - inicio) / 2
2. Si la clave es igual al número en el índice medio, devuelve el medio
3. Si 'clave' no es igual al índice medio:
4. Compruebe si la clave < arr[medio]. Si es reduce tu búsqueda al final = medio — 1
5. Compruebe si la clave> arr [medio]. Si es reduce tu búsqueda al final = medio + 1

Aquí hay una representación visual del patrón de búsqueda binaria modificada:

Problemas con el patrón de búsqueda binaria modificada:

Búsqueda binaria independiente del orden (fácil) Búsqueda en una matriz infinita ordenada (media)

12. Los mejores elementos K

Cualquier problema que nos pida encontrar los elementos 'K' superiores/más pequeños/frecuentes entre un conjunto dado cae bajo este patrón.

La mejor estructura de datos para realizar un seguimiento de los elementos 'K' es Heap. Este patrón hará uso del Heap para resolver múltiples problemas relacionados con elementos 'K' a la vez a partir de un conjunto de elementos dados. El patrón se ve así:

1. Inserte elementos 'K' en el montón mínimo o máximo según el problema.
2. Repita los números restantes y si encuentra uno que es más grande que el que tiene en el montón, elimine ese número e inserte el más grande.

No hay necesidad de un algoritmo de clasificación porque el montón hará un seguimiento de los elementos por usted.

Cómo identificar el patrón Elementos 'K' principales:

• Si se le pide que encuentre los elementos 'K' superiores/más pequeños/frecuentes de un conjunto dado
• Si se le pide que ordene una matriz para encontrar un elemento exacto

Problemas con el patrón Top 'K' Elements:

• Top 'K' Números (fácil)
• Top 'K' Números Frecuentes (medio)

13. Fusión K-way

K-way Merge lo ayuda a resolver problemas que involucran un conjunto de matrices ordenadas.

Cada vez que recibe matrices ordenadas 'K', puede usar un Heap para realizar de manera eficiente un recorrido ordenado de todos los elementos de todas las matrices. Puede insertar el elemento más pequeño de cada matriz en un Min Heap para obtener el mínimo general. Después de obtener el mínimo general, empuje el siguiente elemento de la misma matriz al montón. Luego, repita este proceso para hacer un recorrido ordenado de todos los elementos.

El patrón se ve así:

1. Inserte el primer elemento de cada matriz en un Min Heap.
2. Después de esto, saque el elemento más pequeño (superior) del montón y agréguelo a la lista fusionada.
3. Después de eliminar el elemento más pequeño del montón, inserte el siguiente elemento de la misma lista en el montón.
4. Repita los pasos 2 y 3 para completar la lista fusionada en orden.

Cómo identificar el patrón de fusión de K-way:

• El problema contará con arreglos ordenados, listas o una matriz
• Si el problema le pide que fusione listas ordenadas, busque el elemento más pequeño en una lista ordenada.

Problemas que presentan el patrón de fusión K-way:

• Fusionar K listas ordenadas (medio)
• Pares K con sumas más grandes (difíciles)

14. Clasificación topológica

La ordenación topológica se utiliza para encontrar una ordenación lineal de elementos que tienen dependencias entre sí. Por ejemplo, si el evento 'B' depende del evento 'A', 'A' viene antes que 'B' en el ordenamiento topológico.

Este patrón define una manera fácil de comprender la técnica para realizar la ordenación topológica de un conjunto de elementos.

El patrón funciona así:

1. Inicialización
   a) Almacene el gráfico en listas de adyacencia usando un HashMap
   b) Para encontrar todas las fuentes, use un HashMap para llevar la cuenta de los grados de entrada Construya el gráfico y encuentre los grados de entrada de todos los vértices
2. Cree el gráfico a partir de la entrada y complete el HashMap en grados.
3. Encuentra todas las fuentes
   a) Todos los vértices con '0' en grados serán fuentes y se almacenarán en una Cola.
4. Clasificar
   a) Para cada fuente, haga lo siguiente:
   —i) Agregarlo a la lista ordenada.
   — ii) Obtener todos sus hijos del gráfico.
   — iii) Disminuir el grado de entrada de cada hijo en 1.
   — iv) Si el grado de entrada de un niño se convierte en '0', agréguelo a la cola de fuentes.
   b) Repita (a), hasta que la cola de origen esté vacía.

Cómo identificar el patrón de clasificación topológica:

• El problema tratará con gráficos que no tienen ciclos dirigidos.
• Si se le pide que actualice todos los objetos en un orden ordenado
• Si tiene una clase de objetos que siguen un orden particular

Problemas que presentan el patrón de clasificación topológica:

• Programación de tareas (medio)
• Altura mínima de un árbol (difícil)

¿Qué sigue?

¿Experimenta la fatiga de LeetCode? Aprende estos 14 patrones y tendrás una imagen más completa de cómo abordar un problema sin importar la pregunta.

Si está interesado en una inmersión más profunda a través de los patrones anteriores o los problemas de ejemplo debajo de cada uno, consulte Grokking the Coding Interview: Patterns for Coding Questions . Es el curso más reciente de la serie de entrevistas de Grokking, utilizado por más de 20 000 estudiantes para conseguir empleos en las principales empresas tecnológicas.

El mayor respaldo que puedo darle es que realmente desearía que existiera cuando todavía me estaba preparando para codificar entrevistas.