CDC Internship Diaries

Hello readers. I am Kshitij Agrawal, a 3rd-year B.Tech student from the Dept. of Electronics and Electrical Communication Engineering. I will be interning at Microsoft IDC in summers 2020. This blog covers my preparation methods and aims at giving the readers a first-hand impression of how CDC Internships work.

Background

I initially came to know about Competitive Programming from some of my friends during the start of my 2nd semester. As I had done the PDS course, I decided to try it just for some fun. However, during the 2nd semester, I just solved some PDS level problems on platforms like CodeChef and Hackerrank. Also, after successfully wasting my first-year summer vacations, trying out hand at several things, I finally settled for learning Data Structures and Algorithms thoroughly. So, I started with learning DSA probably in the mid of my 3rd semester. I quite quickly got a knack of it and started afresh with Competitive Programming. I was unaware of Codeforces for a long time and hence relied mainly on SpOJ and CodeChef for practice. However, I was not much serious about Competitive Programming even then and just casually participated in contests without much of upsolving, until I took the Algorithms course in the following semester.

The Algorithms course required me to practice a lot to ace the lab assignments and this was one of the phases where I started doing CP quite sincerely. Along with this, I participated in InterHall OpenSoft Competition, during which I learned a lot of cool Open Source practices and contributed to a nice project, which proved to be one of the major points of discussion in the interviews.

During the 2nd year Summer Break, I focused solely on improving my problem-solving skills, solved a large number of problems on Codeforces and gave a lot of timed contests (there is a feature of Virtual Contests in Codeforces, in case you don’t know). Initially, I had thoughts of trying for an internship in the break but later decided not to go for it as I could not have managed interview preparation along with an intern. The decision proved to be correct as I found a lot of mistakes and loopholes in my preparation while practicing.

Later during June, I started with InterviewBit. I mainly focused on problems on Linked Lists, DP and Trees (Traversals and properties of BST), as problems standard problems related to them must be known thoroughly. In the meantime, I still kept doing problems on Codeforces (as the difficulty level of problems in Coding Rounds are comparable to CF Div 2 Rounds). Interviewbit problems are easy if you have done Codeforces well. Along with Interviewbit I also went through a lot of topics and past interview problems on GeeksForGeeks.

Coding Rounds

The coding rounds for all Day 1 and Day 2 companies (Except Google, it selects through performance in KickStart and probably your CV), start approximately a week before the actual Day 1 and 2 interviews. I sat the for coding rounds of all Day 1 companies, and after a long series of ups and downs in the tests, I was shortlisted for the interviews of Google, Nutanix, Microsoft, Goldman Sachs, Tower Research Capital and DE Shaw (This was my preference list for the interviews).

I had participated in Google KickStart Rounds A, B, and C and had the best rank of 235 (Round B)(and ranks 488 and 484 (Round A & C)) which along with other selection parameters (like CGPA and Resume) proved sufficient for an interview call.

Briefly recalling from the Coding Rounds of all the companies, here is all that I could recollect.

Tower Research Capital: 1 Question (MCQ) on OS along with some other MCQs. 3 questions testing your debugging skills. 1 easy CP problem (very easy if you know STL) and 1 Hard problem involving graphs.

DE Shaw : [2 problems] Routine CP problems. The key to clear this round was a quick understanding of the problem and implementing correctly as the time allotted was quite lesser than other rounds.

Nutanix : [2 problems] Brilliant exam. Very nice and questions. One was a Codeforces problem (which I later came to know) and another problem based on trees and graphs. The difficulty level was such that I qualified for the next round having just partially done both of them. The second round before the interview was a pen & paper based Debugging round, where we were given a code with a lot of errors, which had to be identified and replaced with the correct code.

Uber : [3 problems] One of the best problem sets I have ever seen. This was the test I targeted the most but sadly screwed up very badly due to a lot of over expectations and overconfidence.

Microsoft : [3 problems] All tests apart from this were held on Hackerrank. Microsoft had its own platform, that took a good amount of time to understand. Writing code wasn’t easy and if you are used to environments like Hackerrank, you are going to need a good amount of work to get things going. Also, the problems for everyone aren’t the same as in other rounds. They are picked randomly from a large set of problems. So it’s quite luck-based to get an easy problem set. Mine had one implementation problem (had to take care of a lot of edge cases), and two simple greedy problems. This test was followed by a Written round on the night before the interviews. Everyone was given two problems and had to write code for it in any language of their choice. One was based on merging two BSTs and performing queries on the new tree and the second was a simple DP problem, however, the language of the problem was unclear. Hence it was necessary to communicate with the interviewers, ask questions and tell them your solution before writing it down.

Goldman Sachs : [3 problems + MCQs] 2 coding questions were easy to do. The third was probably a variant of the Travelling Salesman Problem, but the constraints were probably misleading. Apart from this, there were around 10 MCQs on PDS type problems (Linked lists, stacks, Time complexity Analysis) and 10 (maybe 15) MCQs were on Quantitative Aptitude. However, doing one section well (Coding or Quant) was sufficient to be called for an interview.

Apart from these I also appeared for tests of Gartner, Quadeye and American Express. The first two were more focused on Quant and ML-based questions, while American Express had standard InterviewBit level problems. (The test was however canceled later)

Day 1 Interviews

I appeared for the interviews in the above-mentioned order only (Didn’t appear for the companies after Microsoft as I was given an offer straight after the interview), except one round of Tower Research Capital (on Google Hangouts), as Google’s interview was scheduled about an hour later and I had reached Nalanda way too early.

Before delving into it, let me make this clear, I was very nervous before my 1st interview round with Google. I had never appeared for such interviews and was naturally panicking. Fortunately, I did decent enough in Google’s first interview round and was selected for the next to be held after an hour or two. Clearing one round boosted my confidence significantly, thus improving my approach to further interviews in the day.

In the meantime (before Google’s 2nd round) I appeared for Nutanix’s Interview. It was arguably the best interview amongst all the others I had in the day. The interview began with a brief introduction and we directly jumped into the problem. I was given a 2-D Matrix with numbers written in each cell. In one operation you can rotate one row or column by any number of steps. (Ex. Row [1, 2, 3] becomes [2, 3, 1] or [3, 1, 2] etc). I was given the initial state and the final state of the matrix after applying some operations on the initial matrix. (Operations were cumulative, that is the matrix after one operation becomes the initial matrix for the next one). The problem was to find out the list of operations that could lead to the final state.

I initially came up with the wrong solution to the problem which the interviewer pointed out very quickly. He was though very chill and kept giving hints and remarks on my approach. After the earlier proposed wrong solution, I came up with a better approach which he liked and asked to build the complete solution upon. I later understood that the problem reduced to finding a path between two nodes in a graph with the nodes being the states of the matrix and I finally came up with a DFS based approach. However, he wasn’t much convinced with a recursive solution due to the memory overhead associated with it and told that he had a solution using BFS (it too had similar memory overhead but okay…) but similar logic as mine. As the discussion was already over more than 1 hour, he didn’t ask me to write code for it but discussed points from my CV. He seemed interested in my Competitive Programming Competitions’ ranks and performances and asked some questions from the courses I have done. The interview ended and I was told that I will be told of the next round soon (which I couldn’t qualify for).

Following Nutanix’s interview, I came back for Google’s second round. The questions were easy, and I managed to solve them but messed up in writing code for one (Started writing a totally wrong solution immediately after I read the question without considering any edge cases, which I discovered midway while writing the code). After Google’s round, we were told that the results will be out in the evening and we may appear for other interviews. I following my preference order went to Microsoft.

There were a total of 3 rounds in Microsoft, 2 Technical and one HR. The first round began with a brief introduction. The interviewer spent a good amount of time going through all the points in my CV and asked a lot of questions from it. I was asked to describe the projects I did and my contribution to them. Then we jumped into the problem. The first problem was a variation of the Maximum Length Palindromic Prefix Problem. The interviewer was, however, more interested in knowing how many different ways I could solve this problem. He first asked me if I knew a DP based solution to the problem, and asked to write neat code for it. Then we discussed its complexities and he asked to optimize it. I came up with the solution using the string matching KMP Algorithm and he was satisfied with it. Then he gave another problem, where I was given a fixed number of intervals with very large limits (starting and ending limits) and was asked to process queries of a certain type on those. I proposed a solution using Coordinate compression. He said it was fine, but he asked me to think of an even simpler solution. After a lot of discussions, we came to a solution using Binary search on the intervals’ endpoints and he further asked questions from some of my courses and asked me to wait for the next round.

Within 5 minutes I was called for another round. Again same procedure, discussion on CV and projects, followed by a discussion on Hashing, Collisions, methods to avoid Collisions, Universal Hashing, etc. Make sure to cover these topics (esp. Hash-Tables very well). Then he gave me a simple implementation problem and asked to write code for it considering all edge cases and as neat and proper as possible. The code asked was complete code in any language of my choice (I did in C++) which should be ready to compile. After that, he asked me to run a few tests on the code and match its output with the expected output.

After about 5 minutes I was called for the HR Round. It was a standard HR Round. Common HR questions along with discussions on the CV. He asked me if I had questions for him and I asked him the difference in the working strategies and focus of MS India and Redmond, and the several units Microsoft works on in India.

I was asked to wait outside and after some time was told that I have been offered the Internship. Following this, I didn’t appear for the other interviews and ended with a Day 1 Microsoft Offer.

Key Takeaway points

1. Ask questions to the interviewer. At times they make the question unclear purposefully hoping that you may ask for clarifications.
2. Think out loud during the interview, so that the interviewer knows your thought process and may guide you towards the solution.
3. Develop the habit of writing clean code on paper. You will be doing the same in most of the face to face interviews.
4. Practice Competitive Programming a lot. There are a number of reasons for doing it. First, it’s fun. Second, it’s addictive, so you get something you can spend hours upon. Third and most important, it improves your problem-solving skills, something which cracking any interview requires. I never did it much sincerely (still do it very casually) resulting in screwing some very important tests and competitions. (Ranks in competitions like Google Code Jam and FB HackerCup shine on your resume and you for sure won’t want to miss out on those)
5. Try Open-Source projects. They are easy to start and add good value to your CV. My Inter Hall OpenSoft project was appreciated by all the interviewers and they seemed pretty much interested in knowing about it.
6. Participate in Hackathons and such events given you spend a decent time following point (4). Microsoft Code-fun-do is one such good to try out.
7. Don’t panic. Though it is almost impossible not to do so, try to avoid it as much as possible. Keep a smile on your face and a calm head.
8. Lastly but most importantly, “Don’t go for the interviews empty stomach” and try to have a sound sleep before the interviews. The interview process is generally a long one. You probably won’t get time to have lunch as the interview schedule is very tight. You will definitely not want to lose out on months of your hard work just because you were sleepy and hungry on the D-Day.

Glad you reached this far xD. So, that’s it. Feel free to ping me for any questions :)