SDE

The idea is to find maximum sum or all paths starting with every cell of first row and finally return maximum of all values in first row. We use Dynamic Programming as results of many subproblems are needed again and again.

Time Complexity: O(n2). 
Auxiliary Space: O(n2).

The simplest approach to solve the problem is to generate all possible substrings of the given string and print the length of the longest substring which is a palindrome.
Time Complexity: O(N3), where N is the length of the given string. 
Auxiliary Space: O(N) 

Dynamic Programming Approach: The above approach can be optimized by storing results of Overlapping Subproblems. The idea is similar to this post. Below are the steps: 

Maintain a boolean table[N][N] that is filled in a bottom-up manner.
The value of table[i][j] is true if the substring is a palindrome, otherwise false.
To calculate table[i][j], check the value of table[i + 1][j – 1], if the value is true and str[i] is same as str[j], then update table[i][j] true.
Otherwise, the value of table[i][j] is update as false.

This round was the most exciting and challenging of all, as this involved both design and DSA knowledge. We were asked to design a file system in the same language as chosen by us before. Some of the operations we had to perform in our file system were : 

Create a file
Delete a file
Copy a file to the given path
Move a file to the given path
Maintain multiple versions of the same file
Revert to an older version whenever required
We had to write the code for the same in their virtual machines using Remote Desktop, the credentials to which were provided to us a day before the round. 

We also had a meeting with the senior officials of Commvault the night before this round, in which we were told some details like how long the round will last, at what time does the round start, and all of our doubts were cleared if we had any. Also, in the morning, before the coding actually begun, we were explained the problem statement thoroughly by the officials of the company.
It was a 6-7 hour long round, and we were assigned mentors who were connected with us via Zoom and would check our progress at periodic intervals and also resolve our doubts and queries. In the first hour, we were expected to be ready with the design of our file system, and we had to fill the provided classes with data members and member functions that we were planning to use. Anyone who was unable to come up with a design was asked to leave by the assigned mentor. Also, during the coding phase, if anyone’s performance was not satisfactory, they were asked to leave too. Everyone in my room(there were multiple rooms) except me was asked to leave, as after sometime, my mentor stayed with me the whole time. We were expected to write a running code, and the output should be correct as well. If we encountered any bugs, our mentors helped us by pointing out where the error might be. We were allowed to use C++14 in this round, which was a relief for me. 
The mentors were very helpful and motivating, and so were the top officials of the company who addressed us before the round started.
The result of this round was not declared formally, but I made it to end by writing a perfectly running code and my mentor told me that someone from HR will contact me soon, so I assumed that I had qualified this round. Two hours later I received a call from HR to join a Zoom meeting, where the panelists were waiting for me for the third round – the technical interview.

So round 3 was a Long Coding Challenge. I had no clue what they were going to ask in this round. I tried searching online and after reading all the stuff all I could think of was I can’t do it. All the questions that I found looked like they will ask us to code a file system or something related to Linux. But in reality, it was a completely different experience. I really liked this round. This round sure did test my Object-oriented programming skills and logical ability to store data into a self-designed Data Structure.

This round started at 8:40 am. We were briefly introduced to what we were going to do. There were 26 students that were selected for this round, we were divided into groups of three but the task was to be performed independently.

The problem was: We have to design an mp3 player. Sounds complicated right? But no we don’t have to make any user interface or read any files nothing like that. We had to design a program that can store different song details. The main player list, multiple playlists and we had to perform different operations on them.

Okay, this might look complicated. Here is what I did.

I made a class Song that contained attributes like song name, length of the song, copyright, singer. Made constructor and initialized values when an object is created.

Made another class for Playlist. That is going to have a hashmap of SongName as key and Song as its Value.

Made another class called mp3Player for the whole logical operation.

And then there was this Main class that was provided to us as a template so that we can design the missing functions.I think this was the round that almost made me cry. I was so disheartened after this round, it felt like everything I have been doing for the past two months means nothing.

So this round was of 2hours. Yes, you heard it right, there were 2 interviewers and I must say they were brilliant. I was so surprised that after working for so long in a company they remember each and every small concept of almost all of CSE core subjects.

So as the interview started they asked me to introduce myself. Then they asked me about my projects. I told them that I prefer JAVA over other languages.

So the asked me these questions:

What is a JAVA compiler and how does Java run a code.
Name of JAVA compiler – Java in time compiler(I didn’t have a clue at that time).
How does Java supports OOPS & What are OOPS principles.
How many types of Polymorphism are there?
Give real-life examples of Runtime Polymorphism?
How does Runtime polymorphism different from static polymorphism?
Real-life use of Inheritance?
What is faster Java or C? and Why?
Why do you code in Java and not C++?
What frameworks have I worked on?
Implementation of HashMap in Java?
Why do we use just Map while in the left half of Map m=new HashMap<>(); and why I have not used HashMap instead of Map?
Difference between Iterators and Enumerators.
DBMS ACID properties.
Normalisation and its types?
What is DeadLock?
Difference between Process and a Thread?
How will the memory consumption vary in these cases, there is a Process containing 1 thread and there is a Process containing 0 thread?
What are annotations? What do they do?
What are Semaphores?
What are Scheduling Algorithms?
What are directed and undirected graphs?
Can an undirected Graph be a Tree? If yes what are the necessary conditions?
Difference between Structure and a Union in C?
Why do we use Unions? Give real-life examples where a Union is suitable for use?
How is multi-threading achieved in Java?
How to make sure that two running threads using the same function do not collide and results in an unwanted output?