Katkat

Implement sampling and subarray scan

GoogleData Scientist · Technical Screen

Last updated

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.

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.