Coding

Candy

Asked at

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

A line of N kids is standing there. The rating values listed in the integer array ratings are assigned to each kid.

These kids are receiving candy, according to the following criteria:

There must be at least one candy for every child.
Kids whose scores are higher than their neighbours receive more candies than their neighbours.

Return the minimum number of candies needed to distribute among children.

Input : ratings = [1, 0, 5]

Output : 5

Explanation : The distribution of candies will be 2 , 1 , 2 to first , second , third child respectively.

Input : ratings = [1, 2, 2]

Output : 4

Explanation : The distribution of candies will be 1 , 2 , 1 to first , second , third child respectively. The third gets only 1 candy because it satisfy above two criteria.

Input : ratings = [1, 2, 1, 4, 5]

1 <= n <= 104
0 <= ratings[i] <= 105

cpp

class Solution {
public:
    int candy(vector<int>& ratings) {
        //your code goes here
    }
};

java

class Solution {
    public int candy(int[] ratings) {
       //your code goes here
    }
}

python

class Solution:
    def candy(self, ratings):
        #your code goes here

javascript

class Solution {
    candy(ratings) {
        //your code goes here
    }
}

csharp

public class Solution {
    public int Candy(int[] ratings) {

    }
}

func candy(ratings []int) int {

}

Stuck? Show a way to structure it+

01Initialize all candies to one
02Satisfy rising slopes from the left
03Satisfy descending slopes from the right with max
04Sum after both constraints are met

Reference answer

Start by restating the input contract for Candy and testing the smallest boundary case before choosing the algorithm. Give every child one candy initially. Make a left-to-right pass so a child with a higher rating than its left neighbor gets one more, then a right-to-left pass enforcing the analogous right constraint with max(current, right+1). Sum the resulting counts. Explain the invariant while coding, then show how each update preserves it. The two passes are O(n) time and the described candy array uses O(n) space. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

Can this be solved in O(1) extra space?
Tests: complexity analysis
Why does taking max satisfy both neighbors?
Tests: correctness reasoning

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question