Quick 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.

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.

Part 1: Streaming Line Reader from Chunked Source

You are given a stream represented as a list of text chunks. Concatenating all chunks produces the original text stream. Newline characters '\n' separate logical lines. Implement a function that simulates repeatedly calling a line reader: it should return all complete lines in order, without their newline characters. If the final line does not end with a newline, it should still be returned. If the stream ends immediately after a newline, do not add an extra empty line after it. Consecutive newline characters represent empty lines.

Constraints

  • 0 <= len(chunks) <= 100000
  • 0 <= total number of characters across all chunks <= 1000000
  • Chunks contain arbitrary characters, with '\n' used as the only line separator.
  • The algorithm should use O(L_max) auxiliary memory excluding the returned output, where L_max is the length of the longest line.

Examples

Input: (['one\ntw', 'o\n', 'three\nfour', '\nfi', 've'],)

Expected Output: ['one', 'two', 'three', 'four', 'five']

Explanation: The chunks concatenate to 'one\ntwo\nthree\nfour\nfive', so five logical lines are returned.

Input: ([],)

Expected Output: []

Explanation: An empty stream contains no lines.

Hints

  1. Keep a buffer for the current unfinished line and only emit a line when you encounter a newline character.
  2. Be careful with consecutive newlines and with a final line that has no trailing newline.

Part 2: Account Balance Settlement

You are given n people labeled from 0 to n - 1 and a list of money transfer transactions. Each transaction [from, to, amount] means person from paid person to the given amount. For accounting purposes, the payer becomes owed that amount and the receiver owes that amount. Return any list of payback transfers [payer, receiver, amount] such that, after adding these paybacks to the original transactions, every person's net balance is zero. You do not need to minimize the number of payback transfers.

Constraints

  • 0 <= n <= 100000
  • 0 <= len(transactions) <= 100000
  • Each transaction has the form [from, to, amount].
  • 0 <= from, to < n
  • from may equal to, though such a transaction has no net effect.
  • 1 <= amount for each listed transaction
  • The sum of all transaction amounts is at most 1000000000.

Examples

Input: (3, [[0, 1, 10], [1, 2, 5], [0, 2, 5]])

Expected Output: [[1, 0, 5], [2, 0, 10]]

Explanation: Person 0 is owed 15, person 1 owes 5, and person 2 owes 10. The returned paybacks settle all balances.

Input: (2, [[0, 1, 7], [1, 0, 7]])

Expected Output: []

Explanation: The two transactions cancel each other out exactly.

Hints

  1. Compute each person's net balance first. Positive balances are people who should receive money; negative balances are people who should pay money.
  2. Use two pointers to greedily match debtors with creditors until all balances become zero.

Loading coding console...