Embercode: AI-powered software engineer course

1. What does this program print? ``

python
def warmer_with_stack(temps):
    answer = [0] * len(temps)
    waiting = []
    for day, temp in enumerate(temps):
        while waiting and temp > temps[waiting[-1]]:
            earlier = waiting.pop()
            answer[earlier] = day - earlier
        waiting.append(day)
    return answer

print(warmer_with_stack([64, 60, 62, 58, 66, 61]))

``

[4, 1, 2, 1, 0, 0][1, 3, 2, 1, 0, 0][4, 2, 1, 1, 0, 0][4, 1, 2, 1, 0, 1]

2. What does this program print? ``

python
def span_with_stack(prices):
    span = [0] * len(prices)
    higher = []
    for day, price in enumerate(prices):
        while higher and prices[higher[-1]] <= price:
            higher.pop()
        span[day] = day + 1 if not higher else day - higher[-1]
        higher.append(day)
    return span

print(span_with_stack([10, 8, 9, 12, 11, 7]))

``

[1, 1, 1, 4, 1, 1][1, 2, 2, 4, 1, 1][1, 1, 2, 3, 1, 1][1, 1, 2, 4, 1, 1]

3. What is the time complexity of the stack method for the largest rectangle in a histogram, for n bars?

O(n squared), because each bar scans left and rightO(n log n), because the stack is kept sortedO(n), because each bar is pushed once and popped at most onceO(n cubed), because each pop scans the whole stack

4. On a row of n bars whose heights rise by one each step (1, 2, 3, ... n), about how many steps does the brute force method take?

n steps, one for each barabout n log n stepsabout n cubed stepsabout n squared divided by 2 steps

5. In the row {2, 1, 5, 6, 2, 3}, bar 2 (height 5) is popped by bar 4 (height 2). What width does bar 2 get?

1234

Histograms and daily temperatures