Databases
StackOverflow2013
Postsdbo
POPartition an array in order
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POPartition an array in order
    text
    copied!<p>This is an interview question that a friend of mine got and I'm unable to come up with how to solve it.</p> <p><strong>Question:</strong></p> <p>You are given a array of n buttons that are either red or blue. There are k containers present. The value of a container is given by the product of red buttons and blue buttons present in it. The problem is to put the buttons into the containers such that the sum of all values of the containers is minimal. Additionally, all containers must contain the buttons and they must be put in order they are given. For example, the very first button can only go to the first container, the second one can go to either the first or the second but not the third (otherwise the second container won't have any buttons). k will be less than or equal to n.</p> <p>I think there must be a dynamic programming solution for this. </p> <p>How do you solve this ? So far, I've only got the trivial cases where</p> <ul> <li>if (n==k), the answer would be zero because you could just put one in each container making the value of each container zero, therefore the sum would be zero. </li> <li>if (k==1), you just dump all of them and calculate the product.</li> <li>if only one color is present, the answer would be zero. </li> </ul> <p><strong>Edit</strong>:</p> <p>I'll give an example.</p> <p>n = 4 and k = 2</p> <p>Input: R B R R</p> <p>The first container gets the first two (R and B) making its value 1 (1R X 1B) The second container gets the remaining (R and R) making its value 0 (2R x 0B) The answer is 1 + 0 = 1</p> <p>if k=3, the first container would have only the first button (R) the second container would have only the second one (B) the third one would have the last two buttons (R and R) Each of the containers would have value 0 and hence sum and answer would be 0.</p> <p>Hope this clears up the doubts.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload