Google | Intern | Hyderabad/Banglore [Offer]
On campus Internship Opportunity.
Status: Undergraduate, B Tech, Computer Science
Type: Coding Round, 2 Rounds of Interview.
Coding Round
Duration : 1 hour
Number of Problems: 2
First Task
Given a string S of length n, consisting of only '0's and '1's, count the number of distinct decimal subsequences that can be generated from the given string. Print answer with mod 1e9 + 7.
Example:
S = "011"
Result = 3
Distinct Decimal Subsequences = {"0","1","11"}
Expected Time Complexity : O(N)
Comments
It is a modification of a famous problem, Distinct Subsequences.
We need to take care of leading zeroes(which is the tricky part)
Second Task
Given a N x M matrix. We have to find the minimum cost path to reach the first column to last column.
A path is defined as P1,P2,......Pm(one cell in each column). Cost of a path if defined as Max(P1.....Pm) - Min(P1....Pm).
Interesting Points
I solved only 1 problem and got an interview call.
Google doesn't disclose their shortlisting criteria. One student solved both the problems and didn't get an interview call.
Your chance of getting an interview call depends on 3 criterias
* Coding Round Performance
* Resume
* GPA in college
Interview
Interview was conducted on Google Meet and we had to code on Google Docs (all standard stuff).
Duration: 45 minutes
First Round
I was given a problem and had to come up with an efficient solution and code it.
Problem Statement
Given a tree which consists of 2 types of nodes, type 'A' and type 'B'. We had to modify the tree according to 2 rules->
* Remove all type 'B' nodes
* Join all type 'A' nodes to the nearest parent/ancesstor of type 'A'.
* Root node is guranteed to be of type 'A'.
Expected Time Complexity : O(n)
More
I was asked to refactor my code.
Round was wrapped with a quick discussion on time and space complexity.
Shortly After the first round, I got a call for my second round, 5 minutes prior only.
Second Round
Interview was conducted on Google Meet and we had to code on Google Docs (all standard stuff).
Duration: 45 minutes
Problem Statement
Find maximum subarray sum in an array given the condition that the first and last elements of the subarray are equal.
Example
A= { 1,1,2,-1,-3,2,1,}
Result = [1,........1] = 3.
Expected Time Complexity : O(n)
More
I had to come up with some edge cases.
We had a discussion on testing of code after that(tougher part of the interview).
COMMENTS
The problems were doable if you are into Competitive Programming.
The 2nd interview was targeted to test my coding style and do I write readable code or not.
Both the interviewers were asking a lot of questions about testing of codes, devise test cases and come up with some edge cases.
Final Result
After 4-5 hours I was informed about my offer.