I started my inital journey for the interview in the month of January when I was approched by Google Recruiter (I applied through google carrer site). I gave Phone interview round and I was rejected at that paticular time since I just started practicing leetcode questions I wasn't prepared much.
Phone Screen Round:
Given an array of stock prices, find the size of the widest interval over which the stock has lost value. Lost value is defined as the initial value of the interval is larger than the final value of the interval. Intermediate values within the interval may rise above the initial value, but the interval would still be considered as lost value.
Example :
Time: 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16
Price: 50, 52, 58, 54, 57, 51, 55, 60, 62, 65, 68, 72, 62, 61, 59, 63, 72
Ans - 7
Explanation - the widest interval with a net loss in value is from the indices 07 to 14 and has length 14 - 7 = 7
Although a peak value of 72 at time index 11 is present in this interval, it is still considered an interval with loss value.
As I already had solved stock span problem I knew that problem is similar to that and I need to change the if conditions but I didnt had enough time to come up with proper aproach and the interviewer was not giving any kind of hints either and was just making me nervous. So in final I just wrote my brute force aproach which I know was not enough.
Result: Rejected
After 6 moths I contacted the recruiter again asking if I can reaaply and the recruiter gave me green flag.And this time I have prepared extensively.
Phone Screen Round:
Given string "add(1,mul(2,pow(3,3)))" evaluate the final ans.
It was basic calculator programme. I solved it using two stacks and using isAlpha and IsDigit function. The follow up question was what if we had floating numbers or exponential how would we solve it ? We ran of time and I was not able to solve the follow up question.
The interviewer was nice and gave hints whenever I was stuck. He had more than decade of experience and shared lot of insight of working in google.It was nice and fun conversation overall.
Result : Positive(Hire). The recruiter scheduled the next rounds after a month .
Round 1 (DSA round):
Imagine you are given a stream of non-negative integers, until you receive a zero and in that case you need to print a number from the stream with the distribution of the numbers in the stream.
i.e: [1,2,3,1,1,3,0] will have the probabilities array [0.5, 1/6, 2/6] and we have to pick a random number from that.
I already saw this question somwhere and I though about binary search solution but interviewer gave me the hint that no matter what algo u use the probabilty wont change so no need to design any fancy algo.
I was confused and told them to use random function which was correct ans. But since we had internet issues I was not really confident about my ans and this is when instead of having my head in the interview I was really woried about my answer and thought it is over for me so I panicked the entire interview plus the internet connection loss didnt help. After that interviewer asked me regarding the time complexity for each line of code and since I used map to store number i said logn which was wrong since ordered map has O(n) time complexity and I was not able to answer time complexity for erase function in vector too.The interviewer was not that friendly and the bad internet connection from his side didnt help either not his fault though as even I messed up.
Result: Not Hire
Round 2 (DSA round):
Consider a bank with some intial amount of money. Consider an array which represents list of transactions which are going to come through customers. + means deposit - means withdrawl. Bank can choose from which customer they want to start serving the customers and they can refuse any number of customers. But once they start they have to serve till the time its impossible to serve the customers. Maximize the total customers bank can serve.
Example :
Bank has 1 unit of money intially.
Customer transactions : [1, -3, 5, -2, 1]
answer = 3
Bank starts with customer with deposit of 5
1+ 5 = 6
6 - 2 = 4
4 + 1 =5
I was able to come up with the brute force approach and the interviewer approved the approach and told me to come up with optimal approach I came up with the sliding window approach but we were short of time and i was not able to give proper if statement condition again here I messed up because instead of being cool and calmm and focusing my entire energy on solving the problem in front of me I was more focussed on time running out which made me lot of silly mistakes.This time interviewer was friendly and did provide good hints whenver necessary.
Result: Lean hire
Round 3(DSA Round):
Given a tree having nodes with value 0 and 1. write a function to return the number of islands ?
An island of 1 is defined as a group of ones surrounded by zeroes or are at the boundary of the tree.
Given the root of such a binary tree, return the number of islands of one.
Example:
0
/ \
1 0
/ \ / \
1 1 1 1This tree has 3 islands of 1
I went with initial assumption that it is binary tree and I came up with the solution and the interviewer asked me to explain the code which I did and found few mistakes which I corrected .The entire time the interviewer was not communicating much not even telling me that my proposed solution does not pass every test case so i need to change the base condition which would have helped. I think this time the biggest poitive thing for me was that this time I was focussed on solving the problem without fear of being right or wrong .
Result: Not hire
The recruiter cancelled the managerial round since I need at least two hire out of three coding round.The cooling period is one year so the recruiter asked me to reapply again in a year.I was devastated by the result since I poured so much of my time for the preparation and i know of my shortcomings but it doesnt make me feel any better either. I felt like a complete failure and I know this feeling shall pass but it hurts.
Few tips if you are interviewing for google:
- Please brush up the basics of the data structures before the interview and make sure you understand the underlying data structuures used.
- Make sure you go to leetcode discuss and check out the questions asked in last 6 to 7 months .This were all repeated questions.
- Dont overcomplicate the problems ,stick to your basics
- Always come up with the Brute force approach first if you dont know the optimal aproach if you know the bute force chances are interviewer might help you with optimal.
- Dont focus on solving too many problems in leetcode instead focus on solving problems own your own that is the biggest practice you need.
Hope this post helps!!!