They ask all data structure questions. The Google Tech Dev Guide is good enough for preparation. I cleared all the coding rounds but failed the theoretical technical. Here are two questions that I managed to copy.

The interview is on Google Docs, not an editor. You share your camera and screen while typing in the doc, and they have the doc open at the same time.

ACTUAL INTERVIEW QUESTIONS and my solution

Question:

Print all possible sequences of 1s and 2s that sum up to the given number N.

def print_sequence(N): def backtrack(remaining, sequence): if remaining == 0: print(sequence) return

if remaining < 0:
  return

sequence.append(1)
backtrack(remaining - 1, sequence)
sequence.pop()

sequence.append(2)
backtrack(remaining - 2, sequence)
sequence.pop()

backtrack(N, [])

print_sequence(3)

Expected output:

[1, 1, 1]

[1, 2]

[2, 1]

print_sequence(1)

Expected output:

[1]

print_sequence(0)

Expected output:

[]

Test cases:

TC1: N = 3

TC2: N = 1

TC3: N = 0

Complexity:

Time complexity: O(2^N)

Space complexity: O(N)

Question:

Given a list of timestamp ranges, each range represents a user using a Google service. Write a function that returns the count of users using the Google services at a specific query timestamp.

Example:

A range can be represented as: [starting, ending], e.g., [1, 3] or [0, 10] and so on.

For instance, given a list of ranges:

[0, 5]

[6, 8]

[2, 9]

[4, 10]

[3, 5]

For a query timestamp of 3, the users active are from ranges:

[0, 5], [2, 9], [3, 5]

The function should return 3.

def count_active_users(ranges, timestamp): count = 0 for r in ranges: if r[0] <= timestamp <= r[1]: count = count + 1 return count

The above function is a naive approach. A more efficient approach uses preprocessing.

import bisect

def preprocess_ranges(ranges): events = {} for start, end in ranges: events[start] = events.get(start, 0) + 1 events[end + 1] = events.get(end + 1, 0) - 1

sorted_times = sorted(events.keys())

counts = [] current = 0 for t in sorted_times: current += events[t] counts.append(current)

return sorted_times, counts

def query_active_users(sorted_times, counts, timestamp):

Find the index of the rightmost element less than or equal to timestamp

bisect_right finds the insertion point for timestamp to maintain order.

Subtracting 1 gives the index of the element just before it, which corresponds to the count

at or before the timestamp.

idx = bisect.bisect_right(sorted_times, timestamp) - 1 if idx < 0: return 0 else: return counts[idx]

Example Usage:

input_ranges = [[0, 5], [6, 8], [2, 9], [4, 10], [3, 5]] sorted_times, counts = preprocess_ranges(input_ranges)

Query for timestamp 11 (should be 0)

print(f"Active users at timestamp 11: {query_active_users(sorted_times, counts, 11)}")

Query for timestamp 3 (should be 3)

print(f"Active users at timestamp 3: {query_active_users(sorted_times, counts, 3)}")

Additional Test Cases:

def test_active_users(): ranges = [[0, 5], [6, 8], [2, 9], [4, 10], [3, 5]] sorted_times, counts = preprocess_ranges(ranges)

assert query_active_users(sorted_times, counts, 6) == 3 assert query_active_users(sorted_times, counts, 0) == 1 assert query_active_users(sorted_times, counts, 3) == 3 # Corrected based on explanation assert query_active_users(sorted_times, counts, 5) == 3 # Users at the end of range assert query_active_users(sorted_times, counts, 9) == 2 # Users at the end of range assert query_active_users(sorted_times, counts, 10) == 1 assert query_active_users(sorted_times, counts, 11) == 0

Overlapping ranges test

ranges_overlap = [[1, 10], [2, 9], [3, 8], [4, 7]] sorted_times_overlap, counts_overlap = preprocess_ranges(ranges_overlap) assert query_active_users(sorted_times_overlap, counts_overlap, 1) == 1 assert query_active_users(sorted_times_overlap, counts_overlap, 5) == 4 assert query_active_users(sorted_times_overlap, counts_overlap, 10) == 1 assert query_active_users(sorted_times_overlap, counts_overlap, 11) == 0

print("All test cases passed!")

test_active_users()

Complexity:

Time complexity: O(N log N) for sorting events (where N is the number of ranges).

Space Complexity: O(N) for storing event data.