Implement sampling and subarray algorithms
Company: Google
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
This coding round contained two algorithmic prompts:
1. **Uniform sampling in a 2D square**
You are given access to a function `rand01()` that returns independent samples from the continuous uniform distribution `Uniform(0, 1)`. Implement a function that returns a 2D point `(x, y)` sampled uniformly from the square `(-1, 1) × (-1, 1)`. You may call `rand01()` as many times as needed. Briefly explain why your method produces a uniform sample.
2. **Longest increasing contiguous subarray**
Given an integer array `nums` of length `n`, find the length of the longest **contiguous** subarray such that every adjacent pair is strictly increasing; that is, for all valid `i` in the subarray, `nums[i] < nums[i+1]`. Aim for `O(n)` time and `O(1)` extra space. If helpful, also describe how to recover the start and end indices of such a subarray.
Quick Answer: This question evaluates understanding of probabilistic sampling and geometric uniformity alongside array algorithm design for contiguous subarray detection, covering competencies in random number transformation, reasoning about distributions, linear-time scanning, and in-place space optimization.