Linkedin Online Assessment Question With Easy Explanation and Solution

 Dynamic Fares at the Grand Terminal

During the festive season rush, the Grand Railway Terminal is deploying a new dynamic pricing algorithm for its premium express trains.

There are N different booking counters at the terminal. Currently, the i-th counter has an initial allocation of Ai premium tickets available. The terminal's revenue system operates on a strict demand-driven pricing model: the cost of purchasing a ticket from any counter is exactly equal to the number of tickets currently remaining at that specific counter.

Whenever a ticket is sold from a counter, the remaining inventory at that counter decreases by 1, and consequently, the price for the next ticket from that same counter instantly drops by 1 coin.

A massive crowd is waiting, but due to strict departure constraints, the Station Master can issue a maximum of K tickets in total across all counters. Each customer in line buys exactly one ticket.

Your task is to help the Station Master determine the maximum possible revenue that can be generated by optimally choosing which counters to sell tickets from. Since the revenue can be astronomically large, you must output the final maximum revenue modulo 10^9 + 7.

Input Format

• The first line contains two space-separated integers, N and K — representing the number of ticket counters and the maximum total number of tickets the Station Master can sell.

• The second line contains N space-separated integers A1, A2,......, AN — where Ai represents the initial number of tickets available at the i-th counter.

Output Format

• Print a single integer representing the maximum total revenue the terminal can earn, modulo 10^9 + 7.

Constraints

• 1<= N<=10^5

• 1<=Ai, K<=10^6
  
  

Example 1

Input:

5 3 

4 3 6 2 4

Output:

15

Explanation:

The optimal strategy is to sell:

1. One ticket from the 3rd counter (Remaining: 6 --> 5). Revenue = 6

2. Another ticket from the 3rd counter (Remaining: 5 --> 4). Revenue = 5

3. One ticket from either the 1st or 5th counter (Remaining: 4-->3). Revenue = 4

Total optimal revenue = 6 + 5 + 4 = 15.

Example 2

Input:

6 2

5 3 5 2 4 4

Ouput:

10

Approach: Greedy with Max-Heap (Priority Queue)

To maximize our earnings, we must always greedily sell the most expensive ticket available at any given moment.

Since the price of a ticket is equal to the number of remaining tickets a seller has, every time we sell a ticket, its price decreases by 1. This means the "highest price" is constantly changing. To efficiently track and retrieve the maximum value dynamically, a Max-Heap (Priority Queue) is the perfect data structure.

By simulating the process using a Max-Heap, we can always extract the current highest ticket price, add it to our total profit, and then push the decreased price back into the heap for future considerations.

Algorithm: Max-Heap (Priority Queue) Approach

Initialization

Before we begin the simulation, we need to set up our tracking variables and data structures:

• TotalRevenue: Set to 0. This will store our maximum accumulated earnings.

• Modulo Constant (MOD): Define as 10^9 + 7 to prevent integer overflow when adding up large revenues.

• Data Structure: Initialize an empty Max-Heap (or a Priority Queue explicitly configured to pop the maximum value first).

Step 1: Build the Heap

First, we organize our available tickets so we always know which seller has the most:

1. Loop through every element in the given ticket array.

2. Insert each element into the Max-Heap.

Note: The heap will automatically arrange the elements so that the highest ticket count is always at the top, taking O(N) time if built optimally.

Step 2: Simulate Ticket Sales

Now, start a loop that continues as long as we still have tickets to sell (K > 0) AND the Max-Heap is not empty:

• Extract: Pop the top element from the Max-Heap and store it in a variable called CurrentPrice.

• Check Exhaustion: If CurrentPrice is 0, break out of the loop. This means all tickets everywhere are completely sold out.

• Calculate Profit: Add CurrentPrice to TotalRevenue.

• Apply Modulo: Update TotalRevenue = TotalRevenue % MOD to keep the number within limits.

• Update Ticket Count: Subtract 1 from CurrentPrice (since one ticket from this seller was just sold).

• Re-insert: If the updated CurrentPrice is still strictly greater than 0, push it back into the Max-Heap.

• Decrease Quota: Subtract 1 from K (since one ticket has been successfully allocated).

Step 3: Return the Result

Once the loop finishes (either because your quota K reached 0 or all tickets sold out), return the final accumulated value of TotalRevenue.

Time Complexity:

• Heap Construction: Building the initial heap using heapify() takes O(N) time, where N is the number of ticket sellers (size of the array).

• Processing K Tickets: For each of the K tickets we sell, we perform a pop and an optional push operation on the heap. Each heap operation takes O(log N) time. Doing this K times takes O(K log N) time.

• Total Time Complexity: O(N + K log N). This is highly optimal and will easily pass the constraints.

Space Complexity:

• Total Space Complexity: O(N). We are storing the frequencies of all N ticket sellers in our priority queue. No additional space proportional to K is used.
  import heapq

Code in Python:

import heapq

class Solution:

    def maxAmount(self, arr, k):

        MOD = 10**9 + 7

       

        pq = [-x for x in arr]

        heapq.heapify(pq)

       

        maxamount = 0

       

        while k > 0 and pq:

           

            price = -heapq.heappop(pq)

           

           

            if price == 0:

                break

               

            maxamount = (maxamount + price) % MOD

           

            if price - 1 > 0:

                heapq.heappush(pq, -(price - 1))

               

            k -= 1

           

        return maxamount

IF YOU HAVE ANY DOUBT FEEL FREE TO ASK IN COMMENTS!! HAPPY CODING