Katkat
Back

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

Goldman SachsSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Compute the highest average score among students from name and score records, then extend the code for data larger than memory, negative scores, integer overflow and multithreaded processing. The question also covers what atomic operations are in Java and how synchronized differs from ReentrantLock.

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.

public static int highestAverage(String[][] scores)

Each row is {name, score}, with the score written as a decimal string:

{{"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.

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.

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?

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.

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

Hints

Hint 1

Keep less than the scores: Decide the smallest amount of state per student that still lets you compute an average.

Hint 2

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.

Hint 3

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.

Hint 4

Share as little as possible: Decide whether threads need to share any mutable state while they work, and where their results have to meet.

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?