There is list of offers and it's criteria, which looks like this.
Each offer will have list of product ids, if a cart has all these products, then the corresponding discount would be applicable.
Now for a given cart, multiple offers may be applicable. In that case, offer which returns the max discount should be returned.
Example
Lets say the Cart contains these products [1,2,3,5,7,6,9]
List of offers are:
Offer 1- Product I'd [1,3,8] 10%
Offer 2 product ids [1,2,5,9] 15%
Offer 3 product ids [2,5,6] 25%
Offer 4 product ids [1,2,3,4] 30%
Output : 25%
For the cart, offer1 is not applicable as product I'd 8 is not there in the cart.
Offer2 is applicable as product I'd 1,25,9 all are available in the cart.
Offer3 is also applicable
Offer 4 is not applicable as product I'd 4 is not present in the cart.
Thus output would max discount from offer 2 and offer 3.
Which is 25%
Question is how should we store these offers so that we should get the offer amount with minimum time.
Assume this is for a big retail company, where the request comes in large number.
Can anyone please let me know the right data structures for this?
Hi,
You can use two different data structure to maintain the time complexity.
Max-Heap
Hash Map
Hash-Map to put all the products for efficient lookup
Go through all the offers and check whether their elements exist in Hash-map.
If yes , put them in heap.
Max-Heap will contain discounts in descending order but before inserting into heap you need to check that the list of order with id's belongs to product like Product I'd [1,3,8] doesn't belong to original list of these : This is step 1
products [1,2,3,5,7,6,9]
After Insertion you can get Max discount in o(1) in max-heap.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
There is list of offers and it's criteria, which looks like this.
Each offer will have list of product ids, if a cart has all these products, then the corresponding discount would be applicable.
Now for a given cart, multiple offers may be applicable. In that case, offer which returns the max discount should be returned.
Example
Lets say the Cart contains these products [1,2,3,5,7,6,9]
List of offers are:
Offer 1- Product I'd [1,3,8] 10%
Offer 2 product ids [1,2,5,9] 15%
Offer 3 product ids [2,5,6] 25%
Offer 4 product ids [1,2,3,4] 30%
Output : 25%
For the cart, offer1 is not applicable as product I'd 8 is not there in the cart.
Offer2 is applicable as product I'd 1,25,9 all are available in the cart.
Offer3 is also applicable
Offer 4 is not applicable as product I'd 4 is not present in the cart.
Thus output would max discount from offer 2 and offer 3.
Which is 25%
Question is how should we store these offers so that we should get the offer amount with minimum time.
Assume this is for a big retail company, where the request comes in large number.
Can anyone please let me know the right data structures for this?
Hi,
You can use two different data structure to maintain the time complexity.
Hash Map
Hash-Map to put all the products for efficient lookup
Go through all the offers and check whether their elements exist in Hash-map.
If yes , put them in heap.
Max-Heap will contain discounts in descending order but before inserting into heap you need to check that the list of order with id's belongs to product like Product I'd [1,3,8] doesn't belong to original list of these : This is step 1
products [1,2,3,5,7,6,9]
After Insertion you can get Max discount in o(1) in max-heap.