Candy (LC 135)

Requirements

Tackle the classic LeetCode 135 Candy problem:

• There is a line of children, each assigned an integer rating.
• Every child must get at least one candy.
• If a child's rating is higher than an immediate neighbor's, that child must have strictly more candies than the neighbor.
• Compute the smallest total number of candies that meets these conditions.

Notes

• In this phone screen, candidates could give a verbal solution for the initial problem and then proceed to a second task without writing any code.
• The interviewer stressed candidate ownership in two ways: independently raise trade-offs, articulate assumptions, and steer the conversation instead of waiting for step-by-step prompts.
• The standard greedy approach does two passes: start each child with one candy, go left to right to enforce the rule for higher ratings than the left neighbor, then go right to left and, whenever a rating exceeds the right neighbor, set the candy count to max(current, right + 1). The max operation keeps the left-to-right constraint intact; adding up the final counts gives the minimum total in O(n) time and O(n) space.
• Clearly discuss how equal ratings, monotonic sequences, and local peaks or valleys interact with the two neighbor constraints.

Preparation

• Practice delivering a tight verbal outline that names the invariant, justifies why both neighbor constraints are satisfied, and states the time and space complexity before coding.
• Work through the edge cases: one child, all ratings equal, strictly increasing, strictly decreasing, and a peak/valley scenario until you can explain correctness effortlessly.
• Get comfortable comparing viable implementation approaches without being asked; this screen values candidates who proactively discuss trade-offs.