Feature #3: Upselling Products
We'll cover the following...
Description
Amazon wants to upsell related products to the customer during checkout. Amazon wants to do this by recommending a single product picked randomly from a collection of several related products. You must implement three related features to recommend. First, you want to enable adding an item to the list of related products. Second, you want to enable removing an item from the list once it is deprecated. Lastly, you want to enable picking a random item from the list such that any item is equally likely to be picked. You must implement all of these features so that they run in O(1) time.
For this feature, we will keep track of the products by only using their IDs. The insertion, deletion, and retrieval will use the ID of the product. The following illustration shows how products are mapped to IDs:
Solution
This data structure’s most important feature is recommending products at random in time. Let’s consider the data structures with constant time lookup, such as arrays and Hashtables/dictionaries.
If we consider storing all the products in the array, the lookup will be . To implement the random functionality, we need to choose a random index first and then retrieve the array element. We can consider arrays for their constant time insertion and ...
Create a free account to view this lesson.
By signing up, you agree to Educative's Terms of Service and Privacy Policy