Paypal Questions

Round 1

Questions: Our train company wants to assign train cars to ticket inspectors fairly. We want to minimize the difference in the number of tickets between the inspector with the most total tickets and the one with the fewest.

Inspectors must follow the following rules:

• They must inspect cars in order.
• Every inspector must inspect at least one car.
• Inspectors must inspect only consecutive cars.

For five cars with occupancies 18, 15, 20, 16, 17 and three inspectors, the cars may be split as follows:

I 1 | I 2 | I 3 | Diff
- [1, 1, 1, 2, 3] ( 53 ,  16 ,  17 ,   37 )
- [1, 1, 2, 2, 3] ( 33 ,  36 ,  17 ,   19 )
- [1, 1, 2, 3, 3] ( 33 ,  20 ,  33 ,   13 )
- [1, 2, 2, 2, 3] ( 18 ,  51 ,  17 ,   34 )
- [1, 2, 2, 3, 3] ( 18 ,  35 ,  33 ,   17 )
- [1, 2, 3, 3, 3] ( 18 ,  15 ,  53 ,   38 )

The one with a difference of 13 is the fairest. If there are multiple options that are equally fair, return any of them.

Write a function that accepts a collection of how many people are in each car and the number of inspectors available and returns the fairest split.

Time limit: 30 mins

Is it doable in 30 mins?