Fair Distribution of Cookies

MediumBacktrackingbacktracking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an integer array cookies, where cookies[i] is the number of cookies in bag i, and an integer k, the number of children. Every bag must be given, whole, to exactly one child; bags cannot be split. The **unfairness** of a distribution is the largest total number of cookies received by any single child. Return the minimum unfairness over all possible distributions. A child is allowed to receive no bags.

Examples

Input: cookies = [8,15,10,20,8], k = 2
Output: 31
Give `[8,15,8]` (31) to one child and `[10,20]` (30) to the other. The unfairness is 31, and no split does better.
Input: cookies = [6,1,3,2,2,4,1,2], k = 3
Output: 7
Split as `[6,1]`, `[3,2,2]`, `[4,1,2]`, giving totals 7, 7, 7.

Constraints

  • 2 <= cookies.length <= 8
  • 1 <= cookies[i] <= 10^5
  • 2 <= k <= cookies.length

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More backtracking problems