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.

    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:

    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.

    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:

    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:

    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:

    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.

    Etiquetas:

    Deja una respuesta

    Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *