
Problem Statement
The task involves simulating a stock tracking system, where records containing timestamps and associated stock prices are received in a potentially disordered manner. The system must be robust enough to handle updates to previously entered data if discrepancies are found later. The core requirements of the solution are:
- Updating Records: If the same timestamp occurs again with a different price, the system should correct the old invalid data with the new price.
- Retrieving Latest Price: The system should be able to state the most recent price of the stock based on the order of timestamps.
- Finding Maximum and Minimum Prices: It should efficiently report the highest and lowest stock price noted so far.
For managing these functionalities, the implementation will be encapsulated in a StockPrice
class with methods to handle updates, and fetch the current, maximum, and minimum stock prices.
Examples
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 toupdate
,current
,maximum
, andminimum
. current
,maximum
, andminimum
will be called only afterupdate
has been called at least once.
Approach and Intuition
Given the varying and potentially unordered nature of the stock price records, the approach should effectively manage finding the latest, maximum, and minimum prices quickly, even as updates potentially alter previously stored records. Here's how each functionality is handled:
Price Updates Using a Hash Map:
- Use a hash map
timestamp_to_price
to store the latest price for each timestamp. - On every
update(timestamp, price)
, overwrite the existing value if present.
- Use a hash map
Tracking Latest Timestamp:
- Maintain a variable
latest_timestamp
to track the most recent timestamp seen so far. - The
current()
function simply returns the price atlatest_timestamp
.
- Maintain a variable
Efficient Max/Min Price Retrieval with Heaps:
- Use a max-heap to track all
(price, timestamp)
pairs for fast maximum retrieval. - Use a min-heap to track all
(price, timestamp)
pairs for fast minimum retrieval. - When calling
maximum()
orminimum()
, lazy-delete outdated entries by checking if the heap’s top price still matches the current price for that timestamp. If not, discard and continue.
- Use a max-heap to track all
Efficiency Justification:
- All operations aim to run in
O(log n)
time due to heap insertion/removal. - Hash map provides
O(1)
access for verification during lazy deletion. - This hybrid approach allows fast updates, corrections, and real-time analytics on stock price movement.
- All operations aim to run in
By combining direct mappings for accuracy with heaps for efficient ordered access, the solution maintains integrity and speed across dynamic and large-scale inputs.
Solutions
- C++
class MarketData {
int mostRecentTime;
unordered_map<int, int> timePriceMapping;
priority_queue<pair<int, int>> descendingHeap;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> ascendingHeap;
public:
MarketData() {
mostRecentTime = 0;
}
void update(int timestamp, int price) {
mostRecentTime = max(mostRecentTime, timestamp);
timePriceMapping[timestamp] = price;
ascendingHeap.push({price, timestamp});
descendingHeap.push({price, timestamp});
}
int current() {
return timePriceMapping[mostRecentTime];
}
int maximum() {
pair<int, int> top = descendingHeap.top();
while (timePriceMapping[top.second] != top.first) {
descendingHeap.pop();
top = descendingHeap.top();
}
return top.first;
}
int minimum() {
pair<int, int> top = ascendingHeap.top();
while (timePriceMapping[top.second] != top.first) {
ascendingHeap.pop();
top = ascendingHeap.top();
}
return top.first;
}
};
This solution introduces a MarketData
class in C++, designed to manage the fluctuations of stock prices time-efficiently. The class uses two priority queues to keep track of minimum and maximum prices efficiently, and an unordered map to store prices keyed by their timestamp. Here’s a breakdown of the class functionalities:
Constructor (
MarketData()
): Initializes themostRecentTime
to 0 to track the most recent update.update(int timestamp, int price)
Method: Records or updates the given price at the specific timestamp. It adjustsmostRecentTime
to ensure it reflects the latest time. The method then logs the price into the unordered map and pushes the price and timestamp into both maximum and minimum priority queues (implemented with a pair of price and timestamp for direct comparison).current()
Method: Returns the most recent price based on themostRecentTime
.maximum()
Method: Retrieves the maximum price from thedescendingHeap
. If the top of the heap does not match the recorded latest price in the map, it discards the top element (to account for old updates), recalibrates, and then returns the corrected top.minimum()
Method: Retrieves the minimum price from theascendingHeap
in a manner similar tomaximum()
: it verifies the correct minimal price against potential outdated top elements and ensures output accuracy by potentially discarding the outdated tops until the price at the current top matches the one in the map.
Each function is crafted to ensure the operations are efficient, with most operations running in logarithmic time due to the use of binary heaps, and constant time for price retrieval operations via the map.
- Java
class StockTracker {
private int currentTimestamp;
private Map<Integer, Integer> priceByTimestamp;
private PriorityQueue<int[]> ascendingPrices, descendingPrices;
public StockTracker() {
currentTimestamp = 0;
priceByTimestamp = new HashMap<>();
ascendingPrices = new PriorityQueue<>((a, b) -> a[0] - b[0]);
descendingPrices = new PriorityQueue<>((a, b) -> b[0] - a[0]);
}
public void update(int timestamp, int price) {
currentTimestamp = Math.max(currentTimestamp, timestamp);
priceByTimestamp.put(timestamp, price);
ascendingPrices.offer(new int[]{ price, timestamp });
descendingPrices.offer(new int[]{ price, timestamp });
}
public int current() {
return priceByTimestamp.get(currentTimestamp);
}
public int maximum() {
int[] top = descendingPrices.peek();
while (priceByTimestamp.get(top[1]) != top[0]) {
descendingPrices.poll();
top = descendingPrices.peek();
}
return top[0];
}
public int minimum() {
int[] top = ascendingPrices.peek();
while (priceByTimestamp.get(top[1]) != top[0]) {
ascendingPrices.poll();
top = ascendingPrices.peek();
}
return top[0];
}
}
The given Java code defines a class StockTracker
managing stock price fluctuations over time. It effectively tracks the most recent, highest, and lowest prices using efficient data structures.
Data Structures Used:
priceByTimestamp
: A HashMap to associate each timestamp with a corresponding price.ascendingPrices
: A PriorityQueue to keep prices in ascending order to quickly access the minimum price.descendingPrices
: A PriorityQueue to keep prices in descending order to quickly access the maximum price.
Key Methods Implemented:
update(int timestamp, int price)
: Updates or adds the price at a given timestamp. AdjustscurrentTimestamp
to the latest timestamp and stores the price. It also adds the price to both priority queues to keep them updated.current()
: Returns the most recent price by queryingpriceByTimestamp
withcurrentTimestamp
.maximum()
: Retrieves the maximum price by inspecting the top ofdescendingPrices
. It validates the correctness of the top price and adjusts if necessary due to removed or updated entries.minimum()
: Similar tomaximum()
, but checksascendingPrices
for the minimum price, ensuring the top price is still current and correct, making adjustments if needed.
Integrate StockTracker
into applications requiring real-time tracking and querying of stock prices, ensuring accurate and swift responses for current, maximum, and minimum price queries. This approach is optimal for scenarios where price data is frequently updated and queried, leveraging the efficiency of priority queues for immediate access to extreme values.
- Python
class StockTracker:
def __init__(self):
self.current_time = 0
self.price_at_timestamp = {}
self.prices_asc = []
self.prices_desc = []
def update(self, timestamp: int, price: int) -> None:
self.price_at_timestamp[timestamp] = price
self.current_time = max(self.current_time, timestamp)
heappush(self.prices_asc, (price, timestamp))
heappush(self.prices_desc, (-price, timestamp))
def current(self) -> int:
return self.price_at_timestamp[self.current_time]
def maximum(self) -> int:
price, timestamp = self.prices_desc[0]
while -price != self.price_at_timestamp[timestamp]:
heappop(self.prices_desc)
price, timestamp = self.prices_desc[0]
return -price
def minimum(self) -> int:
price, timestamp = self.prices_asc[0]
while price != self.price_at_timestamp[timestamp]:
heappop(self.prices_asc)
price, timestamp = self.prices_asc[0]
return price
This Python3 program implements a StockTracker
class designed to manage and track stock prices along with their timestamps. This utility allows users to update prices at given timestamps, fetch the current price, check the maximum price recorded, and the minimum price recorded since the last update. The implementation utilizes min and max heaps to efficiently fetch the lowest and highest prices, respectively.
Overview of StockTracker
class methods:
__init__
: Initialize the StockTracker instance with necessary attributes such as current time, dictionary for price at each timestamp, and two lists (heaps) for managing ascending and descending order of prices.update(timestamp: int, price: int)
: Update the stock tracker with the stock price at a specific timestamp. This method manages the current time as the latest timestamp and uses heaps to keep track of the prices in sorted order.current() -> int
: Return the current or most recent price of the stock, determined by the most recent timestamp.maximum() -> int
: Retrieve the maximum price that has been logged. This method uses the descending heap, adjusting for any outdated prices that may have changed due to newer updates.minimum() -> int
: Fetch the minimum price recorded. Similar tomaximum()
, this function utilizes the ascending heap and clears any outdated entries to ensure the minimum is current.
This class efficiently handles multiple and possibly non-sequential updates to stock prices using a combination of heaps and a dictionary. This ensures quick retrieval of the current, max, and min prices, making the system robust for real-time financial data tracking where speed and accuracy are crucial.
No comments yet.