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.

You are given an array of size n and an integer k, you have to partition the array into k contiguous subarrays such that the sum of bitwise OR of all the subarrays is maximised. Each element should belong to a partition.

eg -> A = [1, 2, 3, 4], k = 2 1st way: [1], [2, 3, 4] -> (1) + (2 | 3 | 4) = 8 2nd way: [1, 2], [3, 4] -> (1 | 2) + (3 | 4) = 10 3rd way: [1, 2, 3], [4] -> (1 | 2 | 3) + 4 = 7 Hence, the answer is 10.

N = 10^3

This question came up in Trilogy Innovations OA round, Well, I arrived to a simple DP solution that was O(n^3), How can this be optimised further?

You are given an array A of integers, you have to choose two integers x, y such that summation min(abs(A[i] — x), abs(A[i] — y)) for each i in 1 to N is minimised.

e.g:

A = [1, 2, 6, 7]

x = 1, y = 7

(1 — 1) + (2 — 1) + (6 — 7) + (7 — 7) = 2

2 <= N < 10^3

I tried to solve this greedily but got WA.

There are two amazon centers, one in Bangalore and one in Hyderabad where the candidates need to go for interviews. A candidate needs to visit one of the centers and the expense would be on amazon. Each location needs to have half of the candidate(N, candidate number is even) and the cost associated with the travel expense needs to be minimized. Output the cost. Ex: For 6 candidates {20,40}, {10,60}, {5,80}, {60,10}{100,15}, {150,20}. Here lets assume cost is given {Bangalore, Hyderabad} thus first 3 candidates should go to Bangalore and next 3 should go to Hyderabad and total cost is 80.

Please help me out with the most efficient approach. The best I could do is O(n^2) dp solution.