Embercode: AI-powered software engineer course

1. Union by size with no halving. Six items, 0 to 5, each start as their own set. The program then runs unite(0, 1), unite(2, 3) and unite(1, 3). When sizes are equal, the second root goes under the first, as in the lesson. What is the parent array now?

0 0 2 2 4 50 1 2 2 4 50 0 0 2 4 50 0 0 0 4 5

2. Predict the output. This program uses the basic structure with no size rule: unite links the root of its second item under the root of its first item. ``

cpp
#include <iostream>
#include <numeric>
#include <vector>

class Basic {
public:
    explicit Basic(int n) : parent_(n) { std::iota(parent_.begin(), parent_.end(), 0); }

    int find(int x) {
        while (parent_[x] != x) x = parent_[x];
        return x;
    }

    void unite(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra != rb) parent_[rb] = ra;
    }

    int depth(int x) const {
        int d = 0;
        while (parent_[x] != x) {
            x = parent_[x];
            ++d;
        }
        return d;
    }

private:
    std::vector<int> parent_;
};

int main() {
    Basic ds(5);
    for (int i = 1; i < 5; ++i) ds.unite(i, i - 1);
    std::cout << "depth of 0 = " << ds.depth(0) << '\n';
    std::cout << "depth of 4 = " << ds.depth(4) << '\n';
}

``

depth of 0 = 1 then depth of 4 = 0depth of 0 = 4 then depth of 4 = 0depth of 0 = 4 then depth of 4 = 4depth of 0 = 0 then depth of 4 = 4

3. Which statements about union by size and path halving are true? Pick all that apply.

Pick every answer that is true.

Union by size keeps every item's depth at most log2 nPath halving alone keeps the first find on a 10000-item chain short, so union by size is not neededPath halving points each item on a walk at its grandparent, so repeated finds get cheaperPath halving changes which root a find returns, which is why it must be paired with union by size

4. Which statements about the accounts merge program in this lesson are correct? Pick all that apply.

Pick every answer that is true.

Step 2 must unite every pair of emails in an account, because uniting only with the first email leaves some emails in separate setsTwo accounts merge only when they share an email address, never because they share a nameSorting the emails with the name included, using std::sort over the whole account, keeps the name firstSorting the groups by their first email before sorting the emails inside each group can pick the wrong first email

5. Predict the output. This loop gives each email an id the first time it is seen, the same way step 1 of accounts merge does. The line ends with a space, so ignore the trailing space. ``

cpp
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    std::unordered_map<std::string, int> idOf;
    const std::vector<std::string> emails = {"b@x", "a@x", "b@x", "c@x", "a@x"};
    for (const std::string& email : emails) {
        int next = static_cast<int>(idOf.size());
        auto [it, inserted] = idOf.try_emplace(email, next);
        std::cout << it->second << (inserted ? '+' : '=') << ' ';
    }
    std::cout << '\n';
}

``

0+ 1+ 2+ 0= 1=0+ 1+ 0+ 2+ 1+0+ 1+ 0= 2+ 1+0+ 1+ 0= 2+ 1=

Union-find