How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Akuna Capital.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Akuna Capital during technical interviews.

Compute max profit across dated stock quotes | Akuna Capital Coding Question

Quick Overview

This question evaluates a candidate's ability to reason about time-series and transaction-constrained optimization, including handling unsorted inputs, duplicate records, and constructing an explicit sequence of trades under ordering and no-short-selling constraints.

Compute max profit across dated stock quotes

Company: Akuna Capital

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

You are given an unsorted list of price records for multiple stocks, each record as (date, symbol, price). Dates may be repeated across different symbols. Design an algorithm to compute the maximum profit and an explicit trading plan under these rules: ( 1) You can hold at most one share across all symbols at any time. ( 2) You may perform unlimited buy/sell transactions, but every buy must occur on a strictly later date than the previous sell (no same-day buy-and-sell for profit), and short selling is not allowed. ( 3) Assume prices are daily closes; if duplicates or missing dates occur, specify how you handle them. Return: (a) the maximum achievable profit, and (b) the sequence of trades (for each trade, list buy date, buy symbol, buy price, sell date, sell price). Explain your algorithm, prove correctness, and analyze time and space complexity. Discuss edge cases such as unsorted input, duplicate (date, symbol) rows, and non-monotonic dates.

Quick Answer: This question evaluates a candidate's ability to reason about time-series and transaction-constrained optimization, including handling unsorted inputs, duplicate records, and constructing an explicit sequence of trades under ordering and no-short-selling constraints.

You are given an unsorted list of stock price records for multiple symbols. Each record is a tuple (date, symbol, price), where date is an integer day number. Dates may repeat across different symbols, and the input may be in any order. Design a function that computes: 1. The maximum achievable profit. 2. One optimal trading plan. Trading rules: - You may hold at most one share total across all symbols at any time. - You may complete unlimited buy/sell transactions. - Every buy must happen on a strictly later date than the previous sell date. In particular, you may not sell and then buy again on the same date. - Short selling is not allowed. - Prices are daily closing prices. Data-cleaning rules for this problem: - If the same (date, symbol) appears multiple times, keep only the last occurrence from the input. - Missing dates do not need to be filled in; a symbol can only be bought or sold on dates where it has a price record. Return a tuple (max_profit, trades), where trades is a chronological list of trades. Each trade must be represented as: (buy_date, buy_symbol, buy_price, sell_date, sell_price) If no profitable trade exists, return 0 and an empty trade list. A strong interview solution should also be able to justify correctness, explain why same-day switching is disallowed by the transition logic, and analyze time and space complexity.

Constraints

0 <= len(records) <= 200000
Each record is (date, symbol, price) where date is an integer, symbol is a non-empty string, and price >= 0
If duplicate (date, symbol) rows exist, only the last occurrence in the input is considered valid

Examples

Input: ([(3, 'A', 8), (1, 'A', 5), (2, 'A', 9), (4, 'A', 7), (5, 'B', 3), (7, 'B', 10), (6, 'B', 2)],)

Expected Output: (12, [(1, 'A', 5, 2, 9), (6, 'B', 2, 7, 10)])

Explanation: Buy A on day 1 and sell on day 2 for profit 4. Then buy B on day 6 and sell on day 7 for profit 8. Total profit is 12.

Input: ([(1, 'A', 1), (2, 'A', 5), (2, 'B', 1), (3, 'B', 5)],)

Expected Output: (4, [(1, 'A', 1, 2, 5)])

Explanation: You cannot sell A on day 2 and then buy B on day 2, because a buy must be on a strictly later date than the previous sell. So the best valid profit is 4, from trading A only.

Input: ([(1, 'A', 10), (2, 'A', 4), (2, 'A', 6), (4, 'A', 9), (3, 'B', 1), (5, 'B', 5)],)

Expected Output: (4, [(3, 'B', 1, 5, 5)])

Explanation: The duplicate row for (2, 'A') is resolved by keeping the last occurrence, so A's day-2 price is 6. Trading B from day 3 to day 5 yields profit 4, which is better than trading A from day 2 to day 4 for profit 3.

Input: ([],)

Expected Output: (0, [])

Explanation: With no price records, no trade can be made.

Input: ([(10, 'X', 7)],)

Expected Output: (0, [])

Explanation: A single price record is not enough to complete a buy-then-sell transaction.

Solution

def solution(records):
    from collections import defaultdict

    class Node:
        __slots__ = ('prev', 'trade')

        def __init__(self, prev, trade):
            self.prev = prev
            self.trade = trade

    latest = {}
    for date, symbol, price in records:
        latest[(date, symbol)] = price

    by_date = defaultdict(dict)
    for (date, symbol), price in latest.items():
        by_date[date][symbol] = price

    hold_profit = {}
    hold_buy = {}
    hold_node = {}
    flat_profit = 0
    flat_node = None

    for date in sorted(by_date):
        today = by_date[date]

        prev_flat_profit = flat_profit
        prev_flat_node = flat_node

        best_flat_profit = flat_profit
        best_flat_node = flat_node

        for symbol, price in today.items():
            if symbol in hold_profit:
                candidate = hold_profit[symbol] + price
                if candidate > best_flat_profit:
                    best_flat_profit = candidate
                    buy_date, buy_price = hold_buy[symbol]
                    best_flat_node = Node(
                        hold_node[symbol],
                        (buy_date, symbol, buy_price, date, price)
                    )

        for symbol, price in today.items():
            candidate = prev_flat_profit - price
            if candidate > hold_profit.get(symbol, float('-inf')):
                hold_profit[symbol] = candidate
                hold_buy[symbol] = (date, price)
                hold_node[symbol] = prev_flat_node

        flat_profit = best_flat_profit
        flat_node = best_flat_node

    trades = []
    node = flat_node
    while node is not None:
        trades.append(node.trade)
        node = node.prev
    trades.reverse()

    return flat_profit, trades

Time complexity: O(n log n), dominated by sorting the distinct dates after O(n) duplicate-collapsing. Space complexity: O(n).

Hints

Normalize the data first: collapse duplicate (date, symbol) rows, then process dates in sorted order.
Use dynamic programming with two kinds of states: the best profit when you end a date with no stock, and for each symbol the best profit when you end the date holding that symbol. Be careful: sells for a date must be evaluated before buys for that same date.

Quick Overview