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 *