Google will, probably, abstract away the low level details (network communication, concurrency primitives, etc.) in the Distributed Code Jam problems, since it's only 3 hours long.
The solution will most likely be composed of 2 parts. First a divide function (doing the calculation) and then a combine function(collecting node results and outputting the answer).
Now for the given problem example, let's say that we have a sandwich that is 100 units long. Each unit has a taste value. If we were only allowed to eat from the sides, we would find maximum subsequence sums, one starting from the left and the other from the right. It's pretty straightforward.
Now consider the length to be 10^10 distributed across 100 nodes.
There are two key observations:
- A node's dataset might be partially or completely in the solution or the solution doesn't involve this node's dataset.
- There will be edge nodes. One containing the left endpoint and the other containing the right endpoint (They might be the same).
First, we send a query to each node for the sum of data they have and apply the same algorithm to find two sums(from left, from right). After we find these values we query the edge nodes to learn the exact borders of the subsequences (Since we will only find the approximate borders by only querying the sums).
Read full article from (10) What approach can be used to solve a sample problem distributed from the Google Code Jam? - Quora
No comments:
Post a Comment