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 easy 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 sampling, subarray scan, and percentile estimate

Quick Overview

This multi-part problem evaluates skills in random sampling and geometric probability for uniform 2D sampling, algorithmic array processing for finding the longest strictly increasing contiguous subarray, and statistical approximation and interpolation from bucketed histogram counts to estimate percentiles.

Company: Google

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

You will solve **three independent coding tasks**. ## Problem 1: Generate a 2D uniform sample in a square You are given access to a function `rand01()` that returns an i.i.d. sample from a **continuous** Uniform(0, 1) distribution. Write a function `samplePoint()` that returns a 2D point `(x, y)` that is uniformly distributed over the square: - \((-1, 1) \times (-1, 1)\) **Constraints/requirements**: - You may call `rand01()` as many times as needed. - The output must be uniform over the area of the square. --- ## Problem 2: Longest increasing continuous subarray Given an integer array `nums`, compute the length of the **longest contiguous subarray** that is **strictly increasing**. Example: - `nums = [1, 3, 5, 4, 7]` → answer is `3` (subarray `[1, 3, 5]`) Clarifications: - “Continuous” means contiguous (a subarray), not a subsequence. - Strictly increasing means `nums[i] < nums[i+1]`. --- ## Problem 3: Approximate an n-th percentile from bucketed counts You have search queries aggregated into **K buckets** (a histogram). Each bucket `i` has: - `left_i`: left boundary (inclusive) - `right_i`: right boundary (exclusive, unless it is the last bucket) - `count_i`: number of observations in that bucket You do **not** know the individual values inside buckets—only bucket boundaries and counts. Write a function to return an **approximation** of the `p`-th percentile (e.g., `p=0.90` for 90th percentile). Required behavior/assumptions (state clearly in your answer): - Buckets are ordered by boundary. - Total count is `N = sum(count_i)`. - You may assume values are **uniformly distributed within the bucket** used to locate the percentile (to enable interpolation). Output: - A single numeric estimate of the percentile value.

Quick Answer: This multi-part problem evaluates skills in random sampling and geometric probability for uniform 2D sampling, algorithmic array processing for finding the longest strictly increasing contiguous subarray, and statistical approximation and interpolation from bucketed histogram counts to estimate percentiles.

Part 1: Map Uniform Random Samples to a Square

You are implementing the core of a function `samplePoint()` that should return a point uniformly distributed over the square `(-1, 1) x (-1, 1)`. For deterministic testing, instead of calling `rand01()` inside the function, you are given two independent samples `u` and `v` from `Uniform(0, 1)`. Convert them into the corresponding point `(x, y)` that is uniform over the square. In real random sampling, `u` and `v` come from a continuous distribution, so hitting the exact boundaries has probability 0; however, test cases may include `0` and `1`.

Constraints

`0 <= u <= 1`
`0 <= v <= 1`
`u` and `v` should be treated as independent samples
Your mapping must preserve uniformity over the square area

Examples

Input: (0.25, 0.75)

Expected Output: (-0.5, 0.5)

Explanation: Map each coordinate with `2*t - 1`.

Input: (0.5, 0.5)

Expected Output: (0.0, 0.0)

Explanation: The center of `[0, 1]` maps to the center of the square.

Input: (0.0, 1.0)

Expected Output: (-1.0, 1.0)

Explanation: Boundary-value edge case used for deterministic testing.

Input: (1.0, 0.0)

Expected Output: (1.0, -1.0)

Explanation: Another boundary-value edge case.

Hints

How do you linearly map a number from `[0, 1]` into `[-1, 1]`?
If the x-coordinate and y-coordinate are transformed independently in the same way, the 2D point remains uniform over the square.

Part 2: Longest Increasing Continuous Subarray

Given an integer array `nums`, return the length of the longest contiguous subarray that is strictly increasing. A subarray must use consecutive elements, and strictly increasing means every next element is greater than the previous one.

Constraints

`0 <= len(nums) <= 200000`
`-10^9 <= nums[i] <= 10^9`
If the array is empty, return `0`

Examples

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

Expected Output: 3

Explanation: The longest strictly increasing contiguous subarray is `[1, 3, 5]`.

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

Expected Output: 1

Explanation: Equal neighbors do not count as strictly increasing.

Input: ([],)

Expected Output: 0

Explanation: Edge case: empty array.

Input: ([10],)

Expected Output: 1

Explanation: Edge case: a single element is an increasing subarray of length 1.

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

Expected Output: 5

Explanation: The entire array is strictly increasing.

Hints

Scan the array from left to right and track the current increasing streak length.
When `nums[i] <= nums[i-1]`, the increasing streak must restart at length `1`.

Part 3: Approximate a Percentile from Histogram Buckets

You are given histogram buckets describing aggregated observations. Each bucket is a tuple `(left, right, count)`, where `left` is the inclusive left boundary, `right` is the right boundary, and `count` is the number of observations in that bucket. Buckets are ordered by boundary and may include zero-count buckets. Return an approximation of the `p`-th percentile by assuming values are uniformly distributed inside the bucket that contains the percentile. Use this rule: let `N` be the total count, let `target = p * N`, find the first bucket whose cumulative count is at least `target`, and interpolate linearly inside that bucket. For `p = 0`, return the left boundary of the first bucket with positive count. For `p = 1`, return the right boundary of the last bucket with positive count.

Constraints

`1 <= len(buckets) <= 200000`
`left < right` for every bucket
`count` is a non-negative integer
Buckets are ordered by boundary
The total count `sum(count)` is positive
`0 <= p <= 1`

Examples

Input: ([(0, 10, 50), (10, 20, 30), (20, 40, 20)], 0.9)

Expected Output: 30.0

Explanation: Total count is 100, target is 90, which lies halfway through the last bucket, so the estimate is `20 + 0.5 * (40 - 20) = 30.0`.

Input: ([(0, 5, 2), (5, 15, 8)], 0.5)

Expected Output: 8.75

Explanation: Total count is 10, target is 5, which lies in the second bucket. Fraction inside the bucket is `(5 - 2) / 8 = 0.375`, so estimate is `5 + 0.375 * 10 = 8.75`.

Input: ([(0, 5, 2), (5, 15, 8)], 0.0)

Expected Output: 0.0

Explanation: Edge case: the 0th percentile is the left boundary of the first positive-count bucket.

Input: ([(0, 5, 2), (5, 15, 8)], 1.0)

Expected Output: 15.0

Explanation: Edge case: the 100th percentile is the right boundary of the last positive-count bucket.

Input: ([(0, 5, 0), (5, 10, 10)], 0.25)

Expected Output: 6.25

Explanation: Zero-count buckets are skipped. The percentile lies 25% of the way through the second bucket.

Hints

First locate which bucket contains the percentile by scanning cumulative counts.
Once you know the correct bucket, use the fraction of the bucket's count needed to reach the target rank, then scale that fraction across the bucket width.

Quick Overview