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 Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Solve order-statistics and XOR-triplet problems

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given two separate algorithmic problems. ## Problem 1: Count smaller elements to the right Given an integer array `nums` of length `n`, for each index `i` compute the number of indices `j > i` such that `nums[j] < nums[i]`. - **Input:** `nums` (may contain duplicates and negative values) - **Output:** an array `ans` of length `n`, where `ans[i]` is the count of smaller elements strictly to the right of `i` - **Constraints (typical interview scale):** `1 ≤ n ≤ 10^5`, `|nums[i]| ≤ 10^9` - **Expectation:** design an appropriate data structure / approach to meet an efficient time bound (e.g., ~`O(n log n)`), and be ready to discuss complexity and edge cases. ## Problem 2: Count triplets satisfying an XOR inequality on subarray XORs You are given `n` integers `a1, a2, ..., an` (`1 ≤ n ≤ 10^5`, `0 ≤ ai ≤ 10^9`). Define the function - `F(i, j) = ai XOR a(i+1) XOR ... XOR aj` for `1 ≤ i ≤ j ≤ n`. Count the number of index triplets `(x, y, z)` with `1 ≤ x ≤ y ≤ z ≤ n` such that: - `F(x, y) XOR F(y, z) > F(x, z)`. Notes: - `XOR` is the bitwise exclusive-or. - The output should be the **count** of valid triplets (an `O(n^3)` enumeration is not acceptable for the given constraints). - You may assume the answer fits in 64-bit signed integer unless otherwise specified. - Interview expectation: simplify using prefix XOR and reason about the inequality bit-by-bit to derive an efficient algorithm.

Quick Answer: This multi-part question evaluates skills in order-statistics and efficient counting for array inversion-like problems, alongside bitwise manipulation and prefix-XOR reasoning for combinatorial triplet counting.

Part 1: Count Smaller Elements to the Right

Given an integer array nums, compute for every index i how many elements to its right are strictly smaller than nums[i]. Duplicates do not count as smaller, and values may be negative or very large. Return an array ans where ans[i] is the number of indices j > i such that nums[j] < nums[i]. If the input is empty, return an empty list.

Constraints

0 <= len(nums) <= 10^5
-10^9 <= nums[i] <= 10^9

Examples

Input: ([5, 2, 6, 1],)

Expected Output: [2, 1, 1, 0]

Explanation: For 5, the smaller elements to its right are 2 and 1. For 2, only 1 is smaller. For 6, only 1 is smaller.

Input: ([-1, -1],)

Expected Output: [0, 0]

Explanation: Equal values are not strictly smaller.

Input: ([],)

Expected Output: []

Explanation: Edge case: empty input returns an empty list.

Input: ([42],)

Expected Output: [0]

Explanation: A single element has nothing to its right.

Input: ([3, 2, 2, 6, 1],)

Expected Output: [3, 1, 1, 1, 0]

Explanation: For 3, the smaller values to the right are 2, 2, and 1. Each 2 has only 1 smaller element to its right.

Hints

If you scan from right to left, every element you have already seen is to the right of the current index.
Because values can be negative and large, map them to sorted ranks before using a Fenwick tree or segment tree.

Part 2: Count Triplets with XOR Inequality

You are given an array nums of non-negative integers. For 1-based indices, define F(i, j) as the XOR of nums[i] through nums[j], inclusive. Count the number of triplets (x, y, z) such that 1 <= x <= y <= z <= n and F(x, y) XOR F(y, z) > F(x, z). The array can be large, so an O(n^3) enumeration is not acceptable. If the input is empty, return 0.

Constraints

0 <= len(nums) <= 10^5
0 <= nums[i] <= 10^9
The answer fits in a signed 64-bit integer

Examples

Input: ([],)

Expected Output: 0

Explanation: Edge case: there are no triplets in an empty array.

Input: ([0],)

Expected Output: 0

Explanation: For the only triplet (1,1,1), both sides are equal to 0, so the inequality is false.

Input: ([1, 1],)

Expected Output: 2

Explanation: The valid triplets are (1,1,2) and (1,2,2).

Input: ([2, 3, 1],)

Expected Output: 6

Explanation: There are 6 valid triplets after evaluating all x <= y <= z combinations.

Input: ([1, 2, 3],)

Expected Output: 5

Explanation: Five triplets satisfy the inequality.

Hints

Write every subarray XOR using prefix XORs P[k] = nums[0] XOR nums[1] XOR ... XOR nums[k-1].
For a fixed y, let b be the highest set bit of nums[y]. Comparing T and T XOR nums[y] depends first on bit b.

Quick Overview

This multi-part question evaluates skills in order-statistics and efficient counting for array inversion-like problems, alongside bitwise manipulation and prefix-XOR reasoning for combinatorial triplet counting.