algorithm_fridays_week05.py

# Required function
def merge_class_ages(class_a, class_b):
  if (class_a == None and class_b == None) or (type(class_a) != list and type(class_b) != list):
    return []

  if class_a == None and type(class_b) == list:
    return class_b

  if type(class_a) == list and class_b == None:
    return class_a
  
  class_a_length = len(class_a)
  class_b_length = len(class_b)

  if class_a_length == 0 and class_b_length == 0:
    return []

  # Handle edge cases
  if class_a_length == 0 and class_b_length != 0:
    return class_b

  if class_a_length != 0 and class_b_length == 0:
    return class_a
  
  # If the last age in class A is less than or equal to the first age in class B,
  # there's no need for further computation, since both list are already sorted
  if class_a[class_a_length - 1] <= class_b[0]:
    return class_a + class_b

  # If the last age in class B is less than or equal to the first age in class A,
  # there's no need for further computation, since both list are already sorted
  if class_b[class_b_length - 1] <= class_a[0]:
    return class_b + class_a
  
  return truncated_merge_sort(class_a, class_b)

# This function is the meat of the solution.
#
# This is a truncated merge sort because it doesn't do any spliting,
# seeing that both list are already sorted, it just merges them.
# 
# While there are 3 loops in here, this actually takes O(n) since
# we iterate through each element in both lists only once.
#
# Space complexity is O(n), we created a new array to hold the newly
# sorted elements which is double the space, but O(2n) is equal to O(n)
def truncated_merge_sort(list_1, list_2):
  i = j = 0
  new_list = []

  # One list will definitely be exhausted in this loop if uneven in length
  while i < len(list_1) and j < len(list_2):
    if list_1[i] < list_2[j]:
      new_list.append(list_1[i])
      i += 1
    else:
      new_list.append(list_2[j])
      j += 1

  # So we append whatever may be left from the unexhausted list
  while i < len(list_1):
    new_list.append(list_1[i])
    i += 1
  
  while j < len(list_2):
    new_list.append(list_2[j])
    j += 1
  
  return new_list

def test_case_1():
  class_a = [13, 15, 19]
  class_b = [11, 13, 18]
  merged_list = merge_class_ages(class_a, class_b)
  print(merged_list) # [11, 13, 13, 15, 18, 19]
  return merged_list

if __name__ == '__main__':
  assert test_case_1() == [11, 13, 13, 15, 18, 19], 'Test case fails'

Hello @toristejuFO, thank you for participating in Week 5 of #AlgorithmFridays.

This is a decent attempt at solving the problem and I like that your code is very readable with judicious use of comments. However, here is the one feedback I have for you:

• Your check on line 3 makes your solution fail some of the test cases; one of such is for when one of the input class arrays has a None value. Ideally your solution should return class_a if class_b has a None value and vice-versa but yours returns an empty list as shown below.

merge_class_ages(None, [1, 2, 3]); // should return [1, 2, 3] but yours returns []

Apart from that, your solution works for the other test cases. Kudos to you!

Let me know what you think.

Thanks for the feedback @meekg33k.

My thought initially was that, if one of the data types I received is not what I am expecting, I should return an empty list to signal to the user that something is wrong, so i.e they should at least make it and empty list.

I understand better now. I've updated now to handle it more properly. Please review. Thanks.