Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # given: values > 0
- # returns (min, pod) found element and it's value and position in input
- def find_min(vals):
- min_val, min_idx = None, -1
- for idx, val in enumerate(vals):
- if val < 0:
- continue
- if min_val is None or val < min_val:
- min_val = val
- min_idx = idx
- return min_val, min_idx
- def merge_lists(lists):
- result = []
- window = [None] * len(lists)
- indices = [0] * len(lists)
- # O(len(aws) + len(azure) + len(GCP))
- while True:
- # collect current value for each csp
- for c in range(len(lists)):
- curr_csp = lists[c]
- idx = indices[c]
- v = curr_csp[idx] if idx < len(lists[c]) else -1
- window[c] = v
- # find min v, increment idx for given list, ignore Nones
- min_val, min_idx = find_min(window)
- if min_val is None:
- break
- result.append(min_val)
- indices[min_idx] += 1
- return result
- aws = [34, 45, 47, 98]
- azure = [1, 56, 89]
- GCP = [2, 7, 78, 103, 204]
- # (input, expected) pairs
- cases = [
- ([aws, azure, GCP], [1, 2, 7, 34, 45, 47, 56, 78, 89, 98, 103, 204]),
- ([], []),
- ([[]], []),
- ([[1, 2, 3], []], [1, 2, 3]),
- ([[1, 2, 3]], [1, 2, 3]),
- ([[1, 2, 3], [1, 2, 3]], [1, 1, 2, 2, 3, 3]),
- ([[1, 2, 3], [4, 5, 6]], [1, 2, 3, 4, 5, 6]),
- ([[1, 20, 300], [2, 32, 302], [3, 33, 303]], [1, 2, 3, 20, 32, 33, 300, 302, 303]),
- ]
- for c in cases:
- input_, expected = c
- result = merge_lists(input_)
- print(result)
- assert result == expected
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement