Optimal Product Selection — Problem Statement & Solution Guide
Problem Description
You are given a list of products, where each product is an array containing its rating and price. Implement a function that takes this list and a maximum allowed budget as input, and returns the product with the highest rating that is within the budget. If there are multiple products with the highest rating within the budget, return any one of them.
Examples
Input
[[5, 50], [3, 30], [1, 10], [5, 50]]
Output
[5, 50]
Explanation: Step-by-step: Given the input list of products, we first sort the list in descending order based on the rating. Then, we iterate through the sorted list to find the first product that is within the budget. In this case, the first product with rating 5 and price 50 is within the budget, so we return it.
Input
[[10, 100], [8, 80], [6, 60], [4, 40]]
Output
[10, 100]
Explanation: Step-by-step: Given the input list of products, we first sort the list in descending order based on the rating. Then, we iterate through the sorted list to find the first product that is within the budget. In this case, the first product with rating 10 and price 100 is within the budget, so we return it.
Constraints
- 1 <= number of products <= 1000
- 1 <= product rating <= 5
- 1 <= product price <= 1000
- 1 <= max allowed budget <= 1000
Optimal Approach & Strategy
The optimized approach is to use a single pass through the list of products to find the product with the highest rating that is within the budget. This approach has a time complexity of O(n), where n is the number of products. It can be implemented using a simple loop that keeps track of the current highest rating and corresponding product.
Brute Force Approach
The brute force approach is to iterate over the list of products and compare each product's rating and price with the current highest rating and budget. This approach has a high time complexity and is not efficient for large inputs. It can be improved by using a more efficient data structure.
Verified Code Solutions
function recommendProduct(products, budget) {
let highestRatedProduct = null;
let highestRating = -Infinity;
for (let i = 0; i < products.length; i++) {
if (products[i][1] <= budget && products[i][0] > highestRating) {
highestRating = products[i][0];
highestRatedProduct = products[i];
} else if (products[i][1] <= budget && products[i][0] === highestRating) {
highestRatedProduct = products[i];
}
}
return highestRatedProduct;
}#include <iostream>
#include <vector>
using namespace std;
vector<int> recommendProduct(vector<vector<int>>& products, int budget) {
vector<int> highestRatedProduct;
int highestRating = 0;
for (int i = 0; i < products.size(); i++) {
if (products[i][1] <= budget && products[i][0] > highestRating) {
highestRating = products[i][0];
highestRatedProduct = products[i];
}
}
return highestRatedProduct;
}
int main() {
vector<vector<int>> products = {{5, 100}, {3, 50}, {4, 80}};
int budget = 100;
vector<int> recommendedProduct = recommendProduct(products, budget);
cout << "[" << recommendedProduct[0] << ", " << recommendedProduct[1] << "]" << endl;
return 0;
}class Solution {
public int[] optimalProductSelection(int[][] products, int budget) {
if (products.length == 0) {
return null;
}
int maxRating = 0;
int[] result = null;
for (int[] product : products) {
if (product[1] <= budget && product[0] > maxRating) {
maxRating = product[0];
result = product;
}
}
return result;
}
}def optimal_product_selection(products, budget):
if not products:
return None
max_rating = 0
result = None
for product in products:
if product[1] <= budget and product[0] > max_rating:
max_rating = product[0]
result = product
return resultfunction recommendProduct(products, budget) {
let highestRatedProduct = null;
let highestRating = -Infinity;
for (let i = 0; i < products.length; i++) {
if (products[i][1] <= budget && products[i][0] > highestRating) {
highestRating = products[i][0];
highestRatedProduct = products[i];
} else if (products[i][1] <= budget && products[i][0] === highestRating) {
highestRatedProduct = products[i];
}
}
return highestRatedProduct;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.