-
Notifications
You must be signed in to change notification settings - Fork 0
/
DESCRIPTION
38 lines (30 loc) · 1.96 KB
/
DESCRIPTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Imagine that you manage a t-shirt printing company. Each morning you review
all orders placed the prior day and determine how long each order will take to
fulfill. On any given day, only a certain number of your printing machines
are operational. Your job is to schedule each printing job with one of the
operational printing machines in such a manner that (a) all t-shirts are
printed in the least amount of time, and (b) the distribution of work across
machines is as fair as possible (i.e. the standard deviation of the time each
machine spends working is minimized).
Your objective is to write a FairDistribution class that satisfies the
following test cases. The code in the test cases is sufficient to define the
methods you must implement.
This is an NP complete problem, and as such I have only provided very small
datasets in the test cases. Test case #3 takes the longest to solve (See
**Notes below about how to run the Test Case #3) and you may find it easier
to comment it out early in your development phase. On a MBP Pro with a 2.4
GHz dual core processor and 4GB RAM, it took just over 3 minutes to solve.
The other three test cases took only a couple of seconds.
Note that test cases 2 and 4 define specific distributions against which you
can verify. Test cases 1 and 3 have more than one acceptable distribution
and as such I have not provided a specific distribution to test against.
Note also that there is a well known algorithm that provides a much
faster though not optimal solution. It will pass all tests except for test
case #3. If you are only able to determine this particular solution, please
still consider submitting your solution for consideration.
** Notes:
To accommodate the fact that Test Case #3 takes a long time to run, you
can run the test normally, and TC#3 will not run. When you want the TC#3
to run, then you can run the following:
ruby test_solution_acceptance.rb full
The word "full" will signal it to run all the test cases.