Katkat
Back

Design a Trade Ledger Class

MetaSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem evaluates your ability to design a class interface that maintains an ordered collection of events and allows efficient retrieval based on time-based criteria.

Design a Trade Ledger Class

You are tasked with designing a TradeLedger class to record financial trades as they occur. Each trade consists of a trade_id (string), symbol (string), price (float), and a timestamp (integer).

Your class should support the following operations:

  1. record_trade(trade_id, symbol, price, timestamp): Stores the trade information. You can assume timestamps are added in non-decreasing order.
  2. get_trades_in_range(start_time, end_time): Returns a list of all trades where start_time <= timestamp <= end_time. The returned list should be sorted by timestamp.
  3. get_latest_trades(n): Returns the n most recent trades, sorted by timestamp in descending order.

Requirements

  • Choose appropriate data structures to optimize for these operations.
  • Explain the time complexity for each method.

Example

ledger = TradeLedger()
ledger.record_trade("T1", "AAPL", 150.0, 100)
ledger.record_trade("T2", "GOOG", 2800.0, 200)
ledger.record_trade("T3", "AAPL", 155.0, 300)

# Returns trades with T2 and T3
ledger.get_trades_in_range(150, 300)

# Returns [T3, T2]
ledger.get_latest_trades(2)

Constraints

  • n will be a positive integer.
  • Total number of trades can be up to 10^5.
  • The timestamps are integers.

Edge Cases

  • Searching for a range that contains no trades.
  • Requesting more trades than are currently in the ledger.
  • Multiple trades having the exact same timestamp.

Hints

Hint 1

Since trades are recorded with non-decreasing timestamps, consider how this property affects your choice of storage.

Hint 2

For the range query, if you store trades in a simple dynamic array (list), you can use binary search to find the starting index efficiently.

Hint 3

For the latest trades query, think about how to access the end of your storage structure in constant or near-constant time.

Follow-up questions

  • How would your implementation change if trades could arrive out of order (i.e., non-chronological timestamps)?
  • How would you modify this class to support multi-threading if multiple producers are recording trades simultaneously?
  • If the ledger needed to store millions of trades, how would you persist this data to disk while maintaining performance?