Katkat
Back

Solve order-statistics and XOR-triplet problems

GoogleSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to use Fenwick trees for order statistics and the properties of prefix XORs to solve counting problems efficiently.

Part 1: K-th Smallest Element in a Dynamic Array

Implement a data structure that supports the following operations on an array of integers:

  1. add(val): Add a value to the data structure.
  2. kth_smallest(k): Return the k-th smallest element currently in the collection.

Assume values are in the range [1, 10^6] and you need to perform Q operations (up to 2 * 10^5).

Part 2: XOR Triplets

You are given an array of integers arr. A triplet (i, j, k) is called a "good triplet" if 0 <= i < j <= k < arr.length and the XOR sum of the subarray arr[i...j-1] is equal to the XOR sum of the subarray arr[j...k].

Implement a function count_good_triplets(arr) that returns the total number of good triplets.

Example: Input: arr = [2, 3, 1, 6, 7] Output: 4 Explanation: The triplets are (0, 1, 2), (0, 2, 2), (2, 3, 4), and (2, 4, 4).

Constraints:

  • 1 <= arr.length <= 10^5
  • 0 <= arr[i] <= 10^9

Edge Cases

  • Empty array or array with one element.
  • Arrays where all elements are the same or zero.
  • Large values causing overflow (though XOR logic usually mitigates this).

Hints

Hint 1

For Part 1, consider using a Fenwick tree (Binary Indexed Tree) or a Segment Tree where the indices represent the values themselves to maintain frequency counts.

Hint 2

For Part 2, remember that the XOR sum of subarray `arr[a...b]` can be represented as `prefix_xor[b+1] ^ prefix_xor[a]`.

Hint 3

Observe that the condition `XOR(i, j-1) == XOR(j, k)` is equivalent to `prefix_xor[i] ^ prefix_xor[j] == prefix_xor[j] ^ prefix_xor[k+1]`, which simplifies to `prefix_xor[i] == prefix_xor[k+1]`.

Follow-up questions

  • In Part 1, how would your approach change if values were floating-point numbers instead of integers?
  • In Part 2, can you solve the problem in O(n) time and O(n) space?
  • How would you modify the Part 2 logic if the condition changed to requiring the XOR sum of three equal-length subarrays?