This year IISc had record number of applicants for CDS Department. So they had divided the screening process into 4 days, each day having 2 shifts.
The screening process had a written test(Different tests, based on if you choose CD-CS or CD-CP), succeeding in which, was followed by an interview. The written test had 5 simple questions to be solved in 30 minutes. Questions were almost as easy as the GATE 2019 paper.
They called me on 20th May, morning shift, 9am, so naturally I reported at around 8am. The exam started at 9.10am’ish time, went upto 9.40am. Soon after the exam got over, I asked Yogesh sir, if we could quickly check the canteen, as I was hungry as hell. I was told that results will be declared at 10am sharp, and I should decide if I would be on time. Prakruti, the canteen, had a huge queue at the token counter, so alas, I stayed hungry.
Shortlist was out. My name was called, was asked to report at room 201. Waited for quite sometime outside, listening to “Hall of Fame”, by the Script, on loop, on my headphone. and then came my turn. I was called in, and asked to take a seat.
(I DONT REMEMBER WHICH QUESTIONS WERE ASKED BY WHOM, SO I WOULD USE “I” IN GENERAL FOR INTERVIEWER)
I: So Mriganka Shekhar Chakravarty is your name. And you have a Gate score of 729, with an AIR of 558. Am I correct?
Me: Yes, sir.
I: I see you have chosen CD-CS with Cloud Computing as your first choice for lab. Is it correct?
I: But, Mriganka, in the online form where you were supposed to make choices, you selected CD-CP as your preference and now you have switched to CD-CS? Why so?
Me: I dont remember sir, however, that indeed might be a mistake on my part.
I: Okay. No issues. So tell me Mriganka, what are your strengthened subjects?
Me: I feel comfortable with Algorithms and Data Structure.
I: But you have chosen Cloud Computing as your lab right?
Me: Yes sir. But I believe, Algorithms is a subject, which if strengthened can be a launchpad for any other stream of specialization.
I(Everyone smiles): True that, but knowing algorithms is a “Necessary condition, not a sufficient condition”.
Me: I agree sir.
I: Okay, Mriganka please stand in-front of the board, and draw a grid structure.
(TRUST ME, THE WHITE BOARD WAS HEAVEN….. IF YOU EVER INTERVIEW AT ROOM 201, YOU WILL KNOW IT)
I: So Mriganka, you are standing at (x,y) on the grid, and you wish to go to (p,q). What is your shortest path?
Me: Sir, if you could kindly stress on the constraints. Am I allowed to take diagonals on the grid?
I: Yes, you can take right, down and diagonals.
Me: Explained my approach. I started scribbling the mathematical model of the situation.All the while, I kept speaking of what I am thinking. After, sometimes, I came up with the equation that gives the shortest path, dependent on x,y,p,q.
I: Can you prove it?
Me: I started the proof. Stumbled. kept scribbling. I failed. I however remember saying, “For this to be shortest, we need to show, that (x,y) to (p,q) cant be reached any any number of steps shorter than this, basically we need a contradiction approach”.
I: Okay fine. No problem.
I: So do you know what a diameter of a graph is? It is the longest of the shortest paths within the graph. So given a graph, can you work out the length of diameter of a graph?
Me(Holy F**k inside…premature optimization is root of all problems, take it easy and brute force :P): Sure sir. So it is a shortest path problem. Let us run Dijkistra’s on all the vertices, and from among them choose the maximum. This is easy.
I: Okay…. So what is the complexity?
Me: It is O(VElogV) for dijkistra run V times. and O(N^2) for choosing the maximum of the shortest paths. So the complexity is O(EVlogV)+O(V^2).
I:Can you optimize it further?
Me(Quiet for a few moment): I can only worsen it with Floyyd Warshal, with a smile!
(He was probably looking for Johnson’s Algorithm)
I: Okay, Mriganka draw a binary tree.
I: Count the number of children, and the number of nodes with two children. and name them N0 and N2.
I: Now you can see, that N0=1+N2. Prove it.
Me(I WONT USE INDUCTION): Started working around with the degree equations. Got tired after sometimes(I AM HUNGRY). Sorry sir, it would be helpful you could give me a direction to work around(with a smile).
I: Use Induction.
Me( :( ) : Did that.
I: Okay Mriganka, take a seat.
(I DID NOT NOTICE, BY THIS TIME THEY HAD BISCUITS AND SNACKS ON THE TABLE, AND I WAS HUNGGGGRY)
I(No they did not ask me to take snacks xD): Asked a few questions from operating systems, on process isolation and stuffs.
Me: Answered, but I am not personally satisfied with the OS interview. I could do better.
I: Okay, Mriganka, you may leave now :)
Me: Thank you sir :)
I: You must be really hungry. Have some food. You were the one asking to check the canteen out right?
Me: Yes sir, I am reaaaly hungry. Had nothing since morning.
I: See you.
24th May…………….CONGRATULATORY MAIL :)