Amazon - Chennai OA Questions

1. Code Question 1
Amazon has developed a system for managing events and distributing prizes. Recently, a global coding challenge was held with n participants. Each participant earned a score represented by the array points, where points[i] is the score of the i th participant. There are m prizes, and values[i] represents the value of the i th prize.

The goal is to distribute the prizes fairly based on the following rules:

Participants with the same score must receive a prize with the same value.

Participants with higher scores must receive prizes with higher values than those with lower scores.

Given the array points (with size n) and the array values (with size m), determine the prize value each participant will receive. If multiple fair distributions are possible, return the lexicographically smallest distribution.

An array x is lexicographically smaller than an array y if x[i] < y[i], where i is the first position where x and y differ, or if |x| < |y| and x is a prefix of y. For example, [2, 3, 4] is lexicographically smaller than [2, 4, 3] because at the second position, 3 is smaller than 4.

Function Description
Complete the function findFairDistribution in the editor below.

findFairDistribution has the following parameters:

int points[n]: an array of integers denoting the number of points for all participants.

int values[m]: an array of integers denoting the value of all the prizes.

Returns
int[]: an array of integers where the i
th
integer denotes the value of the prize that the i
th
participant will receive.

Constraints
1≤n,m≤2⋅10^5


1≤points[i],values[i]≤10^9


Example
Some of the possible prize distributions:

Prizes Fairness Reason
[4, 3, 2, 3] Fair -
[4, 2, 2, 2] Unfair The second and third participants received a prize with the same value, but the second participant had more points.

[3, 4, 2, 4] Unfair The second participant received a prize with more value than the first participant who got more points.

[4, 4, 2, 3] Unfair The second and fourth participants have the same amount of points, but each received a prize with different values.

The first distribution is the only fair distribution. Hence the answer is [4, 3, 2, 3].

Sample Input 0
STDIN
3
5
5
5
6
2
2
2
3
3
3

Function
points[] size n = 3
points = [5, 5, 5]
values[] size m = 6
values = [2, 2, 2, 3, 3, 3]

Sample Output 0
STDIN
2
2
2

Explanation
All participants have the same amount of points, so they will all receive prizes with the same value. Within [2, 2, 2] or [3, 3, 3], since the first array is lexicographically smaller, hence the answer is [2, 2, 2].


Coding Challenge – Question 2

An Amazon fulfillment center receives a large number of orders each day. Each order is associated with a range of prices of items that need to be picked from the warehouse and packed into a box.

There are n items in the warehouse, which are represented as an array items[n]. The value of items[i] represents the value of the i-th item in the warehouse, and subsequently, there are m orders.

The start index and end index for the i-th order are represented in the arrays startIndex[i] and endIndex[i]. Also, startIndex[i] and endIndex[i] are 0-index based.

For each order, all the items are picked from the inclusive range from startIndex[i] through endIndex[i].

Given arrays items, startIndex, endIndex, and query:
For each query[i], find the count of elements in the range with a value strictly less than query[i].

Example:

n = 5
items = [1, 2, 5, 4, 5]
m = 3
startIndex = [0, 0, 1]
endIndex = [1, 2, 2]
query = [2, 4]
Orders:

OrderNumber Start Index End Index Picked Items
1st 0 1 [1, 2]
2nd 0 2 [1, 2, 5]
3rd 1 2 [2, 5]

Over the 3 orders, the picked items are:
[1, 2, 1, 2, 5, 2, 5]

For the first query (query[0] = 2), 2 picked items have values less than 2.

For the second query (query[1] = 4), 5 picked items have values less than 4.

Answer: [2, 5]