Skip to content

Instantly share code, notes, and snippets.

@bobfang1992
Created January 2, 2021 22:16
Show Gist options
  • Save bobfang1992/56ea78551d2700f38293fde9e02af24c to your computer and use it in GitHub Desktop.
Save bobfang1992/56ea78551d2700f38293fde9e02af24c to your computer and use it in GitHub Desktop.
Mock Interveiw 1--1265. Print Immutable Linked List in Reverse
// 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment