Jobs

Interviews

Discussions

Print Immutable Linked List in Reverse

Medium

Asked by:

8 views

Topics:

Linked ListsRecursion

You are given an immutable linked list, print its values in reverse.

You are given an interface:ImmutableListNode { public void printValue(); // print the value of this node. public ImmutableListNode getNext(); // return the next node. }

The linked list is represented by the head ImmutableListNode.

Example 1:

Input: head = [1,2,3,4]
Output: [4,3,2,1]

Example 2:

Input: head = [0,-4,-1,3,-5]
Output: [-5,3,-1,-4,0]

Example 3:

Input: head = [-2,0,6,4,4,-6]
Output: [-6,4,4,6,0,-2]

Constraints:

The length of the linked list is between [1, 1000].
The value of each node is between [-1000, 1000].

Follow up:

Could you solve it with:

O(n) time and O(1) space?
O(n) time and O(n) space?

Try coding it in LeetCode

Print Immutable Linked List in Reverse

Medium

Asked by:

8 views

Topics:

Linked ListsRecursion

You are given an immutable linked list, print its values in reverse.

You are given an interface:ImmutableListNode { public void printValue(); // print the value of this node. public ImmutableListNode getNext(); // return the next node. }

The linked list is represented by the head ImmutableListNode.

Example 1:

Input: head = [1,2,3,4]
Output: [4,3,2,1]

Example 2:

Input: head = [0,-4,-1,3,-5]
Output: [-5,3,-1,-4,0]

Example 3:

Input: head = [-2,0,6,4,4,-6]
Output: [-6,4,4,6,0,-2]

Constraints:

The length of the linked list is between [1, 1000].
The value of each node is between [-1000, 1000].

Follow up:

Could you solve it with:

O(n) time and O(1) space?
O(n) time and O(n) space?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Since the linked list is immutable, how will I access the nodes? Will I be provided with an API or interface to do so, and if so, can you describe it?
What is the expected behavior if the linked list is empty?
What is the maximum possible length of the linked list?
Can I assume the values stored in the linked list nodes are integers?
Are there any constraints on the space complexity I should be aware of?

Brute Force Solution

Approach

The challenge is to display a linked list backwards, but we can't change the list itself. The most basic way is to visit each element, store it, and then print the stored elements in reverse order of access.

Here's how the algorithm would work step-by-step:

Start at the beginning of the linked list.
Go through the list, one element at a time, and as you go, remember each element's value in the order you encounter them.
Once you reach the end of the linked list, you have a list of all the values in the original order.
Now, take the list of values you collected and print them out, but starting from the last value you remembered and going backwards to the first one.

Code Implementation

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

def print_immutable_linked_list_reverse_brute_force(head):
    node_values = []
    current_node = head

    # Traverse the linked list and store node values
    while current_node:
        node_values.append(current_node.data)
        current_node = current_node.next

    # Iterate backwards through the stored values
    # to print in reverse order.
    for i in range(len(node_values) - 1, -1, -1):
        print(node_values[i])

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list once to store all the node values. This traversal takes O(n) time, where n is the number of nodes in the list. Then, it iterates through the stored values in reverse order to print them, which also takes O(n) time. Thus, the dominant time complexity is O(n).

Space Complexity

O(N) – The algorithm stores each element's value in the order encountered while traversing the linked list. This implies the use of an auxiliary data structure, likely a list or array, to hold these values. Since the number of elements stored is directly proportional to the number of nodes (N) in the linked list, the space used by this auxiliary data structure grows linearly with N. Therefore, the space complexity is O(N).

Optimal Solution

Approach

Since we can't change the list itself, and we can only move forward, we need a way to visit the end before we start printing. The best way to do this is to dive deep into the list recursively, and then print as we come back out.

Here's how the algorithm would work step-by-step:

First, check if the current item in the list is valid.
If the item is valid, move to the next item in the list using the allowed 'next' function.
Keep doing this until you reach the end of the list.
Once you're at the end, start printing the value of the current list item.
Then, go back to the previous item in the list (which is where you were before calling the 'next' function).
Print the value of that item.
Keep going back up the list, printing the value of each item as you return from each 'next' call.

Code Implementation

class ImmutableListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def printValue(self):
        print(self.val)

    def getNext(self):
        return self.next

def printLinkedListInReverse(head):
    if head:
        next_node = head.getNext()

        # Recursively call function to reach end of the list
        printLinkedListInReverse(next_node)

        # Prints the current node's value after the recursive calls return
        head.printValue()

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses recursion to traverse the linked list. For a linked list of size n, the recursive function will be called n times, once for each node in the list. Each function call performs a constant amount of work (checking if the node is valid and calling the 'next' function or printing the node's value). Therefore, the time complexity is directly proportional to the number of nodes in the list, resulting in O(n) time complexity.

Space Complexity

O(N) – The dominant space usage in this algorithm comes from the recursive calls. Each call to the 'next' function, as described in the plain English explanation, adds a new frame to the call stack. Since we recurse until the end of the list, the maximum depth of this recursion, and therefore the number of stack frames, is directly proportional to the number of nodes in the linked list, N. Therefore, the auxiliary space used by the call stack is O(N).

Edge Cases

Case	How to Handle
Null Immutable Linked List	Return without any operation if the head is null.
Empty Immutable Linked List	Return without any operation if the list is empty (head is not null, but getNext() returns null on the first node).
Single Node Immutable Linked List	Print the value of the single node and return.
Immutable Linked List with duplicate values	The algorithm should correctly print all values, regardless of duplicates.
Extremely long Immutable Linked List (potential stack overflow with recursion)	Use an iterative approach (e.g., storing values in an array/list then printing in reverse) to avoid stack overflow issues.
Immutable Linked List containing maximum integer values	The printing operation should handle maximum integer values correctly without overflow.
Immutable Linked List containing negative values	The algorithm should correctly print negative values.
Memory constraints for large Immutable Linked Lists	Consider using a divide-and-conquer strategy by processing the list in chunks to avoid excessive memory usage.

Null Immutable Linked List

How to Handle:

Return without any operation if the head is null.

Empty Immutable Linked List

How to Handle:

Return without any operation if the list is empty (head is not null, but getNext() returns null on the first node).

Single Node Immutable Linked List

How to Handle:

Print the value of the single node and return.

Immutable Linked List with duplicate values

How to Handle:

The algorithm should correctly print all values, regardless of duplicates.

Extremely long Immutable Linked List (potential stack overflow with recursion)

How to Handle:

Use an iterative approach (e.g., storing values in an array/list then printing in reverse) to avoid stack overflow issues.

Immutable Linked List containing maximum integer values

How to Handle:

The printing operation should handle maximum integer values correctly without overflow.

Immutable Linked List containing negative values

How to Handle:

The algorithm should correctly print negative values.

Memory constraints for large Immutable Linked Lists

How to Handle:

Consider using a divide-and-conquer strategy by processing the list in chunks to avoid excessive memory usage.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Since the linked list is immutable, how will I access the nodes? Will I be provided with an API or interface to do so, and if so, can you describe it?
What is the expected behavior if the linked list is empty?
What is the maximum possible length of the linked list?
Can I assume the values stored in the linked list nodes are integers?
Are there any constraints on the space complexity I should be aware of?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the linked list.
Go through the list, one element at a time, and as you go, remember each element's value in the order you encounter them.
Once you reach the end of the linked list, you have a list of all the values in the original order.
Now, take the list of values you collected and print them out, but starting from the last value you remembered and going backwards to the first one.

Code Implementation

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

def print_immutable_linked_list_reverse_brute_force(head):
    node_values = []
    current_node = head

    # Traverse the linked list and store node values
    while current_node:
        node_values.append(current_node.data)
        current_node = current_node.next

    # Iterate backwards through the stored values
    # to print in reverse order.
    for i in range(len(node_values) - 1, -1, -1):
        print(node_values[i])

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if the current item in the list is valid.
If the item is valid, move to the next item in the list using the allowed 'next' function.
Keep doing this until you reach the end of the list.
Once you're at the end, start printing the value of the current list item.
Then, go back to the previous item in the list (which is where you were before calling the 'next' function).
Print the value of that item.
Keep going back up the list, printing the value of each item as you return from each 'next' call.

Code Implementation

class ImmutableListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def printValue(self):
        print(self.val)

    def getNext(self):
        return self.next

def printLinkedListInReverse(head):
    if head:
        next_node = head.getNext()

        # Recursively call function to reach end of the list
        printLinkedListInReverse(next_node)

        # Prints the current node's value after the recursive calls return
        head.printValue()

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null Immutable Linked List	Return without any operation if the head is null.
Empty Immutable Linked List	Return without any operation if the list is empty (head is not null, but getNext() returns null on the first node).
Single Node Immutable Linked List	Print the value of the single node and return.
Immutable Linked List with duplicate values	The algorithm should correctly print all values, regardless of duplicates.
Extremely long Immutable Linked List (potential stack overflow with recursion)	Use an iterative approach (e.g., storing values in an array/list then printing in reverse) to avoid stack overflow issues.
Immutable Linked List containing maximum integer values	The printing operation should handle maximum integer values correctly without overflow.
Immutable Linked List containing negative values	The algorithm should correctly print negative values.
Memory constraints for large Immutable Linked Lists	Consider using a divide-and-conquer strategy by processing the list in chunks to avoid excessive memory usage.

Null Immutable Linked List

How to Handle:

Return without any operation if the head is null.

Empty Immutable Linked List

How to Handle:

Return without any operation if the list is empty (head is not null, but getNext() returns null on the first node).

Single Node Immutable Linked List

How to Handle:

Print the value of the single node and return.

Immutable Linked List with duplicate values

How to Handle:

The algorithm should correctly print all values, regardless of duplicates.

Extremely long Immutable Linked List (potential stack overflow with recursion)

How to Handle:

Use an iterative approach (e.g., storing values in an array/list then printing in reverse) to avoid stack overflow issues.

Immutable Linked List containing maximum integer values

How to Handle:

The printing operation should handle maximum integer values correctly without overflow.

Immutable Linked List containing negative values

How to Handle:

The algorithm should correctly print negative values.

Memory constraints for large Immutable Linked Lists

How to Handle:

Consider using a divide-and-conquer strategy by processing the list in chunks to avoid excessive memory usage.