Friends of Appropriate Ages

Interview Problem Interview Medium Prefix Sum Array Counting Sort

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.numFriendRequests(ages). A person aged x may request a distinct person aged y only when y > 0.5*x+7, y <= x, and not (y > 100 and x < 100). Return the number of directed requests.

Starter code

class Solution:
    def numFriendRequests(self, ages):
        pass

Test cases

same-age-pair

{
  "args": [
    [
      16,
      16
    ]
  ]
}

Expected: 2

Wizard outline

Step 1: Initialize Solution.numFriendRequests
Replace the empty starter with the first real state owned by Solution.numFriendRequests. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Distinct Ages case
Complete the readable core algorithm for one representative Interview case. Compress repeated ages into counts and use prefix totals to query every valid recipient interval.
Step 4: Harden the Same Age Pair boundary
Repair the reviewed boundary and pass the complete submission contract. The interval bounds encode the first two rejection rules. Within y<=x, the special over-100 rule cannot add another rejection. The prefix difference counts all eligible people; removing one excludes self for each sender, and multiplication counts every directed pair.

Footguns and prerequisites

Requests are directed, and each sender must exclude themself while still counting other people of the same age.
arrays strings two pointers sliding window

Reviewed references

LeetCode 825 — Friends Of Appropriate Ages

Practice prerequisites

Build Prefix Aggregates(opens in a new tab)
Build Prefix Aggregates isolates after consuming i values, the final aggregate equals sum(values[:i]) and the list has i + 1 entries. That focused state discipline is required when implementing friends appropriate ages as a complete Interview Problem.

Recommended approach and implementation

Count ages 1 through 120 and build prefix population totals. For each sender age, query recipients from floor(age/2+7)+1 through age, subtract the sender, and multiply by the number of senders of that age.

Why it works: The interval bounds encode the first two rejection rules. Within y<=x, the special over-100 rule cannot add another rejection. The prefix difference counts all eligible people; removing one excludes self for each sender, and multiplication counts every directed pair.

class Solution:
    def numFriendRequests(self, ages):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        counts = [0] * 121
        for age in ages:
            counts[age] += 1
        prefix = [0] * 121
        for age in range(1, 121):
            prefix[age] = prefix[age - 1] + counts[age]
        requests = 0
        for age in range(15, 121):
            if counts[age] == 0:
                continue
            lower = age // 2 + 8
            recipients = prefix[age] - prefix[lower - 1] - 1
            requests += counts[age] * recipients
        return requests