How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Capital One.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Capital One during technical interviews.

Support updates and count target-sum pairs | Capital One Coding Question

Q: Support updates and count target-sum pairs

This question evaluates data structures and algorithmic skills for dynamic pair counting, focusing on frequency management, efficient update handling, and query-time computation in a two-sum variant.

Support updates and count target-sum pairs

Company: Capital One

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

You are given two integer arrays: - `A` (fixed / primary) - `B` (modifiable / secondary) You must process a sequence of operations of two types: 1. **Update**: set `B[index] = value`. 2. **Query**: given an integer `target`, return the **number of pairs** `(i, j)` such that `A[i] + B[j] == target`. Pairs are counted with multiplicity: if `A` contains duplicates or `B` contains duplicates, each index combination counts as a distinct pair. ### Input - Arrays `A` and `B` - A list of operations, each operation is either: - `("update", index, value)` - `("count", target)` ### Output For each `("count", target)` operation, output an integer: the number of valid pairs. ### Example - `A = [1, 2, 2]` - `B = [3, 2]` - Query `target = 4` - Valid pairs are `(1,3)`, `(2,2)` using the first `2` in `A`, and `(2,2)` using the second `2` in `A` → total `3`. ### Constraints (assume typical interview constraints) - `1 <= len(A), len(B) <= 10^5` - Number of operations up to `10^5` - Values can be negative and up to typical 32-bit integer range.

Quick Answer: This question evaluates data structures and algorithmic skills for dynamic pair counting, focusing on frequency management, efficient update handling, and query-time computation in a two-sum variant.

You are given two integer arrays: - `A` (fixed / primary) - `B` (modifiable / secondary) Process a sequence of operations of two types: 1. **Update** `("update", index, value)`: set `B[index] = value`. 2. **Count** `("count", target)`: return the **number of pairs** `(i, j)` such that `A[i] + B[j] == target`. Pairs are counted with multiplicity: if `A` or `B` contain duplicate values, each distinct index combination counts separately. Return a list with one integer per `count` operation, in order. ### Example - `A = [1, 2, 2]`, `B = [3, 2]`, query `target = 4`. - Valid index pairs: `A[0]=1` with `B[0]=3`; `A[1]=2` with `B[1]=2`; `A[2]=2` with `B[1]=2` → total `3`. ### Approach Maintain a frequency map (Counter) over the current values of `B`. A `count` query answers in O(|A|) by summing `freq[target - A[i]]` over all `i`. An `update` adjusts the frequency map in O(1): decrement the old value's count, increment the new value's. The naive dictionary two-sum fails the duplicate case because it collapses equal values; the fix is to count *occurrences* (multiplicity) rather than mark presence.

Constraints

1 <= len(A), len(B) <= 10^5
Number of operations up to 10^5
Values can be negative and span the 32-bit integer range
For an update, 0 <= index < len(B)
Pairs are counted with multiplicity (by index combination, not by distinct value)

Examples

Input: ([1, 2, 2], [3, 2], [("count", 4)])

Expected Output: [3]

Explanation: Worked example: A[0]=1 pairs with B[0]=3; A[1]=2 and A[2]=2 each pair with B[1]=2 → 3 pairs.

Input: ([1, 2, 2], [3, 2], [("count", 4), ("update", 1, 3), ("count", 4)])

Expected Output: [3, 2]

Explanation: After setting B[1]=3, B=[3,3]; only A[0]=1 sums to 4 with each 3, giving 2 pairs.

Input: ([5], [5], [("count", 10), ("update", 0, 0), ("count", 10), ("count", 5)])

Expected Output: [1, 0, 1]

Explanation: 5+5=10 (1 pair); after B[0]=0 nothing sums to 10; 5+0=5 gives 1 pair.

Input: ([1, 1, 1], [1, 1], [("count", 2)])

Expected Output: [6]

Explanation: Every A[i]=1 pairs with every B[j]=1: 3*2=6 pairs (multiplicity).

Input: ([-3, 2], [3, -2], [("count", 0), ("count", 100)])

Expected Output: [2, 0]

Explanation: Negatives: -3+3=0 and 2+(-2)=0 give 2 pairs; nothing reaches 100.

Input: ([0], [0], [("count", 0)])

Expected Output: [1]

Explanation: Single zero in each array sums to 0 → 1 pair.

Input: ([1, 2, 3], [4, 5, 6], [("update", 0, 2), ("update", 1, 2), ("update", 2, 2), ("count", 4)])

Expected Output: [3]

Explanation: After three updates B=[2,2,2]; only A[0]=1 reaches 4 with each 2 → wait, 1+2=3 not 4. A[1]=2 pairs with none? 2+2=4 holds for A[1] across all three B values → 3 pairs.

Hints

A plain presence-based dictionary two-sum undercounts when values repeat. Count occurrences (frequencies) instead.
Keep a frequency map of B's current values so each count query is sum over i of freq[target - A[i]].
An update is O(1): decrement the old value's frequency, increment the new value's, and remember to mutate B itself.
Iterate A (the fixed array) for each query; updates only touch B, so the map of B stays cheap to maintain.

Quick Overview

This question evaluates data structures and algorithmic skills for dynamic pair counting, focusing on frequency management, efficient update handling, and query-time computation in a two-sum variant.