Antes de comenzar a practicar para la entrevista de codificación, deberá repasar algunos de los fundamentos de la informática. A continuación se muestra una lista de los temas más importantes, en mi opinión, que debe analizar. Esta lista no es de ninguna manera completa.
Lenguaje de programación
Debe conocer muy bien el lenguaje de programación que elija. Tener fluidez en el idioma que elija le dará más tiempo para pensar sobre el problema real en lugar de pensar en cómo implementar la solución que tiene en mente. Los lenguajes más populares entre las compañías tecnológicas son Java, C / C ++ y Python.
Complejidad del tiempo de ejecución
La mayoría de las veces, el entrevistador le pedirá el tiempo de ejecución de su programa, lo que significa la gran complejidad de O, que es el peor análisis del tiempo de ejecución. En algunos casos, como cuando se trata de algoritmos populares que tienen un mal análisis de O grande (por ejemplo, clasificación rápida), también es útil conocer el tiempo promedio de ejecución.
Estructuras de datos
Listas vinculadas
Cada nodo en una lista vinculada tiene un elemento de datos y un puntero al siguiente nodo.
Una lista vinculada puede estar doblemente vinculada, lo que significa que cada nodo también tiene un puntero al nodo anterior.
Puede insertar un nuevo nodo en una lista vinculada en O (1) vez. Para buscar un elemento en una lista vinculada, necesita O (n) tiempo.
Arboles
Cada nodo en un árbol tiene un elemento de datos y una lista de punteros a sus hijos. La forma más popular de árboles son los árboles binarios, que tienen solo dos hijos.
En algunos casos, los nodos del árbol podrían tener un puntero a su nodo padre.
Una especialización popular de un árbol binario es el Árbol de búsqueda binaria (BST), donde el elemento de cada nodo debe ser mayor que cada elemento en su subárbol izquierdo y menor que cada elemento en su subárbol derecho.
El proceso de visitar cada nodo en un árbol se llama recorrido del árbol. Hay tres formas básicas de explorar un árbol: preordenar, ordenar y postordenar.
Tablas Hash
Se utiliza un mapa hash para asociar una clave con un valor. La ventaja de esta estructura de datos es que, en teoría, cada operación (inserción, eliminación, búsqueda) requiere un tiempo promedio de O (1).
Para insertar un nuevo elemento en el mapa hash, calcula el código hash de la clave. Si el código hash que se calculó ya existe en la estructura, entonces se utiliza una técnica de resolución de colisión. Las dos técnicas de resolución más populares son:
- Encadenamiento separado: cada depósito es independiente y se utiliza algún tipo de lista dinámica para cada índice de código hash.
- Direccionamiento abierto: los depósitos se examinan hasta que se encuentra un depósito desocupado.
¡Esta es quizás la estructura de datos más popular entre los entrevistadores!
Pilas
Una estructura de datos de último en entrar, primero en salir. Sería útil saber cómo implementar una pila desde cero utilizando matrices, ya que un entrevistador podría pedirle que cree una estructura de datos de pila modificada con una funcionalidad especial. Para todos los demás casos en los que necesite usar una pila, puede usar la implementación integrada de su idioma. Para usar una pila de cadenas en Java:
Pila pila = nueva Pila ();
Colas
Una estructura de datos Primero en entrar, primero en salir. Sería útil saber cómo implementar una cola desde cero utilizando matrices, ya que un entrevistador podría pedirle que cree una estructura de datos de cola modificada. Para usar una cola de cadenas en Java:
Queue queue = new LinkedList ();
Gráficos
Un conjunto de nodos que están conectados por enlaces. Se puede representar usando una matriz de adyacencia o una lista de adyacencia. Los entrevistadores pueden preguntar sobre la teoría de gráficos, ya que se usa ampliamente en muchos algoritmos populares.
Intentos
Una estructura de datos de árbol que generalmente contiene caracteres y tiene muchas aplicaciones en algoritmos de manipulación de cadenas. Por lo general, todos los descendientes de un nodo tienen un prefijo común de la cadena asociada con ese nodo y la raíz está asociada con la cadena vacía. Una aplicación popular de esta estructura de datos es la búsqueda en un diccionario de palabras (como una funcionalidad simple de autocompletar en un cuadro de texto).
Algoritmos
Es realmente raro que un entrevistador le pida que implemente un algoritmo específico complicado y largo (como Dijkstra, A *, etc.). Sin embargo, debe tener una idea de cómo funcionan, para qué se utilizan y para poder mantener una conversación básica cuando el tema involucra un algoritmo bien conocido. Además, se recomienda saber qué y cómo funciona la programación dinámica y poder reconocerla. Los siguientes son algoritmos populares más simples que se sugieren para saber cómo implementar, en caso de que el entrevistador le pida que implemente una modificación del algoritmo:
Búsqueda de amplitud primero (DFS)
Búsqueda de profundidad primero (BFS)
Mergesort
Ordenación rápida
Búsqueda binaria
OTRO
Estas son técnicas o conceptos que un entrevistador podría preguntarle, incluso solo en teoría.
Recursividad
Una técnica poderosa que se utiliza para resolver problemas informáticos y que se pregunta con frecuencia en entrevistas. Algunas veces simplifica la solución de un problema y produce código compacto. Recuerde que esta técnica requiere más memoria que una solución iterativa. Además, al escribir una solución recursiva, no olvide la condición de terminación de la recursividad.
Diseño orientado a objetos
Los entrevistadores pueden pedirle que describa los objetos básicos para un sistema dado. Por lo tanto, conocer los fundamentos de los principios orientados a objetos es crucial.
Pruebas
Los entrevistadores pueden pedirle que pruebe su propia solución. Debe saber cómo crear casos de prueba que cubran incluso los casos límite (es decir, haber ingresado algo inesperado). Además, conocer los principios básicos de las Pruebas de Unidad y mencionarlo sería realmente recomendable.
Programacion del sistema
Se pueden preguntar conceptos como roscado, cerraduras y mutex, especialmente si la empresa tiene una parte teórica en su entrevista.
Bitwise
Las operaciones binarias que utilizan operadores bit a bit pueden realizarse periódicamente, especialmente en empresas especializadas en software de nivel inferior.
Memoria de programa
La diferencia entre la pila y las áreas de memoria de montón y cuándo se usa cada una.
FINALMENTE
Mucha práctica con preguntas tipo entrevista.
Una buena forma de prepararse (conjunto de entrenamiento):
Descifrando la entrevista de codificación: 150 preguntas y soluciones de programación
Una buena forma de probar su preparación (Conjunto de prueba):
Coding Interview Ninja: 50 preguntas de codificación con soluciones Java para practicar en tu entrevista de codificación