This is one of the questions I had for an Amazon OA test, I banged my head against it for some time, and found it very hard

to figure out what they were asking as there were some discrepancies in the instructions.

This was an automated evaluation , so no one was around to ask for clarifications.

there are n items, each associated with two positive values a[i] and b[i].

There are infinitely many items of each type numbed from 1 to infinity and the jth item of the ith type costs a[i] (j 1)*b[i] units.

Note each item of each type can be purchased at most once.

Determine the minimum possible cost to purchase exactly m items.

Example

Given n=3, a=[2,1,1], b =[1,2,3], m=4

The optimal types to buy are:

* Choose type i=1, This is the first purchase of this type , so j=1. This item costs a[1] (j-1)*b[i] = 1 (1 - 1) * 2 = 1

* Choose type i=2, This is the first purchase of this type , so j=1. This item costs 1 (1-1)*3=1

* Choose type i=0, This is the first purchase of this type , so j=1. This item costs 2 (1-1)*1=2

* When second item of any type is purchased, j=2. The cost of the item for each type will be:

• Type i=0, costs a[0] (j-1)*b[0]=2 (2-1)*1=3

• Type i=1, costs 1 1*2=3

• Type i=2, costs 1 1*3=4

• Choose either the first or second type as they cost the least.

The total cost to purchase is 1 1 2 3=7

Function Description

public static long getMinimumCost(List<int> a, List<int> b, int m){

}

So for what it's worth here are a few points I get lost at:

* In the example they have n=3 but the function does not take an n as a parameter

so how do you know how to limit the number of types? they did 1, 2, 0 in the example.

Without the N , I would just take 4 "first purchases"

* I am unsure of what they mean by "Note each item of each type can be purchased at most once."

My guess is they mean for a type of X you can only use a[i], b[i] once. Which could lead to

issue when m is higher number that you run out of entries in the a[] and b[]