Stock Price Fluctuation

Medium

MongoDB

1 view

Topics:

ArraysGreedy Algorithms

You are given a stream of records about a particular stock. Each record contains a timestamp and the corresponding price of the stock at that timestamp.

Unfortunately due to the volatile nature of the stock market, the records do not come in order. Even worse, some records may be incorrect. Another record with the same timestamp may appear later in the stream correcting the price of the previous wrong record.

Design an algorithm that:

Updates the price of the stock at a particular timestamp, correcting the price from any previous records at the timestamp.
Finds the latest price of the stock based on the current records. The latest price is the price at the latest timestamp recorded.
Finds the maximum price the stock has been based on the current records.
Finds the minimum price the stock has been based on the current records.

Implement the StockPrice class:

StockPrice() Initializes the object with no price records.
void update(int timestamp, int price) Updates the price of the stock at the given timestamp.
int current() Returns the latest price of the stock.
int maximum() Returns the maximum price of the stock.
int minimum() Returns the minimum price of the stock.

Example 1:

Input
["StockPrice", "update", "update", "current", "maximum", "update", "maximum", "update", "minimum"]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
Output
[null, null, null, 5, 10, null, 5, null, 2]

Explanation
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // Timestamps are [1] with corresponding prices [10].
stockPrice.update(2, 5);  // Timestamps are [1,2] with corresponding prices [10,5].
stockPrice.current();     // return 5, the latest timestamp is 2 with the price being 5.
stockPrice.maximum();     // return 10, the maximum price is 10 at timestamp 1.
stockPrice.update(1, 3);  // The previous timestamp 1 had the wrong price, so it is updated to 3.
                          // Timestamps are [1,2] with corresponding prices [3,5].
stockPrice.maximum();     // return 5, the maximum price is 5 after the correction.
stockPrice.update(4, 2);  // Timestamps are [1,2,4] with corresponding prices [3,5,2].
stockPrice.minimum();     // return 2, the minimum price is 2 at timestamp 4.

Constraints:

1 <= timestamp, price <= 10⁹
At most 10⁵ calls will be made in total to update, current, maximum, and minimum.
current, maximum, and minimum will be called only after update has been called at least once.

Try coding it in LeetCode

Stock Price Fluctuation

Medium

MongoDB

1 view

Topics:

ArraysGreedy Algorithms

You are given a stream of records about a particular stock. Each record contains a timestamp and the corresponding price of the stock at that timestamp.

Unfortunately due to the volatile nature of the stock market, the records do not come in order. Even worse, some records may be incorrect. Another record with the same timestamp may appear later in the stream correcting the price of the previous wrong record.

Design an algorithm that:

Updates the price of the stock at a particular timestamp, correcting the price from any previous records at the timestamp.
Finds the latest price of the stock based on the current records. The latest price is the price at the latest timestamp recorded.
Finds the maximum price the stock has been based on the current records.
Finds the minimum price the stock has been based on the current records.

Implement the StockPrice class:

StockPrice() Initializes the object with no price records.
void update(int timestamp, int price) Updates the price of the stock at the given timestamp.
int current() Returns the latest price of the stock.
int maximum() Returns the maximum price of the stock.
int minimum() Returns the minimum price of the stock.

Example 1:

Input
["StockPrice", "update", "update", "current", "maximum", "update", "maximum", "update", "minimum"]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
Output
[null, null, null, 5, 10, null, 5, null, 2]

Explanation
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // Timestamps are [1] with corresponding prices [10].
stockPrice.update(2, 5);  // Timestamps are [1,2] with corresponding prices [10,5].
stockPrice.current();     // return 5, the latest timestamp is 2 with the price being 5.
stockPrice.maximum();     // return 10, the maximum price is 10 at timestamp 1.
stockPrice.update(1, 3);  // The previous timestamp 1 had the wrong price, so it is updated to 3.
                          // Timestamps are [1,2] with corresponding prices [3,5].
stockPrice.maximum();     // return 5, the maximum price is 5 after the correction.
stockPrice.update(4, 2);  // Timestamps are [1,2,4] with corresponding prices [3,5,2].
stockPrice.minimum();     // return 2, the minimum price is 2 at timestamp 4.

Constraints:

1 <= timestamp, price <= 10⁹
At most 10⁵ calls will be made in total to update, current, maximum, and minimum.
current, maximum, and minimum will be called only after update has been called at least once.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the timestamp and stock price values, and what are their respective data types?
If a timestamp is updated with a new price, should the old price for that timestamp be overwritten, or should we keep a history of prices for each timestamp?
If there are no price updates, or no prices recorded yet, what should be returned when requesting the latest price, maximum price, or minimum price?
Can we assume the timestamps are integers representing seconds since the epoch, or are they more granular (e.g., milliseconds)? Is there an expected range of timestamp values?
How frequently will each operation (update, get latest, get max, get min) be called, and what are the expected read/write ratios to optimize for?

Brute Force Solution

Approach

The brute force approach to finding the best profit from stock prices involves trying every possible combination of buying and selling. We explore all possible pairs of buying and selling days to see which one gives us the most profit.

Here's how the algorithm would work step-by-step:

Look at every single day as a potential buying day.
For each buying day, look at every day that comes *after* it as a potential selling day.
Calculate the profit you would make if you bought on the buying day and sold on the selling day.
Keep track of the biggest profit you find while trying all the different buy and sell day combinations.
Once you've checked every possible buying and selling day pair, the biggest profit you found is the answer.

Code Implementation

def find_max_profit_brute_force(stock_prices):
    max_profit = 0

    # Iterate through all possible buying days
    for buying_day in range(len(stock_prices)):

        # Iterate through all possible selling days after the buying day
        for selling_day in range(buying_day + 1, len(stock_prices)):

            # Calculate the profit for the current buying and selling days
            profit = stock_prices[selling_day] - stock_prices[buying_day]

            # Update max_profit if the current profit is greater
            if profit > max_profit:
                max_profit = profit

    return max_profit

Big(O) Analysis

Time Complexity

O(n²) – The provided approach involves iterating through all possible buying days, which is proportional to n, the number of days (stock prices). For each buying day, the algorithm iterates through all subsequent selling days, resulting in another loop nested within the first. The inner loop's iterations depend on the outer loop index, but in the worst case it approaches n. Consequently, the number of operations is roughly proportional to n * n/2, which simplifies to a time complexity of O(n²).

Space Complexity

O(1) – The provided brute force approach only requires storing a few variables, such as loop counters and a variable to track the maximum profit. These variables use a constant amount of space regardless of the number of stock prices (N). No additional data structures, like arrays or hash maps that would scale with the input size, are created. Therefore, the auxiliary space complexity is constant, O(1).

Optimal Solution

Approach

To efficiently track stock prices, we use a system that allows for quick updates and retrieval of the latest price. The core idea is to maintain a record of timestamps and their corresponding prices and use a method to get the most recent price or update existing ones quickly. We use a structure that is automatically sorted which lets us easily find the maximum price.

Here's how the algorithm would work step-by-step:

Store each stock price update along with its timestamp.
When a new price arrives with a timestamp, either update the existing price for that timestamp or add the new price with its timestamp to our storage.
To get the latest price, simply find the entry with the highest timestamp. Because our storage is always sorted by timestamp, this becomes very efficient.
To find the maximum price, we can keep track of it as updates occur, or when requested, look through our stored data to find the highest price recorded. An efficiently maintained maximum can save time.

Code Implementation

class StockPrice:

    def __init__(self):
        self.timestamp_to_price = {}
        self.latest_timestamp = 0
        self.maximum_price = float('-inf')

    def update(self, timestamp: int, price: int) -> None:
        # Update the timestamp_to_price mapping
        self.timestamp_to_price[timestamp] = price

        # Keep track of the latest timestamp
        self.latest_timestamp = max(self.latest_timestamp, timestamp)

    def current(self) -> int:
        # Find the most recent price based on latest timestamp
        return self.timestamp_to_price[self.latest_timestamp]

    def maximum(self) -> int:
        self.maximum_price = float('-inf')
        # Find the maximum price among all stored prices
        for price in self.timestamp_to_price.values():
            self.maximum_price = max(self.maximum_price, price)

        return self.maximum_price

    def minimum(self) -> int:
        minimum_price = float('inf')
        # Find the minimum price among all stored prices
        for price in self.timestamp_to_price.values():
            minimum_price = min(minimum_price, price)

        return minimum_price

Big(O) Analysis

Time Complexity

O(log n) – Storing stock prices with timestamps requires either updating an existing entry or inserting a new one. A sorted data structure such as a TreeMap (in Java) or equivalent balanced tree is used for storage, allowing for efficient insertion and updates. These operations take O(log n) time, where n is the number of timestamp-price pairs. Retrieving the latest price involves finding the entry with the highest timestamp, which is also an O(log n) operation given the sorted nature of the data structure. Tracking the maximum price either requires updating it on each insertion (O(1) if maintained separately) or searching if not which will involve looking at each timestamp once.

Space Complexity

O(N) – The primary space usage comes from storing each stock price update along with its timestamp. This implies using a data structure like a list or dictionary to hold these pairs. In the worst case, each update has a unique timestamp, resulting in a storage requirement proportional to the number of updates, N, where N is the number of stock price updates. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Initial empty stock price data	Initialize data structures to handle no initial data gracefully, returning appropriate values (e.g., -1 or null) for latest price, max price, and min price until data is added.
Single timestamp-price pair	Handle the case where only one timestamp-price is present; latest, max, and min price should all be equal to that price.
Duplicate timestamps with different prices	The latest timestamp's price should overwrite any previous price at the same timestamp, ensuring only the most recent update persists.
Timestamps arriving in descending order	Ensure that the data structure correctly identifies the latest timestamp even when the input is not sorted.
Extreme price values (very large or very small)	Use appropriate data types (e.g., long or double) to prevent integer overflow or underflow when storing prices.
A large number of timestamp-price pairs	Choose data structures (e.g., balanced trees or heaps) that offer efficient insertion, deletion, and retrieval for a large dataset to avoid performance bottlenecks.
Retrieving max/min price when all prices are the same	The max and min price should be equal to the single unique price value.
Negative price values (if allowed)	Handle negative price values correctly when calculating the maximum and minimum prices, ensuring they are properly compared.