Find Max Products Amazon OA 2023 Solution

Want to solve Find max products Amazon OA 2023?, if yes then this article is for you.

Make sure you check the List of Amazon OA questions in the year of 2022 and 2023. Today, we are going to see another problem from amazon oa called Find max products which was asked in 2022, this questions might be still active in some of the Amazon OA so save all the solutions, now lets see how can we solve this problem.

Contents

1 Find max products Amazon OA 2023 Solution
- 1.1 SOLUTION
2 Amazon OA 2023 Questions with Solution

Find max products Amazon OA 2023 Solution

Amazon Fresh is a new grocery store designed from the ground up to offer a seamless grocery shopping experience to consumers. As part of a stock clearance exercise at the store, given many piles of fresh products, follow the rules given below to stack the products in an orderly manner.

There are a total of n piles of products.
The number of products in each pile is represented by the array numProducts.
Select any subarray from the array numProducts and pick up products from that subarray such that the number of products you pick from the th pile is strictly less than the number of products you pick from the (i+1)^th pile for all indices i of the subarray.

Find the maximum number of products that can be picked.

Example

The numbers of products in each pile are numProducts = [7, 4, 5, 2, 6, 5].

These are some ways strictly increasing subarrays can be chosen (1-based index):

Choose subarray from indices (1, 3) and pick products [3, 4, 5] respectively from each index, which is 12 products. Note that we are forced to pick only 3 products from index 1 as the maximum number of products we can pick from index 2 is 4 and we need to make sure it is greater than the number of products picked from index 1.
Choose subarray from indices (3, 6) and pick products [1, 2, 4, 5] respectively from each index, which is 12 products. Similar to the above case, we are forced to pick only 1 product from index 3 as the number of products at index 4 is only 2.
Choose subarray from indices (3, 5) and pick products [1, 2, 6] respectively from each index, which is 9 products.
Choose subarray from indices (1, 1) and pick all the 7 products.

The maximum number of products is 12.

Function Description

Complete the function findMaxProducts in the editor below.
findMaxProducts has the following

parameters:

int numProducts[n]: the number of products in each pile.

Returns
int: the maximum number of products that can be picked

Constraints

1 ≤ n ≤5000
1 ≤ numProducts[i] <10⁹

Input

STDIN      FUNCTION
-------     -------------
6      ->  numProducts[] size n = 6
2      ->  numProducts = [2, 9, 4, 7, 5, 2]
9
4
7
5
2

Output

Explanation

A few examples of how you can pick the products (1-based index):

Choose subarray from indices (1, 2) and pick products [2, 9] respectively from each index, which is 11 products.
Choose subarray from indices (1, 4) and pick products [2, 3, 4, 7], which is 16 products.
Choose subarray from indices (1, 5) and pick products [1, 2, 3, 4, 5], which is 15 products.

SOLUTION

Program: Find max products Amazon OA Solution in Java

Explanation: Using DP
The idea is very simple, simulate what we would do if we were doing this manually.

Pick any pile to start with. Pick any number of products in that pile and move to the next one.
Based on the number you picked from the previous pile, you can either pick a bigger number of products from the current pile or pick 0 if available products are less than what you picked from the previous pile.
Repeat this process until you find a combination subarray of piles that give you the max products possible.

Using memoization to avoid doing unnecessary work, the idea is that for each pile, the max number of products you can pick is dependent on how many you picked in the previous pile, so when we calculate the max for a pile, we can save that like memo [pileIndex] [previousPileProductsCount] = max-we-can-pick-from-current-pile.

public static void main(String[] args) {
        int[] piles = new int[] { 7, 4, 5, 2, 6, 5 };

        // initialize the memo, this code could be simplified by using a map
        int maxPile = 0;
        for (var pile : piles) {
            maxPile = Math.max(maxPile, pile);
        }
        int n = piles.length;
        int[][] memo = new int[n][maxPile];
        
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i], -1);
        }

        // go through the piles one by one, and find the max we can get if
        // we started at said pile
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, dfs(piles, i, 0, memo));
        }

        System.out.println(max);
    }

    private static int dfs(int[] piles, int index, int prevPileContribution, int[][] memo){
        /**
         * Our dfs termination conditions:
         * 1. we reached the end of piles array.
         * 2. current pile products is less than or equal to what we picked from previous pile.
         * 3. we have calculated the max for this pile before given the same amount picked from the previous pile
         *  */ 
        if(index == piles.length) return 0;
        if(piles[index] <= prevPileContribution) return 0;
        if(memo[index][prevPileContribution] != -1) return memo[index][prevPileContribution];
        
        int pileMax = 0;
        /**
         * loop through the products in this pile from 
         * min = products picked from previous pile +1
         * max = the max products available in this pile
         */
        for(int i=prevPileContribution+1; i<= piles[index]; i++){
            int tempMax = i+ dfs(piles, index+1, i, memo);
            pileMax = Math.max(pileMax, tempMax);
        }

        // store the max we can pick from this pile given what we picked from previous pile
        memo[index][prevPileContribution] = pileMax;
        return  pileMax;
    }

Program: Find max products Amazon OA Solution in Python

Using DP. Not sure if this will work. The time complexity will be O(max(product)*n).

def amazon_fresh(products):
    @lru_cache(None)
    def dp(i, prev):
        if i == len(products):
            return 0

        product = products[i]
        if product < prev:
            return 0

        ans = dp(i + 1, prev)
        for j in range(products[i], -1, -1):
            if j > prev:
                ans = max(dp(i + 1, j)+j, ans)
        return ans

    return dp(0, 0)

Program: Find max products Amazon OA Solution in C++

int solve(vector<int> arr){
    int res = 0;
    vector<int> darr(arr.size());
    darr[arr.size()-1] = arr[arr.size()-1];
    for(int i = arr.size()-2; i>=0;i--){
        if(arr[i] <arr[i+1]){
            darr[i] = arr[i];
        }else{
            darr[i] = arr[i+1]-1;
        }
        if(darr[i] == 0){
            darr[i] = arr[i];
        }
    }
    int sum = arr[0];
    for(int i=1;i<arr.size();i++){
        if(arr[i]<arr[i-1]){
            res = max(res,sum);
            sum=arr[i];
        }else{
            sum+=arr[i];
        }
    }
    res = max(res,sum);
    
    sum = darr[0];
    for(int i=1;i<darr.size();i++){
        if(darr[i]<darr[i-1]){
            res = max(res,sum);
            sum=darr[i];
        }else{
            sum+=darr[i];
        }
    }
    res = max(res,sum);
    return res;
}

int main()
{
    vector<int> arr = {7,4,5,2,6,5};
    int res = solve(arr);
    cout<<res<<endl;
    return 0;
}

Amazon OA 2023 Questions with Solution

2 thoughts on “Find max products Amazon OA 2023 Solution”

Kenny
October 23, 2022 at 9:26 pm
def findMaxProducts(array):
if not array:
return 0
i = 0
currentMaxProducts = 0
while i < len(array):
candidateMaxProducts, i = recursiveHelper(i, 0, array)[0], recursiveHelper(i, 0, array)[1]
currentMaxProducts = max(currentMaxProducts, candidateMaxProducts)
return currentMaxProducts
def recursiveHelper(currentIdx, prevElement, array):
if currentIdx == len(array):
return (0, currentIdx) # next starting point
currentProducts = array[currentIdx]
if currentProducts <= prevElement:
return (0, currentIdx) # next starting point
maxProducts = 0
maxDepthReached = 0
for currentProductCount in range(prevElement + 1, currentProducts+1):
result = recursiveHelper(currentIdx + 1, currentProductCount, array)
candidateMax = currentProductCount + result[0]
maxProducts = max(candidateMax, maxProducts)
maxDepthReached = max(result[1], maxDepthReached)
return (maxProducts, maxDepthReached)
print(findMaxProducts([2,9,4,7,5,2]))
Kenny
October 25, 2022 at 6:50 pm
# DP Solution
def findMaxProducts(array):
if not array:
return 0
i = 0
currentMaxProducts = 0
memo = [[None for _ in range(max(array)+1)] for _ in range(len(array))]
while i < len(array):
candidateMaxProducts = recursiveHelper(i, 0, array, memo)
currentMaxProducts = max(currentMaxProducts, candidateMaxProducts)
i += 1
return currentMaxProducts
def recursiveHelper(currentIdx, prevElement, array, memo):
if currentIdx == len(array):
return 0
currentProducts = array[currentIdx]
if currentProducts <= prevElement:
return 0
if memo[currentIdx][prevElement] is not None:
return memo[currentIdx][prevElement]
maxProducts = 0
minDepthReached = len(array)
for currentProductCount in range(prevElement + 1, currentProducts+1):
result = recursiveHelper(currentIdx + 1, currentProductCount, array, memo)
candidateMax = currentProductCount + result
maxProducts = max(candidateMax, maxProducts)
memo[currentIdx][prevElement] = maxProducts
return maxProducts
print(findMaxProducts([7,4,5,2,6,5]))

Find max products Amazon OA 2023 Solution

SOLUTION

Amazon OA 2023 Questions with Solution

2 thoughts on “Find max products Amazon OA 2023 Solution”

Leave a Comment Cancel reply