Linked List Interview Challenges for Major Tech Companies: Amazon, Facebook, Apple, Microsoft

Question 1 : Remove Duplicates

Write a function to remove duplicates from an unsorted linked list. Input 1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 4 -> 5 Output 1 -> 2 -> 3 -> 4 -> 5

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    def __str__(self):
        temp_node = self.head
        result = ''
        while temp_node is not None:
            result += str(node.value)
            if temp_node.next is not None:
                result += ' -> '
            temp_node = temp_node.next
        return result

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.length += 1

    def remove_duplicates(ll):
        # TODO

Answer : We will assign a pointer that will traverse through the linked list. The we will check if the next node is same as the pointer node or not. If yes, we update the pointer nodes next reference to next node's next node. If not, we simply traverse. At the end, we make a prev node and update the tail to the prev node.

from linkedlist import LinkedList
def remove_duplicates(ll):
    # TODO
    if ll.head is None: 
        return
    current_node = ll.self #will be used to traverse the list.
    prev_node = None  #used to keep track of the node before current_node
    while current_node: 
         runner = current_node 
         while runner.next: 
            if runner.next.value == current_node.value :
                runner.next = runner.next.next
            else: 
                runner = runner.next 
         prev_node = current_node 
         current_node = current_node.next 
    ll.tail = prev_node

• runner = current_node - Inside the while loop, runner is set to the current_node. runner will be used to look ahead in the list for duplicates.

• while runner.next: - This is a nested while loop that runs as long as runner.next is not None. This loop is used to check for duplicates of current_node's value in the remaining list.

• if runner.next.value == current_node.value: - This is a condition to check if the next value in the list (after runner) is the same as the value of current_node.

• prev_node = current_node - After we have checked all the remaining list for duplicates of current_node, we set prev_node to current_node

• current_node = current_node.next - We move current_node one step forward in the list.

• ll.tail = prev_node - After the outer while loop ends (meaning we have traversed the entire list), prev_node is the last node in the list. We set ll.tail to prev_node, effectively updating the tail of the LinkedList.

The time and space complexity

Time : Since the function has a nested loop that, in the worst case, runs for N^2 iterations, the overall time complexity is O(N^2), where N is the number of nodes in the LinkedList.

Space : O(1)

Question 2 : Return nth to last

If n is 3, we need to return the 3rd element to the last node. The logic here is, we make two pointer and set them to head. Our code will take two params - list, and n.

def nthToLast(li, n):
    pointer1 = li.head 
    pointer2 = li.head 
    for i in range(n): 
        if pointer2 is None: 
            return None
        pointer2 = pointer2.next
        while pointer2: 
            pointer1 = pointer1.next 
            pointer2 = pointer2.next 
        return pointer 1

Time complexity: O(N), Space complexity : O(1)

Question 3 : Partition

Write a code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

from LinkedList import LinkedList
def partition(li,x): 
    current_node = li.head 
    li.tail = li.head 
    while current_node: 
        nextNode = current_node.next 
        if current_node.value <= x: 
            current_node.next = li.head 
            li.head = current_node 
        else: 
            li.tail.next = current_node 
            li.tail = current_node 
        current_node = current_node.next 
    if li.tail.next is not None: 
        li.tail.next = None

Time complexity: O(N), Space complexity : O(1)

Question 4 : Sum Lists

you have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, 1's digit is at the head of the list. Write a function that adds two numbers and returns the sum as a linked list.

Code:

from LinkedList mport LinkedList
    def sumList(liA, liB): 
    n1 = liA.head 
    n2 = liB.head
    carry = 0 
    li = LinkedList()
    while n1 or n2: 
        result = carry 
        if n1: 
            result += n1.value 
            n1 = n1.next 
        if n2: 
            result += n2.value 
            n2 = n2.next 
        li.add(int(result % 10))
        carry = result / 10 
    return li

Time complexity: O(N), Space complexity : O(N), because here we are creating another LinkedList.