# 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