Preguntas de entrevista de estructura de datos más frecuentes

¿Qué es una estructura de datos?
Una estructura de datos es una forma de organizar los datos para que los datos se puedan utilizar de manera eficiente. Diferentes tipos de estructuras de datos se adaptan a diferentes tipos de aplicaciones y algunas están altamente especializadas para tareas específicas. Por ejemplo, los árboles B son especialmente adecuados para la implementación de bases de datos, mientras que las implementaciones de compiladores suelen utilizar tablas hash para buscar identificadores. (Fuente: Página Wiki )

¿Qué son las estructuras de datos lineales y no lineales?

Lineal: Se dice que una estructura de datos es lineal si sus elementos forman una secuencia o una lista lineal. Ejemplos: array. Lista enlazada, pilas y colas
No lineal: se dice que una estructura de datos no es lineal si el recorrido de los Nodes es de naturaleza no lineal. Ejemplo: Gráfico y Árboles.

¿Cuáles son las diversas operaciones que se pueden realizar en diferentes estructuras de datos?

¿ Inserción ? Agregue un nuevo elemento de datos en la colección dada de elementos de datos.
Eliminación ? Eliminar un elemento de datos existente de la colección dada de elementos de datos.
transversal ? Acceda a cada elemento de datos exactamente una vez para que pueda ser procesado.
Buscando ? Averigüe la ubicación del elemento de datos si existe en la colección dada de elementos de datos.
¿ Ordenando ? Disponer los elementos de datos en algún orden, es decir, en orden ascendente o descendente en el caso de datos numéricos y en orden de diccionario en el caso de datos alfanuméricos.

¿En qué se diferencia una array de una lista enlazada?

El tamaño de las arrays es fijo y las listas vinculadas tienen un tamaño dinámico.
Insertar y eliminar un nuevo elemento en una array de elementos es costoso, mientras que tanto la inserción como la eliminación se pueden realizar fácilmente en las listas vinculadas.
El acceso aleatorio no está permitido en Linked Listed.
Se requiere espacio de memoria adicional para un puntero con cada elemento de la lista Vinculada.
Las arrays tienen una mejor localidad de caché que puede marcar una gran diferencia en el rendimiento.

¿Qué es Stack y dónde se puede utilizar?
Stack es una estructura de datos lineal en la que el orden LIFO (Último en entrar, primero en salir) o FILO (Primero en entrar, último en salir) para acceder a los elementos. Las operaciones básicas de la pila son: Push, Pop, Peek

Aplicaciones de la pila:

¿Qué es una cola, en qué se diferencia de la pila y cómo se implementa?
La cola es una estructura lineal que sigue el orden primero en entrar , primero en salir (FIFO) para acceder a los elementos. Principalmente, las siguientes son operaciones básicas en la cola: Enqueue, Dequeue , Front, Rear.
La diferencia entre las pilas y las colas está en la eliminación. En una pila, eliminamos el elemento agregado más recientemente; en una cola, eliminamos el elemento que se agregó menos recientemente. Tanto las colas como las pilas se pueden implementar mediante arrays y listas enlazadas.

¿Qué son las notaciones Infijo, Prefijo, Postfijo?

Notación infija: X + Y: los operadores se escriben entre sus operandos. Esta es la forma habitual en que escribimos expresiones. Una expresión como

   A * ( B + C ) / D

Notación de sufijo (también conocida como «notación de polaco inverso»): los operadores XY + se escriben después de sus operandos. La expresión infija dada arriba es equivalente a

   A B C + * D/

Notación de prefijos (también conocida como “notación polaca”): + X YLos operadores se escriben antes de sus operandos. Las expresiones anteriores son equivalentes a

   / * A + B C D

Conversión entre estas notaciones: Haga clic aquí

¿Qué es una lista enlazada y cuáles son sus tipos?

Una lista enlazada es una estructura de datos lineal (como arrays) donde cada elemento es un objeto separado. Cada elemento (es decir, Node) de una lista se compone de dos elementos: los datos y una referencia al siguiente Node. Tipos de lista enlazada:

Lista enlazada individualmente: en este tipo de lista enlazada, cada Node almacena la dirección o referencia del siguiente Node en la lista y el último Node tiene la siguiente dirección o referencia como NULL. Por ejemplo 1->2->3->4->NULL
Lista doblemente enlazada: aquí hay dos referencias asociadas con cada Node, una de las referencias apunta al siguiente Node y otra al Node anterior. P.ej. NULO<-1<->2<->3->NULO
Lista enlazada circular: la lista enlazada circular es una lista enlazada donde todos los Nodes están conectados para formar un círculo. No hay NULL al final. Una lista enlazada circular puede ser una lista enlazada circular sencilla o una lista enlazada circular doble. P.ej. 1->2->3->1 [El siguiente puntero del último Node apunta al primero]

¿Qué estructuras de datos se utilizan para BFS y DFS de un gráfico?

La cola se usa para BFS
La pila se utiliza para DFS. DFS también se puede implementar mediante la recursividad (tenga en cuenta que la recursividad también utiliza la pila de llamadas de función).

¿Se puede implementar el doble enlace usando una sola variable de puntero en cada Node?
Una lista doblemente enlazada se puede implementar utilizando un solo puntero. Consulte la lista enlazada XOR: una lista doblemente enlazada eficiente en memoria

¿Cómo implementar una pila usando la cola?
Una pila se puede implementar utilizando dos colas. Deje que la pila que se implementará sea ‘s’ y las colas que se usarán para implementar sean ‘q1’ y ‘q2’. La pila ‘s’ se puede implementar de dos maneras:

Método 1 (Al hacer que la operación de empuje sea costosa)
Método 2 (Al hacer que la operación emergente sea costosa) Consulte Implementar pila usando colas

¿Cómo implementar una cola usando una pila?
Una cola se puede implementar utilizando dos pilas. Deje que la cola que se implementará sea q y las pilas utilizadas para implementar q sean stack1 y stack2. q se puede implementar de dos maneras:

Método 1 (Al hacer que la operación enQueue sea costosa)
Método 2 (Al hacer que la operación de deQueue sea costosa) Consulte Implementar cola usando pilas

¿Qué estructura de datos se debe usar para implementar la memoria caché LRU?
Usamos dos estructuras de datos para implementar una caché LRU.

Queue que se implementa utilizando una lista doblemente enlazada. El tamaño máximo de la cola será igual al número total de fotogramas disponibles (tamaño de caché). Las páginas usadas más recientemente estarán cerca de la parte trasera y las páginas menos recientes estarán cerca de la parte delantera.
Un hash con número de página como clave y dirección del Node de cola correspondiente como valor. Consulte ¿Cómo implementar el esquema de almacenamiento en caché de LRU? ¿Qué estructuras de datos se deben utilizar?

¿Cómo verificar si un árbol binario dado es BST o no?
Si se ordena el recorrido en orden de un árbol binario, entonces el árbol binario es BST. La idea es simplemente hacer un recorrido en orden y mientras se realiza un seguimiento del valor clave anterior. Si el valor de la clave actual es mayor, continúe; de lo contrario, devuelva falso. Consulte Un programa para verificar si un árbol binario es BST o no para obtener más detalles.

Preguntas de lista enlazada

Preguntas sobre el recorrido del árbol

Convertir una DLL en un árbol binario en el lugar
Consulte Conversión en el lugar de una DLL ordenada a una BST equilibrada

Convertir árbol binario a DLL en el lugar
Ver Convertir un árbol binario dado a una lista doblemente enlazada | Conjunto 1 , Convertir un árbol binario dado en una lista doblemente enlazada | conjunto 2

Eliminar un Node determinado en una lista de enlaces simples
Dado solo un puntero a un Node que se eliminará en una lista de enlaces simples, ¿cómo se elimina?

Invertir una lista enlazada
Escriba una función para invertir una lista enlazada

Detectar bucles en una lista enlazada
Escriba una función C para detectar bucles en una lista enlazada .

¿Qué estructura de datos se utiliza para el diccionario y el corrector ortográfico?
¿Estructura de datos para diccionario y corrector ortográfico?