PPractick

The problem

A parent has cookies of various sizes and children with various greed factors: child i is content only with a cookie of size ≥ g[i]. Each child gets at most one cookie, and each cookie goes to at most one child. Maximise the number of content children. The greedy approach: sort both lists and give each child, from the least greedy, the smallest cookie that satisfies them. A cookie too small for the current child is too small for every greedier child too, so it can be thrown away.

Example: greed [1, 2, 3], cookies [1, 1] → 1.

Function signature

int findContentChildren(vector<int> g, vector<int> s);

Test cases

Input (greed, cookies)	Output	Explanation
([1, 2, 3], [1, 1])	1	Only the child with greed 1
([1, 2], [1, 2, 3])	2
([10, 9, 8, 7], [5, 6, 7, 8])	2	Cookies 7 and 8 satisfy greed 7 and 8
([1, 1], [])	0	No cookies
([2], [1, 1])	0	Cookies can't be combined

(Confirm: each child gets at most one cookie, and cookies can't be split or combined.)

How interviewers phrase it

• "Each child i has a greed factor g[i] and each cookie j has a size s[j]. Maximise the number of content children" (LeetCode 455).

Clarifying questions to ask

1. At most one cookie per child? (Yes.)
2. Can a cookie be split? (No.)
3. How large are the lists? (Up to 3·10⁴, so sorting is fine.)

Follow-ups to expect

1. "Why satisfy the least greedy child first?"
2. "Why is it safe to skip a cookie that's too small?"
3. "Exchange argument?"
4. "What if each child could take several cookies?"
5. "Complexity?"

Related questions

• Insert Interval Medium
• Merge Intervals Medium
• Non-overlapping Intervals Medium
• Stock Buy and Sell Easy
• Lemonade Change Easy
• Jump Game - I Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in