I had started off with a small amount of competitive programming in the Summer break of my 1st year ( Summer of 2017 ) however, I did not really do a lot at that time.
Just the basic knows and hows of the CP world. During my 3rd Semester (Autumn of 2017 ), I had my Algorithms Course (CS21003) and my Algorithms Lab (CS29003) which helped me get a basic implementation level detail of the different basic Data structures:- Heaps, Dictionaries, Binary Trees ( BST, AVL ), and Graphs as well as the Algorithmic Paradigms of Divide and Conquer, Greedy and Dynamic Programming, Linear Time Sorting, Graph Algorithms, and String Matching.
I had also done Naveen Garg’s NPTEL Course on Data Structures and Algorithms so I had knowledge of Red-Black Trees as well.
All this going with the previous knowledge of Arrays, Strings, Stacks, Queues, Linked Lists, Sorting and other PDS Topics.
The intensive theory course kept me in touch with Algorithms and the course kept me in touch with the practical implementation so I had a good foundation to delve into Competitive Programming come the Winter Break (December of 2017 ).
The Introduction to Algorithms Book by CLRS is perhaps the best book for beginners and I believe anyone who wants a firm grasp on these concepts should supplement their learning with the material in this book’s chapters and definitely solve the In-Chapter Exercises as well as the Problems at the end of each chapter. The solutions by Rutgers can also be found online, they are pretty good.
So in December, I started an out and out competitive regime by first getting myself familiar with the Standard Template Library of C++14. Vectors, Strings, Sets, Multisets, Maps, Priority Queues, Stacks, Queues are some of the basic containers that are required. http://www.cplusplus.com was very helpful for this purpose. I then started off implementing the Algorithms taught in class on practice problems using the STL containers on CodeMonks, HackerEarth. I did solve the Codechef and Codeforces contests parallel to this learning process and then used to refer to the editorials after I was done solving/trying on the problems. I did not do much CP during the 4th Semester (Spring of 2018) but delved back into the groove during the Summer Break (May — July 2018). I brushed up my past knowledge and then started off with solving InterviewBit.
The point with InterviewBit and similar interview specific coding platforms is that the questions cover a vast horizontal area, but the vertical depth depends on how you tackle these questions. I used to solve each question in as many ways as I could and then look at the Editorial Solutions, get inspired and then solve it in their way on my own as well. I solved my CLRS again during this time along with Data Structures and Algorithms Made Easy — Narasimha Karumanchi and also read along TopCoder Tutorials on Relevant Topics. Codechef and Codeforces Contests still went hand in hand with this.
The Coding Rounds
I appeared for the Coding Rounds of Nutanix, DEShaw, Goldman Sachs, Rubrik, UBER, and Microsoft. I had also given the Google Kickstart D which is an informal coding round for Google but did not perform well in that. Also, these tests start one week before the actual Day1, something which I did not know so just throwing it out there, and take place on a HackerRank IDE so one might want to make themselves familiar with it.
Nutanix — There were two questions: 1 hour, the first one a fairly simple implementation problem but the second one was a problematic question. The constraints for the second one permitted at most an O(NlogN) solution which would involve Segment Trees — Range Minimum Queries, however, the Online Judge was accepting the O(N*N) solutions. Weak test cases.
DEShaw — Two questions again: 1 hour, the first one a fairly straightforward and the second one involving some rolling implementation of hashing on strings using MAPS.
Goldman Sachs — 2 hours; One coding question which needed some work to be done to reduce the question into a Longest Increasing Subsequence question which was accepting an O(N*N) solution — fairly simple if it strikes. The rest were some MCQs on Prob Stats.
Rubrik — 2 hours : 3 Coding questions and 5 MCQs. Beautiful questions. The MCQs were testing basic Order Statistics Knowledge and the 3 questions finally had some amount of coding required. The 1st one was a Binary Search problem similar to the AGGRCOW on SPOJ. The 2nd one needed an implementation of a data structure with some given operations and their respective time constraints: a simple solution using SETS and MAPS in tandem. The 3rd one was a combinatorics problem which had an O(1) direct formula and also an O(N) implementation. Needed some knowledge of Modular Exponentiation.
Uber — Best Exam, beautiful questions. 3 questions: 1:45 hrs which were later extended to 2:00 hrs so please do not leave the exam hall if you are not done.
The 1st question had some BFS implementation, the 2nd one had a topological sorting base which could be done either by the DFS way or the InDegree way. The 3rd one was, thinking about it a fairly simple observation problem though the question statement could be clearer. Needed to implement using Modular Exponentiation again.
Microsoft — Worst exam. The CoCubes IDE which Microsoft conducts its tests on is very bad, hard to debug the code and difficult to manoeuvre. There were 3 questions A, B and C and to prevent cheating they had a pool of questions for A, B and C and they chose 3 questions randomly generating multiple sets of questions. It was impossible to maintain the same standard of questions and the terrible IDE added to the woes. The first question was a PDS level problem, the rest of the questions had simple to difficult implementations of Linked Lists, Arrays and Strings. The disappointment was mostly because Microsoft is the only one where the coding round has questions on Linked Lists, and I was really good in Linked Lists manipulations. But sadly my set had none and both the people sitting beside me had got questions which I had solved earlier.
DAY 1 Early Morning
The Day1 interviews start early at around 7 am and we need to report by 6 am so need to get up at around 5 am and the results come out by around 3–4 am. So the best thing that can be done is to go off to sleep ASAP on the previous night and get up at around 4:30 am to check the status of your shortlisting. This is something important because I ended up not sleeping the whole day before my massive interview rounds. If you are selected in multiple companies you would get a call anyway so I was awakened as soon as I had fallen asleep. The call basically is for you to give your priority list for the companies you are selected in and you would sit for their interviews in that particular order. So you need to be sure of your preference order, whether you get selected or not is a different issue, you should be ready with your order at all points.
So I made to Nalanda in my Suit at 6 am and the room we were sitting in was stuffy without AC, and a 3 piece suit and tie weren’t helping my cause, neither was the overpacked room, remember I had not slept as well.
So I was called by Rubrik at around 7 am to NR200 corridor and we were made to sit in one of the bigger rooms. The interviews took place in the order of the performance in the coding rounds and so I was called in the first lot (I mention this because only the first three were given offers). I think there were two sets of interviews going on simultaneously. I entered one of the smaller NR200 rooms for my first interview.
RUBRIK: The Interview Rounds
Round1: There was a brief conversation between me and my fairly young interviewer and he was pretty cool and breezy about the process which made me relaxed. I asked him if I could take off my coat and he was like “ C’mon man I am wearing T-Shirts and Jeans, you don’t need to ask me! ” So the air around was pretty chill and after a brief introduction we started off with the problem statement.
It was basically another Data Structure Implementation problem whereby I was given the kind of records I would be needed to store, the operations I needed to perform and their desired Time Complexities. So the problem at the onset looked fairly challenging but I did not lose my head and kept on speaking and conveying whatever I was Understanding about the problem. I initially came up with a wrong solution to which he provided a counterexample fairly quick ( it wasn’t that trivial an error, but that meant they had really good preparation ), but that did not bog me down and kept going and came up with the correct algorithm. After explaining the algorithm to him I was then asked to code it up on paper.
I started off the coding on paper. The one thing that I had in my favour is that I code in a fairly organised and modular manner. My codes are neat, the spacing is ample, variable names are descriptive and I generally do use camelCase.A few things which make one’s code Industry Ready I believe. So I did not really have to keep these things in mind but I went on to just code my Algo.
I did not realise it but I did end up coding an AVL( or RB ) Tree Insertion and Deletion along with the rotation specifications as well.
The interviewer was fairly impressed and the interview ended with me fairly pleased with myself as I did believe I had performed well.
The interviewer was pretty jolly so his smiles didn’t reveal much. These were some intense 45 minutes and I was left for a break of 15 odd minutes.
Round2: The second interview started after the break and even this interviewer was as chill and breezy about the whole process as the first one. So he made me introduce myself and I extended the chat by telling him more about myself than my CV reveals. After some informal chit-chat, we delved into the problem statement.
The problem statement was of a similar line, in which I was given the kind of records I’ll be having and the operations I need to perform and the expected time complexities of these operations.
This time I got the Algorithm fairly quickly because it was similar to something which I had solved some days earlier during one of the Facebook Hacker Cups. It was a Disjoint Set Implementation using Trees ( the ones we use in Kruskal’s MST ).
So I coded that up fairly quickly and went on to explain the code to him. I had added a variation to the typical implementation which would decrease the time complexity further, and I went on to explain to him that for the rest of the time.
He was a little unconvinced about the improvement of the worst case but I stuck to my word. In the end, he told that my Solution was good enough but he had thought of a different solution which involved Graphs and Connected Components. Another 45 minutes of interviewing ended and I came back to my waiting room.
Waiting: I was made to wait for about an hour or so for the 3rd round. The officials around were easing into conversation with me which was positive enforcement that they were interested in me.
After an hour or so I was called into one of the NC 240 rooms for the 3rd round.
Round3: This was not a technical round, it was more of an HR round. I was grilled on my CV and asked why I didn’t want to go for research given my CGPA. He asked me to explain all the projects on my CV and even told me to explain how I went about developing the final product. I kind of realised he was trying to put me in a spot of bother by pointing out possible implementation flaws and weak functionalities but I stood my ground and answered calmly. He further asked me about how they would benefit from me in their team and what my approach would be to their work and similar questions. My approach to certain scenarios and my way of working was something, he said, more suited to an established company than an upcoming growing start-up. So that put me out a little on the back foot but I kept on going strong and firmly sticking to my opinion. He gave me some low-key product management and software engineering questions about how I could possibly make the product better given a set of circumstances to tackle. After an hour or so of chit-chat on varied topics, his questions wrapped up and he opened up to my questions. I asked about why they don’t send interns to the United States and he told why they prefer Interns to stay in India but they would not say no if I wanted to.
I declined that I was ok with Bengaluru, though I had some second thoughts about this later I think it was a better choice for me for personal reasons. He had assured me that the learning experience would be exactly the same so that wasn’t really a loss, but the opportunity to go to Silicon Valley was enticing.
All in all this interview went on for an hour and by the noon of Day 1 I was assured of a Rubrik intern and didn’t have to sit for the rest of the interviews that day.
Keep calm and have a level head. Believe in your skills and keep on conveying your thoughts so that there aren’t long phases of silence. Have a pleasant expression throughout the process and maintain your body posture and demeanour to be perfect during the interview.
Competitive Coding Remarks
My aim was not solely the interviews so my preparation was a little more rigorous, which is why I didn’t really read through Geeks for Geeks as such. I believe if I had continued CP in the 4th semester I may have had a good chance for Google as well. So it’s not late to start, the Spring Semester is enough time to get a good grip on CP, and then you have the whole summer break to prepare. SPOJ and A2OJ are two other sites which might interest you. LeetCode helps as well.
You can find some of my Competitive Codes here on GitHub, and an algorithmic resource base which I have created over the past few years can be found here.