Niklaus Wirth, un informático suizo, escribió un libro en 1976 titulado Algoritmos + Estructuras de datos = Programas.
Más de 40 años después, esa ecuación sigue siendo cierta. Es por eso que los candidatos a ingeniería de software deben demostrar su comprensión de las estructuras de datos junto con sus aplicaciones.
Casi todos los problemas requieren que el candidato demuestre un conocimiento profundo de las estructuras de datos. No importa si te acabas de graduar (de una universidad o de un bootcamp de programación) o si tienes décadas de experiencia.
A veces, las preguntas de la entrevista mencionan explícitamente una estructura de datos, por ejemplo, "dado un árbol binario". Otras veces es implícito, como "queremos hacer un seguimiento de la cantidad de libros asociados con cada autor".
Aprender las estructuras de datos es esencial incluso si solo está tratando de mejorar en su trabajo actual. Comencemos por comprender los conceptos básicos.
¿Qué es una estructura de datos?
En pocas palabras, una estructura de datos es un contenedor que almacena datos en un diseño específico. Este "diseño" permite que una estructura de datos sea eficiente en algunas operaciones e ineficiente en otras. Su objetivo es comprender las estructuras de datos para que pueda elegir la estructura de datos más óptima para el problema en cuestión.
¿Por qué necesitamos estructuras de datos?
Dado que las estructuras de datos se utilizan para almacenar datos de forma organizada, y dado que los datos son la entidad más crucial en la informática, el verdadero valor de las estructuras de datos es claro.
Independientemente del problema que esté resolviendo, de una forma u otra tiene que lidiar con los datos, ya sea el salario de un empleado, los precios de las acciones, una lista de la compra o incluso una guía telefónica simple.
Según diferentes escenarios, los datos deben almacenarse en un formato específico. Tenemos un puñado de estructuras de datos que cubren nuestra necesidad de almacenar datos en diferentes formatos.
Estructuras de datos de uso común
Primero enumeremos las estructuras de datos más utilizadas y luego las cubriremos una por una:
- Matrices
- Pilas
- Colas
- Listas vinculadas
- Árboles
- Gráficos
- Tries (son efectivamente árboles, pero es bueno llamarlos por separado).
- Tablas hash
Matrices
Una matriz es la estructura de datos más simple y más utilizada. Otras estructuras de datos como pilas y colas se derivan de matrices.
Aquí hay una imagen de una matriz simple de tamaño 4, que contiene elementos (1, 2, 3 y 4).
A cada elemento de datos se le asigna un valor numérico positivo llamado Índice , que corresponde a la posición de ese elemento en la matriz. La mayoría de los lenguajes definen el índice inicial de la matriz como 0.
Los siguientes son los dos tipos de matrices:
- Matrices unidimensionales (como se muestra arriba)
- Matrices multidimensionales (matrices dentro de matrices)
Operaciones básicas en matrices
- Insertar: inserta un elemento en un índice determinado
- Obtener: devuelve el elemento en un índice determinado
- Eliminar: elimina un elemento en un índice determinado
- Tamaño: obtiene el número total de elementos de una matriz.
Preguntas más frecuentes de entrevistas de Array
- Encuentra el segundo elemento mínimo de una matriz
- Primeros enteros no repetidos en una matriz
- Fusionar dos matrices ordenadas
- Reorganizar valores positivos y negativos en una matriz
Pilas
Todos estamos familiarizados con la famosa opción Deshacer , que está presente en casi todas las aplicaciones. ¿Alguna vez se preguntó cómo funciona? La idea: almacena los estados anteriores de su trabajo (que se limitan a un número específico) en la memoria en tal orden que el último aparece primero. Esto no se puede hacer simplemente usando matrices. Ahí es donde Stack resulta útil.
Un ejemplo de la vida real de Stack podría ser una pila de libros colocados en orden vertical. Para obtener el libro que está en algún lugar en el medio, deberá quitar todos los libros colocados encima. Así es como funciona el método LIFO (Last In First Out).
Aquí hay una imagen de la pila que contiene tres elementos de datos (1, 2 y 3), donde 3 está en la parte superior y se eliminará primero:
Operaciones básicas de pila:
- Push: inserta un elemento en la parte superior
- Pop: devuelve el elemento superior después de eliminarlo de la pila
- isEmpty: devuelve verdadero si la pila está vacía
- Top: devuelve el elemento superior sin eliminarlo de la pila
Preguntas de entrevistas de Stack más frecuentes
- Evaluar expresión de postfijo usando una pila
- Ordenar valores en una pila
- Verifique los paréntesis balanceados en una expresión
Colas
Similar a Stack, Queue es otra estructura de datos lineal que almacena el elemento de manera secuencial. La única diferencia significativa entre Stack y Queue es que en lugar de usar el método LIFO, Queue implementa el FIFOmétodo, que es la abreviatura de First in First Out.
Un ejemplo perfecto de Cola en la vida real: una fila de personas esperando en una taquilla. Si llega una nueva persona, se unirá a la fila desde el final, no desde el principio, y la persona que esté al frente será la primera en obtener el boleto y, por lo tanto, dejar la fila.
Aquí hay una imagen de la cola que contiene cuatro elementos de datos (1, 2, 3 y 4), donde 1 está en la parte superior y se eliminará primero:
Operaciones básicas de Queue
- Enqueue (): inserta un elemento al final de la cola
- Dequeue (): elimina un elemento del inicio de la cola
- isEmpty (): devuelve verdadero si la cola está vacía
- Top (): devuelve el primer elemento de la cola
Preguntas más frecuentes de entrevistas en cola
- Implementar la pila usando una cola
- Invertir los primeros k elementos de una cola
- Genere números binarios del 1 al n usando una cola
Lista enlazada
Una lista enlazada es otra estructura de datos lineal importante que puede parecer similar a las matrices al principio, pero difiere en la asignación de memoria, la estructura interna y cómo se llevan a cabo las operaciones básicas de inserción y eliminación.
Una lista vinculada es como una cadena de nodos, donde cada nodo contiene información como datos y un puntero al nodo siguiente de la cadena. Hay un puntero de cabeza, que apunta al primer elemento de la lista vinculada, y si la lista está vacía, simplemente apunta a nulo o nada.
Las listas vinculadas se utilizan para implementar sistemas de archivos, tablas hash y listas de adyacencia.
Aquí hay una representación visual de la estructura interna de una lista vinculada:
A continuación se muestran los tipos de listas vinculadas:
- Lista unida (unidireccional)
- Lista doblemente enlazada (bidireccional)
Operaciones básicas de Linked List:
- InsertAtEnd : inserta un elemento determinado al final de la lista vinculada
- InsertAtHead : inserta un elemento dado al inicio / encabezado de la lista vinculada
- Eliminar : elimina un elemento determinado de la lista vinculada
- DeleteAtHead : elimina el primer elemento de la lista vinculada
- Buscar : devuelve el elemento dado de una lista vinculada
- isEmpty : devuelve verdadero si la lista vinculada está vacía
Preguntas más frecuentes de entrevistas de Linked List
- Invertir una lista vinculada
- Detectar bucle en una lista vinculada
- Devuelve el nodo N del final en una lista vinculada
- Eliminar duplicados de una lista vinculada
Gráficos
Un gráfico es un conjunto de nodos que están conectados entre sí en forma de red. Los nodos también se denominan vértices. Un par (x, y) se llama arista , lo que indica que el vértice x está conectado al vértice y . Un borde puede contener peso / costo, mostrando cuánto costo se requiere para atravesar desde el vértice xay .
Tipos de gráficos:
- Gráfico no dirigido
- Gráfico dirigido
En un lenguaje de programación, los gráficos se pueden representar de dos formas:
- Matriz de adyacencia
- Lista de adyacencia
Algoritmos comunes de desplazamiento de gráficos:
- Amplitud primera búsqueda
- Primera búsqueda en profundidad
Preguntas más frecuentes en las entrevistas de Graph
- Implementar la primera búsqueda de amplitud y profundidad
- Comprueba si una gráfica es un árbol o no
- Cuente el número de aristas en un gráfico
- Encuentra el camino más corto entre dos vértices
Árboles
Un árbol es una estructura de datos jerárquica que consta de vértices (nodos) y bordes que los conectan. Los árboles son similares a los gráficos, pero el punto clave que diferencia un árbol del gráfico es que no puede existir un ciclo en un árbol.
Los árboles se utilizan ampliamente en inteligencia artificial y algoritmos complejos para proporcionar un mecanismo de almacenamiento eficiente para la resolución de problemas.
Aquí hay una imagen de un árbol simple y terminologías básicas utilizadas en la estructura de datos del árbol:
Los siguientes son los tipos de árboles:
- Árbol n-ario
- Árbol equilibrado
- Árbol binario
- Árbol de búsqueda binaria
- Árbol AVL
- Árbol negro rojo
- 2-3 Árbol
De los anteriores, el árbol binario y el árbol de búsqueda binaria son los árboles más utilizados.
Preguntas más frecuentes en las entrevistas de Tree
- Encuentra la altura de un árbol binario
- Encuentre el k-ésimo valor máximo en un árbol de búsqueda binaria
- Encuentra nodos a una distancia "k" de la raíz
- Encuentra los antepasados de un nodo dado en un árbol binario
Trie
Trie, que también se conoce como "árboles de prefijos", es una estructura de datos en forma de árbol que demuestra ser bastante eficiente para resolver problemas relacionados con cadenas. Proporciona una recuperación rápida y se utiliza principalmente para buscar palabras en un diccionario, proporcionar sugerencias automáticas en un motor de búsqueda e incluso para enrutamiento IP.
Aquí hay una ilustración de cómo se almacenan en Trie tres palabras "arriba", "por lo tanto" y "sus":
Las palabras se almacenan de arriba hacia abajo, donde los nodos de color verde "p", "s" y "r" indican el final de "arriba", "así" y "sus" respectivamente.
Preguntas más frecuentes en las entrevistas de Trie:
- Contar el número total de palabras en Trie
- Imprime todas las palabras almacenadas en Trie
- Ordenar elementos de una matriz usando Trie
- Formar palabras de un diccionario usando Trie
- Construye un diccionario T9
Tabla de picadillo
El hash es un proceso que se utiliza para identificar objetos de forma única y almacenar cada objeto en un índice único precalculado llamado su "clave". Por lo tanto, el objeto se almacena en forma de un par "clave-valor", y la colección de dichos elementos se denomina "diccionario". Cada objeto se puede buscar usando esa clave. Existen diferentes estructuras de datos basadas en hash, pero la estructura de datos más utilizada es la tabla hash .
Las tablas hash generalmente se implementan mediante matrices.
El rendimiento de la estructura de datos hash depende de estos tres factores:
- Función hash
- Tamaño de la tabla hash
- Método de manejo de colisiones
Aquí hay una ilustración de cómo se asigna el hash en una matriz. El índice de esta matriz se calcula mediante una función hash.
Preguntas más frecuentes de entrevistas de Hashing
- Encuentra pares simétricos en una matriz
- Traza el camino completo de un viaje
- Encuentre si una matriz es un subconjunto de otra matriz
- Compruebe si las matrices dadas son disjuntas
Las anteriores son las ocho estructuras de datos principales que definitivamente debe conocer antes de comenzar una entrevista de codificación.
Si está buscando recursos sobre estructuras de datos para codificar entrevistas, consulte los cursos interactivos y basados en desafíos: Estructuras de datos para codificar entrevistas (Python, Java o JavaScript).
Para preguntas más avanzadas, consulte Coderust 3.0: preparación de entrevistas de codificación más rápida con desafíos interactivos y visualizaciones.
Si se está preparando para una entrevista de ingeniería de software, aquí tiene una hoja de ruta completa para prepararse para la codificación de entrevistas.
¡Buena suerte y feliz aprendizaje! :)