Feature #13: Time-Based Item Price Store
Explore how to design a time-based item price store that tracks price changes with timestamps, enabling retrieval of the correct price at purchase time. Understand the use of hash maps and binary search to efficiently manage and query item prices, essential for handling returns with fluctuating prices in an Amazon-like environment.
We'll cover the following...
Description
Thousands of items are sold on Amazon every minute. Some of the items don’t meet the buyer’s expectations and are returned. Item prices fluctuate over time. It’s possible for the price of a returned item to change since it was purchased. The customer should then be refunded the item price applicable at the time of purchase.
We want to store the prices of items using the timestamp in a data structure and update the price whenever needed, along with the current timestamp. When a customer wants to return an item, we’d like to query the item’s price at that time. An item’s price is unchanged until it is updated.
Our task is to design a time-based item price data structure that can store multiple prices for the same item at different time stamps and retrieve the item’s price at a certain timestamp.
Let’s understand this better with an illustration:
Note: The
timestampsinsetcalls are strictly increasing.
Solution
Let’s approach this problem in the following way:
-
The
TimeMapclass ...