Preguntas de la entrevista de programación de listas vinculadas

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

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 archivo

Insertar 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 y node2 no son nulos
• node1.content es igual a node2.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 Branch

Echemos 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ínea currNode
• currNode.next (el siguiente node de la línea) apunta a prevNode, que actualmente es nulo
• prevNode ha cambiado y ahora apunta a currNode, cambiando sus lugares
• currNode ha cambiado y ahora apunta a nextNode que se estableció previamente en el siguiente node en línea para el currNode. Esto efectivamente avanza currNode 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 como currNode puntos a null y la cabeza se vuelve prevNode 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 al N-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 Heroku

1->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.js

printKthFromLast(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 y pointerB 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. Cuando pointerA 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.js

if 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.