DSA interview question

Book Allocation (Allocate Minimum Pages)

Hard · Algorithms · Topics: binary search on answer, array

The problem

A library must hand out n books, in order, to m students. Each student gets a contiguous block of at least one book, and every book goes to someone. To be fair, the library wants to minimise the maximum number of pages any single student has to read. The answer is a page limit between the thickest single book (someone has to read it) and the total pages (one student reads everything). Given a limit, a greedy pass counts how many students are needed; fewer pages per student means more students. Binary search for the smallest limit that needs at most m students.

Example: pages [12, 34, 67, 90], m = 2 → 113 ([12, 34, 67] and [90]).

Function signature

int allocateBooks(const vector<int>& pages, int m);  // minimum possible maximum; -1 if m > n

Test cases

Input `(pages, m)`	Output	Explanation
`([12, 34, 67, 90], 2)`	113	[12, 34, 67] and [90]
`([15, 17, 20], 2)`	32	[15, 17] and [20]
`([25, 46, 28, 49, 24], 4)`	71	[25, 46], [28], [49], [24]
`([1, 2, 3], 4)`	-1	More students than books
`([10], 1)`	10

(Confirm: books are allocated in order, in contiguous blocks; every student gets at least one book; return -1 if that's impossible.)

How interviewers phrase it

"Allocate minimum number of pages" (GeeksforGeeks, InterviewBit).
The same problem as split array largest sum (S.No 124), painter's partition (S.No 125) and ship capacity (S.No 120).

Clarifying questions to ask

Must each student get at least one book?
Contiguous blocks, in the given order?
What if there are more students than books?
How large are the page counts? (Sums need 64 bits.)

Follow-ups to expect

"What are the bounds on the answer?"
"How do you count students for a limit?"
"Why is 'students needed ≤ m' enough, not '== m'?"
"Why is this 'minimise the maximum'?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview