Search⌘ K
Home
Courses
Decode the Coding Interview in Elixir: Real-World Examples

Feature #13: Time-Based Item Price Store

Understand how to design a data structure that stores and retrieves item prices using timestamps, handling price changes and returns as seen in Amazon. Explore efficient methods with hash maps and binary search to manage time-based data, preparing you for similar real-world coding problems.

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

Solution

Let’s approach this problem in the following way:

  • TimeMap module declares a struct containing two hash maps, prices and timestamp, where item will be the keys, and prices and timestamp will be the values.

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