← Google Interview Insights

Google·Data Scientist·Onsite - Coding / Algorithms·Intermediate

Intermediate
Jun 2026

Summary

Coding round at Google for a Data Scientist role. Two algorithm questions, nothing too exotic, but the second one had a follow-up about index recovery that I wasn't fully prepared for.

Questions Asked (2)

Q1

You have access to a function that returns a uniform random sample between 0 and 1. Write a function that returns a 2D point uniformly distributed over the square with corners at (-1, -1) and (1, 1). You can call the provided function as many times as you need.

Algorithms & Data Structures
Author's notes

This one was pretty approachable once I realized you just scale and shift each coordinate independently.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that the square is a product of two independent uniform distributions over [-1, 1]. Use the provided uniform(0,1) function to generate two independent samples, then transform each to the interval [-1, 1] via the linear map x = 2u - 1. Return the pair as the 2D point.

Pro tip: Mention that this works because the uniform distribution is invariant under linear transformations and the square is a Cartesian product of intervals, so independence is preserved. Also note that if the square were rotated or the region non-rectangular, a different method (e.g., rejection sampling) might be needed.

1. Understand the target distribution

The square is the Cartesian product [-1,1] × [-1,1]. A uniform distribution over this square means the joint density is constant over the square and zero outside.

2. Decompose into independent 1D uniforms

Because the square is a product region, the x and y coordinates are independent and each is uniformly distributed over [-1, 1].

3. Transform uniform(0,1) to uniform(-1,1)

If U ~ Uniform(0,1), then X = 2U - 1 is Uniform(-1,1). This is a linear transformation that preserves uniformity.

4. Generate two independent samples

Call the provided function twice to get independent U1 and U2, then compute X = 2*U1 - 1 and Y = 2*U2 - 1.

5. Return the point and verify

Return (X, Y). Optionally, explain that the joint density is constant 1/4 over the square, confirming uniformity.

Key Points to Mention

  • Independence of coordinates: The square is a product region, so x and y are independent.
  • Linear transformation: X = 2U - 1 maps Uniform(0,1) to Uniform(-1,1).
  • Uniformity preservation: Linear transformations of uniform distributions remain uniform over the transformed interval.
  • Joint density: The joint PDF is constant (1/4) over the square, confirming uniform distribution.
  • Efficiency: Only two calls to the provided function are needed.
  • Alternative methods: Rejection sampling could work but is less efficient; this direct method is optimal.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Q2

Given an integer array, find the length of the longest strictly increasing contiguous subarray. Also discuss time and space complexity, and explain how you would recover the actual start and end indices of that subarray.

Algorithms & Data Structures
Author's notes

The base problem is a standard linear scan.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a single-pass linear scan to track the current increasing run length and the maximum seen so far, updating start/end indices when a new maximum is found. Then state the O(n) time and O(1) space complexity, and explain how the indices are recovered during the scan.

Pro tip: Clarify edge cases upfront (empty array, all equal elements, strictly increasing/decreasing) and mention that the indices are 0-based unless specified otherwise. This shows attention to detail and prevents ambiguity.

1. Clarify requirements and edge cases

Confirm the definition of 'strictly increasing' (each element > previous) and ask about empty arrays, single-element arrays, and whether indices are 0-based or 1-based.

2. Outline the linear scan algorithm

Initialize max_len=1, current_len=1, and start/end indices. Iterate from the second element, incrementing current_len if arr[i] > arr[i-1], else resetting to 1. Update max_len and indices when current_len exceeds max_len.

3. Analyze time and space complexity

Explain that the algorithm makes a single pass over the array, so time complexity is O(n). Only a constant number of variables are used, so space complexity is O(1).

4. Explain index recovery

Describe how to track the start of the current run and update the global start/end when a new maximum is found. For example, when current_len resets, set current_start = i; when max_len updates, set max_start = current_start and max_end = i.

5. Test with examples and discuss alternatives

Walk through a sample array (e.g., [1,3,5,4,7]) to verify the algorithm. Mention that a two-pointer approach is equivalent, and note that this is optimal for a single query.

Key Points to Mention

  • Strictly increasing means each element must be greater than the previous (no equals).
  • Single-pass O(n) time and O(1) space is optimal for this problem.
  • Track current run length, max length, and start/end indices simultaneously.
  • Update indices only when a new maximum length is found to avoid unnecessary writes.
  • Handle edge cases: empty array (return 0), single element (return 1), all equal elements (return 1).
  • The algorithm can be easily adapted to return the subarray itself, not just its length.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.