Feature #13: Time-Based Item Price Store

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 timestamps in set calls are strictly increasing.

Solution

Let’s approach this problem in the following way:

• TimeMap class declares a class containing two dictionaries, prices and timestamps, where items will be the keys, and prices and timestamp will be the values.

• set(self, item, price, timestamp) stores the key item with the value price at the given time timestamp.

  • Check if the key item already exists in the dictionary. If it does, then check if the given price of item does not already exist at the last timestamp in the prices[item]. If it already exists, the item’s price and timestamp will be stored in the prices[item] and timestamps[item] ...