Original article: How to Rock the Coding Interview – Tips That Helped Me Land Job Offers from Google, Airbnb, and Dropbox

En 2017, pasé por algunas entrevistas de programación y recibí ofertas de varias grandes empresas tecnológicas. Entonces, en ese momento, decidí compartir lo que había aprendido en este artículo.

Y es que lo acabo de actualizar para 2022, por lo que será relativamente útil y relevante si estás buscando trabajo ahora.

A pesar de obtener calificaciones decentes tanto en mi clase de Algoritmos CS101 como en mi clase de Estructuras de Datos en la universidad, me estremezco al pensar en pasar por una entrevista de programación que se enfoca en algoritmos.

Por lo tanto, pasé los últimos tres meses averiguando cómo mejorar mis habilidades de programación de entrevistas y finalmente recibí ofertas de grandes compañías tecnológicas como Google, Facebook, Airbnb, Lyft, Dropbox y más.

En esta publicación, compartiré las ideas y los consejos que obtuve en el camino. Los candidatos experimentados también pueden esperar preguntas sobre el diseño de sistemas, pero eso está fuera del alcance de esta publicación.

Muchos de los conceptos algorítmicos probados en entrevistas de programación no son los que uso habitualmente en el trabajo, donde soy Ingeniero Front End (web). Naturalmente, me he olvidado un poco de estos algoritmos y estructuras de datos, que aprendí principalmente durante mi primer y segundo año de universidad.

Es estresante tener que producir código (de trabajo) en una entrevista, mientras alguien examina cada pulsación de tecla que haces. Lo que es peor es que, como entrevistado, se te anima a comunicar su proceso de pensamiento en voz alta al entrevistador.

Solía pensar que ser capaz de pensar, programar y comunicarse simultáneamente era una hazaña imposible, hasta que me di cuenta de que la mayoría de las personas simplemente no son buenas programando en entrevistas cuando recién comienzan. La entrevista es una habilidad en la que puedes mejorar estudiando, preparándose y practicando.

Mi reciente búsqueda de trabajo me ha llevado a un viaje para mejorar mis habilidades de programación en las entrevistas. A los ingenieros front-end les gusta despotricar sobre cómo se rompe el proceso de contratación actual porque las entrevistas técnicas pueden incluir habilidades que no están relacionadas con el desarrollo front-end.

Por ejemplo, escribir un algoritmo de resolución de laberintos y fusionar dos listas ordenadas de números. Como ingeniero front-end, puedo empatizar con ellos.

El front-end es un dominio especializado en el que los ingenieros tienen que preocuparse por muchos problemas relacionados con la compatibilidad de los navegadores, el modelo de objetos del documento, el rendimiento de JavaScript, los diseños de CSS, etc.

Es poco común que los ingenieros front-end implementen algunos de los complejos algoritmos probados en las entrevistas.

En empresas como Facebook y Google, las personas son ingenieros de software en primer lugar y, en segundo lugar, expertos en dominios.

Lamentablemente, las reglas las establecen las empresas, no los candidatos. Hay un gran énfasis en conceptos generales de informática como algoritmos, patrones de diseño, estructuras de datos. Habilidades básicas que debe poseer un buen ingeniero de software. Si deseas el trabajo, debes seguir las reglas establecidas por los maestros del juego: ¡Mejorar tus habilidades de entrevista de programación!

Este post está estructurado en las siguientes dos secciones. Siéntete libre de pasar directamente a la sección que te interese.

  • El desglose de las entrevistas de programación y cómo prepararse para ellas.
  • Sugerencias y sugerencias útiles para cada tema de algoritmo (matrices, árboles, programación dinámica, etc.), junto con preguntas de práctica recomendadas de LeetCode para revisar los conceptos básicos y mejorar esos temas.

El contenido de esta publicación se puede encontrar aquí. Haré actualizaciones allí cuando sea necesario.

Si estás interesado en el contenido de Front End, consulta mi manual de entrevistas de front end aquí.

Elige un lenguaje de programación

Antes que nada, debe elegir un lenguaje de programación para su entrevista de programación algorítmica.

La mayoría de las empresas te permitirán programar en el lenguaje de tu elección. La única excepción que conozco es Google. Permiten que sus candidatos elijan solo Java, C++, Python, Go o JavaScript.

En su mayor parte, recomiendo utilizar un lenguaje con el que esté muy familiarizado, en lugar de uno que sea nuevo para usted pero que la empresa utilice ampliamente.

Hay algunos lenguajes que son más adecuados que otros para codificar entrevistas. Luego hay algunos que absolutamente querrás evitar.

Según mi experiencia como entrevistador, la mayoría de los candidatos eligen Python o Java. Otros lenguajes comúnmente seleccionados incluyen JavaScript, Ruby y C++. Absolutamente, evitaría los lenguajes de nivel inferior como C o Go, simplemente porque carecen de estructuras de datos y funciones de biblioteca estándar.

Personalmente, Python es mi elección de facto para codificar algoritmos durante las entrevistas. Es sucinto y tiene una enorme biblioteca de funciones y estructuras de datos.

Una de las principales razones por las que recomiendo Python es que utiliza API consistentes que operan en diferentes estructuras de datos, como len(), for ... in ... y notación de corte en secuencias (cadenas, listas y tuplas). Obtener el último elemento en una secuencia es arr[-1] , e invertirlo es simplemente arr[::-1]. Puede lograr mucho con una sintaxis mínima en Python.

Java también es una opción decente. Pero debido a que tendrás que declarar constantemente tipos en su código, significa ingresar pulsaciones de teclas adicionales. Esto ralentizará la velocidad a la que codifica y escribe. Este problema será más evidente cuando tengas que escribir en una pizarra durante las entrevistas en el sitio.

Las razones para elegir o no C++ son similares a Java. En última instancia, Python, Java y C++ son opciones decentes. Si has estado usando Java por un tiempo y no tienes tiempo para familiarizarse con otro lenguaje, te recomiendo que te ciña a Java en lugar de retomar Python desde cero.

Esto te ayuda a evitar tener que usar un lenguaje para el trabajo y otro para las entrevistas. La mayoría de las veces, el cuello de botella está en el pensamiento y no en la escritura.

Una excepción a la convención de permitir que el candidato "escoja cualquier lenguaje de programación que desee" es cuando la entrevista es para un puesto de dominio específico, como roles de ingeniero front-end, iOS o Android. Debes estar familiarizado con los algoritmos en JavaScript, Objective-C, Swift y Java, respectivamente.

Si necesitas usar una estructura de datos que el lenguaje no admite, como una cola o un montón en JavaScript, pregúntale al entrevistador si puede suponer que tiene una estructura de datos que implementa ciertos métodos con complejidades de tiempo específicas.

Si la implementación de esa estructura de datos no es crucial para resolver el problema, el entrevistador generalmente lo permitirá.

En realidad, ser consciente de las estructuras de datos existentes y seleccionar las adecuadas para abordar el problema en cuestión es más importante que conocer los intrincados detalles de implementación.

Revisa introducción a las ciencias de la computación

Si has estado fuera de la universidad durante algún tiempo, es muy recomendable que revises los fundamentos de CS. Prefiero repasarlo mientras practico. Escaneo mis notas de la universidad y reviso los diversos algoritmos mientras trabajo en los problemas de algoritmos de LeetCode y Cracking the Coding Interview.

Si tienes interés en cómo se implementan las estructuras de datos, consulta Lago, un repositorio de GitHub que contiene ejemplos de estructuras de datos y algoritmos en JavaScript.

GitHub - yangshun/lago: ? Data Structures and Algorithms library in TypeScript
? Data Structures and Algorithms library in TypeScript - GitHub - yangshun/lago: ? Data Structures and Algorithms library in TypeScript
faviconGitHubyangshun
lago

La maestría deviene de la práctica

Luego, adquiere familiaridad y dominio de los algoritmos y las estructuras de datos en el lenguaje de programación elegido.

Practica y resuelve preguntas de algoritmos en el lenguaje que elijas. Si bien Cracking the Coding Interview es un buen recurso, prefiero resolver problemas escribiendo código, dejándolo funcionar y recibiendo comentarios instantáneos.

Existen diversos recursos online como LeetCode, HackerRank, y CodeForces con los que puedes practicar ejercicios a la vez que te acostumbras al lenguaje.

Según mi experiencia, las preguntas de LeetCode son muy similares a las preguntas que se hacen en las entrevistas.

Las preguntas de HackerRank y CodeForces son más similares a las preguntas de la programación competitiva. Si practicas suficientes preguntas de LeetCode, es muy probable que veas o completes una de las preguntas de su entrevista real (o alguna variante de la misma).
Aprender y llegar a comprender las complejidades de tiempo y espacio de las operaciones comunes en el lenguaje elegido. Para Python, esta página será útil. Además, aprende sobre el algoritmo de clasificación subyacente que se usa en la función sort() del lenguaje y sus complejidades de tiempo y espacio (en Python es Timsort, que es un híbrido).
Después de completar una pregunta sobre LeetCode, generalmente agrego las complejidades de tiempo y espacio del código escrito como comentarios sobre el cuerpo de la función.

En lo personal utilizo los comentarios para recordarme comunicar el análisis del algoritmo después de haber completado la implementación.
Lee sobre el estilo de programación recomendado para tu lenguaje y apégate a él. Si eliges Python, consulta la Guía de estil. Si eliges Java, consulta la Guía de estilo de Java de Google.
Aprende y acostúmbrate a las trampas y advertencias comunes del lenguaje. Si las señalas durante la entrevista y evitas caer en ellos, ganarás puntos de bonificación e impresionarás al entrevistador, independientemente de si el entrevistador está familiarizado con el lenguaje o no.
Obtén una amplia exposición a las preguntas de varios temas. En la segunda mitad del artículo, menciono temas de algoritmos y las preguntas útiles para practicar cada tema. Hacer alrededor de 100 a 200 preguntas de LeetCode debería considerarse como algo bueno.

Si prefieres cursos donde el aprendizaje está más estructurado, aquí hay algunas recomendaciones. De ninguna manera es obligatorio tomar cursos en línea para aprobar las entrevistas.

  • AlgoMonster :Tiene como objetivo ayudarlo a superar la entrevista técnica en el menor tiempo posible. Diseñado por los ingenieros de Google, AlgoMonster utiliza un enfoque basado en datos para enseñarte los patrones de preguntas clave más útiles y tiene contenido para ayudarte a revisar rápidamente las estructuras de datos y los algoritmos básicos. Lo mejor de todo es que AlgoMonster no está basado en suscripción: paguas una tarifa única y obtienes acceso de por vida.
  • Grokking the Coding Interview: Patterns for Coding Questions: por Educative amplía las preguntas de práctica recomendadas en este artículo, pero aborda la práctica desde una perspectiva de patrón de preguntas. Este es un enfoque con el que también estoy de acuerdo para aprender y que he usado personalmente para mejorar en las entrevistas de programación. El curso te permite practicar preguntas seleccionadas en Java, Python, C++, JavaScript y también proporciona soluciones de muestra en esos lenguajes. Aprende y entiende los patrones, no memorices las respuestas.
    Y por supuesto, práctica, práctica y más práctica!

Fases de una entrevesta de programación

¡Felicitaciones, estás listo para poner en práctica tus habilidades! En una entrevista de programación, el entrevistador te hará una pregunta técnica. Escribirás el código en un editor colaborativo en tiempo real (pantalla del teléfono) o en una pizarra (whiteboard), y tendrás de 30 a 45 minutos para resolver el problema.

¡Aquí es donde comienza la verdadera diversión!
Tu entrevistador buscará que cumplas con los requisitos del puesto. Depende de ti demostrarles que tienes las habilidades. Inicialmente, puede parecer extraño hablar mientras programan, ya que la mayoría de los programadores no tienen la costumbre de explicar en voz alta sus pensamientos mientras escriben el código.
Sin embargo, es difícil para el entrevistador saber lo que estás pensando con solo mirar tu código.

Si comunicas tu enfoque al entrevistador incluso antes de comenzar a codificar, puedes validar tu enfoque con ellos. De esta manera, los dos pueden ponerse de acuerdo sobre un enfoque aceptable.

Preparándote para una entrevista remota

Para pantallas telefónicas y entrevistas remotas, ten papel y bolígrafo o lápiz para anotar notas o diagramas. Si te hacen una pregunta sobre árboles y gráficos, generalmente ayuda si dibuja ejemplos de la estructura de datos.

Usa auriculares. Asegúrate de estar en un ambiente tranquilo. No querrás tener un teléfono en una mano y escribir con la otra. Trate de evitar el uso de altavoces. Si la retroalimentación es mala, la comunicación se hace más difícil. Tener que repetirse solo resultará en la pérdida de un tiempo valioso.

¿Qué hacer cuando tengas la pregunta?

Muchos candidatos comienzan a programar tan pronto como escuchan la pregunta. Eso suele ser un gran error. Primero, tómate un momento y repita la pregunta al entrevistador para asegurarse de que comprendes la pregunta.

Si no entiendes la pregunta, entonces el entrevistador puede aclararla.
Siempre busca una aclaración sobre la pregunta al escucharla, incluso si crees que está clara. Es posible que descubras que te has perdido de algo. De esta forma también le muestras al entrevistador que estás atento a los detalles.

Considera hacer las siguientes preguntas.

  • ¿Cuál es el tamaño del input?
  • ¿Cuál es el tamaño del rango de valores?
  • ¿Qué tipo de valores hay? ¿Hay números negativos? ¿Puntos flotantes? ¿Habrá entradas vacías?
  • ¿Hay duplicados en el input?
  • ¿Cuáles son algunos casos extremos que aplican para el input?
  • ¿Cómo se almacena el input ? Si me dan un diccionario de palabras... ¿Es una lista de cadenas o un trie?

Después de haber aclarado suficientemente el alcance y la intención del problema, explica tu enfoque de alto nivel al entrevistador, incluso si es una solución ingenua. Si estás atascado, considera varios enfoques y explica en voz alta por qué puede o no funcionar. A veces, tu entrevistador puede dar pistas y guiarte hacia el camino correcto.
Comienza con un enfoque algo directo; comunica al entrevistador. Explica las complejidades de tiempo y espacio y aclara por qué es malo. En este punto, el entrevistador generalmente mostrará el temido "¿Podemos hacerlo mejor?" pregunta.

Esto significa que están buscando un enfoque más óptimo.
Esta suele ser la parte más difícil de la entrevista. En general, busca trabajos repetidos e intenta optimizarlos almacenando potencialmente en caché el resultado calculado en alguna parte.

Consúltalo más tarde, en lugar de calcularlo todo de nuevo. Proporciono aquí algunos consejos sobre cómo abordar preguntas específicas del tema en detalle a continuación.
Solo comienza a programar después de que tú y tu entrevistador hayan acordado un enfoque y le hayan dado luz verde.

Comenzando a programar

Usa un buen estilo para escribir tu código. Leer código escrito por otros no suele ser una tarea agradable. Leer código con un formato horrible escrito por otros es aún peor. Tu objetivo es hacer que su entrevistador entienda tu código para que pueda evaluar rápidamente si tu código hace lo que se supone que debe hacer y si resuelve un problema determinado.
Utiliza nombres de variables claros y evita nombres que sean letras sueltas, a menos que sean para iteración. Sin embargo, si estás programando en whiteboard, evita usar nombres de variables detallados. Esto reduce la cantidad de escritura que tendrás que hacer.
Siempre explica al entrevistador lo que estás escribiendo. No se trata de leer, palabra por palabra, al entrevistador el código que estás produciendo. Habla sobre la sección del código que estás implementando actualmente en un nivel superior. Explica por qué está escrito así y qué estás tratando de lograr.
Cuando copies y pegues el código, considera si es necesario. A veces lo es, a veces no lo es.

Si te encuentras copiando y pegando una gran cantidad de código que abarca varias líneas, probablemente sea un indicador de que puedas reestructurar el código extrayendo esas líneas en una función. Si se trata de una sola línea que copiaste, por lo general está bien.
Sin embargo, recuerda cambiar las variables respectivas en tu línea de código copiada cuando sea relevante. Los errores de copiado y pegado son una fuente común de errores, ¡Incluso en la programación diaria!

Después de programar

Una vez que hayas terminado de codificar, no anuncies inmediatamente al entrevistador que has terminado. En la mayoría de los casos, tu código no suele ser perfecto. Puede contener bugs o errores de sintaxis. Lo que tienes que hacer es revisar tu código.
Primero, revisa tu código de principio a fin. Míralo como si lo hubiera escrito otra persona, lo estás viendo por primera vez y tratando de detectar errores en él. Eso es exactamente lo que hará tu entrevistador. Revisa y arregla cualquier problema que puedas encontrar.
A continuación, propón casos de prueba pequeños y avance a través del código (no tu algoritmo) con esas entradas de muestra.
A los entrevistadores les gusta cuando les lees la mente. Lo que suelen hacer después de que hayas terminado de codificar es pedirte que escribas pruebas. Es una gran ventaja si escribes pruebas para su código incluso antes de que te soliciten que lo haga. Deberías estar emulando un depurador al recorrer su código. Anota o diles los valores de ciertas variables mientras guía al entrevistador a través de las líneas de código.

Si hay grandes fragmentos de código duplicados en su solución, reestructura el código para mostrarle al entrevistador que valoras la progamación de calidad. Además, busca lugares donde pueda hacer una evaluación de cortocircuito.


Por último, menciona las complejidades de tiempo y espacio de su código y explicas por qué es así. Puedes anotar fragmentos de su código con sus diversas complejidades de tiempo y espacio para demostrar su comprensión del código. Incluso puedes proporcionar las API de su lenguaje de programación elegido. Explica cualquier compensación entre tu enfoque actual y los enfoques alternativos, posiblemente en términos de tiempo y espacio.
Si tu entrevistador está satisfecho con la solución, la entrevista generalmente termina aquí.

También es común que el entrevistador te haga preguntas de extensión, como cómo manejarías el problema si toda la entrada es demasiado grande para caber en la memoria, o si la entrada llega como un flujo. Esta es una pregunta de seguimiento común en Google, donde se preocupan mucho por la escala.
La respuesta suele ser un enfoque de divide y vencerás: realiza un procesamiento distribuido de los datos y solo lee ciertos fragmentos de la entrada del disco en la memoria, escribe la salida nuevamente en el disco y combínalos más tarde.

Practica con entrevistas simuladas

Los pasos mencionados anteriormente se pueden ensayar una y otra vez hasta que los hayas internalizado por completo y se conviertan en una segunda naturaleza para ti. Una buena manera de practicar es asociarse con un amigo y turnarse para entrevistarse.
Un gran recurso para prepararse para entrevistas de codificación es interviewing.io. Esta plataforma ofrece entrevistas de práctica gratuitas y anónimas con ingenieros de Google y Facebook, que pueden conducir a trabajos y pasantías reales.
En virtud de ser anónimo durante la entrevista, el proceso de entrevista inclusiva es imparcial y de bajo riesgo. Al final de la entrevista, tanto el entrevistador como el entrevistado pueden retroalimentarse mutuamente con el fin de ayudarse mutuamente a mejorar.
Hacer bien las entrevistas simuladas desbloqueará la página de trabajos para los candidatos y les permitirá reservar entrevistas (también de forma anónima) con las principales empresas como Uber, Lyft, Quora, Asana y más.

Para aquellos que son nuevos en las entrevistas de codificación, se puede ver una entrevista de demostración en este sitio. Ten en cuenta que este sitio requiere que los usuarios inicien sesión.
He usado interviewing.io, tanto como entrevistador como como entrevistado. La experiencia fue genial. A Aline Lerner, directora ejecutiva y cofundadora de entrevistas.io, y a su equipo les apasiona revolucionar el proceso de codificación de entrevistas y ayudar a los candidatos a mejorar sus habilidades de entrevista.
También ha publicado una serie de artículos relacionados con entrevistas de codificación en el blog interviewing.io. Recomiendo registrarse lo antes posible en interviewing.io, aunque esté en versión beta, para aumentar la probabilidad de recibir una invitación.

image-58

Otra plataforma útil para las entrevistas es Pramp. Mientras que Interviewing.io conecta a los posibles buscadores de empleo con entrevistadores de codificación experimentados, Pramp adopta un enfoque diferente. Pramp te empareja con otro compañero que también busca trabajo. Los dos se turnan para asumir los roles de entrevistador y entrevistado. Pramp también prepara preguntas y brinda soluciones e indicaciones para guiar al entrevistado.

Avanza y conquista

Después de hacer una buena cantidad de preguntas en LeetCode y tener suficiente práctica haciendo entrevistas simuladas, continúe y ponga a prueba sus nuevas habilidades de entrevista.
Postula a tus empresas favoritas o, mejor aún, obtén referencias de tus amigos que trabajan para esas empresas. Las referencias tienden a notarse antes y tienen una tasa de respuesta más rápida que la solicitud sin una referencia. ¡Buena suerte!

Consejos prácticos para resolver preguntas de programación

Esta sección profundiza en consejos prácticos para temas específicos de algoritmos y estructuras de datos, que aparecen con frecuencia en las preguntas de codificación. Muchas preguntas de algoritmos involucran técnicas que se pueden aplicar a preguntas de naturaleza similar.
Cuantas más técnicas tengas en tu arsenal, mayores serán tus posibilidades de pasar la entrevista. Para cada tema, también hay una lista de preguntas recomendadas, que es valiosa para dominar los conceptos básicos. Algunas de las preguntas solo están disponibles con una suscripción paga a LeetCode, que en mi opinión vale la pena si te consigue un trabajo.

Consejos generales

Siempre valida la entrada primero. Verifica las entradas que no son válidas, están vacías, son negativas o diferentes. Nunca asumas que te dan los parámetros válidos.

Alternativamente, aclara con el entrevistador si puedes asumir una entrada válida (generalmente sí), lo que puede ahorrarte tiempo al escribir código que valida la entrada.
¿Hay algún requisito o restricción de complejidad de tiempo y espacio?
Comprueba si hay errores de apagado por uno.

En lenguajes donde no hay coerción automática de tipos, comprobar que la concatenación de valores sea del mismo tipo: int,str, y list.

Después de terminar tu código, use algunas entradas de ejemplo para probar su solución.
¿Se supone que el algoritmo debe ejecutarse varias veces, quizás en un servidor web? En caso afirmativo, es probable que la entrada se pueda procesar previamente para mejorar la eficiencia en cada llamada a la API.

Usa una combinación de paradigmas de programación funcional e imperativa:

  • Escribe funciones puras tan a menudo como sea posible.
  • Usa funciones puras porque es más fácil razonar con ellas y pueden ayudar a reducir errores en su implementación.
  • Evita mutar los parámetros pasados a su función, especialmente si se pasan por referencia, a menos que esté seguro de lo que está haciendo.
  • Logra un equilibrio entre precisión y eficiencia. Usa la cantidad correcta de código funcional e imperativo cuando corresponda. La programación funcional suele ser costosa en términos de complejidad espacial debido a la no mutación y la asignación repetida de nuevos objetos. Por otro lado, el código imperativo es más rápido porque opera en objetos existentes.
  • Evita confiar en la mutación de variables globales. Las variables globales introducen el estado.
  • Asegúrate de no mutar accidentalmente las variables globales, especialmente si tienes que depender de ellas.

Generalmente, para mejorar la velocidad de un programa, podemos optar por usar una estructura de datos o algoritmo apropiado, o usar más memoria. Es un intercambio clásico de espacio y tiempo.
Las estructuras de datos son sus armas. Elegir el arma adecuada para la batalla adecuada es la clave de la victoria. Conozca las fortalezas de cada estructura de datos y la complejidad del tiempo para sus diversas operaciones.
Las estructuras de datos se pueden aumentar para lograr una complejidad de tiempo eficiente en diferentes operaciones. Por ejemplo, un HashMap se puede usar junto con una lista doblemente enlazada para lograr una complejidad de tiempo O(1) para la operación  get and put  en una memoria caché LRU.

HashMaps es probablemente la estructura de datos más utilizada para preguntas de algoritmos. Si estás atascado en una pregunta, su último recurso puede ser enumerar las posibles estructuras de datos (afortunadamente no hay tantas) y considerar si cada una de ellas se puede aplicar al problema. Esto ha funcionado para mí a veces.
Si estás tomando atajos en tu código, díselo en voz alta a tu entrevistador y explícale lo que harías fuera de un entorno de entrevista (sin limitaciones de tiempo). Por ejemplo, explica que escribirías una expresión regular para analizar una cadena en lugar de usar split , que no cubre todos los casos.

Secuencia

Notas

Las matrices y las cadenas se consideran secuencias (una cadena es una secuencia de caracteres). Hay consejos para tratar con matrices y cadenas, que se tratarán aquí.
¿Hay valores duplicados en la secuencia? ¿Afectarían la respuesta?
Comprueba si hay una secuencia fuera de los límites.
Ten cuidado con dividir o concatenar secuencias en tu código. Por lo general, las secuencias de corte y concatenación requieren tiempo O(n). Utiliza índices de inicio y finalización para delimitar un subarreglo o una subcadena siempre que sea posible.
A veces se atraviesa la secuencia desde el lado derecho en lugar de desde el izquierdo.

Domina la técnica de sliding window ya que se aplica a muchos problemas de subcadenas o subarreglos.

Cuando se le dan dos secuencias para procesar, es común tener un índice por secuencia para recorrer. Por ejemplo, usamos el mismo enfoque para fusionar dos matrices ordenadas.

Casos comunes

  • Secuencia vacía
  • Secuencia con 1 o 2 elementos
  • Secuencia con elementos repetidos

Arreglos

Notas

¿La matriz está ordenada o parcialmente ordenada? Si es así, alguna forma de búsqueda binaria debería ser posible. Esto generalmente significa que el entrevistador está buscando una solución que sea más rápida que O(n).
¿Puedes ordenar la matriz? A veces, ordenar la matriz primero puede simplificar significativamente el problema. Asegúrate de que no sea necesario conservar el orden de los elementos de la matriz antes de intentar ordenarlos.
Para las preguntas en las que se trata de la suma o la multiplicación de un subarreglo, puede ser útil el cálculo previo mediante hashing o un prefijo, una suma de sufijos o un producto.
Si te dan una secuencia y el entrevistador te pide espacio O(1), podría ser posible usar la matriz en sí como una tabla hash. Por ejemplo, si la matriz tiene valores solo de 1 a N, donde N es la longitud de la matriz, niega el valor en ese índice (menos uno) para indicar la presencia de ese número.

Practice Questions

Binario

Notas

A veces se hacen preguntas que involucran representaciones binarias y operaciones bit a bit. Debes saber cómo convertir un número de forma decimal a forma binaria, y viceversa, en el lenguaje de programación elegido.
Algunos fragmentos útiles de utilidad:

  • Probar que kth es: num & (1 << k) != 0
  • Conjunto kth bit es: num |= (1 << k)
  • Turn off kth bit: num &= ~(1 << k)
  • Alternar el k-ésimo bit: num ^= (1 << k)
  • Para comprobar si un número es una potencia de 2: num & num - 1 == 0.

Casos comunes

  • Comprueba si hay desbordamiento/subdesbordamiento
  • Números negativos

Preguntas de prácticas

Programación Dinámica

Notas

La Programación Dinámica (DP) se usa generalmente para resolver problemas de optimización. Alaina Kafkes ha escrito una publicación increíble sobre cómo abordar los problemas de DP. Deberías leerlo.
La única forma de mejorar en DP es con práctica. Se necesita mucha práctica para reconocer que un problema puede ser resuelto por DP.
Para optimizar el espacio, a veces no es necesario almacenar toda la tabla DP en la memoria. Los dos últimos valores o las dos últimas filas de la matriz serán suficientes.

Practice Questions

Geometría

Notas

Al comparar la distancia euclidiana entre dos pares de puntos, es suficiente usar dx² + dy². No es necesario sacar la raíz cuadrada del valor.
Para saber si dos círculos se superponen, verifica que la distancia entre los dos centros de los círculos sea menor que la suma de sus radios.

Grafos

Notas

Estar familiarizado con las diversas representaciones gráficas y algoritmos de búsqueda de gráficos, y con sus complejidades de tiempo y espacio.
Se le puede dar una lista de bordes y se le puede asignar la tarea de construir su propio gráfico a partir de los bordes para realizar un recorrido. Las representaciones gráficas comunes son

  • Matriz de adyacencia
  • Lista de adyacencia
  • HashMap de HashMaps

Algunas entradas parecen árboles, pero en realidad son grafos. Aclara esto con tu entrevistador. En ese caso, deberá manejar los ciclos y mantener un conjunto de nodos visitados al atravesar.

Algoritmos de búsqueda de grafos

  • Común: Primera Búsqueda en Amplitud (BFS), Primera búsqueda en profundidad (DFS)
  • Poco común: clasificación topológica, algoritmo de Dijkstra
    Raro: algoritmo de Bellman-Ford, algoritmo de Floyd-Warshall, algoritmo de Prim y algoritmo de Kruskal

En las entrevistas de codificación, los grafos se representan comúnmente como matrices 2-D, donde las celdas son los nodos y cada celda puede atravesar a sus celdas adyacentes (arriba, abajo, izquierda y derecha). Por lo tanto, es importante estar familiarizado con atravesar una matriz 2-D.
Cuando atravieses recursivamente la matriz, siempre asegúrate de que su próxima posición esté dentro de los límites de la matriz. Puedes encontrar más consejos para hacer DFS en una matriz aquí. Una plantilla simple para hacer DFS en una matriz aparece así:

def traverse(matrix):
  rows, cols = len(matrix), len(matrix[0])
  visited = set()
  directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
  def dfs(i, j):
    if (i, j) in visited:
      return
    visited.add((i, j))
    # Traverse neighbors
    for direction in directions:
      next_i, next_j = i + direction[0], j + direction[1]
      if 0 <= next_i < rows and 0 <= next_j < cols: # Check boundary
        # Add any other checking here ^
        dfs(next_i, next_j)
  for i in range(rows):
    for j in range(cols):
      dfs(i, j)

Casos comunes

  • Grafo vacío
  • Grafo con uno o dos nodos
  • Grafo disjuntas
  • Grafo con ciclos

Preguntas de práctica

Intervalo

Notas

Las preguntas de intervalo son preguntas que dan una matriz de matrices de dos elementos (un intervalo). Los dos valores representan un valor inicial y final. Las preguntas de intervalo se consideran parte de la familia de matrices, pero involucran algunas técnicas comunes. Por lo tanto, tienen su propia sección especial.

Un ejemplo de un arreglo con intervalo es el siguiente: [[1, 2], [4, 7]].

Las preguntas de intervalo pueden ser complicadas para aquellos que no tienen experiencia con ellas. Esto se debe a la gran cantidad de casos a considerar cuando las matrices de intervalos se superponen.

Aclara con el entrevistador si [1, 2] y [2, 3] se consideran intervalos superpuestos, porque afecta cómo escribirá sus comprobaciones de igualdad.

Una rutina común para las preguntas de intervalo es ordenar la matriz de intervalos por el valor inicial de cada intervalo.
Tienes que familiarizarte con la escritura de código para verificar si dos intervalos se superponen y fusionar dos intervalos superpuestos:

def is_overlap(a, b):
  return a[0] < b[1] and b[0] < a[1]
  
def merge_overlapping_intervals(a, b):
  return [min(a[0], b[0]), max(a[1], b[1])]

Casos comunes

  • Intervalo único
  • Intervalos no superpuestos
  • Un intervalo totalmente consumido dentro de otro intervalo
  • Intervalos duplicados

Practice Questions

Lista enlazada

Notas

Al igual que las matrices, las listas enlazadas se utilizan para representar datos secuenciales. El beneficio de las listas enlazadas es que la inserción y eliminación de código desde cualquier lugar de la lista es O(1), mientras que en las matrices, los elementos deben cambiarse.
Agregar un nodo ficticio en la cabeza o en la cola podría ayudar a manejar muchos casos extremos en los que las operaciones deben realizarse en la cabeza o en la cola. La presencia de nodos ficticios asegura que las operaciones nunca se ejecutarán en la cabeza o la cola. Los nodos ficticios eliminan el dolor de cabeza de escribir comprobaciones condicionales para tratar con punteros nulos. Asegúrate de quitarlos al final de la operación.
A veces, el problema de las listas enlazadas se puede resolver sin almacenamiento adicional. Trata de tomar prestadas ideas del problema de listas enlazadas inversas.
Para la eliminación en listas vinculadas, puedes modificar los valores de los nodos o cambiar los punteros de los nodos. Es posible que debas mantener una referencia al elemento anterior.
Para particionar listas vinculadas, crea dos listas vinculadas separadas y vuelve a unirlas.
Los problemas de listas enlazadas comparten similitudes con los problemas de matrices. Piensa en cómo resolvería un problema de matriz y aplíquelo a una lista enlazada.

Los enfoques de dos punteros también son comunes para las listas enlazadas:

  • Obtener el kth del último nodo: tienes dos punteros, donde uno está k nodos delante del otro. Cuando el nodo de delante llega al final, el otro nodo está k nodos detrás.
  • Ciclos de detección: tienes dos punteros, donde un puntero aumenta el doble que el otro. Si los dos punteros se encuentran, significa que hay un ciclo.
  • Obtener el nodo medio: tienes dos punteros. Un puntero se incrementa el doble que el otro. Cuando el nodo más rápido llegue al final de la lista, el nodo más lento estará en el medio.

Es bueno acostumbrarse a las siguientes rutinas porque muchas preguntas de listas enlazadas utilizan una o más de estas rutinas en su solución.

  • Contar el número de nodos en la lista enlazada
  • Invertir una lista enlazada en su lugar
  • Encuentra el nodo medio de la lista enlazada usando punteros rápidos o lentos
  • Combinar dos listas juntas

Casos comunes

  • Nodo único
  • Dos nodos
  • La lista enlazada tiene un ciclo. Aclare con el entrevistador si puede haber un ciclo en la lista. Por lo general, la respuesta es no.

Preguntas de práctica

Matemáticas

Notas

Si el código implica división o módulo, recuerda verificar si hay división o módulo por 0.
Cuando una pregunta involucra "un múltiplo de un número", el módulo puede ser útil.
Verifica y maneja el desbordamiento y el subdesbordamiento si estás utilizando un lenguaje escrito como Java y C++. Como mínimo, menciona que es posible un desbordamiento o un desbordamiento y pregunta si necesitas manejarlo.
Considera números negativos y números de coma flotante. Esto puede sonar obvio, pero cuando estás bajo presión en una entrevista, muchos puntos obvios pasan desapercibidos.
Si la pregunta pide implementar un operador como potencia, raíz cuadrada o división, y debes ser más rápido que O(n), la búsqueda binaria suele ser el enfoque.

Algunas fórmulas comunes

  • Suma de 1 a N = (n+1) * n/2
  • Suma de GP = 2⁰ + 2¹ + 2² + 2³ + … 2^n = 2^(n+1)-1
  • Permutaciones of N = N! / (N-K)!
  • Combinaciones of N = N! / (K! * (N-K)!)

Casos comunes

  • División por 0
  • Desbordamiento y subdesbordamiento de enteros

Preguntas de práctica

Matriz

Notas

Una matriz es un arreglo bidimensional. Las preguntas que involucran matrices generalmente están relacionadas con la programación dinámica o el recorrido de gráficos.
Para preguntas que involucren programación transversal o dinámica, tienes que hacer una copia de la matriz con las mismas dimensiones que se inicializan a valores vacíos. Utiliza estos valores para almacenar el estado visitado o la tabla de programación dinámica. Familiarízate con esta rutina:

rows, cols = len(matrix), len(matrix[0])
copy = [[0 for _ in range(cols)] for _ in range(rows)
  • Muchos juegos basados en cuadrículas se pueden modelar como una matriz. Por ejemplo, Tic-Tac-Toe, Sudoku, Crossword, Connect 4 y Battleship. No es raro que se te pida que verifiques la condición ganadora del juego.
  • Para juegos como Tic-Tac-Toe, Connect 4 y Crosswords, la verificación debe realizarse vertical y horizontalmente. Un truco es escribir código para verificar la matriz de las celdas horizontales. Luego transpón la matriz, reutilizando la lógica utilizada para la verificación horizontal para verificar celdas originalmente verticales (que ahora son horizontales).
  • Transponer una matriz en Python es simple:
transposed_matrix = zip(*matrix)

Casos comunes

  • Matriz vacía. Verifique que ninguna de las matrices tenga una longitud de 0.
  • Matriz 1 x 1.
  • Matriz con una fila o columna

Preguntas de práctica

Recursión

Notas

La recursividad es útil para la permutación, porque genera todas las combinaciones y preguntas basadas en árboles. Debes saber cómo generar todas las permutaciones de una secuencia y cómo manejar los duplicados.
Recuerda siempre definir un caso base para que su recursión termine.

La recursividad utiliza implícitamente una pila. Por lo tanto, todos los enfoques recursivos se pueden reescribir iterativamente usando una pila.

Ten cuidado con los casos en los que el nivel de recurrencia es demasiado profundo y provoca un desbordamiento de la pila (el límite predeterminado en Python es 1000). Puedes obtener puntos de bonificación por señalar esto al entrevistador.

La recursividad nunca será una complejidad de espacio O(1) porque se trata de una pila, a menos que haya una optimización de llamada final (TCO). Averigua si su lenguaje elegido es compatible con TCO.

Preguntas de práctica

Cadenas

Notas

Por favor lee los siguientes tips en la secuencia. Aplica para las cadenas también.

Pregunta sobre el conjunto de caracteres de entrada y la distinción entre mayúsculas y minúsculas. Por lo general, los caracteres se limitan a caracteres latinos en minúsculas, por ejemplo, de la a a la z.
Cuando necesites comparar cadenas donde el orden no es importante (como un anagrama), puedes considerar usar un HashMap como contador.

Si tu lenguaje de programación tiene una clase Counter como Python, pregunta si puedes usar esta clase mejor.

Si necesitas mantener un contador de caracteres, un error común es decir que la complejidad del espacio requerida para el contador es O(n). El espacio requerido para un contador es O(1) no O(n). Esto se debe a que el límite superior es el rango de caracteres, que suele ser una constante fija de 26. El conjunto de entrada son solo caracteres latinos en minúsculas.
Las estructuras de datos comunes para buscar cadenas de manera eficiente son

Algunos algoritmos comunes son:

  • Rabin Karp, que realiza búsquedas eficientes de subcadenas, utilizando un hash rodante
  • KMP, que realiza búsquedas eficientes de subcadenas

Caracteres que no se repiten

Usa una máscara de bits de 26 bits para indicar qué caracteres latinos en minúsculas están dentro de la cadena.

mask = 0
for c in set(word):
  mask |= (1 << (ord(c) - ord('a')))

Para determinar si dos cadenas tienen caracteres comunes, realiza & en las dos máscaras de bits. Si el resultado es distinto de cero, mask_a & mask_b > 0 , entonces las dos cadenas tienen caracteres comunes.

Anagrama

Un anagrama es cambio de palabra o juego de palabras. Es el resultado de reorganizar las letras de una palabra o frase para producir una nueva palabra o frase, usando todas las letras originales una sola vez. En las entrevistas, por lo general solo nos molestan las palabras sin espacios en ellas.
Para determinar si dos cadenas son anagramas, existen algunos enfoques plausibles:

  • Ordenar ambas cadenas debería producir la misma cadena resultante. Esto toma el tiempo O (log n) y el espacio O (logn).
  • Si asignamos cada carácter a un número primo y multiplicamos cada número asignado, los anagramas deben tener el mismo múltiplo (descomposición en factores primos). Esto toma O(n) tiempo y O(1) espacio.
  • El conteo de frecuencia de caracteres ayudará a determinar si dos cadenas son anagramas. Esto también toma tiempo O(n) y espacio O(1).
    Palíndromo

Palíndromo

Un palíndromo es una palabra, frase, número u otra secuencia de caracteres que se lee igual hacia adelante y hacia atrás, como señora o coche de carreras.
Aquí hay formas de determinar si una cadena es un palíndromo:

  • Invierte la cuerda y debería ser igual a sí misma.
  • Tienes dos punteros al principio y al final de la cadena. Mueve los punteros hacia adentro hasta que se encuentren. En cualquier momento, los caracteres de ambos punteros deben coincidir.

El orden de los caracteres dentro de la cadena es importante, por lo que los HashMaps generalmente no son útiles.
Cuando una pregunta se trata de contar el número de palíndromos, un truco común es tener dos punteros que se muevan hacia afuera, alejándose del centro. Ten en cuenta que los palíndromos pueden tener una longitud par o impar. Para cada posición de pivote central, debes verificarla dos veces: una vez que incluye el personaje y otra sin el personaje.

  • Para las subcadenas, puedes terminar antes de tiempo una vez que no haya ninguna coincidencia.
  • Para las subsecuencias, use la programación dinámica ya que hay subproblemas superpuestos. Mira esta pregunta.

Casos comunes

  • Cadena vacía
  • Cadena de un solo carácter
  • Cadenas con un solo carácter diferente

Preguntas de práctica

Árboles

Notas

Un árbol es un grafo acíclico no dirigido y conexo.
La recursividad es un enfoque común para los árboles. Cuando notes que el problema del subárbol se puede usar para resolver el problema completo, intenta usar la recursividad.
Cuando utilices la recursividad, recuerda siempre verificar el caso base, generalmente donde está el nodo. null.

Cuando se te pida que atravieses un árbol por nivel, utiliza primero la búsqueda en profundidad.
A veces es posible que tu función recursiva necesite devolver dos valores.
Si la pregunta involucra la suma de nodos en el camino, asegúrate de verificar si los nodos pueden ser negativos.
Debes estar muy familiarizado con la escritura transversal recursiva en orden previo, en orden y posterior al pedido. Como extensión, desafíate a ti mismo escribiéndolos iterativamente.

A veces, los entrevistadores preguntan a los candidatos por el enfoque iterativo, especialmente si el candidato termina de escribir el enfoque recursivo demasiado rápido.

Árbol binario

El recorrido en orden de un árbol binario no es suficiente para serializar un árbol de forma única. También se requiere un recorrido previo o posterior al pedido.

Árbol de búsqueda binario (BST)

El recorrido en orden de un BST te dará todos los elementos en orden.
Estar muy familiarizado con las propiedades de un BST. Valida que un árbol binario sea un BST. Esto aparece con más frecuencia de lo esperado.
Cuando una pregunta implica un BST, el entrevistador suele buscar una solución que se ejecute más rápido que O(n).

Casos comunes

  • Árbol vacío
  • Un solo nodo
  • Dos nodos
  • Árbol muy inclinado (como una lista enlazada)

Preguntas de prácticas

Tries

Notas

Los Tries son un tipo específico de estructura de datos.  Como tal son árboles especiales (árboles de prefijos) que hacen que la búsqueda y el almacenamiento de cadenas sean más eficientes. Los intentos tienen muchas aplicaciones prácticas, como realizar búsquedas y proporcionar autocompletado. Es útil conocer estas aplicaciones comunes para que puedas identificar fácilmente cuándo un problema se puede resolver de manera eficiente utilizando un trie.
A veces, el procesamiento previo de un diccionario de palabras (dado en una lista) en un trie mejorará la eficiencia de la búsqueda de una palabra de longitud k, entre n palabras. La búsqueda se convierte en O(k) en lugar de O(n).

Estar familiarizado con la implementación, desde cero, de una clase Trie y sus métodosadd, remove , y search.

Preguntas de Práctica

Montículo

Notas

Si ves un k superior o inferior mencionado en la pregunta, generalmente es una señal de que se puede usar un montón para resolver el problema, como en Elementos frecuentes K principales.
Si necesitas los k elementos superiores, use un Min Heap de tamaño k. Iterar a través de cada elemento, empujándolo en el montón.

Siempre que el tamaño del almacenamiento dinámico exceda k, elimina el elemento mínimo. Eso garantizará que tengas los k elementos más grandes.

Preguntas de práctica

Conclusión

Las entrevistas de programación son difíciles. Pero afortunadamente, puedes mejorar tus resultados estudiando y practicando para ellas, así como haciendo entrevistas simuladas.
En resumen, para hacerlo bien en la codificación de entrevistas:

  1. Elige un lenguaje de programación
  2. Estudia los principios de las Ciencias de la Computación.
  3. Practica resolviendo ejercicios de algoritmos.
  4. Internaliza el qué hacer y el qué no en las entrevistas
  5. Practica haciendo entrevistas simuladas
  6. Ve a la entrevista a obtener el trabajo

Al seguir estos pasos, mejorarás tus habilidades de codificación de entrevistas y estarás un paso más cerca (o probablemente más) de conseguir el trabajo de sus sueños.

¡Mis mejores deseos!

Si te ha gustado este artículo, ¡compártelo con tus amigos!
También puedes seguirme en GitHub y Twitter.