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 sampling and subarray scan | Google Coding Question

Quick Overview

This question evaluates probabilistic sampling and random-number transformation concepts for generating uniform points in a continuous domain, alongside array-processing and algorithmic analysis skills for identifying the longest strictly increasing contiguous subarray.

Implement sampling and subarray scan

Company: Google

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

A coding interview included the following algorithm questions: 1. You are given access to a function `rand01()` that returns an independent sample from `Uniform(0, 1)`. Write a function that returns a 2D point `(x, y)` uniformly distributed over the square `(-1, 1) x (-1, 1)`. You may call `rand01()` as many times as needed. 2. Given an integer array `nums`, find the length of the longest strictly increasing contiguous subarray (also called the longest increasing continuous subarray). Clarify the time and space complexity of your approach, and mention how you would recover the actual subarray indices if needed.

Quick Answer: This question evaluates probabilistic sampling and random-number transformation concepts for generating uniform points in a continuous domain, alongside array-processing and algorithmic analysis skills for identifying the longest strictly increasing contiguous subarray.

Part 1: Generate a Uniform 2D Point in a Square

You are given successive outputs of a function rand01(), where each output is an independent sample from Uniform(0, 1). Return a 2D point (x, y) uniformly distributed over the square (-1, 1) x (-1, 1). For testability, the input is a list rand_values representing values returned by rand01() in order. Use the first two values that are strictly inside (0, 1), transform them, and return the resulting point. Values equal to 0 or 1 are ignored because the target square is open. In a real continuous uniform sampler, endpoints occur with probability 0.

Constraints

1 <= len(rand_values) <= 10^5
0.0 <= rand_values[i] <= 1.0
At least two values in rand_values are strictly between 0 and 1
The values represent independent samples from rand01()

Examples

Input: ([0.25, 0.75],)

Expected Output: (-0.5, 0.5)

Explanation: x = 2 * 0.25 - 1 = -0.5, y = 2 * 0.75 - 1 = 0.5.

Input: ([0.5, 0.5],)

Expected Output: (0.0, 0.0)

Explanation: Both samples map to the center of the square.

Input: ([0.0, 1.0, 0.125, 0.875],)

Expected Output: (-0.75, 0.75)

Explanation: The endpoint values 0.0 and 1.0 are ignored; 0.125 and 0.875 are used.

Input: ([0.75, 0.25, 0.5],)

Expected Output: (0.5, -0.5)

Explanation: Only the first two valid samples are needed; later samples are ignored.

Hints

A linear transformation maps Uniform(0, 1) to Uniform(-1, 1).
To sample a point uniformly from a square, sample each coordinate independently.

Part 2: Longest Strictly Increasing Contiguous Subarray

Given an integer array nums, find the length of the longest strictly increasing contiguous subarray. A contiguous subarray is a consecutive segment of the original array. The subarray must be strictly increasing, meaning every element must be greater than the previous element. If nums is empty, return 0. If you needed to recover the actual subarray indices as well, you could track the start index of the current increasing run and update the best start/end indices whenever you find a longer run.

Constraints

0 <= len(nums) <= 10^5
-10^9 <= nums[i] <= 10^9
The subarray must be contiguous
The increase must be strict, so equal adjacent values break the run

Examples

Input: ([],)

Expected Output: 0

Explanation: The empty array has no subarrays.

Input: ([7],)

Expected Output: 1

Explanation: A single element is an increasing contiguous subarray of length 1.

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

Expected Output: 3

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

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

Expected Output: 1

Explanation: Equal adjacent values are not strictly increasing, so each run has length 1.

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

Expected Output: 5

Explanation: The longest strictly increasing contiguous subarray is [0, 1, 2, 3, 4].

Hints

Scan from left to right and compare each element with the previous one.
Maintain the length of the current increasing run and the best length seen so far.

Quick Overview