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:
ChunkSource
may return these chunks in sequence: [one
<NL>
tw, o
<NL>
, three
<NL>
four,
<NL>
fi, ve], where
<NL>
denotes a newline character.
nextLine()
should return: one, two, three, four, five, and then
null
.
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.
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:
One valid output payback list is:
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.