CDC Internship Experience

Hi all,

My name is Sidharth Vishwakarma. I’m a third-year undergraduate studying Computer Science and Engineering at IIT Kharagpur. I’ll be interning at AlphaGrep Securities in the summer of 2023. This blog is about my journey and the ups and downs I faced during my CDC preparation.

Preparation:

Since I am from a circuital department, I knew I would have plenty of opportunities in the software companies. After contacting some seniors, I learned that the essential thing to crack a CDC internship in software companies is DSA and C.P.

Since I already had a good knowledge of programming languages like C and C++ from classes 11th and 12th and my first year of the Programming and Data Structures course, I started solving questions and giving contests on CodeChef and Codeforces. At that time, I needed more discipline and regularity, and my problem-solving could have been more consistent. Due to my lack of fundamental algorithmic knowledge, I struggled greatly to get my codes to execute and work.

Then, there came a turning point in my C.P. journey when the course Algorithms-I was introduced to me in my 2nd year (3rd Semester). At this point, I learned about Time Complexity, Space Complexity, and, most importantly, the STL library of C++. After this, I could comprehend, analyze and optimize the code I wrote on coding platforms.

P.S.- I learned STL through the Coding Blocks STL course.

Some Tips: Before beginning your competitive programming adventure, learn about terms like time complexity, space complexity, arrays, and fundamental C++ and STL. Your transfer will go a lot more smoothly as a result. As you go toward mastering programming, make sure to examine other people’s code to see how they implement concepts similar to your own.

Alongside my Algorithms course, I gave contests on CodeChef and Codeforces. I struggled a lot initially, and my rating constantly oscillated between 1100 to 1200 on Codeforces and between 1700 to 1800 on CodeChef. It was around Dec 2021 that I became a 4-star on CodeChef.

I then wanted to focus on Codeforces, so I started with the Div. 2A Codeforces ladder on A2OJ.

I switched to the Div. 2B ladder after the first 50 Div. 2A problems. Until then, around the beginning of April 2022, I became pupil level in Codeforces. On moving forward, when I started with Div. 2C ladder, I learned that I needed to know more about Number Theory, Graph Theory, and Dynamic Programming to take my abilities to a higher level. Even modulo problems were frightening to me at first sight.

Then I decided that instead of roaming here and there for resources, it’s better to follow a course. I then consulted the Competitive Programming course from Coding Blocks to learn more concepts useful for C.P.

The topics that I covered were as follows:

1. Bit Manipulation & Bitmasking
2. Mathematical Concepts
   a. Big Integers
   b. Combinatorics
   c. Linear Recurrences
   d. Pigeonhole Principle
   e. Mathematical Expectation
3. Number Theory
   a. Primes and Factorization
   b. GCD and Extended Euclidean Algorithm
   c. Modulo Concepts
   d. Linear Diophantine Equations
   e. Fermat’s Theorem
   f. Chinese Remainder Theorem
4. Recursion / Divide & Conquer
   a. Implementation Based
   b. Subset Based
   c. Backtracking
   d. Binary Search and Merge Sort
5. Segment Trees
   a. Lazy Propagation
   b. Persistent Segment Trees
6. Fenwick Tree / Binary Indexed Tree (BIT)
7. Greedy Algorithms
8. Graphs
   a. Traversals (BFS & DFS)
   b. Cycle Detection
   c. Bipartite Graphs
   d. Topological Sort in DAGs
   e. Strongly Connected Components
   f. Disjoint Set Union (DSU)
   g. Minimum Spanning Trees
   h. Shortest Paths
   — Single Source Shortest Path using BFS
   — Dijkstra’s Algorithm
   — Bellman Ford Algorithm
   — Floyd-Warshall Algorithm
   i. Implicit Graphs Splitwise Algorithm
   j. Euler Tours
   k. Traveling Salesman Problem
   l. Articulation Points and Bridges
   m. Least Common Ancestor (LCA)
9. Game Theory
10. Dynamic Programing (DP)
    a. 1-D / Linear D.P.
    b. 2-D / Grid-Based DP
    c. Longest Increasing Subsequence (LIS)
11. Geometry & Convex Hull
12. Hashing Concepts
13. Tries & Persistent Tries
14. Square Root Decomposition Mo’s Algorithm

Alongside as I was going through these topics, I frequently gave contests on CodeChef and Codeforces (I never missed a contest), and I also started giving Google Kickstart rounds. When almost a month was left for my CDC to start, I became a 5-star coder on CodeChef and was able to become a specialist on Codeforces. Besides this, I also gave GoC contests that were mainly meant for the CDC and consisted of previous year’s CDC questions. These competitions gave me a solid notion of the difficulty of the coding exam questions and how much more effort I would need to put in to get there.

After completing all the topics mentioned above, I had a good knowledge of many DSA concepts and was confident about my C.P.ing skill.

Some Tips: I recommend you all stick to a particular resource for learning C.P. and DSA. The CP-Algorithms website is a good resource for learning all the above mentioned topics. It has all the concepts explained excellently and is easy to understand. Don’t just learn the topic and move forward. I recommend you practice some problems based on the topic you have learned. There are some problems with each topic on the website. Moreover, you could also use google to search for problems related to the topic.

Also, try to give each and every contest at CodeChef and Codeforces. These platforms are good to start with, but as you get acquainted with DSA, try to give contests on AtCoder.

Since almost only one month was left for the CDC to start as expected, I began with InterviewBit. It’s an excellent resource for preparation for the interviews. It has all the topics that are needed for interviews. After this, I needed to brush up on my C++ OOPS concepts which I did through my Software Engineering course by Prof. Partha Pratim Das in my 4th Semester. Since I was also aiming for the quant profile, I began revising my Probability and Statistics course by Prof. Swanand Ravindra Khare, offered in my 3rd Semester, followed by solving puzzles on platforms like Brainstellar, GeeksforGeeks, and Gurmeet.

Some Tips: No matter how talented you are, InterviewBit is crucial since the ideas utilized in those problems frequently arise in corporate questions. Coming up with some of the solutions fresh in the real coding round could be challenging.

Also, it’s essential to understand the OOPS concepts of C++ clearly since many HFTs coming for systems roles tend to ask them in their interviews. You could also refer to the GeeksforGeeks for learning them. Some of the topics that you need to focus on are as follows:

1. Constness and Inline functions
2. References and Pointers
3. Function and Operator Overloading
4. Dynamic Memory Management (new and delete)
5. Object Oriented Programming
   a. Classes and Objects
   b. Access Specifiers
   c. Constructor / Destructors
   d. Copy Constructor & Copy Assignment Operator
   e. Constness and Static Data Members
   f. Friend Functions / Friend Classes
   g. Operator Overloading in Classes
   h. Concept of namespace
   i. Inheritance (Public, Protected, and Private)
   j. Dynamic Binding & Virtual Functions
   k. Abstract Base Class
6. Casting (const_cast, static_cast, reinterpret_cast, dynamic_cast)
7. Exceptions & Error Handling
8. Function & ClassTemplates
9. Function Objects (Functors)
10. Smart Pointers

Some essential pointers: I spent more time on competitive programming and algorithms to compensate for my lack of inborn talent. As a result, I opted not to apply for or complete any internships during my first and second years of college. But I did not have to suffer in the recruiting process in any way because I didn’t have a CV. For Day 1 and Day 2, taking this risk pays off more handsomely, but as you go into the latter days, your CV will play a more significant role in your shortlisting process.

Coding Rounds:

AlphaGrep:

It was the most intense coding round consisting of 5 coding questions. The first was a standard linked list question. The second was an interactive problem finding the sink in a directed graph. I solved it with some greedy approach. The third one was a medium-hard ad-hoc question based on priority queues and binary search operations like lower and upper bound. The 4th problem was based on bitmasking. I did some brute along with greedy algorithms on the bits to solve this. The last one was based on searching for a key in a level-order sorted tree. I solved this one partially using some binary search techniques.

Google:

The first problem was a dynamic programming problem on an array, was medium-hard and needed some quite good observations. The second question was a trie insertion question. I used a greedy approach with some brute on all possibilities to get to the solution.

Goldman Sachs:

The first question was based on string D.P. I didn’t have much time for this, so I took a simple greedy approach to get partial marks on that. My main focus was on the second one which was based on a grid DFS. I did it with some modifications in the DFS algorithm to approach this problem.

Nutanix:

The first question was a multiple query based question on trees. A simple DFS and D.P. memoization was needed to approach the problem. The next one was on the partitioning of a numerical string. It was challenging and required a bit of permutation and combination. I did it partially under time constraints.

Sprinklr:

There were three questions of increasing difficulty. The first included a sliding window to identify the longest subarray with the highest maximum sum. The second was a graph problem based on node DFS counting and cycle identification in directed graphs. The third was a tree partitioning problem. I did a DFS with some modifications to approach this problem.

The topics in the coding rounds varied from simple to slightly more difficult than medium (around Div. 2D levels), and time was not a concern as long as you had enough practice. I was finally shortlisted to give the interviews of AlphaGrep, Google, Sprinklr, Nutanix and Goldman Sachs.

Interview Stage:

AlphaGrep:

My interview started around 6 am. There was a panel of three interviewers. The first interviewer started by posing some simple algorithmic problems to me. The first problem he asked was about the time complexity of common data structures. It was simple and basic to answer. Next, he moved into some problems based on these data structures, he asked me the algorithms for insertion and deletion in them and posed some problems related to it. The next question that the interviewer asked me was about persistent data structures. He asked about persistent linked lists and persistent trees. It was a standard question about persistent data structures, and since I had already read about them in my Competitive Programming course from Coding Blocks, it was quite easy to answer it.

P.S.- This blog by Anudeep can give you a good understanding of persistent data structures. You need the basic knowledge of segment trees before you start reading this blog.

Now the second interviewer came. He started with a complicated problem that took much work to think about and arrive at a solution. The problem needed the knowledge of Bellman-Ford Algorithm on a Currency Matrix. The discussion on this problem went on for quite a long time, 15–20 mins, and I finally was able to answer this by using some hints from the interviewer.

P.S.- I later came to know that this question is quite famous by the name of the Currency Arbitrage problem.

Then he moved forward, and his next question was based on the use of hash tables on array. He asked me a standard GFG question based on subarray for this. Later he extended it to matrices. It was relatively easy. You need to know how to keep track of prefix sums in a matrix.

At this point, the interview shifted from DSA to C++. He tested my systems knowledge with a wide variety of questions — some basic C++ OOP based questions like shared pointers, virtual functions and dynamic polymorphism, he also asked questions on topics related to memory access and management. I answered most of them with all the knowledge I have from my Software Engineering course. Some of them were outside my scope and required some knowledge of the Operating Systems so I simply told them that these topics will be taught to me in the next semester. At this point, I was at the end of my interview. Finally, the interviewer asked about my preferred role and if I had any questions for them.

After my interview, I had some snacks to energize myself ( I didn’t have any breakfast till that time), but then all of a sudden, the Placecom called me and asked me to go for the H.R. round. When I got into the meeting I saw no one was there, then I got a call from the AlphaGrep HR Manager that I have been selected for the Software Developer Role at AlphaGrep.

Google Round 1:

Since I already got an offer from AlphaGrep, in a typical scenario, you automatically get blocked by other companies if you accept an offer from any of the companies. But since Google pre-schedules your interviews one day before the interview date, I was required to attend it.

There was only one question in the interview, and we needed to write code for that step-by-step each time, improving the efficiency of our algorithm. The question was quite simple and involved the use of unordered maps and some knowledge of graph algorithms. Firstly, I just implemented it by using graphs and naive algorithms. Then finally, by using some hints from the interviewer, I optimized it by using unordered maps.

Google Round 2:

In the 2nd round, there was also a single question, but each time I came up with a solution, the interviewer modified the problem slightly to make it more challenging.

The first variant of the question was involved around basic level-order traversal of a binary tree. I did it in about 5–10 mins. The next variant was based on DFS with removal of nodes in the binary tree, and the last one was just a simple modification to the previous one using the recursive algorithms of finding all permutations of a given array.

Both the interviews lasted around 1 hour each and were relatively easy if you have good knowledge of graphs and some standard algorithms that are implemented on them.

Some Tips: Make sure you are properly prepared for the system’s role in HFT organizations by studying Object-Oriented Programming fundamentals. If you are a five-year student, make sure you know some kinds of stuff about Operating Systems and Computer Networks. I believe that exceptional algorithmic skills and understanding are not much required. Make sure to speak out often. If you express your ideas clearly and in-depth during the interview, the interviewer will probably direct you to the appropriate area.

Some Random Suggestions:

1. Sometimes if you get stuck in a problem where you cannot think of any way to proceed to a solution, always feel free to ask the interviewer for some hints. Sometimes the clues or hints can land up to the exact answer to the problem.
2. Make sure that you prioritize your interviews very carefully. You should not place a company with less chance at a high priority. In that case, that company may take up most of your time, and you will have no time remaining for the companies in which you have a good chance (the maximum number of companies you can sit for interviews in a day is around 3–4). So, choose your preference carefully.
3. Discuss your test with your peers and friends so that you can know their tricks to approach the problem. Even if you cannot solve the question entirely, you will get some marks for the partially accepted test cases.
4. CGPA matters. An above 8.5 CGPA doesn’t always work, particularly in light of the recent surge of high C.G. seeking HFTs and grade inflation. The higher the score, the better, and it may significantly improve your odds if the test is very simple. In that case, they break the ties, usually considering the C.G.
5. Always get your CV reviewed by a senior. A senior has gone through this process and has much more experience than you, so it’s preferable if you ask them to help you with your CV. Talk to them even if you are not very close to them. They are always there to help you. For me also, it wouldn’t be possible without the support of my seniors, especially 18EE Pratyush Saha and 19CS Rohit Raj.
6. Try to give coding competitions like Google Kickstart, Code Jam, and Meta HackerCup. Try to get good ranks (the higher, the better). You can also add them to your CV. They also help a lot in making you get shortlisted for some companies like Google and Microsoft.
7. Lastly, you should be able to accept rejection. The CDC process is random. You may have performed well in a company interview but weren’t shortlisted. On the contrary, you may have solved the problem partially in some other interview but still got shortlisted. Do not lament. In that case, accept it and move on.

Final words:

I want to thank all my family and friends for their constant support in this journey — special thanks to all the seniors who helped me prepare, especially Pratyush Saha and Rohit Raj.

This blog series has gained a lot of my attention and has been helpful to me. Reading as many CDC Chronicles as you can is advised since, even in the worst-case scenario, you’ll get to know the names and contact information of your seniors who could be able to help you further.

Try to do as much as you can. Sometimes you won’t get what you expected, but be consistent and keep confidence in yourself.

I wish you all the best of luck as you go through this CDC internship drive. Believe in yourself, stay focused, and be persistent. I have no doubt that you will all achieve great things in your careers.

Signing off, BYE…