Si está interesado en leer más sobre Programación de Preguntas de entrevistas en general, hemos compilado una lista extensa de estas preguntas, incluidas sus explicaciones, implementaciones, representaciones visuales y aplicaciones.
Introducción
Contenido
- 1 Introducción
- 2 Insertar y eliminar nodes
- 3 Comparación de cadenas representadas como listas vinculadas
- 4 Inversión de una lista
- 5 Seleccionar un node aleatorio
- 6 Encontrar el node medio
- 7 Elemento K del último node
- 8 Frecuencia de un número dado
- 9 Intersección de dos listas enlazadas
- 10 Recursos
- 11 Conclusión
Las listas enlazadas son una estructura de datos que representa una colección lineal de nodes. Una característica específica de las listas vinculadas es que el orden de los nodes no lo dicta su presencia en la memoria, sino los punteros que cada node tiene al siguiente node de la secuencia.
Representación de una lista vinculada
Existen varios tipos de listas vinculadas:
- Listas vinculadas individualmente – Una lista enlazada clásica, como la que se muestra en la imagen de arriba. Los nodes de las listas vinculadas individualmente contienen un puntero al siguiente node de la lista.
- Listas doblemente enlazadas – Este tipo de lista enlazada contiene un puntero al siguiente, pero también un puntero al node anterior de la lista.
- Listas enlazadas circulares – En lugar de contener un puntero nulo al final de la lista, el último node de estas listas contiene un puntero al primer node, haciéndolos circulares.
Dado que la lista vinculada es una de las estructuras de datos más básicas e importantes en informática, hemos compilado una lista de preguntas de entrevistas comunes con respecto a las listas vinculadas para este artículo. ¿Necesitas ayuda para estudiar para tu entrevista? Recomendamos probar un servicio como Problema de codificación diario, que le enviará por correo electrónico preguntas de práctica todos los días.
Insertar y eliminar nodes
Pregunta de entrevista
Elimine el cuarto elemento de la siguiente lista:
2->4->5->3->7->0
Inserte un elemento (6) en la 2a posición en la siguiente lista:
2->4->5->3->7->0
Explicación
Comencemos con una tarea simple: insertar un node en una lista. Hay algunas formas en las que alguien puede pedirle que haga esto:
- Insertar al principio de la lista vinculada
- Insertar al final de la lista vinculada
- Insertar en una posición determinada
Cubrámoslos uno por uno primero, antes de sumergirnos en el proceso de eliminación de un node.
Te puede interesar:Git: eliminar un archivoInsertar nodes
Para insertar un node al comienzo de una lista vinculada, simplemente necesitamos cambiar el encabezado actual de la lista vinculada al nuevo node que estamos insertando, y también apuntar el node insertado al encabezado anterior:
Echemos un vistazo al pseudocódigo:
Node newNode
if head is null
head = newNode
newNode.next = head
head = newNode
Para insertar un node al final de una lista vinculada, simplemente necesitamos cambiar el último puntero de null
al nuevo node:
Echemos un vistazo al pseudocódigo:
Node newNode
last = head;
while(last.next)
last = last.next
last.next = newNode1
Hacemos esto asignando el newNode
como encabezado, si la lista está vacía, e iterando hasta el final de la lista si no lo está, agregando nuestro node.
Y finalmente, para insertar un node en la posición dada, necesitamos establecer el siguiente node de la posición dada como el próximo node del nuevo node, y asignar el nuevo node como el próximo node de la posición dada:
Echemos un vistazo al pseudocódigo:
insertAtPosition(list, node, newNode)
if node is not null
newNode.next = node.next
node.next = newNode;
Eliminar nodes
Lo que tenemos que hacer aquí es recorrer la lista, haciendo un seguimiento del node anterior al node que queremos eliminar.
Al llegar al node que queremos eliminar, apuntamos el node anterior al node después del node objetivo y eliminamos el node objetivo:
removeNode(Node node)
prevNode = null
curr = head
while curr is not null
if prevNode is null
head = curr.next
if curr == node
prevNode.next = curr.next
curr = null
prevNode = curr
curr = curr.next
Comparación de cadenas representadas como listas vinculadas
Pregunta de entrevista
Escriba una función que pueda comparar dos cadenas, representadas como listas vinculadas, como:
Te puede interesar:Git: diferencia entre ‘git fetch’ y ‘git pull’List 1: S->T->A->C->K->A->B->U->S->E
List 2: S->T->A->C->K->O->V->E->R->F->L->O->W
La función puede devolver tres valores:
- 0 – Si las dos listas representan la misma cadena
- 1 – Si la primera lista es lexicográficamente mayor que la segunda lista
- -1 – Si la segunda lista es lexicográficamente mayor que la primera lista
Nota: «Lexicográficamente mayor» significa que una Cadena aparecería después de la otra Cadena según la posición del diccionario.
Si se implementa correctamente, el uso de esa función en este ejemplo en particular debería producir el siguiente resultado:
-1
Explicación
compare(node1, node2):
while node and node are not null AND node1.content is equal to node2.content
node1 = node1.next
node2 = node2.next
if node1 and node2 are not null
if node1.content > node2.content
return 1
else
return -1
if node1 is not null and node2 is null
return 1
if node2 is not null and node1 is null
return -1
return 0
list1 = Node('s')
list1.next = Node('t')
list1.next.next = Node('a')
list1.next.next.next = Node('c')
list1.next.next.next.next = Node('k')
list1.next.next.next.next.next = Node('a')
list1.next.next.next.next.next.next = Node('b')
list1.next.next.next.next.next.next.next = Node('u')
list1.next.next.next.next.next.next.next.next = Node('s')
list1.next.next.next.next.next.next.next.next.next = Node('e')
list2 = Node('s')
list2.next = Node('t')
list2.next.next = Node('a')
list2.next.next.next = Node('c')
list2.next.next.next.next = Node('k')
list2.next.next.next.next.next = Node('o')
list2.next.next.next.next.next.next = Node('v')
list2.next.next.next.next.next.next.next = Node('e')
list2.next.next.next.next.next.next.next.next = Node('r')
list2.next.next.next.next.next.next.next.next.next = Node('f')
list2.next.next.next.next.next.next.next.next.next.next = Node('l')
list2.next.next.next.next.next.next.next.next.next.next.next = Node('o')
list2.next.next.next.next.next.next.next.next.next.next.next.next = Node('w')
compare(list1, list2)
los while
bucle atraviesa ambas listas con dos condiciones adjuntas:
node1
ynode2
no son nulosnode1.content
es igual anode2.content
Esto significa que atravesará ambas listas, node por node, siempre que no lleguen al final de la lista y cada carácter coincida entre ellos. Si alguna de estas dos condiciones devuelve falso, el ciclo se rompe.
los if
declaración compruebe si ambos nodes no son null
:
- Si el contenido del primer node es mayor que el del segundo, devolvemos
1
- Si el contenido del segundo node es mayor que el del primer node, devolvemos
-1
Y los dos finales if
declaraciones simplemente devuelve 1
y -1
en consecuencia, si los tamaños de la lista no coinciden.
En última instancia, si pasa todas las comprobaciones, significa que las listas coinciden y representan la misma Cadena, devolviendo 0
.
Inversión de una lista
Pregunta de entrevista
Invierta la lista vinculada dada:
1->2->3->4->5
Explicación
Hay dos formas de abordar este problema: iterativo y recursivo.
Te puede interesar:Git: Switch BranchEchemos un vistazo al pseudocódigo iterativo detrás de la implementación:
Node prevNode, currNode, nextNode
prevNode = null
nextNode = null
currNode = head
while currNode is not null
nextNode = currNode.next
currNode.next = prevNode
prevNode = currNode
currNode = nextNode
head = prevNode
Para lograr esto, creamos tres nodes: prevNode
, nextNode
y currNode
. Ambos prevNode
y nextNode
apuntan a nulo, y currNode
está configurado para ser el encabezado actual de la lista vinculada.
Un bucle while se inicia con una condición de terminación del currNode
apuntando a nulo, y comienza el proceso de cambio:
nextNode
se convierte en el siguiente node de la líneacurrNode
currNode.next
(el siguiente node de la línea) apunta aprevNode
, que actualmente es nuloprevNode
ha cambiado y ahora apunta acurrNode
, cambiando sus lugarescurrNode
ha cambiado y ahora apunta anextNode
que se estableció previamente en el siguiente node en línea para elcurrNode
. Esto efectivamente avanzacurrNode
marcador a través de la Lista vinculada y comienza el proceso de nuevo.- Como el
currNode
el marcador se mueve, finalmente llega al final y todos los nodes se han invertido. La condición de terminación se cumple comocurrNode
puntos anull
y la cabeza se vuelveprevNode
que es el último node anterior en la lista vinculada. Dado que todas las referencias están invertidas, para completar la inversión, la cabeza también debe apuntar al ahora primer elemento de la secuencia.
Con eso fuera del camino, echemos un vistazo al pseudocódigo recursivo detrás de la implementación:
Node first, rest
Node recursiveReverse(Node current, previous)
if current.next is null
head = current
current.previous = previous
return
first = current.next
current.next = previous
recursiveReverse(first, current)
return head
Seleccionar un node aleatorio
Pregunta de entrevista
Devuelve un node aleatorio de una lista vinculada dada, asegurándose de que la probabilidad de obtener ese node específico es 1 / n donde n es el tamaño de la lista:
1->4->2->5->9->7
Explicación
Hay dos formas de abordar este problema y encontrar una solución:
- Recorriendo la lista y contando sobre la marcha. Luego lo atravesamos nuevamente, seleccionando todos y cada uno de los nodes con probabilidad 1 / n antes de generar un número aleatorio de 0 a
N-i
para el i-ésimo node y seleccionando el node si el número generado es igual a 0 o cualquier otro número fijo del 0 alN-i
rango.
Este enfoque tiene un gran revés: tenemos que recorrer la lista dos veces. Una vez para contarlo y otra vez para seleccionar un node aleatorio. En la mayoría de los casos, este enfoque no es deseado, por lo que recurrimos al otro:
- Muestreo de yacimientos – Seleccionamos el primer elemento, independientemente del tamaño de la lista, ya que no lo conocemos de antemano. Luego, recorremos la lista hacia adelante considerando todos y cada uno de los nodes subsiguientes para la selección con la probabilidad 1 / n donde n es el número de nodes ya visitados. De esta forma, nos aseguramos de que la probabilidad de elegir cualquier node de la lista sea 1 / n.
Nota: Esta es de hecho una versión simplificada de Muestreo de yacimientos, que se utiliza a menudo para seleccionar k elementos de una lista que contiene n elementos donde n es desconocido o muy grande. En este caso, también seleccionamos k elementos, que resulta ser un solo elemento.
Echemos un vistazo al pseudocódigo detrás de la implementación:
reservoirSample(stream, n, k)
i = 0
// initialize reservoir with k elements
reservoir[k]
// populate the reservoir with the wanted number of elements
for i < k
reservoir[i] = stream[i]
// iterate from the (k+1)th element to nth element
while i < n
// pick random number from 0 to i
j = randomNumber(i+1)
// if the random index is smaller than k, replace the element at that index with a new element from te stream
if j < k
reservoir[j] = stream[i]
Encontrar el node medio
Pregunta de entrevista
Número par de elementos
Encuentre el node del medio en la lista vinculada dada:
Te puede interesar:Implementación de una aplicación Node.js en Heroku1->2->3->4->5->6
Número desigual de elementos
Encuentre el node del medio en la lista vinculada dada:
1->2->3->4->5
Explicación
Esta pregunta puede tener dos versiones:
- La lista enlazada tiene un incluso número de elementos: buscamos los dos elementos intermedios ya que no hay un elemento intermedio definitivo, después de lo cual seleccionaremos el segundo elemento intermedio
- La lista enlazada tiene un desigual número de elementos: buscamos el elemento intermedio
Además, también tenemos dos enfoques:
- Cuente los nodes en la lista, divida el número entre 2 y devuelva el node en esa posición.
- Recorra la lista con dos punteros: el primero aumenta en 1, mientras que el segundo aumenta en 2. De esta manera, el segundo llegará al final de la lista cuando el primero esté en el medio.
Comencemos con el pseudo código detrás del primer enfoque:
int count
Node head
while head is not null
count+1
next = head.next
return count
list.getNode(count/2)
Con eso fuera del camino, exploremos el pseudocódigo detrás del segundo enfoque:
Node slow, fast
while(fast is not null && fast.next is not null)
fast = fast.next.next
slow = slow.next
return slow
Elemento K del último node
Pregunta de entrevista
Encuentre el quinto elemento del final de la lista vinculada:
1->2->4->6->7->8->5->9
Explicación
En el caso anterior, estamos buscando el node con el valor 6, ya que es el quinto node mirando hacia atrás desde el final de la lista.
Hay dos formas de llegar a este node:
- Depender de la longitud de la lista – (Longitud – n + 1) th node desde el principio.
- Usando punteros – Un puntero de referencia y un puntero principal. Ambos punteros comenzarán al principio de la lista, con el puntero de referencia desplazado por K nodes a lo largo de la lista. Luego, ambos punteros se repiten en 1 hasta que el puntero de referencia llega al final. Esto hace que el puntero principal se quede atrás del puntero de referencia por node K, apuntando al node que estamos buscando.
Veamos el pseudocódigo si confiamos en el longitud de la lista:
printKthFromLast(int k)
length = 0
Node node = head
// traverse the list and count the elements
while node is not null
node = node.next
length+1
// if the kth element is larger than the length, return the head
if length < k
return
node = head
// traverse the list until the element we're searching for and return it
for i = 0, i < length-k+1, i+1
node = node.next
return node
Veamos el pseudocódigo si confiamos en los punteros:
Te puede interesar:Ejecución de comandos de shell con Node.jsprintKthFromLast(int k)
Node main = head
Node reference = head
// since we're already on the head, the length is equal to 1
length = 1
if head is not null
while length < k
// checks if we've reached the end
if reference is null
return
reference = reference.next
length+1
while reference is not null
main = main.next
reference = reference.next
return main
Frecuencia de un número dado
Pregunta de entrevista
Cuente el número de veces que ha ocurrido un número en una lista vinculada determinada:
1->2->1->3->1->4->1->5
Explicación
Este es un problema común y simple de encontrar y abordar, y solo se necesitan un par de pasos para encontrar una solución:
- Declarar un contador
- Atraviese cada elemento de la lista y aumente el contador cada vez que un elemento sea igual al número cuya frecuencia estamos contando
- Devuelve la cuenta
Echemos un vistazo al pseudocódigo detrás de la implementación:
count(searchFor)
Node curr = head
count = 0
while curr is not null
if curr.data == searchFor
count++
curr = curr.next
return count
Implementar el pseudocódigo en cualquier idioma y ejecutarlo con esta lista produciría:
4
Intersección de dos listas enlazadas
Pregunta de entrevista
Dadas dos listas enlazadas, donde un node en la primera apunta a un node en la segunda, en un lugar aleatorio, encuentre el lugar de intersección de estas dos listas.
Explicación
Hay varios enfoques que puede tomar aquí:
- Fuerza bruta – Como su nombre lo indica, en forma de fuerza bruta, recorra toda la segunda lista, para cada node en la primera lista y verifique la intersección. Este enfoque lleva más tiempo, por lo que es muy ineficaz usarlo con listas grandes.
- Tabla de picadillo – Recorra la primera lista y almacene una dirección para cada node en un conjunto de hash. Luego recorra la segunda lista y si una dirección de la segunda lista ya está almacenada en el conjunto hash, es el node de intersección.
- Dos punteros – Nuevamente, usando dos punteros, podemos encontrar el node de intersección. Inicializar dos punteros,
pointerA
ypointerB
donde ambos punteros recorren la lista paso a paso. Una lista debe ser más pequeño que el otro. Si tuvieran el mismo número de nodes y estuvieran conectados al final, sería simplemente una lista enlazada individualmente. Si tienen el mismo número de nodes, la lista que se conecta a la otra lista antes del final se convierte en la lista «más grande» ya que tiene más nodes individuales. CuandopointerA
llega al final de la lista, redirigirlo al encabezado de la segunda lista. Si en algún punto estos dos punteros se encuentran, ese es el node de intersección. Si es un poco confuso, sería mejor echar un vistazo a la animación adjunta a continuación:
Primero echemos un vistazo al pseudocódigo detrás del fuerza bruta Acercarse:
Node list1_curr = head1
Node list2_curr = head2
while list1_curr is not null
while list2_curr is not null
if list1_curr == list2_curr
return list1_curr
Ahora, echemos un vistazo al pseudocódigo detrás del tabla de picadillo Acercarse:
getIntersectionHashTables(Node head1, Node head2)
nodes = hashSet
Node pointerA = head1
while pointerA is not null
nodes.add(pointerA)
pointerA = pointerA.next
if nodes is empty
return null
Node pointerB = head2
while pointerB is not null
if nodes contain pointerB
return pointerB
pointerB = pointerB.next
return null
Este también es bastante simple:
- Tenemos dos cabezas para cada lista vinculada.
- Agregamos todos los nodes de la primera lista en un conjunto hash y luego recorremos la segunda lista, verificando si la tabla hash ya contiene dicho node.
- Si la tabla hash contiene el node, se devuelve y si no,
null
es regresado.
Finalmente, echemos un vistazo a dos punteros Acercarse:
Te puede interesar:Publicación y suscripción a mensajes de AWS SNS con Node.jsif pointerA is null and pointerB is null
return null
while pointerA is not pointerB
pointerA = pointerA.next
pointerB = pointerB.next
if pointerA is null
pointerA = headB
if pointerB is null
pointerB = headA
return pointerA
Recursos
Si está buscando una mejor manera de practicar este tipo de preguntas de entrevistas de programación, así como otras, le recomendamos que pruebe un servicio como Problema de codificación diario. Te enviarán un nuevo problema para resolver todos los días, todos los cuales provienen de las mejores empresas. También puede obtener más información aquí si desea más información.
Conclusión
En este artículo, hemos cubierto las preguntas de entrevistas comunes relacionadas con las listas vinculadas.
Nuevamente, si está interesado en leer más sobre Programación de preguntas de entrevista en general, hemos compilado una lista extensa de estas preguntas, incluidas sus explicaciones, implementaciones, representaciones visuales y aplicaciones.