Quick Overview

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.

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

Company: Sig

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

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.

Overview: 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.

Read the full Sig Software Engineer interview experience this question came from

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`. 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: the i-th returned value is the number of triples in the multiset immediately after the i-th operation. A single count can exceed `2^31 - 1`, so use 64-bit arithmetic (`long` in Java, `long long` in C++). Every count stays within `2^53`. Example 1: 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. Example 2: 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.

Constraints

  • The multiset starts empty.
  • 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: long in Java and long long in C++. Every count stays within 2^53.
  • Exactly one count is returned per operation, in operation order.

Examples

Input: (['+4', '+5', '+6', '+4', '+3', '-4'], 1)

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

Explanation: Source example 1: 6/5/4 forms one triple, the second '+4' doubles it, '+3' adds the 5/4/3 progression for a total of 4, and '-4' removes every 4 so nothing is left.

Input: (['+1', '+3', '+5', '+3', '-7', '+5'], 2)

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

Explanation: Source example 2: '-7' is absent so the unchanged count 2 is still reported; the final '+5' gives occurrence counts 2, 2 and 1 for 5, 3 and 1, i.e. 4 triples.

Hints

  1. Each operation changes the number of occurrences of exactly one value, so ask which triples can appear or disappear because of that single change instead of recounting everything.
  2. A triple is pinned down by the three values a, a - diff and a - 2 * diff, so the value an operation touches may be the largest, the middle, or the smallest element of an affected triple.
  3. '-x' can change an occurrence count by more than one at a time, and it must still report a count when x was not present at all.

Loading coding console...

Show the approach

Approach

Keep a hash map counts from value to number of occurrences plus a running total. The answer after an operation is exactly the sum over every value a of counts[a] * counts[a - diff] * counts[a - 2 * diff], but recomputing that sum per operation is too slow for 100000 operations, so maintain it incrementally.

An operation changes the occurrence count of exactly one value x by a single delta: '+x' gives delta = 1, and '-x' gives delta = -counts[x], which is 0 when x is absent. Because diff >= 1, the five values x - 2diff, x - diff, x, x + diff, x + 2diff are pairwise distinct, so exactly three terms of the sum mention x: the term where x is the largest element (a = x), the term where x is the middle element (a = x + diff), and the term where x is the smallest element (a = x + 2*diff). Every other factor in those three terms belongs to a different value and is untouched by the operation, so the sum changes by delta * (counts[x-diff]counts[x-2diff] + counts[x+diff]counts[x-diff] + counts[x+2diff]*counts[x+diff]), where all neighbour counts are read before (equivalently after) the update since the operation never modifies them.

Invariant: after processing operation i, total equals the full triple sum for the current multiset. It holds initially (empty multiset, total 0), and the update above is precisely the difference between the sums before and after the single-value change, so it is preserved; hence each appended value is the required count. Updating a bulk removal in one step is what keeps the whole run linear: each operation does O(1) map lookups.

Edge cases: '-x' for an absent x has delta 0, performs no update and still appends the unchanged total; a value whose count returns to 0 is erased from the map so it can never contribute a phantom factor; x = 0 or diff = 1000000000 make neighbour keys negative or larger than 2^31 - 1, which is harmless because keys are ordinary 64-bit integers and missing keys read as 0; values repeated many times multiply, so pqr can exceed 2^31 - 1 and every accumulator must be 64-bit (long in Java, long long in C++); JavaScript numbers are exact here because every count stays within 2^53.

Time complexity:
O(n)
Space complexity:
O(n)