Optimization of a hackerrank algorithm

Question

I got asked this on hacker rank and I haven't figured out a solution that didn't run out of allotted time. I used php and allotted time was 9 seconds...

The idea is there are "ticket stalls" with a certain number of tickets, say 9. Any ticket they sell is priced at the number of tickets that remain, so first ticket would be $9, second $8 etc...

You're given two lines of data, say:

2 4
1 5

The first row contains two numbers:

1. The number of stalls
2. How many tickets are sold

The second line contains a list of how many tickets each stall has initially, so in this case stall 1 has 1 ticket, stall 2 has 5 tickets.

The problem: what is the maximum amount of money you can make selling the given number of tickets?

In this case, you sell four tickets from stall two for a price of 5 + 4 + 3 + 2 = $14

So how do you solve it. I figured out two ways, both of which ran out of time

1. Load the stall numbers (second line) into an array. Go through that array N times (the number of tickets to sell) picking the largest number out, adding it on to an aggregator, decreasing that number. Then you have the total in the aggregator.

2. Load the stall numbers into an array. Sort the array. Go backwards through the array and as you do: store that number (current), add it to the aggregator, go to the next value. If it is the same (current), then add it to aggregator, subtract 1 from it, keep going. If it is different, go back to the end of the array and start again. Do that N times (the internal loop, not the external one).

The problem: neither one worked.

Can anyone think of a better solution?

Answer 1

If you are afraid of DP, this is the O(n) solution you should try. Following code considers only the largest element and go on decreasing it until we reach the required ticket count. It keeps track of multiplication factor by storing it as value in hashMap. In the end if number of tickets is greater than required tickets, it subtracts recently added ticket price from the result until number of tickets becomes equal to required tickets.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class TicketClass {
    public static void main(String[] args){
        int[] arr = {10,10,2,8,6,4};
        int ticket = 23;
        Arrays.sort(arr);
        int mul = 1;
        int k = 0;
        System.out.print("Hello World");
        long res = 0;
        Map<Integer,Integer> hm = new HashMap<>();
        for(int i:arr){
            if(hm.containsKey(i)){
                hm.put(i,hm.get(i)+1);
            }
            else
                hm.put(i,1);
        }

        int curr = arr[arr.length-1];

        while(k < ticket){
            mul=hm.getOrDefault(curr,mul);
            res += curr*mul;
            curr--;
            k += mul;
            if(hm.containsKey(curr))
                hm.put(curr,hm.get(curr)+mul);
        }

//End of while loop
        curr++;
        while(k > ticket){
            k--;
            res -=curr;
        }
        System.out.println("ticket "+k);
        System.out.println(res);
    }
}

Answer 2

Here is an implementation in PHP, this does not create an additional array as some other answers do. There are always a bunch of different ways to solve this problems, look this over and it may give you ideas in the future. There are lots of ways to improve this for practical use, but this was just to show alternative way to quickly solve the problem

class booth {

public $booths = [];
public $left = 0;
public $count = 0;
public $total = 0;
public $booth = 0;
public $nextBooth = 0;

function __construct() {
    $this->booths = [3, 7, 5, 2, 0, 2, 5, 15, 9, 1, 39, 91, 0, 58, 29];
    $this->left = 25;

    sort($this->booths);

    $this->booth = array_pop($this->booths);


    while($this->left > 0 && count($this->booths) > 0) {
        $this->count++;
        $this->nextBooth = array_pop($this->booths);        
        $this->countTotal($this->booth - $this->nextBooth);
    }

    // found end of array -- clear out any that are left
    if($this->left > 0)
        $this->countTotal(1);

    echo "total: " + $this->total."\r\n";
}

// everything global except loops
function countTotal($loops) {

    for($i = 0; $i < $loops, $this->left > 0; $i++) {
        if ($this->count > $this->left) 
            $this->count = $this->left;

        $this->total += $this->booth * $this->count;
        $this->left -= $this->count;
        $this->booth--;

    }
}

}

new booth();

Answer 3

1. Create an array of the number of stalls that have an amount of tickets remaining. (so {0, 3, 0, 2} means 2 stalls have three tickets and 3 stalls have one ticket)
2. decrement the highest non-zero entry, increment the entry below it, and add that entry's index to your total.
3. repeat #2 once for every ticket sold.

There's also an obvious way to improve this by multiplying out by MIN(count in highest stall, remaining tickets to be sold).

NOTE: in order for this to perform well, your implementation language must have true arrays (i.e., constant access time, regardless of the index). I do not know PHP, but some languages (JS?) use sequential lists to mimic arrays, but do not have the same performance.

---

Below is the Java implementation of the mentioned approach (read through comments to understand better):

        int[] stalls = new int[] { 4, 7, 1, 4, 8, 8 };
        int t = 4;

        Arrays.sort(stalls);

        int tickets = stalls[stalls.length - 1];
        int[] dp = new int[tickets + 1];

        for (int i = 0; i < stalls.length; i++) {
            dp[stalls[i]]++;
        }

        int total = 0;
        int i = dp.length - 1;

        while (t > 0) {
            if (dp[i] > 0) {
                total += i;
                t--;
                dp[i]--;
                dp[i - 1]++;
            } else {
                i--;
            }
        }

        System.out.println(total);

Answer 4

Little optimization on the MaxHeap solution:

You don't need to remove tickets one by one. If you have a top window, you need to know how many tickets it has and how many tickets the next one has. Then you can remove the difference and calculate the total price in one operation.
With a slight modification you can do the same if you have several windows with the same max number of tickets.

Answer 5

Let's see why your solution times out.

Load the stall numbers (second line) into an array. Go through that array N times (the number of tickets to sell) picking the largest number out, adding it on to an aggregator, decreasing that number. Then you have the total in the aggregator.

This is O(N*M), where N is the number of tickets to sell, and M is the number of ticket booths. It's pretty much a brute force approach, which often is not enough to beat hackerrank's tests.

Load the stall numbers into an array. Sort the array. Go backwards through the array and as you do: store that number (current), add it to the aggregator, go to the next value. If it is the same (current), then add it to aggregator, subtract 1 from it, keep going. If it is different, go back to the end of the array and start again. Do that N times (the internal loop, not the external one).

Maybe it is me, but I don't really understand what you mean here. From what I see it sounds like this is still O(N*M). How do you handle cases where a large number of tickets was decreased so many times that it broke the sort you made before?

What you need here is a data structure that can efficiently retrieve the current maximum, and can efficiently pop / insert new elements. It looks like a max-heap is a good candidate. Just keep the number of available tickets in each booth in a max-heap. To sell N tickets with M booths, do this N times:

1. Extract the maximum - O(log(M))
2. Add it to the result accumulator - O(1)
3. Decrement it - O(1)
4. Insert it into the heap - O(log(M))

Overall complexity is O(N*log(M)), which is probably the best you can do.

C++ implementation:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int max_revenue(vector<int> &tickets, int n) {

    make_heap(tickets.begin(), tickets.end());

    int res = 0;
    for (int i = 0; i < n; i++) {
        res += tickets.front();
        pop_heap(tickets.begin(), tickets.end());
        tickets[tickets.size()-1]--;
        push_heap(tickets.begin(), tickets.end());
    }

    return res;
}

int main(void) {
    int booths;
    cin >> booths;
    int n;
    cin >> n;

    vector<int> tickets(booths);
    for (int i = 0; i < booths; i++)
        cin >> tickets[i];

    cout << max_revenue(tickets, n) << endl;

    return 0;
}