Implement stream line reader and settle balances
Overview
This question evaluates streaming I/O and buffered string-processing competency for Part 1 and transaction netting with balance computation for Part 2, covering skills in memory-bounded parsing, data-structure bookkeeping, and algorithmic flow reasoning.
Part 1: Streaming line reader from chunked source
You are given an existing class ChunkSource with a method nextChunk() that returns the next piece of text from a stream, or null when the stream is finished. Each returned chunk is an arbitrary substring of the original text and may contain zero or more newline characters (line breaks). The text, when all chunks are concatenated, is made of logical lines separated by newline characters.
Implement a class LineReader with a method nextLine() that returns the next complete line (without the newline character) each time it is called, internally calling ChunkSource.nextChunk() as needed. When there is no more data, nextLine() should return null.
Example:
- Underlying logical lines: one, two, three, four, five (separated by newline characters).
-
The
ChunkSourcemay return these chunks in sequence: [one <NL> tw, o <NL> , three <NL> four, <NL> fi, ve], where<NL>denotes a newline character. -
Consecutive calls to
nextLine()should return: one, two, three, four, five, and thennull.
Assume the total stream is very large so you must use only O(L_max) additional memory, where L_max is the length of the longest single line.
Part 2: Account balance settlement
You are given a list of money transfer transactions. Each transaction is represented as (from, to, amount) meaning from paid to the given amount. There are n different people across all transactions.
You must output any list of payback transfers (payer, receiver, amount) such that, after applying all paybacks in addition to the original transactions, every person's net balance becomes zero. You do not need to minimize the number of payback transactions; any valid settlement is acceptable.
Example: Input transactions:
- (A, B, 10)
- (B, C, 5)
- (A, C, 5)
One valid output payback list is:
- (C, A, 10)
- (B, A, 5)
After these paybacks, the net balance of A, B, and C is zero.
Design and implement an algorithm that takes the list of transactions and returns such a list of paybacks, or an empty list if everyone's net balance is already zero.