Coding

Assign Cookies

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Consider a scenario where a teacher wants to distribute cookies to students, with each student receiving at most one cookie.

Given two arrays, **student **and cookie, the ith value in the Student array describes the minimum size of cookie that the ith student can be assigned. The jth value in the Cookie array represents the size of the jth cookie. If Cookie[j] >= Student[i], the jth cookie can be assigned to the ith student. Maximize the number of students assigned with cookies and output the maximum number.

Input : student = [1, 2, 3] , cookie = [1, 1] **Output :**1 Explanation : You have 3 students and 2 cookies. The minimum size of cookies required for students are 1 , 2 ,3. You have 2 cookies both of size 1, So you can assign the cookie only to student having minimum cookie size 1. So your answer is 1.

Input : student = [1, 2] , cookie = [1, 2, 3] Output : 2 Explanation : You have 2 students and 3 cookies. The minimum size of cookies required for students are 1 , 2. You have 3 cookies and their sizes are big enough to assign cookies to all students. So your answer is 2.

Input : student = [4, 5, 1] , cookie = [6, 4, 2]

1 <= student.length <= 3*104
0 <= cookie.length <= 3*104
1 <= student[i] , cookie[j] <= 231 - 1

cpp

class Solution{    
    public:
    int findMaximumCookieStudents(vector<int>& Student, vector<int>& Cookie){
        //your code goes here
    }
};

java

class Solution {
    public int findMaximumCookieStudents(int[] Student, int[] Cookie) {
        //your code goes here
    }
}

python

class Solution:
    def findMaximumCookieStudents(self, Student, Cookie):
        #your code goes here

javascript

class Solution {
    findMaximumCookieStudents(Student, Cookie) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public int FindMaximumCookieStudents(List<int> Student, List<int> Cookie)
    {
        //your code goes here
    }
}

func findMaximumCookieStudents(Student []int, Cookie []int) int {

}

Stuck? Show a way to structure it+

01Sort student requirements and cookie sizes.
02Compare the least-demanding unmatched student with the smallest unused cookie.
03Match when sufficient; otherwise discard the cookie as too small for everyone remaining.
04Justify that the smallest adequate cookie preserves options for later children.

Reference answer

Sort both arrays. Use pointer i for the least-demanding unmatched student and j for the smallest unused cookie. If cookie[j] >= student[i], assign it and advance both pointers. Otherwise the cookie is too small for this student and therefore too small for every later, more demanding student, so discard it by advancing j. The number of successful matches is maximal. The exchange argument is that assigning a larger-than-needed cookie to the current student cannot improve the count; replacing it with the smallest adequate cookie leaves at least as much flexibility for later students. Sorting dominates at O(s log s + c log c) time, and the scan is linear. Extra space depends on the sorting implementation. Each student receives at most one cookie because its pointer advances only on a match.

Then expect these follow-ups

What exchange argument proves the greedy choice?
Tests: greedy proof
What if each student could receive multiple cookies whose sizes add up?
Tests: model change

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question