How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Solve Banana Speed and Interval Merge | Google Coding Question

Solve Banana Speed and Interval Merge

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

During two technical phone screens for a new graduate software engineering role, the candidate was asked to solve two coding problems: minimum eating speed and merging overlapping intervals. ### Constraints & Assumptions - Provide clear algorithms, correctness reasoning, complexity, and edge cases. - For minimum eating speed, each hour can be spent on only one pile. - For interval merging, intervals overlap when the next start is less than or equal to the current merged end. - Use sorted or binary-search approaches where appropriate. ### Clarifying Questions to Ask - Are `piles` and `h` always positive? - Is `h` at least the number of piles? - Are interval endpoints inclusive? - Can intervals be empty or unsorted? ### Part 1 - Minimum Eating Speed Given `piles` and `h`, return the minimum integer speed `k` such that all piles can be eaten within `h` hours. #### What This Part Should Cover - Binary search on answer from 1 to `max(piles)`. - Feasibility function using sum of `ceil(pile / k)`. - Why feasibility is monotonic. - Complexity and edge cases. ### Part 2 - Merge Overlapping Intervals Given intervals `[start, end]`, merge all overlapping intervals and return non-overlapping intervals sorted by start. #### What This Part Should Cover - Sort by start. - Maintain current merged interval. - Extend on overlap, otherwise append and start a new interval. - Complexity and edge cases. ### What a Strong Answer Covers - Recognizes monotonic binary search for eating speed. - Uses integer-safe ceiling division. - Correctly defines interval overlap. - Gives clean code and complexity for both problems. ### Follow-up Questions - How would you avoid floating-point division in the banana problem? - What if `h` is smaller than the number of piles? - How do you merge touching intervals like `[1,3]` and `[3,5]`? - How would you handle streaming intervals?

Quick Answer: Solve minimum eating speed and merge intervals for a new graduate phone screen. The solution covers binary search on answer, integer ceiling division, monotonic feasibility, interval sorting, overlap merging, correctness, complexity, and edge cases.

Minimum Eating Speed (Koko Eating Bananas)

Koko loves to eat bananas. There are `n` piles of bananas; the i-th pile has `piles[i]` bananas. The guards will return in `h` hours. Koko can decide her constant bananas-per-hour eating speed `k`. Each hour she chooses one pile and eats `k` bananas from it. If that pile has fewer than `k` bananas, she eats all of them and does not eat more during that hour. An hour is spent on only one pile. Return the minimum integer speed `k` such that she can finish all the bananas within `h` hours. Example: - `piles = [3, 6, 7, 11]`, `h = 8` -> `4` - `piles = [30, 11, 23, 4, 20]`, `h = 5` -> `30` - `piles = [30, 11, 23, 4, 20]`, `h = 6` -> `23` Constraints: `1 <= piles.length <= h`, `1 <= piles[i] <= 10^9`.

Constraints

1 <= piles.length <= h
1 <= piles[i] <= 10^9
h can be as large as 10^9

Examples

Input: ([3, 6, 7, 11], 8)

Expected Output: 4

Explanation: At k=4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 hours. k=3 needs 1+2+3+4 = 10 > 8, so 4 is minimal.

Input: ([30, 11, 23, 4, 20], 5)

Expected Output: 30

Explanation: With exactly 5 piles and 5 hours, each pile must be eaten in one hour, so k must be at least max(piles) = 30.

Input: ([30, 11, 23, 4, 20], 6)

Expected Output: 23

Explanation: One extra hour lets the largest pile (30) be split, so the bottleneck drops to 23.

Input: ([1000000000], 2)

Expected Output: 500000000

Explanation: A single billion-banana pile over 2 hours needs ceil(1e9 / k) <= 2, giving k = 5e8.

Input: ([1], 1)

Expected Output: 1

Explanation: Single pile of 1 banana, 1 hour: minimum speed is 1.

Input: ([312884470], 312884469)

Expected Output: 2

Explanation: Large pile, nearly that many hours: ceil(pile / 2) = 156442235 <= h, and speed 1 would need 'pile' hours which exceeds h, so 2 is minimal.

Hints

If speed k finishes in time, any larger speed also finishes in time. This monotonicity lets you binary search on the answer.
The answer lies in [1, max(piles)]: speed 1 is the slowest, and max(piles) finishes every pile in at most one hour.
Hours needed at speed k is sum of ceil(pile / k). Use integer-safe ceiling: (pile + k - 1) // k to avoid floating point.

Merge Overlapping Intervals

Given an array of intervals where `intervals[i] = [start_i, end_i]`, merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input, sorted by start. Two intervals overlap when the next start is less than or equal to the current merged end (endpoints are inclusive, so `[1,3]` and `[3,5]` merge into `[1,5]`). Example: - `[[1,3],[2,6],[8,10],[15,18]]` -> `[[1,6],[8,10],[15,18]]` - `[[1,4],[4,5]]` -> `[[1,5]]` Constraints: `0 <= intervals.length`, `start_i <= end_i`, input may be unsorted.

Constraints

0 <= intervals.length
intervals[i] = [start_i, end_i] with start_i <= end_i
Input may be unsorted and may contain nested or touching intervals

Examples

Input: ([[1, 3], [2, 6], [8, 10], [15, 18]],)

Expected Output: [[1, 6], [8, 10], [15, 18]]

Explanation: [1,3] and [2,6] overlap -> [1,6]; [8,10] and [15,18] are disjoint and stay separate.

Input: ([[1, 4], [4, 5]],)

Expected Output: [[1, 5]]

Explanation: Touching intervals with inclusive endpoints (4 <= 4) merge into [1,5].

Input: ([],)

Expected Output: []

Explanation: Empty input returns an empty list.

Input: ([[5, 7]],)

Expected Output: [[5, 7]]

Explanation: A single interval is returned unchanged.

Input: ([[1, 4], [2, 3]],)

Expected Output: [[1, 4]]

Explanation: [2,3] is nested inside [1,4]; max(cur_end, end) keeps the wider end.

Input: ([[4, 5], [1, 4], [0, 0]],)

Expected Output: [[0, 0], [1, 5]]

Explanation: Unsorted input. After sorting: [0,0],[1,4],[4,5]. [0,0] is disjoint from [1,4]; [1,4] and [4,5] touch -> [1,5].

Input: ([[-5, -1], [-3, 2], [6, 8]],)

Expected Output: [[-5, 2], [6, 8]]

Explanation: Negative endpoints: [-5,-1] and [-3,2] overlap -> [-5,2]; [6,8] stays separate.

Hints

Sort intervals by start. After sorting, any interval that overlaps the current merged interval must come before the first interval whose start exceeds the current end.
Track a current merged interval (cur_start, cur_end). If the next start <= cur_end, extend cur_end = max(cur_end, end); otherwise append the current and start a new one.
Use <= (not <) for the overlap test so touching intervals like [1,3] and [3,5] merge. Don't forget to append the final pending interval.

Quick Overview

Solve minimum eating speed and merge intervals for a new graduate phone screen. The solution covers binary search on answer, integer ceiling division, monotonic feasibility, interval sorting, overlap merging, correctness, complexity, and edge cases.