Katkat
Back

Maintain pair-sum counts under replacements

VisaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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 (
  3. -> output [2, 1]. Design a data structure to support very large inputs efficiently and state the time and space complexity of your approach.