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 medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Google during technical interviews.

Implement percentage RMSE and bootstrap its CI

Quick Overview

This question evaluates implementation and statistical reasoning skills, focusing on robust numerical computation of percentage RMSE (including handling zeros/negatives, optional country weights, and numerical stability) and nonparametric bootstrap methods for confidence intervals.

Company: Google

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a CSV with columns [country, actual_revenue, predicted_revenue], define percentage RMSE as pRMSE = sqrt(mean_i((pred_i/actual_i − 1)^2)). a) Implement pRMSE carefully: handle zeros/negatives, optional country weights, and numerical stability. b) Implement a nonparametric n‑of‑n bootstrap to obtain a 95% CI for pRMSE; justify the choice of resample size and discuss when a stratified or cluster bootstrap is preferable. c) What is the exact probability that one bootstrap resample equals the original sample in exactly the same order? Provide the formula in terms of n and explain why it is typically tiny. d) Discuss limitations of bootstrapping this metric (heavy tails, dependence across countries) and mitigations.

Quick Answer: This question evaluates implementation and statistical reasoning skills, focusing on robust numerical computation of percentage RMSE (including handling zeros/negatives, optional country weights, and numerical stability) and nonparametric bootstrap methods for confidence intervals.

Part 1: Implement percentage RMSE with filtering, weights, and numerical stability

You are given revenue records as tuples (country, actual_revenue, predicted_revenue). Define percentage RMSE as pRMSE = sqrt(mean((predicted / actual - 1)^2)). Implement a robust version with these rules: use only rows with actual_revenue > 0, predicted_revenue >= 0, and positive weight; if a country is missing from the weight map, use weight 1.0; compute the relative error as (predicted - actual) / actual for better numerical stability; return the weighted pRMSE rounded to 12 decimal places. If no valid rows remain, return None.

Constraints

0 <= len(rows) <= 200000
-10^15 <= actual_revenue, predicted_revenue <= 10^15
Weights may be omitted; missing countries default to weight 1.0
Rows with actual_revenue <= 0, predicted_revenue < 0, or weight <= 0 must be ignored

Examples

Input: ([('US', 100.0, 110.0), ('CA', 200.0, 180.0)], None)

Expected Output: 0.1

Explanation: Both rows have relative error magnitude 0.1, so pRMSE = sqrt((0.01 + 0.01) / 2) = 0.1.

Input: ([('A', 100.0, 120.0), ('B', 100.0, 100.0)], {'A': 3.0, 'B': 1.0})

Expected Output: 0.173205080757

Explanation: Weighted mean square error is (3*0.04 + 1*0.0) / 4 = 0.03, so pRMSE = sqrt(0.03).

Hints

The expression predicted / actual - 1 is algebraically equal to (predicted - actual) / actual, but the second form is numerically safer when predicted is very close to actual.
Filter invalid rows first, then compute a weighted mean of squared relative errors.

Part 2: Bootstrap a 95% CI for pRMSE with deterministic resampling

Given revenue records as tuples (country, actual_revenue, predicted_revenue), compute the pRMSE on the valid rows, then build a nonparametric n-of-n bootstrap confidence interval. First filter rows exactly as in Part 1: keep only rows with actual_revenue > 0, predicted_revenue >= 0, and positive country weight if a weight map is provided. Let n be the number of valid rows. For each bootstrap replicate, sample exactly n valid rows with replacement. To make this problem deterministic, use this pseudo-random generator: state = seed % 97 initially; on each draw, update state = (17 * state + 43) % 97 and select index = state % n. Compute B bootstrap pRMSE values, sort them, and form a 95% percentile CI using indices floor(0.025 * B) and ceil(0.975 * B) - 1. Return the original estimate and the CI bounds, each rounded to 6 decimal places. If no valid rows exist, return None.

Constraints

0 <= len(rows) <= 5000
1 <= B <= 5000
0 <= seed <= 10^9
Use n-of-n resampling, where n is the count of valid rows after filtering
Rows with actual_revenue <= 0, predicted_revenue < 0, or weight <= 0 must be ignored before bootstrapping

Examples

Input: ([('A', 100.0, 100.0), ('B', 100.0, 200.0)], 4, 2, None)

Expected Output: (0.707107, 0.0, 1.0)

Explanation: The original pRMSE is sqrt((0^2 + 1^2)/2) = 0.707107. With the specified generator and B = 4, the bootstrap estimates are [1.0, 0.0, 1.0, 0.707107].

Input: ([('A', 100.0, 110.0), ('B', 200.0, 220.0)], 6, 5, None)

Expected Output: (0.1, 0.1, 0.1)

Explanation: Every valid row has the same relative error 0.1, so every bootstrap sample also has pRMSE 0.1.

Hints

Resample from the filtered valid rows, not from the raw input.
Store all bootstrap estimates, sort them, then pick the two required order-statistic positions.

Part 3: Exact probability that a bootstrap resample matches the original sample in order

In an n-of-n bootstrap, a resample is formed by drawing n items independently with replacement from the original sample of size n. Compute the exact probability that the bootstrap resample is exactly equal to the original sample in the same order. Return the answer as a reduced fraction (numerator, denominator). For n = 0, define the probability as 1 because the empty resample is the only possible resample.

Constraints

0 <= n <= 100
For n > 0, the exact probability is 1 / n^n
The fraction should be reduced

Examples

Input: (3,)

Expected Output: (1, 27)

Explanation: There are 3^3 = 27 ordered resamples of length 3, and exactly one matches the original sample in order.

Input: (1,)

Expected Output: (1, 1)

Explanation: With one element, the only possible bootstrap draw matches the original.

Hints

Each of the n positions in the resample must pick one specific original item.
There is exactly one successful ordered resample out of n^n equally likely ordered resamples when n > 0.

Part 4: Detect bootstrap risks for pRMSE and recommend mitigations

You are given records as tuples (country, region, actual_revenue, predicted_revenue). Build a rule-based advisor that flags when an ordinary bootstrap CI for pRMSE may be unreliable. Work only on valid rows with actual_revenue > 0 and predicted_revenue >= 0. Apply these rules: (1) if there are no valid rows, return ['insufficient_data']; (2) if the number of valid rows is less than min_valid, include 'collect_more_data'; (3) compute squared relative errors e_i = ((predicted - actual) / actual)^2, let m be their median, and if m = 0 with max(e_i) > 0, or if m > 0 and max(e_i) / m >= tail_ratio, include both 'winsorize_or_log_transform' and 'report_robust_metric'; (4) if any region contains valid rows from at least 2 distinct countries, include 'cluster_bootstrap_by_region'; (5) if there are at least 2 regions and the largest region contains strictly more than imbalance_threshold of the valid rows, include 'stratified_bootstrap_by_region'. Return all triggered recommendations sorted lexicographically.

Constraints

0 <= len(rows) <= 200000
Use only valid rows with actual_revenue > 0 and predicted_revenue >= 0
Recommendation labels must be unique and sorted lexicographically
Median is the middle value after sorting, or the average of the two middle values for an even number of items

Examples

Input: ([('US', 'NA', 100.0, 100.0), ('CA', 'NA', 100.0, 90.0), ('MX', 'NA', 100.0, 1000.0), ('FR', 'EU', 100.0, 100.0)],)

Expected Output: ['cluster_bootstrap_by_region', 'collect_more_data', 'report_robust_metric', 'stratified_bootstrap_by_region', 'winsorize_or_log_transform']

Explanation: There are only 4 valid rows, one extreme error dominates the median, and region NA is both repeated across countries and overly dominant.

Input: ([('A', 'R1', 100.0, 102.0), ('B', 'R2', 100.0, 98.0), ('C', 'R3', 100.0, 101.0), ('D', 'R4', 100.0, 99.0), ('E', 'R5', 100.0, 100.0)],)

Expected Output: []

Explanation: There are enough valid rows, no heavy-tail warning, no repeated region with multiple countries, and no region imbalance.

Hints

Start by filtering valid rows; every later rule should use the filtered data only.
Heavy tails can be detected by comparing the largest squared relative error against the median, while dependence and imbalance come from region counts and distinct country counts.

Quick Overview