The questions are still open and you can try them here.
The question was about dividing an array into K + 1 segments such that the minimum segment is maximized. The minimum segment is the segment that has the smallest sum of elements. If you don't remember the question, you can find it below.
There was also a restriction on where the array can be cut because of the caramels. To make the algorithm easier to write, we can first rewrite the array so that chunks of chocolates with caramels are grouped together. The solution will be equivalent.
Once we got rid of the caramels, there are multiple ways to solve this problem:
- Binary search. We can do a binary search on the result. For each value we try, we can check whether there is a way to split the array into at least K + 1 parts so that the sum in each segment is greater or equal to the candidate value. If it’s possible, we set the new minimum value to be the value tried. If it’s not possible, we set the new maximum value to be the value we tried minus one.
- Dynamic programming. We can create a two-dimensional array where each cell (i, j) keeps track of the result with the first i chunks of chocolates and with j segments. The size of the array is (N + 1) * (K + 2), where N is the number of chunks. When there is only one segment, the result is the sum of the number of hazelnuts in the first i elements, which is how we can initialize our array. We can then compute the value of a cell (i, j) by looking at the cells with j - 1 segments and taking the best value by trying the split the chocolate at positions from 1 to i. The equation looks like this:
We will describe the binary search solution because it’s easier to understand.
In pseudo-code, it would look like this:
/*
// The main function
Read the first line and parse into an array A
Initialize an empty list C for the chocolates
Read the second line
While parsing the sorted caramels from the second line, go through the chocolates of the array A
If the chocolate is at the beginning of a caramel, sum all the hazelnuts of the caramel and add the result to C. Set the caramel index to the next caramel.
Otherwise, put the hazelnuts of the chocolate into C.
Read and save the number of cuts K
Initialize the minimum solution, min, to be the minimum of the chocolates of C
Initialize the maximum solution, max, to be the sum of the values of C divided by K + 1
While the minimum is strictly smaller than the maximum,
Initialize the mid value to be (min + max + 1) / 2
Call the isPossible function that checks whether we can cut the list C into at least K + 1 segments that each has a sum of at least mid
If it’s the case, set the minimum to the mid value.
Otherwise, set the maximum to be (mid - 1).
Print the minimum
// The isPossible function
The isPossible function receives the list C and the number of cuts K and the candidate value minSum as parameters
Initialize segmentCount to 0, which will keep track of the number of segments
Initialize the hazelnutCount to 0
For each hazelnut in C,
Add hazelnut to hazelnutCount
If hazelnutCount is greater than minSum,
Reset hazelnutCount to 0
Add 1 to the segmentCount
If segmentCount is greater or equal to K + 1,
Return true
Return false
*/
Every Thursday at TransferWise Singapore, we take a break at 3pm and have Fika. It's about taking a break while munching on goodies bought by the lovely Office team people and chatting with other Wisers. Zid, our lovely Office manager bought a big bar of caramel hazelnut chocolate that consists of N chunks. Each chunk contains a number of hazelnut(s) given by the array chocolate. Zid wants to share the chocolate with K Wisers so he cuts the chocolate bar into K + 1 pieces with K cuts, where each piece consists of some consecutive chunks. Zid also wants to avoid splitting some of the chunks as they contain caramel. The chunks that should not be split is given as a range [start, end] (both bounds inclusive) in the 2D array caramel. Being magnanimous, Zid will eat the piece with the least number of hazelnuts and gives the other pieces to the K Wisers. Find the maximum total hazelnut(s) of the piece Zid can get by cutting the chocolate bar optimally.
The first line represents the chocolate array Space-separated between array elements The second line represents the 2D caramels array Space-separated between the 1D arrays Comma-separated between 1D array elements If line is empty, there is no caramel The third line represents the K Wisers Example:
6 3 2 8 7 5
0,1 2,4
2
The above represents input values: chocolate = [6,3,2,8,7,5] caramels = [[0,1],[2,4]] k = 2
N - length of chocolate array
1 <= N <= 10000
M - length of caramels array
0 <= M <= N
0 <= M[0], M[1] < N (within the bounds of chocolate array)
Caramels do not overlap and they are sorted in ascending order (e.g. [[4,8],[3,7]] would not appear in test inputs)
0 <= k < 1000
k + 1 <= N
The maximum total hazelnut(s) of the piece Zid can get by cutting the chocolate bar optimally
Output: 5
[6, 3] -> 6 + 3 = 9
[2, 8, 7] -> 17
[5] -> 5
6 3 2 8 7 5
2
9
With no caramel, Zid is free to cut the chocolate bar into chunks with no restriction. The illustration below show the optimal way to cut the chocolate.
[6, 3] -> 6 + 3 = 9
[2, 8] -> 2 + 8 = 10
[7, 5] -> 7 + 5 = 12
NOTE: The solution below is invalid because some of the pieces do not consist of consecutive chunks
[3, 7] -> 3 + 7 = 10
[2, 8] -> 2 + 8 = 10
[5, 6] -> 5 + 6 = 11
6 3 2 8 7 5
0,2
2
8
[6, 3, 2] -> 6 + 3 + 2 = 11
[8] -> 8
[7, 5] -> 7 + 5 = 12
6 3 2 8 7 5
2,4
2
5
[6, 3] -> 6 + 3 = 9
[2, 8, 7] -> 17
[5] -> 5