Katkat
Back

Count Equal-Difference Triples After Each Add or Remove-All Operation

SIG (Susquehanna)Software Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Process a stream of add-one and remove-all operations on a multiset and report, after each operation, how many element triples form an arithmetic progression with a fixed positive difference. It tests efficient incremental updates, correct treatment of duplicate occurrences, and counts that exceed the 32-bit range.

Process a stream of operations on a multiset of integers and, after every operation, report how many triples of elements form an arithmetic progression with common difference diff.

Each operation is a string. "+x" adds one occurrence of the integer x to the multiset, and "-x" removes every occurrence of x from it. After each operation, count the triples (a, b, c) of elements currently in the multiset such that a - b == diff and b - c == diff.

Function Signature

count_triples_after_each(operations: list[str], diff: int) -> list[int]

Rules

  • The multiset starts empty.
  • "+x" adds one more occurrence of x, even if x is already present.
  • "-x" removes all occurrences of x. If x is absent, the operation changes nothing, but a count is still reported for it.
  • Triples are counted over individual occurrences: a triple chooses one occurrence of a value a, one occurrence of b = a - diff, and one occurrence of c = a - 2 * diff. If those three values occur p, q, and r times, they contribute p * q * r triples.
  • Return one count per operation, in operation order.

Constraints

  • 1 <= len(operations) <= 100000.
  • Each operation is + or - followed immediately by the decimal digits of x, where 0 <= x <= 1000000000 and there are no leading zeros except for x = 0 itself.
  • 1 <= diff <= 1000000000. Requiring a positive diff is a convention of this exercise.
  • A count can exceed 2^31 - 1 (for example, when three consecutive progression values each occur tens of thousands of times), so use 64-bit arithmetic. Every count stays within 2^53.

Examples

Input: operations = ["+4","+5","+6","+4","+3","-4"], diff = 1

Output: [0,0,1,2,4,0]

After "+6", the values 6, 5, 4 form one triple. The second "+4" doubles that to 2. After "+3", the progressions 6, 5, 4 and 5, 4, 3 each contribute 2 triples because 4 occurs twice, giving 4. Removing every 4 leaves no progression.

Input: operations = ["+1","+3","+5","+3","-7","+5"], diff = 2

Output: [0,0,1,2,2,4]

"-7" removes nothing, so the count stays 2. The final "+5" makes the occurrence counts of 5, 3, and 1 equal to 2, 2, and 1, giving 4.