Top K Symbols by Traded Volume

The end-of-day report lists the symbols that traded the most. The trade log holds one row per fill, so a busy symbol appears thousands of times and a quiet one once.

Implement top_k_symbols(trades, k). trades is a sequence of symbol and quantity pairs in any order. Rank symbols by their total quantity across all their trades:

• The largest total comes first.
• If two symbols have the same total, the one that comes first alphabetically ranks higher.

Return the top k symbols in rank order. If there are fewer than k distinct symbols, return all of them.

std::vector<std::string> top_k_symbols(
    const std::vector<std::pair<std::string, long long>>& trades, int k);

Each trade is a {symbol, quantity} pair and the result is the ranked symbols.

Examples

top_k_symbols({{"AAPL", 100}, {"MSFT", 250}, {"AAPL", 200}, {"NVDA", 50}}, 2);
// {"AAPL", "MSFT"}  (AAPL totals 300, MSFT 250)

top_k_symbols({{"XOM", 10}, {"BP", 10}, {"SHEL", 5}}, 2);
// {"BP", "XOM"}  (a tie at 10, broken alphabetically)

Constraints

• Up to \(2 \times 10^6\) trades and \(4 \times 10^5\) distinct symbols; k >= 1.
• Quantities are positive integers.
• The hidden performance test asks for the top 40,000 of 400,000 symbols from 2,000,000 trades. Picking the largest remaining symbol k times scans every symbol k times and will not finish. A heap of size k gives \(O(n + m \log k)\) for n trades and m symbols; sorting all m totals, \(O(n + m \log m)\), also passes.