lol_py's blog

Nutanix OA coding question, please help!!
By lol_py, 16 months ago, In English

You are given two integer arrays p and q of length n each and an integer maxPower. There are n machines, ith machine consumes p[i] power and produces q[i] quantity. You need to maximize the quantity by consuming not more the maxPower power. Partial consumption of power by a machine is not allowed.

1 <= n <= 36

1 <= maxPower < 10^9

1 <= p[i], q[i] < 10^9

eg:

n = 3

p = [2, 2, 2]

q = [1, 2, 3]

maxPower = 4,

If we select 1st and 2nd index(0 based), the consumed power is 4 and the quantity produced is 5 which is maximum in this case.

I think this is a standard 0/1 knapsack problem but with the given constraints how can we solve this problem.

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
16 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I guess it can be solved using meet in the middle. (generally for meet in the middle constraints are around n<=40).

First we will divide the array into 2 arrays. Then we can write a recursion for generating all the possible arrays storing information of power consumed and quantity produced. Sort the 2 generated arrays. Then we can use lower/upper bound to find the optimum answer.

→ Reply
»
16 months ago, # |
← Rev. 6   Vote: I like it -24 Vote: I do not like it

anyone help?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    do you even consider reading the questions/blogs before replying ?

    → Reply