Embercode: AI-powered software engineer course

1. What does this program print? ``

python
import bisect


def tails(nums):
    tails = []
    for x in nums:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return tails


print(tails([5, 1, 2, 2, 3]))

``

[5, 1, 2, 3][1, 2, 3][1, 2, 2, 3][5, 2, 3]

2. What does this program print? ``

python
import bisect


def tails(nums):
    tails = []
    for x in nums:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return tails


print(tails([10, 20, 3, 15, 4, 16]))

``

[10, 20, 16][3, 15, 16][3, 4, 16][3, 4, 15, 16]

3. For a list of 100,000 numbers, about how many halving steps does one binary search on the tails list take?

About 1,000About 50,000About 100,000About 17

4. What is the time complexity of the tails method from this lesson for a list of n numbers?

O(n log n)O(n)O(n^2)O(2^n)

5. Which statement about the values in the tails list is true?

They are always the largest values seen so far in the inputThey stay in increasing order from left to right, which lets binary search workThey always form a real increasing subsequence of the inputThey are kept in the same order as the input numbers

LIS in n log n