Embercode: AI-powered software engineer course

1. Predict the output of this program. ``

python
from bisect import bisect_left, bisect_right

values = [40, 10, 40, 1000]
sorted_values = sorted(set(values))
print(sorted_values)
print(bisect_left(sorted_values, 40))
print(bisect_left(sorted_values, 20))
print(bisect_left(sorted_values, 20), bisect_right(sorted_values, 40) - 1)
print(bisect_left(sorted_values, 2000))

``

[10, 40, 1000] 1 1 1 2 3[10, 40, 1000] 0 1 1 1 3[10, 40, 1000] 1 1 1 1 3[10, 40, 1000] 1 0 1 1 3

2. Predict the output of this program. ``

python
def merge(x, y):
    out = []
    i = j = 0
    while i < len(x) and j < len(y):
        if x[i] <= y[j]:
            out.append(x[i])
            i += 1
        else:
            out.append(y[j])
            j += 1
    out.extend(x[i:])
    out.extend(y[j:])
    return out

a = merge([2, 5], [6, 8])
b = merge([1, 7, 9], [3])
print(a)
print(b)
print(len(b))

``

[2, 5, 6, 8] [1, 7, 9, 3] 4[2, 5, 6, 8] [1, 3, 7, 9] 3[2, 6, 5, 8] [1, 3, 7, 9] 4[2, 5, 6, 8] [1, 3, 7, 9] 4

3. The sorted list is [5, 42, 900, 1000000000]. Which index does bisect_left(sorted, 6) return?

0124

4. Why can a merge sort tree count the values below 40 in a range, when a sum tree cannot?

A sum tree is too slow for ranges, so the merge sort tree loops over the range insteadA merge sort tree stores the largest value of each node, and that is enough to count values below 40A sum tree keeps one total per node, while a merge sort tree keeps a sorted list per node, so a binary search can count the values below a boundA merge sort tree sorts the query range on every call, and then counts the values below 40

5. Which statements about the coordinate compression and merge sort tree lessons are true? Pick all that apply.

Pick every answer that is true.

The list stored in an inner node of a merge sort tree is built by merging the two sorted lists of its childrenA fully covered node in a count query adds up its stored values one by one to get the countThe rank tree is sized by the number of distinct values, not by the largest value in the inputbisect_left returns -1 for a value that is not in the sorted list

Compression and merge sort trees