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.

Apply Range Overwrite Queries | Google Coding Question

Apply Range Overwrite Queries

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given an integer array `nums` of length `n` and a list of range-assignment queries. Each query is a tuple `(left, right, value)`, where `left` and `right` define an inclusive index range, and the operation means: - for every index `i` such that `left <= i <= right`, set `nums[i] = value` All queries are applied **in the given order**, so later queries overwrite earlier updates on overlapping positions. Return the final state of the array after processing all queries. Your solution should be as efficient as possible. Example: - `nums = [1,2,3,4,5]` - `queries = [(1,3,9), (2,4,7)]` After the first query: `[1,9,9,9,5]` After the second query: `[1,9,7,7,7]` Return `[1,9,7,7,7]`. You may assume: - `0 <= left <= right < n` - `n` and the number of queries can both be large, so a naive `O(n * q)` approach may be too slow.

Quick Answer: This question evaluates a candidate's competency in array manipulation and range-update algorithms, focusing on efficient handling of batch assignments and overlapping updates.

You are given an integer array `nums` and a list of range-assignment queries. Each query is a tuple `(left, right, value)`, meaning every element from index `left` to index `right` inclusive should be set to `value`. Queries are applied in the given order, so later queries overwrite earlier ones on overlapping positions. Return the final state of the array after processing all queries. A naive `O(n * q)` simulation may be too slow for large inputs, so your solution should be as efficient as possible.

Constraints

0 <= n <= 200000
0 <= q <= 200000, where q = len(queries)
-10^9 <= nums[i], value <= 10^9
For every query `(left, right, value)`, `0 <= left <= right < n` when `n > 0`

Examples

Input: ([1, 2, 3, 4, 5], [(1, 3, 9), (2, 4, 7)])

Expected Output: [1, 9, 7, 7, 7]

Explanation: After `(1,3,9)`, the array becomes `[1, 9, 9, 9, 5]`. After `(2,4,7)`, positions 2 through 4 are overwritten, giving `[1, 9, 7, 7, 7]`.

Input: ([5, 6, 7], [])

Expected Output: [5, 6, 7]

Explanation: There are no queries, so the array stays unchanged.

Input: ([0, 0, 0, 0], [(0, 3, 1), (1, 2, 5), (2, 2, -3)])

Expected Output: [1, 5, -3, 1]

Explanation: Apply the queries in order: `[1,1,1,1]`, then `[1,5,5,1]`, then `[1,5,-3,1]`.

Input: ([], [])

Expected Output: []

Explanation: An empty array with no queries remains empty.

Input: ([8, 8, 8, 8, 8, 8], [(0, 5, 1), (2, 4, 2), (1, 3, 3), (5, 5, 9)])

Expected Output: [1, 3, 3, 3, 2, 9]

Explanation: The full-array overwrite is partially replaced by later queries, and the last query changes only index 5 to 9.

Hints

Try processing the queries from last to first. The first time you assign an index in reverse order, you already know its final value.
Use a disjoint-set / union-find style 'next unfilled index' structure so you can skip positions that have already been finalized.

Quick Overview

This question evaluates a candidate's competency in array manipulation and range-update algorithms, focusing on efficient handling of batch assignments and overlapping updates.