Katkat
Back

Support updates and count target-sum pairs

Capital OneMachine Learning Engineer · Online Assessment
HardMachine Learning EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests the ability to maintain frequency counts of elements in a dynamic dataset and perform efficient range-sum queries for pairs that satisfy a target condition.

Problem Statement

You are building a real-time monitoring system that processes a stream of integers. You need to support two operations:

  1. update(index, new_value): Update the value at a given index (0-indexed) in the array. The array is initially filled with 0s.
  2. count_pairs(target): Return the number of unique pairs (i, j) such that i < j and array[i] + array[j] == target.

Function Signature

class PairCounter:
    def __init__(self, size: int):
        # Initialize an array of length 'size' with all 0s
        pass

    def update(self, index: int, new_value: int) -> None:
        # Update the value at 'index' to 'new_value'
        pass

    def count_pairs(self, target: int) -> int:
        # Return the count of pairs (i, j) where i < j and arr[i] + arr[j] == target
        pass

Constraints

  • size <= 10^5
  • Total operations <= 10^5
  • new_value and target range between -10^6 and 10^6.

Example

pc = PairCounter(5)
pc.update(0, 1)  # arr = [1, 0, 0, 0, 0]
pc.update(1, 2)  # arr = [1, 2, 0, 0, 0]
pc.update(2, 1)  # arr = [1, 2, 1, 0, 0]

# Pairs (i, j) where i  arr[0] + arr[2] = 1 + 1 = 2
# Result: 1

pc.count_pairs(2) # returns 1

Edge Cases

  • Updating an index to its existing value.
  • target is 0 or negative.
  • Large number of identical values in the array (e.g., all 0s).

Hints

Hint 1

Maintain a global frequency map (hash map) to keep track of the counts of each value currently in the array.

Hint 2

When updating index `i` from `old_val` to `new_val`, calculate how the number of pairs changes based on the frequencies of `target - old_val` and `target - new_val`.

Hint 3

Be careful to handle the case where `target - val` equals `val` (i.e., `target` is exactly double the value) correctly to avoid overcounting.

Follow-up questions

  • How would your solution change if we needed to count pairs where `array[i] + array[j] <= target`?
  • What is the time complexity of `count_pairs`? Can you optimize it to O(1) if the target value remains constant between updates?
  • How would you handle potential integer overflow if the number of pairs exceeds 2^31 - 1?