mgrzybek

Untitled

Dec 1st, 2021 (edited)
590
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # given: values > 0
  2.  
  3. # returns (min, pod) found element and it's value and position in input
  4. def find_min(vals):
  5.     min_val, min_idx = None, -1
  6.     for idx, val in enumerate(vals):
  7.         if val < 0:
  8.             continue
  9.  
  10.         if min_val is None or val < min_val:
  11.             min_val = val
  12.             min_idx = idx
  13.  
  14.     return min_val, min_idx
  15.  
  16.  
  17. def merge_lists(lists):
  18.     result = []
  19.     window = [None] * len(lists)
  20.     indices = [0] * len(lists)
  21.  
  22.     # O(len(aws) + len(azure) + len(GCP))
  23.     while True:
  24.         # collect current value for each csp
  25.         for c in range(len(lists)):
  26.             curr_csp = lists[c]
  27.             idx = indices[c]
  28.             v = curr_csp[idx] if idx < len(lists[c]) else -1
  29.             window[c] = v
  30.  
  31.         # find min v, increment idx for given list, ignore Nones
  32.         min_val, min_idx = find_min(window)
  33.  
  34.         if min_val is None:
  35.             break
  36.  
  37.         result.append(min_val)
  38.         indices[min_idx] += 1
  39.     return result
  40.  
  41.  
  42. aws = [34, 45, 47, 98]
  43. azure = [1, 56, 89]
  44. GCP = [2, 7, 78, 103, 204]
  45.  
  46. # (input, expected) pairs
  47. cases = [
  48.     ([aws, azure, GCP], [1, 2, 7, 34, 45, 47, 56, 78, 89, 98, 103, 204]),
  49.     ([], []),
  50.     ([[]], []),
  51.     ([[1, 2, 3], []], [1, 2, 3]),
  52.     ([[1, 2, 3]], [1, 2, 3]),
  53.     ([[1, 2, 3], [1, 2, 3]], [1, 1, 2, 2, 3, 3]),
  54.     ([[1, 2, 3], [4, 5, 6]], [1, 2, 3, 4, 5, 6]),
  55.     ([[1, 20, 300], [2, 32, 302], [3, 33, 303]], [1, 2, 3, 20, 32, 33, 300, 302, 303]),
  56. ]
  57.  
  58. for c in cases:
  59.     input_, expected = c
  60.     result = merge_lists(input_)
  61.     print(result)
  62.     assert result == expected
  63.  
RAW Paste Data