Optimize ribbon piece length by binary search

Q: Optimize ribbon piece length by binary search

This is a Coding & Algorithms interview question from Meta for Machine Learning Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given an array lengths of positive integers and an integer k, you may cut each element into pieces of integer length L > 0. Find the maximum L such that you can obtain at least k pieces in total. If it is impossible to obtain k pieces, return 0. Constraints: 1 <= lengths.length <= 200000, 1 <= lengths[i] <= 1e9, 1 <= k <= 1e12. Design an O(n log max(lengths)) algorithm using a monotonic predicate and binary search over L. Be explicit about integer overflow handling and edge cases (e.g., very large k, many short lengths).

Optimize ribbon piece length by binary search

Comments (0)