Important! These are all exam-level problems. Do not attempt these problems without a solid foundation in the subject and use them for exam practice.
1. Fill in the implementation below for sum_reverse, which takes in a linked list and changes every value to be that value + everything after it. This function should not return anything.
def sum_reverse(ll):
"""Change every value in ll to be the sum of the current value with everything after it.
linked = Link(3, Link(4, Link(5)))
>>>sum_reverse(linked)
>>>>linked.rest.rest.first
5
>>>linked.rest.first
9
>>>linked.first
12
"""
if ll.rest is Link.empty:
return
sum_reverse(ll.rest)
ll.first += ll.rest.firstdef sum_reverse(ll):
"""Change every value in ll to be the sum of the current value with everything after it.
linked = Link(3, Link(4, Link(5)))
>>>sum_reverse(linked)
>>>>linked.rest.rest.first
5
>>>linked.rest.first
9
>>>linked.first
12
"""
if _______ is Link.empty:
return
______________
ll.first += __________2. Implement every_other, which takes in a linked list and outputs a new linked list whichcontains every other element starting from the second.
def every_other(ll):
"""Output a new linked list which has every other element of ll starting from the second element.
>>>linked = Link(4, Link(3, Link(2, Link(1))))
>>>new_linked = every_other(linked)
>>>new_linked.first == linked.rest.first
True
>>>new_linked.rest.first == linked.rest.rest.rest.first
True
"""
if ll or ll.rest is Link.empty:
return Link.empty
return Link(ll.rest.first, every_other(ll.rest.rest))def every_other(ll):
"""Output a new linked list which has every other element of ll starting from the second element.
>>>linked = Link(4, Link(3, Link(2, Link(1))))
>>>new_linked = every_other(linked)
>>>new_linked.first == linked.rest.first
True
>>>new_linked.rest.first == linked.rest.rest.rest.first
True
"""
if _____________ is Link.empty:
return ___________
return ______________________________________3. Implement, in any way you'd like, hardcore_mapper, a function which takes in a linked list and a function which takes in one argument. Hardcore_mapper does one of two things; it apply the function to EVERY ELEMENT in the linked list if and only if it is a valid linked list, otherwise, it will do nothing. One quick note: Only the large linked list has a possibility of being invalid, any nested linked lists are guarenteed to be valid. Hint: Think about what makes a Linked List valid
def hardcore_mapper(fn, list):
"""Either apply the function to the current linked list or do nothing if the linked list is invalid.
>>>linked1 = Link(4, Link(2, Link(Link(3))))
>>>linked2 = Link(3, Link(2, 4))
>>>hardcore_mapper(linked1, lambda x: x + 4)
>>>hardcore_mapper(linked2, lambda x: x + 4)
>>>linked1.first
8
>>>linked1.rest.rest.first.first
7
>>>linked1.first == 3
True
>>>linked1.rest.rest == 4:
True
"""
if not validate(list):
return
if lst is Link.empty:
return
if type(lst.first) == Link:
hardcore_mapper(fn, lst.first)
else:
lst.first = fn(lst.first)
hardcore_mapper(fn, lst.rest)
def validate(lst):
if lst is Link.empty:
return True
elif lst.rest is not Link.empty and type(lst.rest) != Link:
return False
else:
return validate(lst.rest)
Disclaimer: This is NOT the only way to do this problem, try yours out in the interpreter if you would like. The idea was to both know the definition of linked lists along with how to deal with nested lists.def hardcore_mapper(ll, function):
"""Either apply the function to the current linked list or do nothing if the linked list is invalid.
>>>linked1 = Link(4, Link(2, Link(Link(3))))
>>>linked2 = Link(3, Link(2, 4))
>>>hardcore_mapper(linked1, lambda x: x + 4)
>>>hardcore_mapper(linked2, lambda x: x + 4)
>>>linked1.first
8
>>>linked1.rest.rest.first.first
7
>>>linked1.first == 3
True
>>>linked1.rest.rest == 4:
True
"""
"YOUR CODE HERE"