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
