Google’s Online Challenge for 2021 Intern (India) Experience
I saw a job posting on Google’s career page so I applied for the Google internship but without any hope, as I am from a tier – 3 colleges. But after some days I got an email regarding the test link and other credentials.
So, let’s talk about the coding test.
The coding test was held on HackerEarth, it consists of 2 questions one was easy and the other one was a little tricky. We had 60 minutes to solve these questions. I solved both questions. So, the questions were like this:
Question 1: Unspecified Words
Problem Statement: 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.
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
Question 2: XOR query
Problem Statement: I didn’t remember the actual statement but it was something like we are given an array with a single element i.e 0 and after that, we have some queries which are of 2 types :
- Type 1: Insert the given element into the array
- Type 2: XOR all the elements present in the array with the given element.
Input format:
- An integer Q which represent the count of queries that are going to be asked
- Q lines having two integers n and m
- n represents the type of operation i.e 1 or 2
- m represents the element that will be used to do operation according to the given type of operation.
Output format: Print the final array after all the given queries in sorted order.
Constraints
1<=Q<=107 n = 1 or 2 1<=m<=109
Sample Input:
6 1 3 1 5 2 5 1 6 1 7 2 6
Sample Output:
0 0 1 6
It was such an amazing experience, now I am waiting for some good news.