For this feature, we want to suggest products customers can buy to make their orders eligible for free delivery. The minimum order amount to qualify for free shipping varies by customer location. When a customer views their cart and the current total does not qualify for free shipping, we want to show them a pair of products that can be bought together to make the total amount equal to the amount required to be eligible for free delivery. You can assume that it was a corporate decision to show a pair of products instead of a single product. Historical data collected by your team shows that customers are more willing to buy multiple products as it gives the illusion of a better deal. Also, the UX team says that only two items should be displayed given the screen space for this feature.
To implement this feature, we will have access to a list of products that the customer is likely to buy. These products will include the items from their wishlist and other items based on previous purchases. We will also be given the amount, n, that the customer needs to spend in addition to the current total: n=[free shipping price−current total].
Let’s say you are given a list of numbers containing the prices of products that a customer is likely to buy, {2, 30, 56, 34, 55, 10, 11, 20, 15, 60, 45, 39, 51}. In addition, the amount that needs to be spent to claim the free delivery offer is 61 dollars. Then, we can see that the sum of 10 and 51 is 61. Therefore, we will suggest the customer buys these products. Our program should return the indices of these products in an array such as: {5, 12}.
You can assume that the list contains at least one pair of products to suggest. If there is more than one pair, you can suggest any of them.
The following illustration shows how products are mapped to prices for the example we are discussing. The prices have been rounded off for simplicity.
The illustration given below shows how we obtained the result from the list of prices.
One-pass Hash Table
Algorithm
It turns out we can do it in one pass. While we are iterating and inserting elements into the hash table, we also look back to check if the current element’s complement already exists in the hash table. If it exists, we have found a solution and return the indices immediately.
Implementation
Complexity Analysis
- Time complexity: O(n). We traverse the list containing n elements only once. Each lookup in the table costs only O(1) time.
- Space complexity: O(n). The extra space required depends on the number of items stored in the hash table, which stores at most n elements.
If you like the content please follow me here @medium and at LinkedIn
