This is a Google interview question from careercup. Here is the original post,
"You are given a log of wood of length `n’. There are `m’ markings on the log. The log must be cut at each of the marking. The cost of cutting is equal to the length of the log that is being cut. Given such a log, determine the least cost of cutting.
"
2. Analysis
Before diving into the anslysis, let's be clear about my understanding on this problem.
- The log can be cut on both sides
- The cost is accumulated on log cut off each time (total m marking, m cuts)
- The log still in the hand is not counted as cost
Assuming given a log of length n with m markings use D to represent the length between neighboring markings, d0, d1, ..., dm.
- Size of D: m+1
- Sigma(di) = n, where i from 0 to m
m = 1
One marking, one cutting to d0 and d1. In this case literally decide to cut from which side. Cut d0, then cost is d0 and cut d1 the cose is d1. Therefore the least cost of cutting this log is min(d0, d1).
m = 2
Two markings, two cuttings to d0, d1 and d2. Now we have 4 ways of cutting
- Cut d0 off, then the cost is d0 + f(1) = d0 + min(d1, d2),
where sud-problem f(1): the remaining log d1, d2
- Cut d2 off, then the cost is d2 + f(1) = d2 + min(d0, d1),
where sud-problem f(1): the remaining log d0, d1
- Cut d0+d1 off, then the cost is d0+d1+f(1) = d0+d1+min(d0,d1),
where sud-problem f(1): the cut-off log d0, d1
- Cut d1+d2 off, then the cost is d1+d2+f(1) = d1+d2+min(d1, d2),
where sud-problem f(1): the cut-off log d1, d2
Let consider the value of d0, d1, and d2
If d0 is the largest, then the cost follows
- d0 + min(d1, d2)
- d2 + d1
- d0 + d1 + d1
- d1 + d2 + min(d1, d2)
Minimize the cost, therefore d2+d1 is th least cost.
If d1 is the largest, then the cost follows,
- d0 + d2
- d0 + d2
- d0 + d1 + d0
- d1 + d2 + d2
Minize the cost, therefore d0+d2 is the least cost.
If d2 is the largest, then the cost follows,
- d0 + d1
- d2 + min(d0, d1)
- d0 + d1 + min(d0, d1)
- d1 + d2 + d1
Minimize the cost, therefore d0+d1 is the least cost.
Now we can conclude that the least cost will be sum of the m least logs. It is also equals to the length of log minus the longest log, n - max(di).
m = 3
Three markings, three cuttings to d0, d1, d2, and d3. Now we have 24 ways of cutting
- Cut d0 off, then the cost is d0+f(2),
where the sub-problem f(2) with remaining log: d1, d2, d3
cost = d0 + (d1+d2+d3 - max(d1, d2, d3))
= n - max(d1, d2, d3)
- Cut d0 and d1 off, then the cost is d0+d1+f(1)+f(1)
where two sub-problems f(1), cut-off log d0, d1 and remaining log d2,d3
cost = d0 + d1 + (d0+d1 - max(d0, d1)) + (d2+d3 - max(d2, d3))
= n + d0 + d1 - max(d0, d1) - max(d2, d3)
- Cut d0,d1 and d2 off, then the cost is d0+d1+d2+f(2)
where the sub problem f(2) with cut-off log d0, d1, d2
cost = d0 + d1 + d3 + (d0+d1+d2 - max(d0, d1, d2))
= n + d0 + d1 + d2 - d3 - max(d0, d1, d2)
- Cut d3 off, then the cost is d3 + f(2),
where the sub-problem f(2) with remaining log: d0, d1, d2
cost = d3 + (d0 + d1 + d2 - max(d0, d1, d2))
= n - max(d0, d1, d2)
- Cut d3, d2 off, then the cost is d3+d2+f(1)+f(1)
where two sub-problems f(1), cut-off log d3, d2 and remaining log d1, d0
cost = d3 + d2 + (d3+d2 - max(d3, d2)) + (d1+d0 - max(d1, d0))
= n + d3 + d2 - max(d3, d2) - max(d1, d0)
- Cut d3, d2, d1 off, then the cost is d3+d2+d1+f(2)
where the sub-problem f(2) with cut-off log d3, d2, d1
cost = d3 + d2 + d1 + (d3+d2+d1 - max(d3, d2, d1))
= n + d3 + d2 + d1 - d0 - max(d3, d2, d1)
Again lets consider the largest value of di.
If d0 is the largest one, then the cost follows,
- n - max(d1, d2, d3)
- n + d0 + d1 - d0 - max(d2, d3) = n + d1 - max(d2, d3)
- n + d0 + d1 + d2 - d3 - d0 = n + d1 + d2 - d3
- n - d0
- n + d3 + d2 - max(d3, d2) - d0
- n + d3 + d2 + d1 - d0 - max(d3, d2, d1)
Minimize the cost, therefore n - d0 is the least cost
If d1 is the largest one, then the cost follows,
- n - d1
- n + d0 + d1 - d1 - max(d2, d3) = n + d0 - max(d2, d3)
- n + d0 + d1 + d2 - d3 - d1 = n + d0 + d2 - d3
- n - d1
- n + d3 + d2 - max(d3, d2) - d1
- n + d3 + d2 + d1 - d0 - d1 = n + d3 + d2 - d0
Minimize the cost, therefore n - d1 is the least cost
- n - d2
- n + d0 + d1 - max(d0, d1) - d2
- n + d0 + d1 + d2 - d3 - d2 = n + d0 + d1 - d3
- n - d2
- n + d3 + d2 - d2 - max(d1, d0) = n + d3 - max(d1, d0)
- n + d3 + d2 + d1 - d0 - d2 = n + d3 + d1 - d0
Minimize the cost, therefore n - d2 is the least cost
If d3 is the largest one, then the cost follows,
- n - d3
- n + d0 + d1 - max(d0, d1) - d3
- n + d0 + d1 + d2 - d3 - max(d0, d1, d2)
- n - max(d0, d1, d2)
- n + d3 + d2 - d3 - max(d1, d0) = n + d2 - max(d1, d0)
- n + d3 + d2 + d1 - d0 - d3 = n + d2 + d1 - d0
Minimize the cost, therefore n - d3 is the least cost
Now we can conclude that the least cost is the n - max(di) if m = 3.
m as any value
Use the induction theory this can be concluded that the least cost is equal to n - max(di).
3. How to Cut?
As the solution is rolled out, the longest log will be remained in the hand and the rest will be cut off and regarded as the cost. The solution of cutting is quite simple - always pick up the shorter log to cut on the both side for each cutting. In this way it will guarantee the longest log will remain on the hand as the last.
No comments:
Post a Comment