Highest Average Student Score: Out-of-Memory Input, Overflow and Thread Safety in Java

Given a list of exam results, each a pair of a student's name and an integer score, return the highest average score of any student, rounded down to an integer. A student's average is the sum of their scores divided by the number of scores they have. ```java public static int highestAverage(String[][] scores) ``` Each row is `{name, score}`, with the score written as a decimal string: ```text {{"Bob", "87"}, {"Mike", "35"}, {"Bob", "52"}, {"Jason", "35"}, {"Mike", "55"}, {"Jessica", "99"}} ``` Bob averages 69.5, Mike 45, Jason 35 and Jessica 99, so the answer is 99. The code was written on paper, with no editor or compiler, and each follow-up below asked for changes to the first version rather than an abstract discussion. ### Clarifying Questions - What should be returned for an empty input? - Can a row be malformed (missing score, non-numeric text), and should it be skipped or rejected? - Are names case-sensitive, and can they carry surrounding whitespace? - What range can a score take, and how many scores can one student have? ### Part 1 — Highest average in memory Write `highestAverage` for an input that fits in memory. ```hint Keep less than the scores Decide the smallest amount of state per student that still lets you compute an average. ``` #### What This Part Should Cover - A single pass with per-student aggregates rather than per-student score lists - How the averages are compared and rounded - Time and space complexity in terms of records and distinct students ### Part 2 — The data does not fit in RAM The records now come from a file far larger than memory. Adapt the solution. ```hint Which size has to fit? There are two sizes here: the number of records and the number of distinct students. Work out which one your Part 1 state depends on, and what to do if even that one is too big. ``` #### What This Part Should Cover - Streaming the input when the per-student state fits in memory - Partitioning the input so that each partition's state fits when it does not - The I/O cost of the approach and why the partial results combine correctly ### Part 3 — Negative scores and integer overflow What changes if scores can be negative? What if a sum of scores can exceed the range of a Java `int`? ```hint Look at the division Check which way Java's integer division rounds when the quotient is negative, and how many maximal scores fit in an `int` sum. ``` #### What This Part Should Cover - Rounding down versus truncation toward zero for negative averages - Initial values that silently assume non-negative scores - Choosing types that cannot overflow, and failing loudly when an input is out of range - Whether floating-point arithmetic is needed at all ### Part 4 — Multithreading, atomics and locks Process the input with multiple threads. Then explain what "atomic" means, including what Java's atomic classes provide, and the differences between `synchronized` and `ReentrantLock`. ```hint Share as little as possible Decide whether threads need to share any mutable state while they work, and where their results have to meet. ``` #### What This Part Should Cover - How the work is split and how partial results are merged - Which operations on shared state are not atomic, and how atomic classes and locks fix that - `synchronized` versus `ReentrantLock`: capabilities, failure modes and when each fits - Memory visibility: why the merging thread sees every worker's writes ### What a Strong Answer Covers - Clarifies empty input, malformed rows and score ranges before writing code - A correct one-pass solution that stores only a sum and a count per student - External-memory reasoning that separates "too many records" from "too many students" - Exact integer handling of negative values and overflow, without floating-point surprises - A concurrent version with little or no shared mutable state, plus accurate explanations of atomicity and Java locking ### Follow-up Questions - Return the name of the student with the highest average instead. How do you compare two averages exactly, and how do you break ties? - Scores keep arriving, and the current highest average must be available at any moment. What do you maintain? - How would you test that the multithreaded version always matches the single-threaded one? - Would you use a parallel stream with a grouping collector instead of managing threads yourself? What does it hide?