Mock Interveiw 1--1265. Print Immutable Linked List in Reverse

1265.py

// Print Immutable Linked List in Reverse
// immutable linked list, print out all values of each node in reverse

// APIs:
// ImmutableListNode: An interface of immutable linked list, you are given the head of the list.
// You need to use the following functions to access the linked list (you can't access the ImmutableListNode directly):
// ImmutableListNode.printValue(): Print value of the current node.
// ImmutableListNode.getNext(): Return the next node.

# getNext() -> ImmutableListNode or None

# (1) constant space complexity? 100 * number of items you can hold in memory
# 1, 2, 3, 4 .... 1_000_000_000
# n * m 
# first count the number of elements in your list O(n)
# divide the list into smaller chunck which you can process in memory O(n)
# you remember which how many chuncks you have and deal with them in revesre order O(n)

1 2 3 4 5 6 7 8 9 (9)
1 2 3 4
1 2
3 4
5 6 7 8 9
5 6
7 8
9
[1, 4, 7] O(n) 3
[1 2 3] [4 5 6] [7 8 9] O(n/m) + O(m) space and time (m * O(n/m)) = (n)
[3 2 1] [6 5 4] [9 8 7]

def print_reversed_linked_list(head: ImmutableListNode):
	def count_number_of_items(head: ImmutableListNode) -> int:
  	counter = 0
    node = head
    while node != None:
    	node = node.getNext()
      counter += 1
    return coutner
  
  number_of_items = counter_number_of_items(head)
  current_item = number_of_items
  printed_items = 0
  
  while printed_items != number_of_items:
  	counter = 0
    node = head
  	while counter != current_item:
  		node = node.getNext()
      counter +=1 
    node.printValue()
    current_item -= 1
    printe_items += 1
    
    
# (2) space complexity < O(N) , time complexity = O(N)?
# N elems in list
# divide into m chunks of smaller lists
# we can actually reverse one chunck in O(n/m) time with O(n/m) space
# n/m + m ==> O(log n) ; if m := log(n)