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.

Hints

  1. A linear transformation maps Uniform(0, 1) to Uniform(-1, 1).
  2. 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.

Hints

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

Loading coding console...