This blog summarizes my experience of the Google Online Assessment for the SDE Intern role (2025). The assessment consisted of two questions to be solved within one hour, with no individual time limits, and both questions were visible from the beginning.

Format

• Total Questions: 2
• Duration: 60 minutes
• Navigation: Free movement between questions allowed

Problem 1: String Swapping

Statement

You are given a string s of length n (1 ≤ n ≤ 1e5). You can perform the following operation any number of times: For index i from 1 to n-1 (1-based), you may choose to swap s[i] and s[i+1]. However, if you choose to swap at index i, then you cannot swap at index i+1. You must count the number of distinct strings that can be formed by performing any number of such operations.

Observations

This is a classic non-overlapping interval problem, which maps to a 1D DP. At each index, there are two choices: Do not swap → move to i+1 Swap → swap i and i+1, then skip i+2 since the next index becomes unavailable

Approach

Use dynamic programming to compute the number of unique configurations. Since we can process in left-to-right manner, we define dp[i] = number of unique suffixes starting at position i. If two substrings are the same after a swap or skip, memoize to avoid recomputation.

Problem 2: GCD-1 Partition

Statement

Given an array a of size n (1 ≤ n ≤ 1e5), find the number of ways to partition it into two disjoint sets such that: Every element belongs to exactly one of the two sets. The union of the two sets contains all elements of the original array. Let p1 and p2 be the product of the elements in the two sets respectively. The GCD of p1 and p2 is 1. Return the number of such valid partitions.

Observations

Any two elements that share a common prime factor must belong to the same set. Otherwise, their product will contribute the same prime, and the GCD will not be 1.

Approach

Factorize each element to find all prime factors. Use DSU (Disjoint Set Union) to merge sets of prime factors. For example: For number 6 = 2 * 3, union 2 and 3. For number 10 = 2 * 5, union 2 and 5. After processing all numbers, we will get several disjoint groups of primes where each group must lie in only one partition. Let k = number of such independent connected components. We can choose which side each of the k groups goes to, so total partitions: 2^k

Exclude: The case where all groups go to one side (invalid) The case where no group is chosen for one side (also invalid)

Final Answer: 2^k-2

This is a write-up of the DE Shaw Online Assessment for the SDE Intern 2025 role. The test consisted of 3 DSA problems with the following structure:

Format

3 programming questions

Separate timers for each question:

Q1: 20 minutes Q2: 30 minutes Q3: 30 minutes

• Questions had to be attempted in order.
• No ability to return to a previous question.
• Time left on a previous question could not be transferred to the next.

Problem 1: Divisible Substrings (20 mins)

Given a string s of lowercase English letters (length ≤ 1000), map each character c to a value using:

val(c) = (c - 'a' + 1) / 3 + 1

For example:

'a', 'b' → 1 'c', 'd', 'e' → 2 ... 'x', 'y', 'z' → 9

Count the number of substrings such that the sum of character values in the substring is divisible by the length of that substring.

A brute-force O(n²) approach, utilizing a nested loop, is effective.

Problem 2: Airport Scanner Simulation (30 mins)

Given two arrays:

time[i]: time when the i-th person wants to access the scanner (sorted) direction[i]: 0 if arrival, 1 if departure

Only one person can use the scanner at a time. At any given time, the priority rules are:

• If the scanner was used in the previous second, the same direction gets preference.
• If unused in the previous second, departure (1) gets preference.

Determine, for each person (in input order), the exact time they pass through the scanner.

This is a simulation problem. Maintain two queues (one for arrivals, one for departures), both with (index, time) pairs. Process second-by-second, applying the direction rules carefully. Track the scanner's usage state at each second.

Problem 3: Nearest Sensor in Row or Column (30 mins)

Given n sensors (n ≤ 10⁵), each with:

A unique string identifier

An (x, y) coordinate with 0 ≤ x, y ≤ 10⁸

You are given q queries, each being a string ID of a sensor. For each query, report the nearest sensor in the same row (same y) or the same column (same x). If there are multiple such sensors at the same distance, choose the one with the lexicographically smallest ID. If there are no such sensors, return "NONE".

The approach was as follows:

• Group all sensors by their x-coordinate and y-coordinate.
• For each group (i.e., each row or column), sort the sensors by their other coordinate.
• Store these sorted vectors of (coordinate, ID) pairs.
• For each sensor, check its position in its row and column group, and examine only the immediate neighbors (i.e., previous and next in the sorted list).
• Compare the distances and pick the closest sensor. In case of a tie, choose the one with the smaller ID.

Summary Q1: Straightforward brute-force or prefix sum-based substring counting. Q2: Simulation-heavy with direction-based rules and careful time tracking. Q3: Coordinate grouping with adjacent comparisons in sorted row/column lists.

The problems increased in complexity, testing implementation ability, data structure usage, and simulation accuracy under time constraints.