The CDC Chapter

Hi, I am Naman Jain, a 3rd year undergraduate from the Department of Computer Science and Engineering, IIT Kharagpur. I will be doing my internship at Nutanix Technologies, Bengaluru in the 2021 summers.

This article is going to be about my journey of Competitive Programming, CDC internship preparation, and the Selection Process.

I started doing Competitive Programming in my 3rd sem just to keep my mind active. I started by solving div.2 C (Codeforces) ladder problems from a2oj. Then kept on increasing the difficulty level to div.2 D in 3rd sem itself and div.2 E in my 4th sem. Alongside I also used to read algorithms and data structures used in the problems from geeksforgeeks and code them myself. Also, I used to participate in contests held on codeforces to keep a check whether I am improving.

I would advise you not to skip questions that you are not able to do, instead read editorials and others’ code to get the concept behind the problem. Doing questions in your comfort zone won’t actually improve your competitive programming skills.

CDC Internship Preparation

As I came to hear that our CDC internship selection tests are going to start in August, which was quite unexpected to me as I expected them in winters :(, I started solving questions from the interview bit for gaining confidence on standard problems. Also, I started solving the monthly challenge on Leetcode, which mostly has easy-medium problems.

When the interviews were approaching, I started reading about some interview experiences, the questions asked in interviews, and also some random topics from geeksforgeeks.

Shortlisting Rounds

1. Google: 2 coding problems (60 mins.) on HackerEarth. The coding questions were not the same for all. In my first problem, queries were given to xor the numbers in an interval of the given array with a number and finally outputting the sum. The second problem was a good dynamic programming problem. Since this was my first coding test, I was a bit nervous and I didn’t observe that C was selected as the default language, in which I wrote a C++ code :(. Also, the whole code disappeared when I switched the language. Only 30 mins. were remaining and had 0 questions completed but I managed to complete both the questions on time :). The shortlisting was done based on the coding test and CV.
2. DE Shaw : 3 coding problems (95 mins.) on HackerRank. First was an easy observation problem. The second was a number theory problem, which could be solved using digit dp or a good observation of representing the number with a different base. The third was a question on trees. I solved the first and third problems.
3. Sprinklr : 3 coding problems (90 mins.) on HackerEarth. The first was a simple div.2 A level problem. The second was a good implementation problem on graphs. The third was a digit dp problem. I solved the first and second problems.

Till here, I was quite demotivated as I was not able to solve all the problems in DE Shaw and Sprinklr tests. So, I decided to work hard and solve all the problems in the upcoming tests.

4. Nutanix: They conducted 2 rounds. First was a coding round on HackerRank with 2 questions (75 mins.). The first question was a simple greedy problem. The second was on cycles in the graph which could be solved either with binary search with cycle detection or DSU with bfs/dfs. I solved both problems. The second round was a debugging round, where we were supposed to find out and correct bugs in the given code.

5. Microsoft : 3 coding questions (90 mins.) on mettl. The questions were not the same for all. The first was to find the longest palindromic subsequence, a dp problem. The second and third were also dp problems. I felt this was the easiest.

6. Uber : 3 coding questions (90 mins.) on codesignal. The first question was on dealing with large numbers which could be done easily with python. The second was a digit dp problem. The third was a string transformation dp problem. Since the test was in the morning, I was feeling sleepy, and also since I did the first 2 questions in 20 mins., I took some rest :) ended up taking around an hour to solve the 3rd question because of which I wasn’t shortlisted :(.

7. Goldman Sachs: There were 5 sections. The first section contained 2 coding questions (30 mins.). The first question was an easy problem, though I felt that 1 test case was wrong in it. The second question seemed to be very difficult where we asked to find the shortest path length from one point to another on a 2d plane with lines in between which you couldn’t cross. One idea I came up with was to build a graph and apply Dijkstra but didn’t had enough time to code that. The second and third sections contained MCQs based on aptitude, maths, and programming. The fourth section contained 1 coding question (45 mins.). It was a good question on graphs based on the idea of visiting edges. This question was exactly the same as a Codechef long question. It was also accepting very high time complexity solutions though :). The fifth section contained 2 subjective questions.

8. Quadeye: This also had 5 sections. One section had 2 coding questions (40 mins.), both of which were quite easy. Other sections contained MCQs on quant, systems, and programming and a section containing 2 subjective questions.

I was shortlisted for all the companies except Uber.

Things to Learn

1. If you are not able to think of an optimized solution, try going with an un-optimized solution with an aim to pass as many test cases as possible.
2. Many companies also see CV and CGPA alongside coding test performance for shortlisting.
3. It might be possible that some test cases are wrong, though very rare chances of that. So, do not waste much time on that.
4. Try completing all the problems as soon as possible, as many companies see the time of completion too.
5. Don’t be nervous as this is just an internship selection :).

Interviews

This was quite a bad experience for me as I was not able to give interviews for my top 2 priority companies.

Nutanix: They just took 1 long technical round. The interviewer started by asking a question on 2 pointers. I explained my solution along with the required time complexity and space complexity. He looked fine with my solution and asked me to dry run the test case on it. Then he extended the question by adding more constraints to the problem. I came up with a 3 pointer solution which I explained to him and did the dry run on the given test case. The dry run was taking much time as there were many operations to be done. Then he asked me a problem on hashing, wherein given an array, you need to check if pairs can be formed covering each element in exactly one pair such that the sum of elements in a pair is divisible by K. I explained to him an O(n) solution using hashing. Finally, he asked me to code my 3 pointer solution to the previous question. I was satisfied with my performance in this round.

Microsoft: They took 3 technical rounds. In the first round, they asked some questions on CV and a very easy question on bfs/dfs. In the second round, they asked me to explain my projects some basic observation questions, and asked me to code. He also asked me some good conceptual questions on Django as I wrote that in my CV. I couldn’t answer them, so he asked me to explain another project which I explained to him nicely. I was called for the third round. In the third round, I was asked to design a data structure, where we could insert, delete, or output a random number from the currently present numbers. I initially came up with a solution to use a balanced binary search tree that had O(logn) time complexity for all 3 operations. She asked me to optimize it further. Then I used an additional array to mark each element as present or deleted, a hash map to access each element quickly, and a Fenwick tree with binary search (to find kth present element) to output a random number. It was a bit of a complex solution. But it brought down the complexity to O(1) for insert/delete and O(logn) for a random number. Then she gave me a hint to place the element to be deleted at the end of the vector. Then I was able to complete my sol. bringing down O(1) complexity for all 3 operations. Then she asked me to code. Finally, she asked me a question wherein if you were given the details of friends of each person on Facebook, compute how closely 2 people know each other on Facebook. I came up with an idea to build a graph and apply bfs.

As soon as the 3rd round of Microsoft ended, I got to know that I received an offer from Nutanix and they took me out of Microsoft as I filled Nutanix as a higher priority than Microsoft. I asked them if I could give interviews for my higher preference companies, but they told me that I might lose the offer from Nutanix. It was already too late, so I decided to go with Nutanix without taking any risk.

Conclusion: It was overall a good experience for me with many ups and downs. I didn’t face much trouble because I was doing competitive programming for 1 year. In fact, looking back, I can say that I enjoyed the whole process. To summarise, there will be moments when things don’t go well, but just be patient and never lose hope.

Remarks

1. Try not to sit for your lower preference companies as you can’t give interviews for more than 3–4 companies. Also being selected in your lower preferences companies won’t make you feel good.
2. Prepare well for everything you write in your CV, especially your projects.
3. Do not take so much pressure for interviews as the interviewers are really nice :)