AdityaDSingh's blog

Google Online Assessment (OA) IIT Bhubaneswar (2025) (for SDE Intern)
By AdityaDSingh, history, 13 months ago, In English

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

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
13 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    13 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Does it also involve camera montiorring also?

    → Reply
»
13 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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?

→ Reply
  • »
    »
    13 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it
    O(N) time, O(1) space
    → Reply
  • »
    »
    13 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    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.

    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);
}
    → Reply
    • »
      »
      »
      13 months ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it +1 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        13 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
    • »
      »
      »
      13 months ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      Thanks

      → Reply
    • »
      »
      »
      13 months ago, hide # ^ |
       
      Vote: I like it +4 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
13 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
13 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

#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;

    }
}
→ Reply