Google Online Assessment (OA) IIT Bhubaneswar (2025) (for SDE Intern)

№	Пользователь	Рейтинг
1	Benq	3857
2	jiangly	3810
3	maroonrk	3534
4	tourist	3528
5	Kevin114514	3510
6	turmax	3411
7	Um_nik	3387
8	Radewoosh	3367
9	heuristica	3322
10	strapple	3317

№	Пользователь	Вклад
1	Qingyu	158
2	maspy	150
3	Um_nik	146
4	Errichto	139
5	adamant	136
6	maroonrk	134
7	DNR	133
8	nik_exists	131
8	Dominater069	131
10	Proof_by_QED	130

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

rec(int i, string &s){ if(i >= n - 1) return 1; if(dp[i] != -1) return dp[i]; //if both are not equal then swap int swap = 0; if(s[i] != s[i + 1]) swap = rec(i + 2, s); //when not swapping just move ahead int notSwap = rec(i + 1, s); return dp[i] = (swap + notSwap); }

#include <bits/stdc++.h> using namespace std; int n; int solve(int i, string &s, vector<int> &dp){ if(i<0) return 1; if(dp[i]!=-1) return dp[i]; int noswap = solve(i-1,s,dp); int doswap =0; if(i!=n-1 && s[i]!=s[i+1]) doswap = solve(i-2,s, dp); return dp[i] = noswap+doswap; } int main(){ int t; cin >> t; while(t--){ cin >> n; string s; cin >> s; vector<int> dp(n,-1); cout << solve(n-1,s,dp) << endl; } }

Комментарии (24)

Написать комментарий?

agcodemaster

13 месяцев назад, скрыть # |

I got the problem 2 also as GCD partition. but unfortunately couldn't think of Disjoint set during the OA.

→ Ответить

AdityaDSingh

13 месяцев назад, скрыть # ^ |

Yeah, it was tough to figure out initially, but I took a case like {2, 4, 6, 3}. Eventually, I realized that although splitting {2,4} in set 1 and {3} in set 2 is understood, I cannot send 6 in either of them, hence it's actually just 1 big group of all 4 elements

TRIBALCHIEF0009

3 месяца назад, скрыть # ^ |

Does it also involve camera montiorring also?

pvr04

If possible, could you share the solution to the first one? I'm not sure how to handle the case with identical strings, since storing all strings in a set or map might cause MLE, right?

jdoe73x

O(N) time, O(1) space

int solve(const string& s) {
    constexpr int MOD = 1e9 + 7;
    const int n = (int)s.size();
    int dp0 = 1, dp1 = 0;
    for (int i = 1; i < n; i++)
        dp1 = exchange(dp0, (dp0 + dp1) % MOD) * (s[i] != s[i - 1]);
    return (dp0 + dp1) % MOD;
}

Thanks

← Rev. 2 →

I had solved with O(n) space and O(n) time. Let rec be my recursive function and dp[i] store the number of strings possible starting at index i.

ay012

← Rev. 3 →

can you pls give a sample test case for the problems? like for first problem what is the answer for s=abcd ? also since we can do the operation as many times so lets say in first operation we swap ab only and choose not to swap the remaining ones we arrived at bacd ,now again we choose to do operation this time will we be able to choose indices 1,2 and dont choose to swap the rests ? so can we get bcad ? that swapping restriction is for one operation right ?

thanks understood

Possible strings for abcd:

abcd (No swap) bacd (swap at i = 0) acbd (swap at i = 1) abdc (swap at i = 2) badc (swap at i = 0 and i = 2)

Utsav_Kasvala

Why are you adding 1 in the swap case ? I think adding 1 would give wrong answer , for example "ab" , with your solution answer would be 3 , but correct answer is 2.

Yeah, my bad I will correct that. Thanks for pointing it out

its_ritik_

2 месяца назад, скрыть # ^ |

But I am unable to getting it that how is it checking swapped string is unique or not ??

SamS_99

Apologies for this trivial thing, but for problem 2, shouldn't solution be (2^k-2)/2

Slayer_ayp

why are you doing /2 ?

preventing overcounting.

for {2,4,7,3}, S1 = {3} s2 = {2,4,7} partition is same as S1 = {2,4,7} and S2= {3} partition

I think?

ashishsam

in the OA they had asked for ordered partitions

No, order was to be maintained like set 1 and set 2 were specified as far as I remember

AGRU

For 2 question , the maximum value of array element is important. if its 1e18 then it won't be possible to do with the method u mentioned.

Yeah you are right, but it was within the bounds, I don't remember exactly but it was close to 1e5 or 1e6.

abhi_mishra

Means there sieve would be applicable?

Sieve would work , for more reference : GFG Article for Prime Factorization using sieve

Yes, even I used spf array

2 месяца назад, скрыть # |

Can this be a correct solution Or am I missing something ?

Блог пользователя AdityaDSingh

Format

Problem 1: String Swapping

Statement

Observations

Approach

Problem 2: GCD-1 Partition

Statement

Observations

Approach