Interview Questions for Minimum Cost of Tasks

Question

I got this problem as an interview questions and I was blank all the way, I thought it was pressure but as I try to do it now I am still blank, anyway to solve this problem, I am blank so a solution would be more helpful than just explaining it as I am just trying to move on from this problem and do something else, more of like a review question that i can look at for the next interview prep. Thanks in advance.

Assume that you have a list of n home maintenance/repair tasks (numbered from 1 to n) that must be done in list order on your house. You can either do each task i yourself at a positive cost (that includes your time and effort) of c[i]. Alternatively, you could hire a handyman who will do the next 4 tasks on your list for the fixed cost h (regardless of how much time and effort those 4 tasks would cost you). You are to create a dynamic programming algorithm that finds a minimum cost way of completing the tasks. The inputs to the problem are h and the array of costs c[1], . . . , c[n].

Here is an example. [1,3,5,6,7,2,1,3,1000] is the cost array by yourself. The handyman cost is 11. For any sequence greater than or equal to 4 tasks we would add handyman to do the tasks. In this case we would add handyman for 1...4, and 5....8, hence the total cost here is 23, and it is the minimum. Note that the handyman can not do less than 4 consecutive tasks.

Here are the subproblems I was given to solve:

1. find and justify a recurrence (with boundary conditions) giving the optimal cost for completing the tasks

2. O(n)-time recursive algorithm with memoization for calculating the value of the recurrence and a bottom up algorithm

Answer 1

For every i you calculate the best cost to do tasks 1 to i. For 0 <= i <= 3, you have to do the tasks yourself. For i >= 4, you have the choice of doing task i yourself and doing tasks 1 to i-1 in the best possible way, or let the handyman do the last 4 tasks, and do the previous i-4 tasks in an optimal way.

Answer 2

Equivalence to another question

Here is how we can find the problem in the question is basically the same as the problem in another question. Hence the answer over there can be adapted easily to this problem.

     the problem here <---> the problem over there               
           home tasks <---> weekly shipments
cost c[i] by yourself <---> cost s_i * r by company A
         next 4 tasks <---> next 4 weeks
   cost h by handyman <---> cost 4c by company B
         minimum cost <---> minimum cost

For example, for cost array [1,3,5,6,7,2,1,3,1000] and handyman cost 11 here, we have the corresponding problem of $r=1$, frights by pounds[1,3,5,6,7,2,1,3,1000] and $c=11/4=3.75$.

You might want to ask why or how I can connect these two problems together. A simple reason is that I wrote the answer to the other question. Another reason is that I have been solving, modifying and creating problems about algorithms constantly. I would encourage you to try that kind of exercises from time to time.

Exercises

Exercise 1. Imagine a different backdrop of this problem.

Exercise 2. (A slight generalization) Let us have the same problem as in the question, the same list of $n$ consecutive tasks and a handyman with the following change. Besides 4 consecutive tasks of the fixed cost $h$, the handyman can also do the next 3 consecutive tasks on your list for the fixed cost of $g$, regardless of how much time and effort those 3 tasks would cost you. Find an $O(n)$-time recursive algorithm that calculates the lowest cost for completing the tasks. (This problem degenerates to the original problem if we let $g$ be sufficiently large.)

Here is the idea to solve exercise 2.

Let $dp[i]$ be the lowest cost to do tasks 1 to $i$ inclusive. The base cases and the recurrence relation for $dp[i]$ is given by the following description.

• When $1 \leq i \leq 2$, you have to do all the tasks by yourself.
• When $i=3$, either you do all the tasks or let the handyman does all 3 tasks.
• When $i\geq 4$, the arrangement of lowest cost to complete all tasks must be one of the following ways.
  • You will do the last task by yourself. Complete the other $i-1$ tasks with the lowest cost.
  • Let the handyman do the last three tasks with cost $g$. Complete the other $i-3$ tasks with the lowest cost.
  • Let the handyman do the last four tasks with cost $h$. Complete the other $i-4$ tasks with the lowest cost.