Implement stream line reader and settle balances
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## 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 `ChunkSource` may 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 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.
---
## 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.
Quick Answer: 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.