Embercode: AI-powered software engineer course

1. What does this program print? ``

cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{3, 7, 7, 10};
    auto lo = std::lower_bound(v.begin(), v.end(), 7) - v.begin();
    auto hi = std::upper_bound(v.begin(), v.end(), 7) - v.begin();
    std::cout << lo << ' ' << hi << '\n';
}

``

1 21 32 30 3

2. What does this program print? ``

cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<long long> adds{1000, 7, 1000, 250};
    std::vector<long long> sorted = adds;
    std::sort(sorted.begin(), sorted.end());
    sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
    for (std::size_t i = 0; i < adds.size(); ++i) {
        auto rank = std::lower_bound(sorted.begin(), sorted.end(), adds[i]) - sorted.begin();
        std::cout << rank << (i + 1 < adds.size() ? ',' : '\n');
    }
}

``

1000,7,1000,2500,1,0,22,0,2,12,1,2,0

3. A query on the merge sort tree in lesson 11 visits about 2 log2 n nodes, and each node that lies fully inside the range does one binary search. What is the total time of one query?

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

4. Why does the lesson 10 program read every add line before it builds the sorted list of values?

So each value gets its final rank, because a value that arrives later could shift the ranks of values already placedSo the tree can be sized before the first add line is readSo lower_bound can skip the empty rangesSo std::unique runs in constant time

5. Which statements about the merge sort tree in lesson 11 are true?

Pick every answer that is true.

Each node stores the sorted list of the values in its segment.A parent's sorted list is made by sorting its values again from scratch.A count query runs one std::lower_bound on each node that lies fully inside the query range.Changing one array value is cheap, because only one node stores that value.A strict less-than count uses std::upper_bound on each node's list.

Compression and merge sort trees