Google on-campus hiring test 2022 Solutions

[@vaalarivan_p]

Are the problems in Google oa sorted in the order of their difficulties?

[@Anonymous____________A721]

Are these really google qns?
All are medium
I wish i would get these😅

[@rohitrout6450]

P4 is such an amazing question😍

[@K_CO_ManjeetVats]

Hi bhaiya , I am not able to solve a single problem in Google coding round .I solved around 380 problems on leetcode . Bhaiya , i want to ask then how should i practice so that i am able to solve the problem. I know algorithm (like dp,greedy ) also know data structure (graph,trees) and solved medium level problem on them. But ,now i am frustrated that i am practicing but not able to solve problems. Please help

[@aayushgupta1711]

in problem 1
if on a path some value has occured more than half the nodes lying on that path.. then the remaining nodes would surely not satisfy the condition
so I guess question boils down to finding simple path consisting of the nodes of value same as a root

[@PIE_1e9]

Thanks for this video❤️

[@focus15624]

Hi. Can u advice me, if candidate master level is enough to crack Google?

[@vaibhavkaura2136]

Can you plzz do today's leetcode contest too, it was bit difficult than usual
Thankyou for the solutions

[@tirthsuthar6818]

I Guess no need to do trie solution in 2 question of string because it was said that the value of n*k
map mp;
for(int i=0;i

[@Harisamsharma]

This won't work because every string will have k prefixes and the total length of all prefixes of a string will be around k^2, so the total length of all prefixes will be nk^2. So it should MLE if you try to maintain a map.

[@vaibhaves]

We can also do problem 3 with merge sort approach

[@kunalbabbar7399]

for problem 1 can we maintain max cnt and chk if its greater than 1/2 of curr_len instead of maintaining a multiset?

[@hell-o8470]

what was the cf rating difficulty rating for problem P4 special paths?

[@Harisamsharma]

1800 I would say

[@hell-o8470]

​@@Harisamsharma And what could be the rating of last problem Partition string?
And thanks for this video.
Isn't last problem easier compared to 2nd last?

[@samagrapathak3854]

@@hell-o8470 1800 vo merse ho gai thi i am specialist

[@kshitizjaiswal6933]

Prefix sum thing can be done with a pointer and single variable too

[@eusebiu1050]

Nice explanations. Btw, I see that you have a dark theme for chrome that changes everthing to dark, even codeforces logo as I saw, which is awsome. How did you setup that?

[@nandapavan9987]

in probelm 5 for dp[i][j] we also need to check whether jth character is even right??

[@leviackerman9882]

how to solve good paths if the path don't always start from root ie it can start and end anywhere?

[@ShubhamKumar-me7xy]

You can solve problem 1 in O(n), anyway it was unnecessary :)

[@YashRaj-bn7du]

hello , Can u upload today google question test and solution

[@UtkarshAgarwal-YearBTechMining]

i think you wrote a little too much code for the last problem ..this much also satisfies i thinkm though the idea is same
int sol_2(string s, int n, int m, int k)
{
vector dp(n + 1, vector(k + 1));
vector pref(n + 1, vector(k + 1));
for(int i=0;i

[@jeevanalexen]

in problem c, we can't use lowerbound to count number of pairs?

[@Harisamsharma]

Because we have to make sure i

[@sumitprajapati821]

For problem D: special path.
I did the following . I don't know if its correct. was working on samples + looked intuitive.
Root the tree at node 1.
For each node "i" ,let up[i] = index of the ancestor of i closest to root.( the blocking points are the node where the value is greater than val[i])
Now I claim that two nodes i and j, such that val[i] = val[j] will form special path if and only if up[i] = up[j]
So we can create a mapmp;
and do mp[{val[i],up[i]}]++;
and finally added the NC2 to our answer for each value in the map.
the up array can be calculated using binary lifting (there may be a some easier way).
Worked out example.
Consider the tree in the sample
(1-base indexing}
up[] = {1,1,1,3,1,1}
map will look like
{3,1} -> 3
{2,1} -> 2
{1,3} -> 1
so ans=3C2 + 2C2 + 1C2 = 3+1+0 = 4.
Do let me know, if there exist a counter example.

[@joydeepdas4105]

In which colleges did it happen

[@sidharthdhiman4522]

bhaiya this policy based data structures include statement is not working on my vs code what should I do ?

[@Harisamsharma]

A quick hack is to use an online ide, for example codechef's ide

[@yogeshagarwal403]

@@Harisamsharma will these policy based data structures include statement works in online assessment tests?, like on hackerearth , hackerrank etc

[@Harisamsharma]

@@yogeshagarwal403 yes, they do.

[@VishalKumar-bx4rn]

There is a video by priyansh agarwal on ordered_set usme he will say how to fix that error check that video

[@sidharthdhiman4522]

@@VishalKumar-bx4rn i did the same thing but there is still issue , it gets terminated

[@ankushgupta2528]

In Problem 3, after buiding 'A', can't we use binary search to count?

[@jeevanalexen]

that is what I thought

[@Harisamsharma]

You can't sort the array, since we need to satisfy i

[@Mutant23]

can you provide dsu template

[@dennyage4791]

Bro which editor you are using in this video

[@Harisamsharma]

Sublime text

[@Live-hh6li]

Thanks
If you find more of such problems
Please post videos
They will be really helpful

[@naha_ne_ja_nahane]

Thanks

[@shivangupadhyay8002]

can you please provide link to that file

[@Harisamsharma]

Added in the description