Embercode: AI-powered software engineer course

1. What does this program print? ``

cpp
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> a = {3, 1, 2, 2, 4, 3, 5};
    vector<int> tail;
    for (int x : a) {
        auto it = lower_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) tail.push_back(x);
        else *it = x;
    }
    cout << "LIS length = " << tail.size() << endl;
    for (int t : tail) cout << t << " ";
    cout << endl;
}

``

LIS length = 3, then 1 2 5LIS length = 5, then 1 2 2 3 5LIS length = 4, then 1 2 3 5LIS length = 4, then 1 2 2 5

2. What does this program print? ``

cpp
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> t1, t2;
    for (int x : {2, 6, 6, 3, 7}) {
        auto it1 = lower_bound(t1.begin(), t1.end(), x);
        if (it1 == t1.end()) t1.push_back(x); else *it1 = x;
        auto it2 = upper_bound(t2.begin(), t2.end(), x);
        if (it2 == t2.end()) t2.push_back(x); else *it2 = x;
    }
    cout << "strict length = " << t1.size() << endl;
    cout << "non-strict length = " << t2.size() << endl;
}

``

strict length = 4, non-strict length = 4strict length = 3, non-strict length = 4strict length = 3, non-strict length = 3strict length = 2, non-strict length = 4

3. What is the time complexity of the length-only program for n numbers?

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

4. The lesson says the link method takes roughly how many steps for n = 200,000 numbers?

about 200,000about 18about 20 billionabout 3.6 million

5. For the input 1 2 0, what is the tail list after all three numbers are read?

1 2 00 21 20 1 2

LIS in n log n