Implement stream line reader and settle balances
Part 1: Streaming Line Reader from Chunked Source
You are provided with an existing class, ChunkSource, which offers a method nextChunk(). This method returns the next segment of text from a continuous stream, or null when the stream has concluded. Each chunk returned is an arbitrary substring of the original text and may contain zero or more newline characters (line breaks). When all chunks are concatenated, they form a sequence of logical lines, each terminated by a newline character.
Your task is to implement a LineReader class. This class must expose a method, nextLine(), which, upon each invocation, returns the next complete logical line from the stream, excluding the terminating newline character. The LineReader should internally call ChunkSource.nextChunk() as necessary to acquire more data. Once all data has been processed and no more lines are available, nextLine() should return null.
Example:
- Underlying logical lines:
one,two,three,four,five(each followed by a newline character). ChunkSourcesequence:["one\n tw", "o\n ", "three\n four", "\n fi", "ve"]- Consecutive
nextLine()calls should yield:"one","two","three","four","five", and subsequentlynull.
Constraint: The total stream size can be very large. Your implementation must use only O(L_max) additional memory, where L_max represents the length of the longest single line in the stream.
Part 2: Account Balance Settlement
You are given a list of money transfer transactions. Each transaction is represented as a tuple (from, to, amount), indicating that the person identified by from paid the person identified by to the specified amount. There are n distinct individuals involved across all transactions.
Your objective is to produce any valid list of payback transfers, also represented as (payer, receiver, amount). The condition for validity is that, after applying these payback transfers in addition to the original transactions, the net balance for every single person involved becomes exactly zero. You are explicitly not required to minimize the number of payback transactions; any list that achieves the zero-balance state for everyone is acceptable.
Example:
-
Input Transactions:
(A, B, 10)(B, C, 5)(A, C, 5)
-
One Valid Output Payback List:
(C, A, 10)(B, A, 5)
After these paybacks, the net balance for A, B, and C will be zero.
Design and implement an algorithm that processes the given list of transactions and returns such a list of paybacks. If everyone's net balance is already zero initially, an empty list should be returned.
AI interview prep
Core dilemma
Demonstrating robust handling of unbounded data streams under tight memory constraints, coupled with the ability to design and implement a clear, correct algorithm for financial settlements without over-optimization.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Implement stream line reader and settle balances
Part 1: Streaming Line Reader from Chunked Source
You are provided with an existing class, ChunkSource, which offers a method nextChunk(). This method returns the next segment of text from a continuous stream, or null when the stream has concluded. Each chunk returned is an arbitrary substring of the original text and may contain zero or more newline characters (line breaks). When all chunks are concatenated, they form a sequence of logical lines, each terminated by a newline character.
Your task is to implement a LineReader class. This class must expose a method, nextLine(), which, upon each invocation, returns the next complete logical line from the stream, excluding the terminating newline character. The LineReader should internally call ChunkSource.nextChunk() as necessary to acquire more data. Once all data has been processed and no more lines are available, nextLine() should return null.
Example:
- Underlying logical lines:
one,two,three,four,five(each followed by a newline character). ChunkSourcesequence:["one\n tw", "o\n ", "three\n four", "\n fi", "ve"]- Consecutive
nextLine()calls should yield:"one","two","three","four","five", and subsequentlynull.
Constraint: The total stream size can be very large. Your implementation must use only O(L_max) additional memory, where L_max represents the length of the longest single line in the stream.
Part 2: Account Balance Settlement
You are given a list of money transfer transactions. Each transaction is represented as a tuple (from, to, amount), indicating that the person identified by from paid the person identified by to the specified amount. There are n distinct individuals involved across all transactions.
Your objective is to produce any valid list of payback transfers, also represented as (payer, receiver, amount). The condition for validity is that, after applying these payback transfers in addition to the original transactions, the net balance for every single person involved becomes exactly zero. You are explicitly not required to minimize the number of payback transactions; any list that achieves the zero-balance state for everyone is acceptable.
Example:
-
Input Transactions:
(A, B, 10)(B, C, 5)(A, C, 5)
-
One Valid Output Payback List:
(C, A, 10)(B, A, 5)
After these paybacks, the net balance for A, B, and C will be zero.
Design and implement an algorithm that processes the given list of transactions and returns such a list of paybacks. If everyone's net balance is already zero initially, an empty list should be returned.