A take-home question from some company’s recruitment process (not me applying). It’s similar to another blog post that I had in mind to write, so might as well just combine both of them into one.
The question (rewritten by me):
There is a long bar of chocolate containing hazelnuts and caramel. It is originally contiguous, with grooves along the length of the bar (like with Toblerone or Kinder Bueno). Each section of the chocolate bar contains some number of hazelnuts, and may also contain caramel.
Let’s say Alice wants to split the chocolate bar to share with
kpeople, including herself. She would have to break the chocolate bar atk-1points along the bar intokpieces.
Alice is like any other person - she wants to appear generous but secretly wants as many hazelnuts in her chocolate as possible. She devises a plan for breaking the chocolate so that she gets the piece with the least hazelnuts out of the
kpieces, but yet maximize the number of hazelnuts in her own piece.
Alice also doesn’t want to break the chocolate bar such that the breakage point is in between 2 sections with caramel, since that will make a mess all over the place. Caramel belongs in the stomach, not on the floor.
Given all of these rules, can you find out how many hazelnuts will be in Alice’s share of the chocolate?
For example:
2 | 3 | 4 | 5
| C | C |This bar of chocolate has 4 sections, with 2, 3, 4, and 5 hazelnuts in each section respectively. The middle 2 sections has caramel in it.
Given 2 people (Alice and one other friend), the answer should be 5, since Alice would have make a break in between the third and fourth section. Alice’s friend will get 9 hazelnuts while Alice will get 5 hazelnuts.
Another example:
4 | 3 | 6 | 2
| | |It is also possible that the bar does not contain any caramel at all, in which case it is okay to break the chocolate bar in between any 2 sections.
Given 3 people (Alice and two other friends), the answer should be 3, since this time Alice would have broken it between the first and second section, and between the second and third section. This yields 4 hazelnuts for the first friend, 8 hazelnuts for the second friend, and 3 hazelnuts for Alice.
This question can be split into two parts. The first part involves coalescing the caramel sections together, since they can be treated as a single section.
Then, it is simply an application of Minimum Partition Difference, which I’ve written a top-down recursive memoization version of here. This is due to the observation that what Alice is trying to do is to minimize the imbalance between all of the pieces. In other words, she is trying to minimize the difference between the largest piece and the smallest piece (thus the name of the algorithm).
I’ve chosen to represent the hazelnuts in each section as a list of integers. The caramel in the chocolate is represented as a list of tuples, each of which indicates the start and end sections (inclusive) of the parts of chocolate bar containing caramel. The last argument we need is the number of people involved (including Alice).
from typing import List, Tuple
class memoized:
def __init__(self, func):
self.cache = {}
self.func = func
def __call__(self, *args):
if args in self.cache:
return self.cache[args]
result = self.func(*args)
self.cache[args] = result
return result
def minimum_partition_difference(arr, k):
@memoized
def _minimum_partition_difference(l, r, k):
if k == 1:
return sum(arr[l:r + 1])
maximum = float('-inf')
for i in range(l, r):
maximum = max(
maximum,
min(sum(arr[l:i + 1]), _minimum_partition_difference(i + 1, r, k - 1)),
)
return maximum
return _minimum_partition_difference(0, len(arr) - 1, k)
def chocolate(hazelnuts: List[int], caramel: List[Tuple[int, int]], people: int):
if caramel:
# sort the caramel hazelnuts
caramel.sort(key=lambda x: x[0])
coalesced_hazelnuts = []
# put the first bunch of non-caramel sections first
coalesced_hazelnuts.append(sum(hazelnuts[0:caramel[0][0]]))
for i, r in enumerate(caramel):
coalesced_hazelnuts.append(sum(hazelnuts[r[0]:r[1] + 1]))
# put those non-caramel sections that are in between caramel sections
if i != len(caramel) - 1:
next_chunk = caramel[i + 1]
coalesced_hazelnuts.extend(hazelnuts[r[1] + 1:next_chunk[0]])
# put the last bunch of non-caramel sections
coalesced_hazelnuts.extend(hazelnuts[caramel[-1][1] + 1:])
else:
coalesced_hazelnuts = hazelnuts
return minimum_partition_difference(coalesced_hazelnuts, people)
print(chocolate([2,3,4,5], [(1,2)], 2)) # 5
print(chocolate([4,3,6,2], [], 3)) # 3
print(chocolate([6,3,2,8,7,5], [(2,4)], 2)) # 9The time complexity of this solution is dominated by the second part, which is O(kn^2^), where k is the number of people, and
n is the number of sections in the chocolate.
This is because we are calculating (and memoizing) the intermediate result for every value of
i, where i varies from 1 to k, and every subarray/subsection of the
chocolate bar ((n^2^ + 1)/2 subarrays in an array).
The time complexity of the first part is mainly from the sorting of the caramel sections (assuming the input isn’t already sorted).
The original blog post I wanted to write was about one of my brother’s homework assignment questions, which goes something like this (again abridged):
Given a list of jobs and their runtimes, and
kprocessors, we want to distribute the jobs contiguously between the processors so that we minimize the total running time, which is counted as the time it takes to complete all the jobs.
Find the shortest possible runtime for a given list of jobs and number of processors.
This requires us to invert the version of the Minimum Partition Difference algorithm above to return the size of the largest partition instead of the size of the smallest partition.
def minimum_partition_difference(arr, k):
@memoized
def _minimum_partition_difference(l, r, k):
if k == 1:
return sum(arr[l:r + 1])
minimum = float('inf')
for i in range(l, r):
minimum = min(
minimum,
max(sum(arr[l:i + 1]), _minimum_partition_difference(i + 1, r, k - 1)),
)
return minimum
return _minimum_partition_difference(0, len(arr) - 1, k)There is an interesting way to solve MPD using “binary search” as well, which I might write about soon.