Feature #3: Upselling Products

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 array of related products. Second, you want to enable removing an item from the array once it is deprecated. Lastly, you want to enable picking a random item from the array 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: