Google online coding challenge: Internship 2021 Cutoff score? How many question req?

general
,
1

I was able to get both question accepted
these were my questions
if someone solved both and is contacted for interview plz share with me here

also i would like to know about the difficulty of questions so please share how many you were able to solve

Thanks…

Q1
Q12736×1495 355 KB
Q2
Q22736×1504 347 KB

2 Likes
2

Hey may I know the approach for the first question ? I too got the same question and couldn’t do it

3

Do a DFS and store all nodes values on path from 1 to current node in an array
traverse in reverse and find closest node which is coprime to current node value

time lt was 10 sec so n^2 worked

5 Likes
5

/* Closest pair problem solution Google*/

#include<bits/stdc++.h>
using namespace std;

int n;
vector g[10000+5];
int val[10000+5];
int vis[10000+5]={0};
int ans[10000+5]={100};
vectorinside;

void dfs(int v,vector& inside){

vis[v]=1;
int in=inside.size();
int flag=1;
for(int i=in-1;i>=0;i–){
if(__gcd(val[v],val[inside[i]])==1){
ans[v]=inside[i];
flag=0;
break;
}
}
if(flag){
ans[v]=-1;
}

inside.push_back(v);
for(int i=0;i<g[v].size();i++){
if(vis[g[v][i]]==0)
dfs(g[v][i],inside);
}
inside.pop_back();
}

int main(){

cin>>n;

for(int i=1;i<=n;i++){
   int x;
   cin>>x;
   val[i]=x;
}

for(int i=1;i<=n-1;i++){
    int x,y;
    cin>>x>>y;
    g[x].push_back(y);
    g[y].push_back(x);
}
dfs(1,inside);

for(int i=1;i<=n;i++){
    cout<<ans[i]<<" ";
}
cout<<endl;

}

6

Is this the google 2021 intern role in America and is this the online assessment?

7

It was for India and it was the online assessment round

1 Like
8

I’m looking for the America online assessment… so nervous after seeing these two : (

9

I believe there are tonnes of such problems (US specific) on leetcode https://leetcode.com/discuss/interview-question/352460/Google-Online-Assessment-Questions

10

Thanks. i have seen this before. But not sure are the Online coding question exactly the same he listed.

11

To be honest, it wont help. You would get something quite different. Maybe something you’re weak at. Its google after all, they know where u weak at xD

2 Likes
12

can you give the solution of 2nd question.
Thanks

13

May be the test cases were weak… in the worst case a tree can be like an normal list…in that case it should time out… the values of nodes are <= 100 (from constraints)
so you could just find the values which are coprime with the current node’s value easily… and for each such value we can find the distance between such a node and the current node easily… by this way the time complexity will be O(N)

14

I was also able to get both the questions. Did you get any reply from them?

15

How did you register for it? Did you use this link? https://prismatic-age-179203.appspot.com/

16

This has happened to many students

17

I gave my coding round today. Just wanted to confirm that we only have to click the submit button beside compile and test, and if all test cases pass we are done, right? I couldn’t see my score and hence confused.

18

Did anyone get a reply from them? On further process?

19

Cutoff : Be a GIRL
Else : Rejected.

12 Likes
20

lol…

21

If you want to know a better solution, then we can use sparse table to store the gcd from i to 2^j th parent. Now If we iterate over every element and then do a binary search it would just take n*log(n)*log(n) time. Is this solution cool (We can apply Binary search as gcd will be decreasing function while moving up the ancestors)