diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/plot.md | 312 |
1 files changed, 312 insertions, 0 deletions
diff --git a/doc/plot.md b/doc/plot.md new file mode 100644 index 0000000..4f1139e --- /dev/null +++ b/doc/plot.md @@ -0,0 +1,312 @@ +# Capital Match Hiring Coding Challenge
+
+## Introduction
+
+Archaeologists and anthropologists would have a hard time believing that
+millenia ago, there was already a healthy and booming democracy. Yet recent
+evidence surfaced suggested that in the ancient Kingdom of Malodivo, the
+democratic way of life was the norm, even though it is a bit peculiar by
+modern standards. Not much was known about this Kingdom; about the only thing
+we have fully figured out was its parliamentary system of governance, owing to
+the fact that the sole piece of written evidence was the Kingdom's
+*Parliamentary Gazette*, a document recording the discussions and resolutions
+of the various bills in its Parliament.
+
+Reading through the *Gazette*, we can now piece together a few tidbits of the
+workings of the Parliament. The Parliament apparently meets every once in a
+while (the exact frequency is unknown because we have not yet figured out
+conversions between the Gregorian calendar and the calendar system used in the
+Kingdom), and the members, who represent the constituents in districts, submit
+bills for discussion and debate. The implementation of a bill requires
+funding, naturally. Such funding is provided by the taxes paid by the members
+of the parliament which ultimately comes from their constituents. In other
+words, instead of each citizen paying taxes individually to a central
+authority, each citizen pays the taxes to their elected members of the
+Parliament.
+
+Different members of the parliament have different priorities and have
+different levels of support for each bill. They signal their varying degrees
+of support through funding decisions: they would pledge different amounts of
+their constituents' tax dollars to each bill. It would be easy if the sum of
+the funds needed by all bills is equal to all the taxes collected; in this
+case, the members' wishes could be fulfilled exactly. However, more often than
+not, this does not happen. Owing to a booming economy, the total amount of
+funding required for all bills is often less than the total tax paid by all
+members. In this case, a widely cherished Article in the *Tax Code of the
+Kingdom of Malodivo* comes into effect:
+
+> Article XIV. All taxes collected by the Government but not used for the
+ implementation of any bill shall be refunded.
+
+Since the Parliament usually cannot pass enough bills to deplete the total
+taxes it collected, it will simply reduce the amount of tax paid, and the
+members will have a leftover amount. The citizens are happy because their
+effective tax rate is reduced. It is important that once the Parliament has
+decided on the funding needed for a bill, the bill cannot legally receive
+extra funds; it is however possible that a bill will receive less funds than
+the Parliament decides.
+
+Your task, is to write a program to determine the best combination of the
+funds from each member of the Parliament that go to each bill.
+
+## Scenario
+
+Suppose in the 137th Parliamentary Session of the Kingdom of Malodivo, four
+bills were introduced and passed:
+
+| Name of Bill | Category | Funds Needed |
+| ------------------------------------------------------ | -------- | ------------ |
+| An Act to Construct the Great Wall of Malodivo | Defense | ₡200,000 |
+| An Act to Construct Shelters for the Homeless | Welfare | ₡40,000 |
+| An Act to Fund the Development of Longer-Lasting Paper | Science | ₡14,000 |
+| An Act to Increase Retirement Benefits for Veterans | Welfare | ₡90,000 |
+
+As one could calculate, the total fund needed to implement these bills is
+₡344,000. Although in this example the sum happens to be a multiple of a
+thousand, generally the funds needed could be any nonnegative integer. (It's
+quite trivial to handle a bill that needs no funding: every member of the
+Parliament simply contributes ₡0 to the bill.)
+
+Each member of the Parliament also has a total amount of taxes collected:
+
+| District | Total Available Funds |
+| ----------------------------- | --------------------- |
+| District of Palolene | ₡200,000 |
+| District of Southern Palolene | ₡150,000 |
+| District of Lakos | ₡400,000 |
+
+For each member of the parliament, the member has listened to his/her
+constituents in a district and has decided how much of the taxes should go to
+each category. There is a bijection between each member and each district, so
+these two terms may be used interchangeably. For example, the District of
+Palolene has the following table of funds allocation:
+
+| Category | Funding Provided to *Each* Bill In This Category |
+| -------- | ------------------------------------------------ |
+| Defense | ₡1,000 |
+| Welfare | ₡3,000 |
+| Science | ₡5,000 |
+
+However, the district could also provide specific funding amount for each bill:
+
+| Name of Bill | Category | Funding Provided |
+| ------------------------------------------------------ | -------- | ------------------------ |
+| An Act to Construct the Great Wall of Malodivo | Defense | Use default for category |
+| An Act to Construct Shelters for the Homeless | Welfare | Use default for category |
+| An Act to Fund the Development of Longer-Lasting Paper | Science | ₡7,500 |
+| An Act to Increase Retirement Benefits for Veterans | Welfare | ₡500 |
+
+As you can see, the District of Palolene does not have a large population of
+veterans, so the constituents have collectively decided to provide fewer funds
+for this bill. In certain cases, the constituents may even decide to provide
+zero funding to a bill they vehemently dislike. On the other hand, the
+District decides that a durable writing medium is so important that it will
+allocate ₡7,500 instead of ₡5,000 to the bill. Indeed a district could support
+a bill so enthusiastically that it will decide to provide a higher amount than
+the default for the category. However in any case the amount will never be
+negative.
+
+Usually the total funding as decided above across all districts for a
+particular bill will exceed the amount required for that bill. In this case,
+you should reduce the contribution by each district proportionally. In other
+words, the proportions of the actual contribution among each district should
+be as similar as possible as the amount each district originally decides to
+provide. For example if a bill needs ₡10, but there are two districts and they
+are willing to provide ₡400 and ₡600 respectively, then these two districts
+will actually contribute only ₡4 and ₡6, satisfying the principle of
+proportionality. Again, since only the smallest unit of currency in this
+Kingdom is ₡1, all amounts are integers, and so suitable rounding needs to be
+performed.
+
+It should further be noted that the example above shows a prosperous year,
+when the citizens have made good money and have a lot of taxes to pay. It is
+quite possible that during a depression, the total available funds could
+dwindle to such small amount that they could not fund all the bills the
+Parliament has passed. In this case, the same principle of proportionality
+applies. For example if there are two bills and a district wishes to provide
+₡200 for one bill and ₡500 for another, but it only has ₡7 in total tax dollar
+collected, then it should contribute only ₡2 and ₡5 respectively towards these
+two bills. The issue with rounding also applies.
+
+Different categories of the bills will generally be implemented by different
+Ministries. For example the Ministry of Defense will receive the funds for the
+bills in the Defense category, etc. (There is a bijection between the
+categories of the bills and the ministries, so they could also be used
+interchangeably.) However, the citizens of the Kingdom of Malodivo are
+generally suspicious of corruption. They are worried that giving too much
+money to a particular Ministry will tempt its Ministers and staff to be
+corrupt and misuse the funds. Therefore, each District also has upper limits
+on how much money they will provide for each Ministry. The following table
+shows the limits for the District of Palolene:
+
+| Ministry | Maximum Funding Provided To All Bills In This Category |
+| -------- | ------------------------------------------------------ |
+| Defense | ₡3,000 |
+| Welfare | ₡3,199 |
+| Science | ₡15,000 |
+
+For example, the maximum funding for all bills in the Welfare category is
+capped at ₡3,199. Yet for the two bills in the Welfare category, the District
+of Palolene has decided to fund ₡500 for one of them and ₡3,000 for the other.
+The sum, ₡3,500, exceeds the maximum funding limit, ₡3,199. In this case, the
+maximum funding limit takes precedence; the actual funding provided will sum
+to ₡3,199, and ideally should be ₡457 and ₡2,742 respectively due to the
+principle of proportionality. It goes without saying that rounding issues also
+apply.
+
+The interaction between the three principles of proportionality may not always
+work out so well. It is your choice which proportionality is prioritized, or
+you can even devise a better principle of proportionality that takes into
+account all three in a balanced way.
+
+In the unlikely event that across all members, the total funding provided to a
+certain Ministry is capped so low that bills could not receive the full
+funding, the situation should be left as is. The Ministry will simply have
+less funds available to implement the bill. For example, suppose that the
+suspicion towards the Ministry of Welfare is widespread, and other members
+have similarly low caps for Welfare bills, then it is quite possible that the
+Ministry of Welfare could not receive enough funds; it'll just have to make do
+with that and heed this warning to reduce corruption, or potentially face the
+deprivation of funds and the Minister could be forced to resign.
+
+## Requirement
+
+Your program will read the above data in the format of a JSON document,
+perform computation, and write the result in a JSON document.
+
+You have the freedom to decide the schema for your input and output JSON
+documents.
+
+As an example, you can use the following as a starting point but feel free to
+change things as you see fit:
+
+```js
+{
+ "bills": [{
+ "name": "An Act to Construct the Great Wall of Malodivo",
+ "category": "Defense",
+ "amount": 200000
+ },
+ {
+ "name": "An Act to Construct Shelters for the Homeless",
+ "category": "Welfare",
+ "amount": 40000
+ },
+ {
+ "name": "An Act to Fund the Development of Longer-Lasting Paper",
+ "category": "Science",
+ "amount": 14000
+ },
+ {
+ "name": "An Act to Increase Retirement Benefits for Veterans",
+ "category": "Welfare",
+ "amount": 90000
+ }],
+ "districts": [{
+ "name": "Palolene",
+ "availableFunds": 200000,
+ "categoryDefaultFunding": [{
+ "category": "Defense",
+ "amount": 1000
+ },
+ {
+ "category": "Welfare",
+ "amount": 3000
+ },
+ {
+ "category": "Science",
+ "amount": 5000
+ }],
+ "billSpecificFunding": [{
+ "bill": "An Act to Increase Retirement Benefits for Veterans",
+ "amount": 500
+ },
+ {
+ "bill": "An Act to Fund the Development of Longer-Lasting Paper",
+ "amount": 7500
+ }],
+ "caps": [{
+ "category": "Defense",
+ "amount": 3000
+ },
+ {
+ "category": "Welfare",
+ "amount": 3199
+ },
+ {
+ "category": "Science",
+ "amount": 15000
+ }]
+ }]
+}
+```
+
+The schema for the output is entirely decided by you, but at the very least
+you should include the actual amounts that go towards each bill by each
+district. You may optionally include other helpful information such as whether
+a bill is fully funded, or the remaining balance of each district, or anything
+else that you see fit.
+
+### A Simplification
+
+It should also be noted that there are very few *hard requirements*. In fact
+there are only two:
+
+1. reading and writing data must be done in JSON;
+
+2. the program must be written in Haskell, but feel free to use any GHC
+ extensions or open-source Haskell libraries.
+
+As long as you fulfill these two requirements, we are interested in taking a
+look at your code and having further discussions.
+
+Besides these two, you should exercise your liberty in trying to follow the
+description above. If you deviate from the above (likely), you should document
+them either as comments in the program or in a separate writeup.
+
+Efficiency is not a primary concern here. We do not expect any particular
+Big-O complexity, but rather ask that your program finishes running in a
+reasonable human-scale of time, i.e. at most a minute or two.
+
+For your convenience, we have also provided a simplification of the problem
+that could serve as a nice starting point:
+
+* You may assume there are no maximum funding limits or bill-specific
+ amounts;
+
+* There is only one bill;
+
+* It just so happens that the amount for the bill (i.e.
+ funds needed) is greater than or equal to the sum of the amounts for each
+ district (i.e. total funds provided).
+
+You should first get this simplification working, and then gradually add more
+features and more complexities. Choose which features to implement according to
+your taste. It's perfectly fine even if you do not implement everything. We
+just want to see some working code, your design decisions, and your thought
+processes.
+
+## Unspecified Behavior
+
+You should have noticed that this document does not specify every detail. For
+example it specifies that the actual proportion should be as similar as
+possible to the specified proportions, but the precise measure of similarity
+is not specified here. You may use a widely used metric such as the L2 norm,
+but also feel free to come up with your own. For many places where the
+document is vague, it could very well be intentional and please pick anything
+that is reasonable.
+
+## Submission
+
+You are given a week to ponder and solve this. If you finish early, feel free
+to tell us; if you need a bit of extra time, also feel free to tell us so we
+can arrange an extension.
+
+Once you are done, please put your code in a private GitHub/Bitbucket
+repository or email us the code. We will look through your code. If we like
+what you have written, we will then schedule a chat over Hangouts or Skype and
+we will have further discussions about the code; otherwise we will provide
+written feedback to let you know why we think you are not a good fit for the
+role.
+
+Good luck!
|