OS & Memory

Walk a Page Table

Difficulty

Asked at Hudson River Trading, Jump Trading

Read the problem, hints and solution here. The editor needs a bigger screen: open this page on a laptop to write and run your code.

Available in Python and C++. You are solving it in C++. Switch to Python

xxxxxxxxx xxxxxxxxx(xxxxxx, xxxx, xxxxxxxx, xxxxx_xxxx, xxxxxx_xxxx), xxxxx xxxxx xxxxxxx xxxxxxxxx xxxx xxxxxxxx xxxx xx xxxxxxx x xxxxx-xxxxx xxxx xxxxx. xxxxx xxxxxxx x xxxxxxx xxxxxxxxxxxx xx x xxxxxxx xxxxxxx. xxxxxxxxxxx xx xxxxx xxxxxxx x xxxx xxxx xxx xxxxxx xxxxx xxx xxx xxxxxxxx xxxxx: xxxx xxxxxx xx xxx-xx, xxxx xxxxx x xxxxx xx xxx xxxxxxx, xxxx xxxxx xxxxxxxx xx xxx xxxxx xxxx xxxxx xxx xxxx xxxxx xxxx. xxx xxx xxxx xxxx xx xxxxxxxx xx xxxxx xxxxxx xxxxxx, xxxxx xx xxx xxx xxx xxxxxx xxx xxx x xxxx xxxxx xx xxxxxx. xxx::xxxxxx<xxx::xxxx<xxx::xxxxxx, xxxxxxxx xxxx xxxx>> xxxxxxxxx( xxxxx xxx::xxxxxxxxx_xxx<xxxxxxxx xxxx xxxx, xxx::xxxxxxxxx_xxx<xxxxxxxx xxxx xxxx, xxx::xxxxx<xxxxxxxx xxxx xxxx, xxxx, xxxx, xxxx>>>& xxxxxx, xxxxxxxx xxxx xxxx xxxx, xxxxx xxx::xxxxxx<xxx::xxxx<xxxxxxxx xxxx xxxx, xxxx>>& xxxxxxxx, xxxxx xxx::xxxxxx<xxx>& xxxxx_xxxx, xxx xxxxxx_xxxx); xxxxxx: xxxx x xxxxx xx xxx xxxxx, xxx x xxxxx xxxx xx xxxxx xx xx xxxxx {xxxxxx, xxxxxxx, xxxxxxxx, xxxx}. xxxx: xxx xxxxx xxxxxx xx xxx xxx-xxxxx xxxxx. xxxxxxxx: {xxxxxxx_xxxxxxx, xx_xxxxx} xxxxx. xxxxx_xxxx: xxx xxxx xxxxxxx xxxx xxxxx xxxx xxxxx, xxx xxxxx xxxxx. xxxxxx_xxxx: xxx xxxx xxxx xxx xxxx xxxx xxx xxx xxxxxx xxxxxx x xxxx. x xxxxxxx xxxxxxx xx xxxxx xxxxxx xxxxxx xxxx xxx xxxxxxx, xxxx xxxxxxxxxxx xxxxx: xxx xxxxx x xxxxx xxxx xx xxx xxx, xxxx xxxxx x, xxx xx xx xxxx xx xxx xxxxxx xx xxx xxx xxxx. xx xxxx xxxxx, xxxxx xxxx xxxxx'x xxxxx: xx xxxxx, xx xx xxxxx xxxx xxxxxxx xxxxx: xxx xxxxxx xx x xxxxx xx xxxx xxxxx. xx_xxxxx xxx xxx xxxxx xx xxx xxxxxxxx: xxx xxxxxx xx x xxxxxxxxxx xxxxx xx xxxx xxxxx. xxxx xx xxxx, xx xxxx xx xxx xxxx xxxxx: xxx xxxx xxxxx xxxx. xxxxx xxx xxxx xxxxx xxxx xxxxxxx xxx xxxxxxxxx xxxxxx xxxxx xxx xxxxxx, xx xxx xxxxxxxx xxxxxxx xx xxxxxx xxxxxxx xx xx xxxx xxxx xxxx, xxxx xxx xxx xxxx xx xxx xxxxxxx xxxxxxx xxxxxxxxxx. xxx xxxxxx xx xx xxxx xxxx xxxxxxxx xxxxxxx. xxxxxxxxx xxxxxx xxxxxx xxxx xx xxx xxxx xxxxx. xxxxxx xxx xxxxxx xxx xxxxxxx, xx xxxxx. x xxxxxx xx {"xx", xxxxxxxx}, {"xxxxx", xxxxx} xx {"xxxxxxx", xxxxx}. xxxxxxxx xxxx xxx xxxxxx xx x xxxx xxxx x x-xxx xxxxxx, xx x-xxx xxxxxxxxx: xxx::xxxxxxxxx_xxx<xxxxxxxx xxxx xxxx, xxx::xxxxxxxxx_xxx<xxxxxxxx xxxx xxxx, xxx::xxxxx<xxxxxxxx xxxx xxxx, xxxx, xxxx, xxxx>>> xxxxxx = { {x, {{x, {x, xxxx, xxxx, xxxxx}}, {x, {x, xxxx, xxxx, xxxx}}}}, {x, {{x, {xx, xxxx, xxxx, xxxxx}}, {x, {xx, xxxx, xxxxx, xxxxx}}}}, }; xxxxxxxxx(xxxxxx, x, {{xxxx'xx'xxxx, xxxxx}}, {x, x}, x); // {{"xx", xxx}} xxxxxxxxx(xxxxxx, x, {{xxxx'xx'xxxx, xxxxx}}, {x, x}, x); // {{"xx", xxx}} xxx xxxxx xxxxx xxxxxxxx. xxxxx x xx xxx xxxx xxxxx xxxxx x, xxxxx x xx xxxx xxxxx xxxxx xx, xxx xxx xxxxxx x xxxxx xxxxxx xx: ( xx xxxxx xx + x = xxx ). xxx xxxxxx xxxx x xxxx xxxx xx xxx xxx xxxxx. xxx xxxx xxxxx xxxxxxxxxxx, xx xxx x xxxx xxxx xxxxx xxxx xxxxxxx xxxxx x xxxxxx xxxx xx xxx xxxxxx xxxxxxx: xxxxx x xxxx x x-xxx xxxxxx xx xx_xxxx, xxxxx xx ( x xxxxx xx + xx = xxx ). xxxx xx xxxxxxx xxx x x xx xxxx xxxxxxx xx xxxx xxxxxxxx, xxx xxxxx xx xxxx x x xx xxxx xxxx x xxxx xxx xxxxx. xxxxxxxxxxx xx xx ( x xxxxx xx^x ) xxxxxxxx, xx xx x xxxxxx, xxx xxxxxxxxx xx xx xx xxxx. xxx x++ xxxxxxxxxxx xxxx xxxxxx xxx xxxxx xx xxxx xxxxxxxxxxxx. xxx xxxxx xxxxx xxxxxxx: x xxxxx xx xxx xxx xx x xxxx xxxxxxx, x xxxxx xx xxx xxxxxx xx xx xxxxxxxx xxxx xxxxxx x xxxxxx xxxx xxxxxxxxx xxxxxx. xxxxx xxx xxxxxxxxxx xx xxxxx xxxxx, xxx xxxx xx xxx xxxx. x xxxx-xxxx xxxxx xxxxxx xx xxxxx xxxxxxxxxx xxxxx xx xxxx-xxxx. xxxxxxxxxx xxxx xx xxxxx xxxxxxx xxxxxxxxxx xx xxx xxxxxx. xxx xxxxxxxx xxxx xxxx xxx xxxxxxxxx xxx xxxxxx, xx x xx-xxx xxxxx xxxx xxx xxxxxxxx x xxxxxx xxxx.

This problem is only available to subscribers.

Language:

Python 3.12 C++23

translate

#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>

// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
std::vector<std::pair<std::string, unsigned long long>> translate(
        const std::unordered_map<unsigned long long,
                                 std::unordered_map<unsigned long long, std::tuple<unsigned long long, bool, bool, bool>>>& tables,
        unsigned long long root,
        const std::vector<std::pair<unsigned long long, bool>>& requests,
        const std::vector<int>& level_bits,
        int offset_bits) {
    // ...
    (void)tables;
    (void)root;
    (void)requests;
    (void)level_bits;
    (void)offset_bits;
    return {{"fault", 99}};
}

Unlock to runUpgrade

Unlock the problem to run it against the tests.