https://youtu.be/XP9Zg--DLr8

main.cc

//
//  main.cc
//  anthropic_interview
//
// clang++ -O2 -Wall -Wformat -Wformat=2 -Wconversion -Wimplicit-fallthrough -Werror=format-security -fstack-protector-strong -fPIE -D_FORTIFY_SOURCE=3 -std=c++23 main.cc -o main

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

struct Sample {
    double ts;
    std::vector<std::string> stack;
};

struct Event {
    std::string kind;
    double ts;
    std::string name;
    
    void PrintDebug() {
        std::println("-------");
        std::println("Kind {} ", kind);
        std::println("ts {} " ,ts);
        std::println("Name {} ", name);
        std::println("------");
    }
};

std::vector<Event> convertToTrace(const std::vector<Sample>& samples) {
    // write your code here
    // Event{"start", "7.5", "main"};
    // Event{"start", "9.2", "my_fn"};
    // Event{"start", "9.2", "my_fn2"};
    // Event{"end",   "10.7", "my_fn"};
    // Event{"start", "10.7", "my_fn2"};
    
    std::vector<Event> events;
    std::vector<std::string> prev;

    for (const auto& s : samples) {
        auto [old_it, new_it] =
            std::mismatch(prev.begin(), prev.end(),
                          s.stack.begin(), s.stack.end());

        size_t common = static_cast<size_t>(std::distance(prev.begin(), old_it));

        for (size_t i = prev.size(); i > common; --i) {
            events.push_back(Event{"end", s.ts, prev[i - 1]});
        }


        for (size_t i = common; i < s.stack.size(); ++i) {
            events.push_back(Event{"start", s.ts, s.stack[i]});
        }

        prev = s.stack;
    }

    return events;
}

int main(int argc, const char * argv[]) {
    
    Sample s1{7.5, {"main"}};
    Sample s2{9.2, {"main", "my_fn", "my_fn2"}};
    Sample s3{10.7 , {"main", "my_fn"}};
    Sample s4{11.1 , {"main"}};
    Sample s5{11.2 , {}};
    
    std::vector<Sample> s = {s1, s2, s3, s4, s5};
    auto events = convertToTrace(s);
    
    for (auto &e : events) {
        e.PrintDebug();
    }
    
    return EXIT_SUCCESS;
}