They called 245 students for the interviews, out of which 32 candidates appeared including all categories,because rest candidates had taken admission elsewhere in Initial COAP rounds.This Interview was my last hope of admission at 464 (general) rank as i couldnot clear IIT kanpur MS interview and was offered PHD in CDS at IISC to which i politely said no, couldnot give Bombay test due to semester exams.
The Interview Process is as follows:
Date:JULY 15 ,2019. VENUE:LH3 IIT HYDERABAD.
I was expecting a written test of three questions as this was the pattern followed every year,but this year the pattern was different and the question paper consisted of 35 multiple choice questions with a marking scheme of +4 and -2.The questions were of basic level, I am not mentioning the questions here,but majority questions were from Graph Theory, Algorithms,and questions were covered from all Gate Subjects,anyone with basic knowledge of Gate could easily solve the test.
Results were declared within an hour and 25 out of 32 candidates were shortlisted for interviews.There were two panels for interviews and i was the second candidate to be interviewed.I was a bit nervous before the Interview but the seniors at IIT Hyderabad(Ankit Sir) were very helping and asked me to calm down before the interview and told me that the written test was just for initial screening and there was no weightage of written test for selection procedure,although i was confident that i had scored a decent score in written.
Next came the turn for Interview, There were three Interviewers 1.HOD MV SIR 2. N.R Arvind Sir 3 Rogers Mathews Sir
For the Interview Process I will refer Interviewer as I and Myself as M.
I1: Introduce Yourself.
I1: So what subjects are you comfortable with.
M:Algorithms And Data Structures.
I2: Ok ,so Archit consider you have an array of integers and you are giving a bunch of indices say i and j, and you have to compute the sum of all array elements from i to j.
M: Sir one way is to compute the sum again and again for each query asked bruteforce, but it will take a lot of time. Time Complexity: (Number of queries*O(n)).
I2:Ok archit that seems correct but can you improve the Time Complexity.
M: After thinking for 5 seconds i replied Sir we Can use segment trees(I knew segment trees because i liked Competitive Programming and did Competitive Programming for about 2 years in college).
I2: Can you please elaborate on your approach.
M:Took a chalk and i explained the whole concept on board, they didnot ask for code.I heard them saying that he is going good while i was writing my approach(boosted my confidence).
I2:Can you tell the Time Complexity.
M: Sir one query will take logn time so total time complexity will be O(q*logn).
I2:Archit can you solve one query in O(1) time by doing some pre-computation.
Thought for 5 seconds and the approach clicked in my mind as i had used this approach many times during solving codechef and hackerrank problems.
M:Sir we can build a prefix array and then solve all queries in constant time , example an array 5,1,2,4,3 and indexing be zero based
we build a prefix array like prefix for the above array will be 5, 6, 8,12,15. Now suppose we have bunch of indices i and j. So the sum of array from i to j will be prefix[j]-prefix[i-1].
I2: Smiled and asked me archit are you a competitive programmer?
M: Yes Sir i started doing CP in second year of my college.
I1: So archit tell me what other subjects are you comfortable in?
At this point i was a bit nervous because they were switching subject, but i kept cool as this was my last chance for admission this year.
M:Theory Of Computation.
I1: is 0^n1^n (n=1 to n=2019) CFG,REGULAR?
M: Sir every finite language is regular so the above Language is regular.
Asked me about some more Grammars.
I1:Can you proove that 0^n1^n is not regular.
M: Sir we need to keep a count on the value of number of zeros pushed and if we encounter 1 we pop until stack is empty,we cannot make a dfa for above language.
I1:That is fine archit but this is not the proof.
M: Yes Sir,this is not the proof.I didnot practice proofs in TOC.
I1: Can you state pumping lemma for regular languages
I1:What is the idea of pumping lemma for regular language or any language in general.
M:Sir it is a negation test,if a language doesnot satisfy pumping lemma it is not regular,but if it satisfies the pumping lemma it may or maynot be regular.
I1: DFA AND NFA have the same power?
M: YES, SIR
M:Every DFA is already a NFA and there is a conversion algorithm from NFA to DFA although the DFA obtained might not be minimal.
I1: Ok, what about DPDA and NPDA
M: NPDA is more powerful than DPDA.
I1: Give Examples
M: ww^r,wcw^r respectively.
I1:Ok ,archit we are done with you, you can leave now.
I wanted to be confident about my selection and had read past interview experience of Digvijay Pandey Sir so i asked the professors if they wanted to ask some more questions.
I2: No archit we are done with you.
I1:Oh you want some more questions
M: Yes Sir.
I1:You are given n identical balls and k distinct bins what are the ways to distribute these balls in bins.
M: I wrote the answer on board immediately.
I1: How did you write the answer immediately.
M: Smiled and replied,Sir the modification of same question was there in the written exam.
I1:Oh,is it so let me check your written sheet,
M:Yes sir,Sir Also there were 2-3 ambiguous questions in the written test,
I1: Oh it might be the case because we have not set the question paper, never mind archit now you can leave.
M: Finally i was confident and i left the hall.
Overall I had an amazing interview experience,
Thanks to GO COMMUNITY for beautiful explanations of questions,and yes Competitive Programming does help in the interviews.