Las estructuras de datos más importantes que debe conocer sobre su entrevista de programación

Nicklaus Wirth, un informático suizo, escribió un libro en 1976 titulado Algorithms + Data Structures = Programs .

Después de más de 40 años, esta identidad sigue siendo válida. Esta es la razón por la cual los solicitantes de empleo que desean convertirse en programadores deben demostrar que conocen las estructuras de datos y pueden aplicarlas.

En casi todas las tareas, un candidato necesita una comprensión profunda de las estructuras de datos. Al mismo tiempo, no es tan importante si eres un graduado (graduado de una universidad o cursos de programación), o si tienes decenas de años de experiencia detrás de ti.

A veces, en las preguntas de la entrevista, se menciona directamente una u otra estructura de datos, por ejemplo, "dado un árbol binario". En otros casos, la tarea se formula de una manera más velada, por ejemplo, "usted necesita rastrear cuántos libros tenemos de cada autor".

Estudiar estructuras de datos es un negocio indispensable, incluso si solo está tratando de mejorar profesionalmente en su trabajo actual. Comencemos con lo básico.

Traducido a Alconost

¿Qué es una estructura de datos?

En resumen, una estructura de datos es un contenedor en el que la información se organiza de manera característica. Gracias a este "diseño", la estructura de datos será efectiva en algunas operaciones e ineficiente en otras. Nuestro objetivo es comprender las estructuras de datos de tal manera que pueda elegir entre ellas las más adecuadas para resolver el problema específico que enfrenta.

¿Por qué necesitamos estructuras de datos?

Dado que las estructuras de datos se utilizan para almacenar información de manera ordenada, y los datos son el fenómeno más importante en informática, el verdadero valor de las estructuras de datos es obvio.

No importa qué tipo de tarea esté resolviendo, de una forma u otra tendrá que lidiar con los datos, ya sea el salario de un empleado, cotizaciones de acciones, una lista de productos para ir a la tienda o un directorio telefónico regular.

Dependiendo del escenario específico, los datos deben almacenarse en un formato adecuado. Tenemos a nuestra disposición una serie de estructuras de datos que nos proporcionan diversos formatos.

Estructuras de datos comunes

Primero, enumeremos las estructuras de datos más comunes y luego analicemos cada una de ellas:

1. Matrices
2. Pilas
3. Colas
4. Listas vinculadas
5. Arboles
6. Cuenta
7. Burs (en esencia, estos también son árboles, pero deben considerarse por separado).
8. Tablas hash

Matrices

Una matriz es la estructura de datos más simple y más común. Otras estructuras de datos, como pilas y colas, se derivan de matrices.

Aquí se muestra 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 y corresponde a la posición de este elemento en la matriz. En la mayoría de los lenguajes de programación, los elementos de la matriz están numerados desde 0.

Hay dos tipos de matrices:

• Unidimensional (como se muestra arriba)
• Multidimensional (matrices en las que están incrustadas otras matrices)

Las operaciones de matriz más simples.

• Insertar: inserta un elemento en una posición con un índice dado
• Get: devuelve un elemento que ocupa una posición con un índice dado
• Eliminar: elimina el elemento con el índice especificado
• Tamaño: obtenga el número total de elementos en la matriz

Preguntas frecuentes de la entrevista

• Encuentra el segundo elemento mínimo de la matriz
• Encuentra enteros no repetidos en una matriz
• Combina dos matrices ordenadas
• Reordenar valores positivos y negativos en una matriz

Pilas

Todos conocen la famosa opción "Cancelar", que se proporciona en casi todas las aplicaciones. Alguna vez se preguntó cómo funciona? El significado es este: el estado anterior de su trabajo se guarda en el programa (el número de estados guardados es limitado), y se ubican en la memoria en este orden: el último elemento guardado va primero. Las matrices por sí solas no pueden resolver este problema. Aquí es donde la pila es útil.

La pila se puede comparar con una gran pila de libros. Si necesita un libro cerca del centro de la pila, primero tendrá que quitar todos los libros de arriba. Así es como funciona el principio LIFO (Último en llegar, primero en ir).

Parece una pila que contiene tres elementos de datos (1, 2 y 3), donde 3 está arriba; por lo tanto, se eliminará primero:

Las operaciones de pila más simples:

• Empujar: empuja un elemento sobre la pila 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
• Superior: devuelve el elemento superior sin eliminarlo de la pila

Entrevista Preguntas frecuentes sobre la pila

• Calcular la expresión de postfix usando stack
• Ordenar valores en la pila
• Verificar paréntesis balanceados en expresión

Colas

Una cola, como una pila, es una estructura de datos lineal en la que los elementos se almacenan en orden secuencial. La única diferencia significativa entre la pila y la cola es que en la cola, en lugar de LIFO, se aplica el principio FIFO (Primero en llegar, primero en ir).

Un ejemplo realista ideal de una cola: esta es la cola de clientes en la taquilla. Un nuevo comprador está al final de la línea, no al principio. El que está en la cola primero será el primero en comprar un boleto y dejarlo primero.

Aquí hay una imagen de una cola con cuatro elementos de datos (1, 2, 3 y 4), donde 1 va primero y sale primero de la cola:

Operaciones de cola simples

• Enqueue (): agrega un elemento al final de la cola
• Dequeue (): elimina un elemento del frente de la cola
• isEmpty () - Devuelve verdadero si la cola está vacía
• Arriba (): devuelve el primer elemento de la cola

Preguntas frecuentes de la entrevista

• Implementar una pila usando una cola
• Pague los primeros k artículos en la cola
• Genera números binarios del 1 al n usando una cola

Lista vinculada

Una lista vinculada es otra estructura de datos lineal importante que a primera vista se asemeja a una matriz. Sin embargo, una lista vinculada difiere de una matriz en la asignación de memoria, la estructura interna y la forma en que se realizan las operaciones básicas de inserción y eliminación.

Una lista vinculada se asemeja a una cadena de nodos, cada uno de los cuales contiene información: por ejemplo, datos y un puntero al siguiente nodo de la cadena. Hay un puntero de cabecera correspondiente al primer elemento en una lista vinculada, y si la lista está vacía, se dirige simplemente a nulo (nada).

Se implementan listas enlazadas, sistemas de archivos, tablas hash y listas de adyacencia.

Así es como puede visualizar la estructura interna de una lista vinculada:


Hay tipos de listas vinculadas:

• Lista de enlace único (unidireccional)
• Lista doblemente vinculada (bidireccional)

Las operaciones más simples con listas vinculadas son:

• InsertAtEnd : inserta el elemento especificado al final de la lista vinculada.
• InsertAtHead : inserta el elemento especificado al principio (desde el encabezado) de la lista vinculada
• Eliminar : elimina el elemento especificado de la lista vinculada.
• DeleteAtHead : elimina el primer elemento de una lista vinculada.
• Buscar : devuelve el elemento especificado de la lista vinculada.
• isEmpty : devuelve verdadero si la lista vinculada está vacía

Preguntas frecuentes de la entrevista:

• Pagar una lista vinculada
• Encuentra el bucle en la lista vinculada
• Devuelve el enésimo nodo desde la parte superior de la lista vinculada
• Eliminar valores duplicados de la lista vinculada

Cuenta

Un gráfico es un conjunto de nodos conectados entre sí en forma de red. Los nodos también se llaman vértices. El par (x, y) se llama borde, lo que significa que el vértice x está conectado al vértice y . Un borde puede tener peso / costo, un indicador que caracteriza lo costosa que es la transición del vértice x al vértice y.


Tipos de gráficos:

• Gráfico no dirigido
• Gráfico Orientado

En un lenguaje de programación, los gráficos pueden ser de dos tipos:

• Matriz de adyacencia
• Lista de adyacencia

Algoritmos transversales de gráficos comunes:

• Amplia búsqueda
• Búsqueda de profundidad

Preguntas frecuentes de la entrevista:

• Implemente búsquedas de amplitud y profundidad
• Comprueba si el gráfico es un árbol o no
• Cuenta el número de aristas en un gráfico
• Encuentra el camino más corto entre dos picos

Arboles

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, sin embargo, la diferencia clave entre un árbol y un gráfico es esta: no hay ciclos en un árbol.

Los árboles se usan ampliamente en el campo de la inteligencia artificial y en algoritmos complejos, actuando como un depósito efectivo de información para resolver problemas.

Aquí hay un diagrama de árbol simple y una terminología básica asociada con esta estructura de datos:


Existen los siguientes tipos de árboles:

• N-árbol
• Árbol equilibrado
• Árbol binario
• Árbol de búsqueda binaria
• Árbol AVL
• Ébano rojo
• 2-3 árboles

De los árboles anteriores, el árbol binario y el árbol de búsqueda binaria se usan con mayor frecuencia.

Preguntas frecuentes de entrevistas sobre árboles:

Encuentra la altura de un árbol binario
Encuentre el kth valor máximo en el árbol de búsqueda binario
Encuentra nodos ubicados "k" desde la raíz
Encuentra los antepasados ​​de un nodo dado en un árbol binario

Boro

El boro, también conocido como el "árbol de prefijos", es una estructura de datos en forma de árbol que es especialmente efectiva para resolver problemas de cadenas. Proporciona una recuperación rápida de datos y se utiliza con mayor frecuencia para buscar palabras en un diccionario, completar búsquedas e incluso para el enrutamiento IP.

Así es como se almacenan en el bosque las tres palabras "top" (top), "so" (por lo tanto) y "sus" (ellas):


Las palabras están ordenadas de arriba a abajo, y los nodos verdes "p", "s" y "r" completan, respectivamente, las palabras "arriba", "así" y "su".

Preguntas frecuentes sobre entrevistas en las entrevistas:

• Cuenta la cantidad total de palabras almacenadas en el bosque de pinos
  
• Mostrar todas las palabras almacenadas en el bosque.
  
• Ordenar elementos de matriz con boro
  
• Construir palabras de vocabulario con boro
  
• Crear diccionario T9
  

Tabla hash

El hash es un proceso utilizado para identificar objetos de forma exclusiva y almacenar cada objeto mediante un índice precalculado llamado "clave". Por lo tanto, el objeto se almacena como un valor clave, y una colección de dichos objetos se denomina diccionario. Cada objeto se puede buscar por su clave. Existen diferentes estructuras de datos basadas en el principio del hash, pero la mayoría de las veces se usa una tabla hash a partir de dichas estructuras.

Como regla general, las tablas hash se implementan utilizando matrices.

El rendimiento de una estructura de datos hash depende de los siguientes tres factores:

• Función hash
• Tamaño de tabla hash
• Método de procesamiento de colisión

A continuación se muestra cómo un hash se asigna a una matriz. El índice de esta matriz se calcula utilizando una función hash.

Entrevista Preguntas frecuentes sobre hash:

• Encuentra pares simétricos en una matriz
• Rastrea el camino completo
• Averigua si una matriz es un subconjunto de otra matriz
• Compruebe si las matrices son disjuntas

Lo anterior describe las ocho estructuras de datos más importantes que definitivamente necesita saber antes de ir a una entrevista de programación.

¡Buena suerte y aprendizaje interesante! :)

Sobre el traductor

El artículo fue traducido por Alconost.

Alconost localiza juegos , aplicaciones y sitios en 68 idiomas. Traductores en lengua nativa, pruebas lingüísticas, plataforma en la nube con API, localización continua, gestores de proyectos 24/7, cualquier formato de recursos de cadena.

También hacemos videos de publicidad y capacitación , para sitios que venden, imágenes, publicidad, capacitación, teasers, expliner, trailers de Google Play y App Store.

Más detalles