Original Leetcode link:
Preparation :
I started doing leetcode in late July and did them daily, religiously without a break even when I was very tired. Never missed a day since 3rd Sep(except one)
This has been my main source of studying for coding question. I also took help of youtube to understand complex algorithms like Tarjan, DP. I still suck at DP and union find. I can’t solve most hard questions but I can solve most of the medium ones unless they are DP questions.
When I started I had very little knowledge of how to apply data structures like heaps, hash maps and algorithms like backtracking, memorization, recursion to solve the problems. Used to be bad in dealing with trees too. Had no idea about sliding window approach so yeah clueless about so many things.
But as days passed on I gained more knowledge everyday. Constant practice made my skills sharp. The first contest I gave, I did 2 questions the next one all 4(hard one was actually a medium in this) and 3 questions in every contest since. (They happen very early morning at my place so I give virtual contests later if I am not up).
This has been my main source of studying for coding question. I also took help of youtube to understand complex algorithms like Tarjan, DP. I still suck at DP and union find. I can’t solve most hard questions but I can solve most of the medium ones unless they are DP questions.
When I started I had very little knowledge of how to apply data structures like heaps, hash maps and algorithms like backtracking, memorization, recursion to solve the problems. Used to be bad in dealing with trees too. Had no idea about sliding window approach so yeah clueless about so many things.
But as days passed on I gained more knowledge everyday. Constant practice made my skills sharp. The first contest I gave, I did 2 questions the next one all 4(hard one was actually a medium in this) and 3 questions in every contest since. (They happen very early morning at my place so I give virtual contests later if I am not up).
I started with trying to do 3 questions/day but as days went by it took me less time to solve them so I increased the count and on weekends I used to do more than usual. Consistency is the key here + I actually like doing these problems Which made it easy to not loose the way. I also bought leetcode premium for an year just 2 days before my phone screen to do google specific questions and filter out good questions from the bad ones.
Interview experience:
Phone screen (Mid oct):
I was at around 200 mark on leetcode during my phone screen. It was quite simple binary tree based question which I solved fairly quickly as I was told by my recruiter that there will be two questions in this round. But there was no follow up or second question. We just had discussions on what test cases will I test it on and how will I check the validity of my answer. I wasn’t sure if I understood him correctly on checking validity and told him whatever came to my mind. Then he asked if I have any questions and I discussed about his work.
I was at around 200 mark on leetcode during my phone screen. It was quite simple binary tree based question which I solved fairly quickly as I was told by my recruiter that there will be two questions in this round. But there was no follow up or second question. We just had discussions on what test cases will I test it on and how will I check the validity of my answer. I wasn’t sure if I understood him correctly on checking validity and told him whatever came to my mind. Then he asked if I have any questions and I discussed about his work.
The recruiter followed up and said the feedback was quite positive and I will move to onsite. There will be 4 technical and 1 behavioural round and 2 coding questions per round in technical rounds. No design round. I was a bit relieved coz design is where I suck. Also since my home is quite near the google office my rounds were split into 3+2 to be held on 2 days.
Onsite day 1(mid nov):
Round 1(Technical): Went okay. I was asked two questions.
Fairly easy queue based question. Although it was easy it was tricky because there were some edge cases I had to identify and come up with a solution. I explained every step of my thinking process along with how I am iterating and moving towards a perfect solution and coded it. I took more time to solve this as I was super nervous and was over explaining things.
A hard dp based question doable in O(n^2) for which I gave a non-dp O(n^3) solution and coded it. I did explain what I am doing perfectly to my interviewer though and he didn’t ask me for optimisation. I realised several days after the interview that it could have been done in O(n^2)
Round 1(Technical): Went okay. I was asked two questions.
Fairly easy queue based question. Although it was easy it was tricky because there were some edge cases I had to identify and come up with a solution. I explained every step of my thinking process along with how I am iterating and moving towards a perfect solution and coded it. I took more time to solve this as I was super nervous and was over explaining things.
A hard dp based question doable in O(n^2) for which I gave a non-dp O(n^3) solution and coded it. I did explain what I am doing perfectly to my interviewer though and he didn’t ask me for optimisation. I realised several days after the interview that it could have been done in O(n^2)
Round 2(Technical): Was probably the worst out of the 4
Fairly easy string based question which I explained and coded well but took more Time as I was extra cautious and nervous.
Medium level follow up of question 1 for which I explained a Trie based approach but couldn’t code it properly (probably the biggest red flag I gave)
Fairly easy string based question which I explained and coded well but took more Time as I was extra cautious and nervous.
Medium level follow up of question 1 for which I explained a Trie based approach but couldn’t code it properly (probably the biggest red flag I gave)
Round 3(Behavioral): Meh. Nothing much to talk about this. I don’t think I did good but my recruiter had told not to worry about behavioural rounds.
I was disappointed due to my round 2 performance and thought this will be it. My recruiter followed up and I told him the same. That I don’t think the second round went very well. He said he will check the feedback and then schedule the future rounds. But the following day he told me the feedback was quite positive although there are some concerns but we can go ahead with next rounds however I need to nail the next two rounds and not leave room for any imperfection.
Onsite day 2(end of nov):
I don’t know why but only 1 question per round was asked in these rounds. I didn’t know this in advance.
I don’t know why but only 1 question per round was asked in these rounds. I didn’t know this in advance.
Round 4(Technical): Went perfect
Medium level question which could have been done in more than one way. I did it using heaps. She wasn’t convinced if my approach will work and gave me some test cases on which it worked fine so she was fine with it and told me to code. I wrote a code which she went through and didn’t find any errors. We had some time left as I was expecting another question. But this was it. The interviewer asked me if I have any questions for her and we had a fair length of discussion about her work
Medium level question which could have been done in more than one way. I did it using heaps. She wasn’t convinced if my approach will work and gave me some test cases on which it worked fine so she was fine with it and told me to code. I wrote a code which she went through and didn’t find any errors. We had some time left as I was expecting another question. But this was it. The interviewer asked me if I have any questions for her and we had a fair length of discussion about her work
Round 5(Technical): Went good (maybe)
It was a tricky interview for me. In the start the interviewer told me we will begin with a simple question and gave me a question on counting number of subsequences satisfying a particular property from a given array. I didn’t find it easy at all and started telling my thoughts and approach. First O(n^2) using suboptimal data structure and then an optimal O(n) approach by using the optimal data structure. It took me quite some time to arrive at the final solution and I had very less time left to code. I was so nervous as I knew my chances are 0 if I don’t finish this code now so I wrote it at a speed like never before. After writing I realised I could have made some optimisations in my code but I told my interviewer about those and that if I had more time I’d have done these changes. He went through my code and didn’t find any bugs. We finished just on time. But I wasn't sure if I was too slow and he had follow ups or second question in mind which he never got to ask because of this or this was the only question. asked him if the round was supposed to have two questions to which he just polietly smiled and said nothing like that.
It was a tricky interview for me. In the start the interviewer told me we will begin with a simple question and gave me a question on counting number of subsequences satisfying a particular property from a given array. I didn’t find it easy at all and started telling my thoughts and approach. First O(n^2) using suboptimal data structure and then an optimal O(n) approach by using the optimal data structure. It took me quite some time to arrive at the final solution and I had very less time left to code. I was so nervous as I knew my chances are 0 if I don’t finish this code now so I wrote it at a speed like never before. After writing I realised I could have made some optimisations in my code but I told my interviewer about those and that if I had more time I’d have done these changes. He went through my code and didn’t find any bugs. We finished just on time. But I wasn't sure if I was too slow and he had follow ups or second question in mind which he never got to ask because of this or this was the only question. asked him if the round was supposed to have two questions to which he just polietly smiled and said nothing like that.
Post interview:
I guess my feedback was mixed due to which I went through team matching first and then passed HC with the support of my HM. The recruiter had been a big help throughout and was very transparent and kept me updated about every step and built a strong case for me. He mailed me my result as soon as the HC was over and I felt so lucky to have made it through. I was 50% sure I won’t get the offer.
Interview Guide & Tips:
Which resources do I study from?
Note: If you don't know CS fundamentals and basics at all take courses to get familiar with all the data structures and well known algos first. I knew these in theory due to my academic background.
I actually was pretty confused about this and for a painfully long time and I've studied from the wrong sources and wasted a lot of time. I fortunately got hooked on the LC this time. I believe that LC is a pretty great resource itself if you use it well. But the only problem is that it is hard to find an effective list of questions you should do here.
Apart from LC, I liked EPI quite a lot but I came to know about it much later and most of the questions in it were done by me already so I just continued on LC. However I did have plans to go through specific topics in EPI which I am not good at like DP. Maybe I'll still do it sometime.
Interview bit is quite good too and the timer there helps increase speed. I did some problems there after day 1st of my onsites when I saw that time is proving to be an issue. Also things are split into topics there which is good but I don't think it covers that much breath. You'll ultimately have to come to LC. I also feel it comes down to individual preferences.
I find questions on leetcode to be quite simplistic and that is not all LC offers, even the interview posts by others keeps you motivated and updated about what companies are asking currently. Most days I start by just opening LC and read some of these posts if I don't feel like solving any problem. Reading these posts give me motivation and even some new questions to try.
To being with there is top interview questions, top 100 liked questions list which are good to begin with. If you'll do just these you'll be good to do for amazon and other not so hard companies(amazon is hard but not due to coding part, due to system design and LP in my opinion).
Barring google interviews, 50-70% of the coding questions I faced in every interview towards the end of my prep were already seen problems verbatim. Even some google interview problems were variations of LC problems or just worded differently.
Hackerrank has many questions which are not useful for our purpose. I am not a very big fan of competitive programming kind of questions and neither do companies ask them. It also has code autocomplete feature which is a no no. I also don't like writing scanner class just to take input for every question I do there.
The key is definitely consistency and the amount of problems you solve provided you learn and understand every problem you solve.
Whenever I come across any question I don't understand I see the solution and solve it the next day to know if my brain has retained the info and weed out the devil which is in the details. There are some questions which I don't understand even after seeing solutions. I head to youtube, channels like back to back SWE for them and if I still don't understand or find a better explanation I just put them on my future list to revisit on a later date.
Time Needed?
About time, it varies what is an ideal time from person to person. People who have been doing these questions from a long time casually or people who did competitive programming in the past will definitely need less time to recall and revise everything(Wasn't the case with me). But its ideal if you have long time to prepare(by your standards) because nothing can make up for the lack of time. You can optimize and prioritize but mind can only absorb and retain so much info in a day, it is definitely possible to cut down time needed to prepare though by optimizing and going through only most probable topics and rely on luck to be through.
EPI has different list of questions to do given the time you have left. So maybe do that.
About time, it varies what is an ideal time from person to person. People who have been doing these questions from a long time casually or people who did competitive programming in the past will definitely need less time to recall and revise everything(Wasn't the case with me). But its ideal if you have long time to prepare(by your standards) because nothing can make up for the lack of time. You can optimize and prioritize but mind can only absorb and retain so much info in a day, it is definitely possible to cut down time needed to prepare though by optimizing and going through only most probable topics and rely on luck to be through.
EPI has different list of questions to do given the time you have left. So maybe do that.
Some helpful tips/material provided by my recruiter:
When you practice, do not use an IDE. You need to be able to write legible, compilable code without help with regards to layout, or spelling of standard library class/method names. I suggest solving similar style algorithmic/ DS problems on a google document or on paper to simulate a real interview.
When you practice, do not use an IDE. You need to be able to write legible, compilable code without help with regards to layout, or spelling of standard library class/method names. I suggest solving similar style algorithmic/ DS problems on a google document or on paper to simulate a real interview.
Technical Preparation tips:
Understand Google Interview process:
- https://www.youtube.com/watch?v=IWIi3C8Md_E
- https://www.youtube.com/watch?v=ko-KkSmp-Lk
- https://www.youtube.com/watch?v=oWbUtlUhwa8
- https://www.youtube.com/watch?v=XKu_SEDAykw&feature=em-subs_digest
- https://www.youtube.com/watch?v=XOtrOSatBoY&t=1s
The main areas software engineers should prepare to succeed at interview at Google:
Algorithm Complexity: It's fairly critical that you understand big-O complexity analysis. Again run some practice problems to get this down in application. See https://www.bigocheatsheet.com/
If you get a chance, try to study up on fancier algorithms, such as Dijkstra and A*.
Sorting: Know how to sort. Don't do bubble-sort. You should know the details of at least one n*log(n) sorting algorithm, preferably two (say, quicksort and merge sort). Merge sort can be highly useful in situations where quicksort is impractical, so take a look at it.
Hashtables: Arguably the single most important data structure known to mankind. You absolutely should know how they work. Be able to implement one using only arrays in your favorite language, in about the space of one interview.
Trees: Know about trees; basic tree construction, traversal and manipulation algorithms. Familiarize yourself with binary trees, n-ary trees, and trie-trees. Be familiar with at least one type of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree, and know how it's implemented. Understand tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder.
Graphs: Graphs are really important at Google. There are 3 basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list); familiarize yourself with each representation and its pros & cons. You should know the basic graph traversal algorithms: breadth-first search and depth-first search. Know their computational complexity, their tradeoffs, and how to implement them in real code.
Other data structures: You should study up on as many other data structures and algorithms as possible. You should especially know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise. Find out what NP-complete means.
Mathematics: Some interviewers ask basic discrete math questions.This is more prevalent at Google than at other companies because we are surrounded by counting problems, probability problems, and other Discrete Math 101 situations. Spend some time before the interview refreshing your memory on (or teaching yourself) the essentials of combinatorics and probability. You should be familiar with n-choose-k problems and their ilk – the more the better.
Operating Systems: Know about processes, threads and concurrency issues. Know about locks and mutexes and semaphores and monitors and how they work. Know about deadlock and livelock and how to avoid them. Know what resources a processes needs, and a thread needs, and how context switching works, and how it's initiated by the operating system and underlying hardware. Know a little about scheduling. The world is rapidly moving towards multi-core, so know the fundamentals of "modern" concurrency constructs.
Coding: You should know at least one programming language really well. You will be expected to write some code in at least some of your interviews. You will be expected to know a fair amount of detail about your favorite programming language.
Sample Topics:
Coding: Sample topics: construct / traverse data structures, implement system routines, distill large data sets to single values, transform one data set to another.
Algorithm Design / Analysis: Sample topics: big-O analysis, sorting and hashing, handling obscenely large amounts of data, elegance and efficiency, decompose large problems and solve parts. Also see topics listed under 'Coding'.
System Design: Sample topics: features sets, interfaces, class hierarchies, designing a system under certain constraints, simplicity and robustness, tradeoffs.
Development Practices: Sample topics: validating designs, testing whiteboard code, preventing bugs, code maintainability and readability, refactor/review sample code.
Open-Ended Discussion / Role Related Knowledge: Sample topics: biggest challenges faced, best/worst designs seen, performance analysis and optimization, testing, ideas for improving existing products.
PS/DS: (Some questions will be repetitive across these links. Study in the order mentioned below)
https://www.interviewbit.com/search/?q=Microsoft (Not so imp)
How to know if you are ready?
You will be coding on a Google Doc for the phone interview.
Interview topics may cover anything on your resume (especially if you have stated that you are an expert!), whiteboard coding questions, building and developing complex algorithms and analyzing their performance characteristics, logic problems, systems design and core computer science principles - hash tables, stacks, arrays, etc. Computer Science fundamentals are prerequisite for all engineering roles at Google, regardless of seniority, due to the complexities and the global scale of the projects you would be participating in as a Googler.
You will be coding on a Google Doc for the phone interview.
Interview topics may cover anything on your resume (especially if you have stated that you are an expert!), whiteboard coding questions, building and developing complex algorithms and analyzing their performance characteristics, logic problems, systems design and core computer science principles - hash tables, stacks, arrays, etc. Computer Science fundamentals are prerequisite for all engineering roles at Google, regardless of seniority, due to the complexities and the global scale of the projects you would be participating in as a Googler.
Do you feel confident with CS fundamentals?
Do you know what to ask to clarify the questions?
Can you find the optimal solution of the complicated coding/algorithm problems, present it in a very efficient/clean coding (no/less bug), and share your thoughts logically?
Is your problem solving and coding speedy and efficient with your profound knowledge in CS fundamentals?
Do you know what to ask to clarify the questions?
Can you find the optimal solution of the complicated coding/algorithm problems, present it in a very efficient/clean coding (no/less bug), and share your thoughts logically?
Is your problem solving and coding speedy and efficient with your profound knowledge in CS fundamentals?
No comments:
Post a Comment