Find Cutoff Score for Each School - Problem

You are given two tables: Schools and Exam.

The Schools table contains information about school capacities - the maximum number of students each school can accept.

The Exam table shows exam score distribution - for each score, it tells you how many students achieved at least that score.

Goal: For each school, find the minimum score requirement that:

  • Ensures the school can accept all students who meet the requirement (even if they all apply)
  • Maximizes the number of students who can potentially apply
  • Uses a score that exists in the Exam table

If multiple scores satisfy these conditions, choose the smallest score. If no valid score exists, return -1.

Table Schema

Schools
Column Name Type Description
school_id PK int Unique identifier for each school
capacity int Maximum number of students the school can accept
Primary Key: school_id
Exam
Column Name Type Description
score PK int Exam score threshold
student_count int Number of students who scored at least this score
Primary Key: score

Input & Output

Example 1 — Basic School Cutoff Selection
Input Tables:
Schools
school_id capacity
1 2
2 3
Exam
score student_count
500 10
600 5
700 2
Output:
school_id score
1 700
2 700
💡 Note:

School 1 (capacity=2): Score 500 has 10 students (>2), score 600 has 5 students (>2), score 700 has 2 students (≤2). Choose 700.

School 2 (capacity=3): Score 500 has 10 students (>3), score 600 has 5 students (>3), score 700 has 2 students (≤3). Choose 700 to maximize students.
Example 2 — No Valid Score
Input Tables:
Schools
school_id capacity
1 1
Exam
score student_count
400 5
500 3
Output:
school_id score
1 -1
💡 Note:

School 1 (capacity=1): All scores have more than 1 student. Score 400 has 5 students, score 500 has 3 students. No valid cutoff exists, so return -1.
Example 3 — Tie Breaking by Minimum Score
Input Tables:
Schools
school_id capacity
1 3
Exam
score student_count
300 3
400 3
500 1
Output:
school_id score
1 300
💡 Note:

School 1 (capacity=3): Scores 300 and 400 both have exactly 3 students (maximum that fits). Score 500 has only 1 student. To maximize students while breaking ties, choose minimum score 300.

Constraints

  • 1 ≤ school_id ≤ 1000
  • 1 ≤ capacity ≤ 100000
  • 1 ≤ score ≤ 1000
  • 1 ≤ student_count ≤ 100000
  • score values are unique in Exam table
  • Higher scores have same or fewer students than lower scores

Visualization

Tap to expand
School Admission Cutoff StrategyInput Tablesschool_idcapacity1223scorestudents5001060057002✗ Too Many StudentsScore 500: 10 students > capacityScore 600: 5 students > capacity✓ Valid ChoiceScore 700: 2 students ≤ capacityOutputschool_idscore17002700Strategy: Maximize Students Within Capacity1. Cross join schools with all exam scores2. Filter: keep only scores where student_count ≤ school_capacity3. For each school, pick minimum score with maximum valid students
Understanding the Visualization
1
Cross Join
Match every school with every exam score
2
Filter
Keep only combinations where student_count ≤ capacity
3
Optimize
For each school, pick minimum score with maximum valid student count
Key Takeaway
🎯 Key Insight: Use CROSS JOIN to explore all school-score combinations, then apply capacity constraints to find optimal cutoffs

Related Problems

Asked in
Amazon 15 Microsoft 12 Google 8
28.5K Views
Medium Frequency
~18 min Avg. Time
890 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen