Maintain pair-sum counts under replacements
Company: Visa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
You are given two integer arrays A and B and a list of operations:
(
1) Query(T): return the number of pairs (i, j) such that A[i] + B[j] = T.
(
2) Replace(idx, val): set B[idx] = val. Return an array containing the result of each Query in order. Example: A = [1, 3], B = [2, 4]; operations: Query
(
5), Replace(0,
3), Query
(
4) -> output [2, 1]. Design a data structure to support very large inputs efficiently and state the time and space complexity of your approach.
Quick Answer: This question evaluates the ability to design dynamic data structures and perform algorithmic complexity analysis for maintaining pair-sum counts under element replacements, testing skills in efficient query/update handling and scalability.
Support Query(T) for count of A[i]+B[j]=T and Replace(idx,val) updates to B.
Examples
Input: ([1, 3], [2, 4], [('Query', 5), ('Replace', 0, 3), ('Query', 4)])
Expected Output: [2, 1]
Explanation: Prompt example.
Input: ([1, 1], [1], [('Query', 2)])
Expected Output: [2]
Explanation: Duplicates in A.
Input: ([0], [0], [('Replace', 0, 5), ('Query', 5)])
Expected Output: [1]
Explanation: Update B value.
Hints
- Keep frequency counters for A and B; queries iterate the smaller/static A counter.