Katkat
Back

Implement sampling, subarray scan, and percentile estimate

GoogleData Scientist · Technical Screen
EasyData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to generate random uniform points within a geometric shape, process contiguous array properties using linear scans, and perform linear interpolation on histogram data to approximate percentiles.

Part 1: Geometric Sampling

Write a function sample_circle(radius) that returns a random coordinate (x, y) uniformly distributed within a circle centered at (0, 0) with the given radius.

Part 2: Longest Increasing Subarray

Given an array of integers nums, find the length of the longest strictly increasing contiguous subarray. Example: nums = [1, 3, 5, 4, 7] returns 3 (subarray [1, 3, 5]).

Part 3: Percentile Estimation

You are given a list of tuples bins = [(lower_bound, upper_bound, count), ...] representing a histogram of a dataset. Write a function estimate_percentile(bins, p) that returns the estimated value of the p-th percentile (where p is between 0 and 100), assuming a uniform distribution of values within each bucket.

Constraints

  • radius > 0
  • len(nums) up to 10^5
  • bins are sorted by lower_bound and cover the entire data range.

Example for Part 3

bins = [(0, 10, 50), (10, 20, 50)], p = 75. Total count is 100. The 75th percentile is the 75th value. The first bucket holds 50 values, so we need the 25th value from the second bucket. Since the second bucket is (10, 20), we interpolate 25/50 of the way: 10 + (20-10) * (25/50) = 15.0.

Hints

Hint 1

For Part 1, remember that sampling by radius directly will cluster points at the center; use the square root of a random uniform variable to account for the area density.

Hint 2

For Part 2, use a single pass with two pointers or a tracking variable that resets whenever the current element is not strictly greater than the previous.

Hint 3

For Part 3, calculate the cumulative sum of counts to identify the target bucket, then use linear interpolation based on the proportion of the target index within that bucket.

Follow-up questions

  • How would you modify the sampling function if the shape were a triangle instead of a circle?
  • How does the time complexity of the percentile estimation change if the input bins are not sorted?
  • What are the trade-offs between using bucketed histogram data versus storing the raw data for percentile calculations?