This was rather a short interview that lasted for, maybe a decade of minutes.

I enter the room. I was asked to sit. They asked me my place of origin, my college name, and my CGPA till the 7th semester, as I am a final year student. I will represent Interviewer as “I”

I: What is your favorite subject?

Me: I love Algorithms and Data Structure.

I: You are given 3 distinct elements in an array of size n, and you are required to sort them. Go on the board.

Me: Firstly I assume these elements as A,B,C and defined their precedence as A>B>C. I will have two pointers, one at the starting(S) and the other at the end(E) of the array. When I encounter a C, I swap it with the element at the S and increment S. When I see an A, I swap it with E, and decrease E. I do nothing on seeing a B. This way in constant space and O(n) time, we achieve glory. Please note that, it is a O(1) space and O(n) time algorithm.

I: What if you have 5 elements to work with?

Me: This is not going to work in that case sir. So my approach would be, if we encounter say “i” while traversing the array, we can hash at index “i”, with the frequency of “i” in the list. This will waste me O(n) space.

I: Assume that these 5 numbers could be arbitrarily large… What are you going to do then, this approach is going to waste you huge space right??

Me: Yes, I will define a mapping of these numbers to the set {1,2,3,4,5}, such that the mapping preserves precedence. Then I change the original array according to the mapping, sort them in the previously discussed algo, and then, reproduce the array, the the reverse mapping.

I: What else do you know apart from Algorithms?

Me: Theory of computers fascinate me.

I: What is a Universal Turing Machine?

Me: Answered.

I: We are done. Do you have any query?

Me: Umm… Yea, Is there any weightage to the GATE score in the selection process? “With a big smile”

I: Yes there is.

Me: Thank you sir.

NOTE: EVERYONE (MORE THAN 90% PEOPLE) MENTIONED ML/AI AS THEIR INTEREST OF RESEARCH, SO THEY WERE SMASHED ON MATRICES AND PROBABILITY.

Wish you a good health, Jai Hind! :)

Result : Selected

congo @Mriganka.

please mention your gate rank