Round Date Round Details

Coding June 2, On the basis of their application, shortlisted participants will be

Challenge 2023 invited for the first round - a coding round to test their coding
skills. Participants will have to take up a real-life challenge during
a specified time window. be provided a time window during which
you will be asked to take up this challenge at your convenience.
Both, your coding scores and resumes will be taken into
consideration at the end of the round.

Learning June Participants shortlisted from the coding round will be invited for an
Cohorts 10, immersive learning experience as part of the Learning Cohorts.
2023 Here, they’ll engage and learn with Googlers, while also working
on assignments that will be evaluated in this round.

Ideathon July 6, The finalists will put their knowledge into practice and ideate
2023 solutions for a themed problem statement. This round is divided
into two parts - in the first section, participants submit their code
repository. Based on the submissions, students will be shortlisted
for the final presentation round. The best solutions amongst the
lot will be judged by senior Google leaders.

ROUND 1- Google Online Challenge

Coding Round Questions (2022)

Problem-1 : Given a string consisting of '0' , '1' and '?' , find the longest substring of the
string which will have an equal number of zeroes and ones after replacing the question
marks. Maximum possible length of the input string is 1000..

Problem - 2 : For each index 'i' find the number of indices 'j' such that A[j]>A[i] &&
B[j]>B[i].Two arrays 'A' and 'B' of length at most 100000 are given in the input..

Coding Round Questions (2021)

Question1: The cost of a string

Your task is to create a string S considering lowercase English alphabets. You are given an
array A of size 26 where A[i] denotes the cost of using the ith Alphabet (consider 1-based
indexing). Find lexicographically the largest string S that can be created such that the cost of
building the string is exactly W. For example, ‘abc’ is lexicographically smaller than ‘abcd’.
Input format:

The first line contains an integer T denoting the number of test cases.
The first line of each test case contains 26 space-separated integers denoting the costs of
characters from ‘a’ to ‘z’.
The second line of each test case contains an integer W.
Output format: For each test case, print the required string S in a new line.

Sample input

1
1 1 2 33 4 6 9 7 36 12 58 32 28 994 22 255 47 69 558 544 21 36 48 85 48 58
236

Sample output

zzzze

Question 2 Harmonic sequence

You are given an array keys of N elements. Then there will be Q queries and in each query
you will be given an Integer X. You have to ans for each query in "Yes" or "No". It will be
"Yes" if you can find any element in keys such that its and with X equals 0 i.e
keys[i]&X==0 is satisfied else it will be "No".

Example input

3
123
5
1
2
3
4
5

Example output

Yes
Yes
No
Yes
Yes
Explanation

1&2=0
2&1=0
there is no element in keys whose and with 3 equals 0
4&1=0
5&2=0

Constraints
N<=1e5, Q<=1e5, keys[i]<=1e5, X<=1e5

Question 3 Distinct subsequences

You are given a string S of length N consisting of 0s and 1s only. Convert all its
subsequences into its decimal representation and return the number of distinct decimal
representations formed by its subsequences.

This question is similar to Distinct Subsequences II

Example input

3
110

Example output

Exaplanation

Subsequences having distinct decimal representations are 1,0,11,10,110 which corresponds

to 1,0,3,2,6 in decimal.

Constraints
N<=1e5

Question 4

You have designed a robot. The robot can move only left or right based on the given
instruction. The robot is initially at point 0 on the X-axis. You are given N pairs of instructions.
Each pair of instruction contains an integer and a character ('L' or 'R'). For example consider
an instruction (3,R), It means that robot has to move 3 units right from current position along
X-axis. You are allowed to perform the following Operation at most once. =>You can remove
any number of consecutive instructions but condition is that the number of left and right
instructions should be equal For example, You can remove (2,L)(3,R) or (2,L)(3,R)(7,R)(1,L)
But cant remove (1,L) or (2,R)(2,R)(4,L) You are required to find Maximum distance robot
can go from initial position 0.

1<=T<=10 1<=N<=1e5 0<=Di<=1e6 (Integer in the input instruction)

Input: T=1,N=5,instructions{(2,L)(3,R)(4,L)(1,R)(5,L)}. Output: 8. Explanation: Remove first

and second Instructions.

Question 5
Given an array of positive integers. The task is to find the size of the smallest subset such
that the Bitwise OR of that set is Maximum possible. (Google Online Challenge 2021)
Sample Input:
arr[] = {5, 1, 3, 4, 2}

Sample Output:
2

Explanation:
7 is the maximum value possible of OR, 5|2 = 7 and 5|3 = 7
Question 6
There are N words in a dictionary such that each word is of fixed length M and consists only
of lowercase English letters, that is (‘a’, ‘b’, ‘c’, ………’z’).
A query word is denoted by Q. The length of a query word is M. These words contain
lowercase English letters but at some places instead of a letter between ‘a’, ‘b’……’z’
there is ‘?’. Refer to the Sample Input section to understand this case.
A match count of Q, denoted by match_count(Q), is the count of words that are in
the dictionary and contain the same English letters(excluding a letter that can be in
the position of ‘?’) in the same position as the letters are there in the query word Q.
In other words, a word in the dictionary can contain any letters at the position of ‘?’
but the remaining alphabets must match with the query word.
You are given a query word Q and you have required to compute match_count.
(Google Online Challenge 2021)
Input format:

The first line contains two space-separated integers N and M denoting the number of
words in the dictionary and length of each word respectively
The next N lines contain one word each from the dictionary.
The next line contains an integer Q denoting the number of query words for which
you have to compute match_count,
The next Q lines contain one query word each.
Output format: For each query word print match_count for a specific word in a new
line.
 Constraints:
1<=N<=5 x 104
1<=M<=7
1<=q<=105

Sample Input:
5 3
cat
map
bat
man
pen
4
?at
ma?
?a?
??n

Sample Output:
2
2
4
2

Coding Round Questions (2020)

Question 1 : Count the number of N digit integer that are divisible by both X and Y.

Example : N = 2
X=5
Y=7

Output : 2

Explanation : The number of 2 digit integers that are divisible by both 5 and 7 is 2 (35 and
70).

Question 2 :
You are given a matrix of size N x N. Assign the letter 'a' an ID 1, 'b' an ID 2, and so on.
Here, A[i][j] denotes the value in cell(i,j) of matrix A denotes the cost of writing the letter
corresponding to ID j immediately after the letter corresponding to ID i.
Now, You are given a string S consisting of distinct lowercase alphabets and you have to
determine the minimum cost to generate any permutation of the given string.
Note: The cost of writing the first character is zero as no characters are present before the
first character.

Example : N=5

05153
40942
7 9 0 10 7
12802
39770

S = abcde

Output : 8

Explanation : The permutation dbeac can be generated at a minimum cost of 8 as :

- cost of writing d = 0
- cost of writing b after d = 2
- cost of writing e after b = 2
- cost of writing a after e = 3
- cost of writing c after a = 1

Total cost = 0+2+2+3+1 = 8