Embercode: AI-powered software engineer course

1. What does this program print? ``

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

using namespace std;

constexpr long long INF = numeric_limits<long long>::max() / 4;
using Matrix = vector<vector<long long>>;

Matrix floydWarshall(int n, const vector<array<long long, 3>>& edges) {
    Matrix dist(n, vector<long long>(n, INF));
    for (int v = 0; v < n; ++v) dist[v][v] = 0;
    for (auto [a, b, w] : edges) dist[a][b] = min(dist[a][b], w);
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) {
                if (dist[i][k] == INF || dist[k][j] == INF) continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
    return dist;
}

int main() {
    auto d = floydWarshall(4, {{0, 1, 3}, {1, 2, 2}, {0, 2, 9}, {2, 3, -4}, {1, 3, 6}});
    cout << d[0][3] << '\n';
}

``

-4951

2. What does this program print? Each line of output is one line of cout. ``

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

using namespace std;

constexpr int NONE = -1;

vector<int> rebuildPath(const vector<int>& parent, int source, int target) {
    if (target != source && parent[target] == NONE) return {};
    vector<int> path;
    for (int v = target; v != NONE; v = parent[v]) path.push_back(v);
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    vector<int> parent = {NONE, 0, 0, 2, 1, NONE};
    auto path = rebuildPath(parent, 0, 4);
    cout << path.size() << ' ' << path.front() << ' ' << path.back() << '\n';
    cout << rebuildPath(parent, 0, 5).size() << '\n';
}

``

3 0 4 then 13 4 0 then 03 0 4 then 02 0 4 then 0

3. Someone moves the parent update in Dijkstra's loop above the distance check: ``

cpp
for (const Edge& e : g[v]) {
    r.parent[e.to] = v;
    if (d + e.weight < r.dist[e.to]) {
        r.dist[e.to] = d + e.weight;
        pq.push({r.dist[e.to], e.to});
    }
}

`` What goes wrong?

Nothing changes, because the parent is only read after the search endsA longer route can overwrite a vertex's parent, so the parent array no longer matches the distance tableThe heap gets duplicate entries, so the program crashes when it pops themThe distances become wrong, because the parent line also changes dist

4. This version of rebuildPath is supposed to return the route from the source to the target in order: ``

cpp
vector<int> rebuildPath(const vector<int>& parent, int source, int target) {
    if (target != source && parent[target] == NONE) return {};
    vector<int> path;
    for (int v = target; v != NONE; v = parent[v]) path.push_back(v);
    return path;
}

`



It is called with

parent = {NONE, 0, 1}` for the route from 0 to 2. What does it return?

2 1 0, the route backwards, because the list is never reversed0 1 2, because the loop already writes the list in order from the sourceAn empty list, because the target already has a parent2 1 0 followed by -1, because the loop writes NONE at the end

5. Floyd-Warshall runs its innermost body once for each combination of k, i and j. For a graph with 100 vertices, how many times does that innermost body run?

Type a number.

Paths and all-pairs