My IITD interview was scheduled on 24 May, 2018. I have made up my mind to not join IITB and join IITD(due to location preference). I was setting my foot inside an IIT for the first time in my life. The first shock came when I entered the college gate. I asked the guard where is **** hostel. As I was on foot he started smiling and politely replied beta wo hostel to 2 kilometer door hai. Then I remembered that this is not NIT srinagar(My B tech college). It is one of the most prestigious IITs. How naive of me to underestimate its campus area. While I was thinking all this an auto came from inside the campus. The guard stop that auto and asked him to take me to the hostel. I reached the hostel and told the receptionist that I have come for M tech interview. I was asked to pay Rs800 for two day day boarding and mess facility usage. I was then allotted a room. I met some other candidates and spent the whole day roaming here and there.

On the day of interview first there was a briefing in which Professor Sarangi gave us details about the interview process. Points from the briefing:

• A candidate has to score at least 7 points out of 10 in the interview to be even considered for M tech programme.
• A candidate has to score at least 9 points out of 10 in the interview to be considered for MSR programme.
• Weightage given to GATE score would be 70 percent. 30 percent weightage would be given to interview.
• Even if only 10 candidates qualify the interview, IITD would proceed with only those 10 candidates. No compromise on quality and no waiting list.

After this we were asked to sit inside a waiting room. My turn came in the very last. I entered the interview room to find 3 people sitting there. I greeted them and they asked me to take a seat. After this the 1st person asked the following questions:

1. What is quicksort?
2. Can you find the kth largest element in an array using the approach taken by quicksort?
3. Write the code for that algorithm?
4. A rectangular grid was drawn and I have to find the number of paths from one corner to another?
5. Write code for printing all paths in question 4?
6. Find the recurrence relation for the recursive solution that I wrote for Question 5?

I was able to answer all questions completely except question 3 where the professor confused me and then I got stuck.

The first professor was satisfied. After this the 2nd professor asked

1. Give the mathematical proof for If a number is divisible by 3 then the sum of digits must me divisible by 3 ?

I said I don’t know and then he asked the 3rd professor to ask questions?

1. He explained a processor (which can have infinite number of cores) and then told about a program where the sequential part is 20 percent and rest is parallel. He then asked to find the minimum number of cores required to achieve 10 times speed up?( A tricky one)
2. My answer to first question made him happy. He made some changes to the above question and asked me to solve the question. I don’t remember that question now. This was the last question of the interview.

Result: selected for M Tech but joined IITB.

250 students got interview call for the 2nd round, out of which finally 7 got selected for this program.
Shortlisting criteria

3 rounds were taken- Aptitude test(about 23 got shortlisted, about 100 showed up), 1st Interview(13 got shortlisted) and in final interview 7 got offers.

1. Aptitude was an easier version of gate(only technical aptitude).

2. Two professors were there, who asked me for my CV(seldom it happens). They asked for my introduction and I think they were a bit impressed with that.
They asked what I did in 2017, after passing out and various general questions like why I didn't attempt Gate in 2017, did I take any coaching, etc.
After that, they asked me an algorithm question and told me to explain my logic on board. They asked me to calculate the time complexity of the solution I suggested. They looked a bit satisfied.

They then moved to Networks and asked lots of questions. The questions were a little bit practical rather than theories we have gone through while Gate preparation. Since I was not really good with that, I tried to explain whatever I knew and admitted that I don't have that much of practical knowledge(I would advice to not directly jump on to this "I don't know" thing).

They asked me questions related to OS like multithreading, multiprogramming, implementation of multithreading with socket programming, practical examples of where these techniques are used.
They also asked me to rate myself in coding out of 10 and about what was the biggest/challenging code I have ever written.

My interview lasted about 15-20 minutes and was not expecting to get shortlisted.
Results came and then here starts last round.

3. Three professors gave a small introduction to projects they were having vacancies in. We were supposed to enter our preferences.
Then the interview started and they asked me different questions related to core subjects the projects were in like- Networks, Compiler, and Computer Architecture.
I was asked if I have any other calls and I told them about IIITA. Since the offer acceptance date of IIITA and interview date of IITH were clashing, I took a risk.
(non-refundable 40K were already paid in NSR round, that is another part).
They asked me various HR type questions like about my preferences, etc. And they looked quite happy with my answers. (This time I didn't have any gut feeling of rejection).

Just the next day, results got announced and finally, 7 people got offers and efforts finally paid off!

Since I have gone through a long journey, before this little success, I have some suggestions for those who are willing to get through.
Ps. Toppers' suggestions can help you better to score exceptional, mine can just add on to them so that journey becomes worth remembering.

My suggestions would be:
1. Not to quit in between. Here I am talking about starting with full enthusiasm and planning to reattempt even before attempting.

2. No matter what comes to your way, don't ever lose your hope. Keep faith even when everybody loses it.

3. There is no substitute for hard work.

4. Hope in every opportunity that comes to your way, maybe that is where you belong.

I will try writing a blog on GO/ Quora about this journey, where an average scorer landed up in the best.
I wish you all the luck. Thanks for reading

GATE Score: 604

Rank: 1644

Category: GEN

There was a written test followed by the interviews. Only the candidates who cleared the written were eligible for the interviews. Around 50 students appeared for the written test on 26th November.

Written Test:

The difficulty of the test was comparable to that of the GATE exam (although there were some extra topics). There were questions from Algorithms, Programming, Compiler Design, Probability, Linear Algebra and also some (around 5) questions from Machine Learning. There were 20 total questions. A blank paper sheet was also provided for doing rough work.

(Trying my best to recollect the questions)

1. Algorithms Question => Related to the worst case and the average case of the Quicksort algorithm. (There were some cases and the correct option was to be selected)
    
2. Evaluate a prefix expression.
    
3. A question from compiler design => What is a+++b? 
    
4. Machine Learning Question => What will happen if we increase “k” in K-means clustering? (I don’t remember the exact options but they were related to variance and bias. I was able to answer.) 
    
5. Machine Learning Question based on Classification => Minimum number of one-vs-one classifiers required to classify 6 classes? (Multiple options.  Answer: 15)
    
6. Machine Learning Question => Which ML algorithm will be used to predict the number of calls in a call center based on previous data? (Multiple options. Answer: Linear Regression)
    
7. A question related to parallelization of 2 code segments. Two loops were given where we had to tell which of those 2 can be parallelized.
    
8. Some questions on probability.
    
9. A couple of questions on linear algebra.

(Sorry! That’s all I remember)

I answered around 15 questions and got shortlisted for the interview round. 20 candidates were selected for the interview rounds.

The Subjective test:

This test was only meant for the interviews. It was not to be used as a shortlisting criterion for the interviews. There were 2 questions, one on designing an algorithm and other related to distributions in probability.

I was only able to answer the algorithm question. The question is as follows:

Question:

A person is stuck on a square island which can be represented using an NxN matrix M. The person is allowed to take n steps. In a single step the person can move in either direction. The person dies if he steps out of the island. Give an algorithm to compute the probability that the person will stay alive after taking n steps.

The Interview:

My first interview panel had 2 professors.

Interviewer 1 (from Compilers background): Tell us about yourself.

Me: Told about myself. About projects I have done in the past, my research interests, etc.

Interviewer 1: Okay! So you have answered the question related to parallelization (in the written test, it was the correct answer). * He stood up and wrote those 2 code segments on the board *. Can you explain?

Me: I explained why one code segment can be parallelized and why the other one cannot be parallelized.

Interviewer 1: What is the order of parallelization in terms of big-oh?

Me: O(N). It was a for loop running N times. Each run was independent,

 * Some more discussion on why the other one cannot be parallelized *

Interviewer 1: * wrote another question from the written test and asked me to explain *. The question was the evaluation of a+++b.

Me: I told him how it will work. Gave him Finite State Machines for it. He was quite impressed.

Interviewer 1: Okay! What about a++++b?

Me: Explained.

Interviewer 1: And what about a+++++b?

Me:  * At this point, I was like, what?* I tried to explain as much as I could. He was satisfied.

Interviewer 1: He then gave me some languages and asked which machines (FA, PDA or TM) can accept them?

Me: answered.

Interviewer 1: Asked about my BE project and what algorithms I used in it.

Me: I answered.

Interviewer 1: Okay! We are done.

Interviewer 2 (from Computer Architecture background): * Finally broke his silence * Are you interested in answering CSO questions.

Me: I told him that I’m not good with that subject.

Result:

Selected. I received the offer letter on 20th December.

I got selected in IIT Kanpur, and this is the reason why I started preparation for GATE in the first place, so for me, this is pretty much the same as getting AIR-1 in GATE, This was made possible only because of my brothers, whole GO community and specially Astitva[It feels like for 2 years we’re only discussing questions and concepts together]

About me: https://jun03.github.io/portfolio/

GATE 2019: marks- 63.33, Rank – 582[In 2018 at marks 63.33 rank was 176, you can imagine what will happen in 2020]
IIT M: Did not qualify the written test

IIT K: Selected in MS

Cleared written of BARC(Preparing for Interview).

Post GATE :  

Did all coding assignments(Special thanks to Digvijay sir), participated in codechef competitions, got back on Hackerrank, Completely read OS:3 easy pieces with its homework assignments, revised GATE concepts, I used to collect questions and take Astitva’s interview and he did same for me (It was really helpful)

Written Test: Logical questions mostly which check your understanding, ex: Program whose output is based on endianness of system, order of socket primitives, etc.

Programming - 3 Questions[Main program(40 points) was to complete function to input and merge two sorted linked list], All were easy- finished them in 1 hour while given time was 2 hours

Interview: My interview was comparatively shorter than others 10-15 minutes
They asked me to take a seat, then sir said: So you're a system guy, huh? I said yes[I don't know why but a cool dude voice in my head said: Yeah, I'm a system guy, It kinda felt nice to hear something like this], then they asked about my college, I mentioned name - they asked me twice to confirm because maybe they hadn't heard of such a college name before, they asked me about programming test, I said I completed those before time and passed both hidden and visible test cases,then a couple of general question then it started:
P- professor, A - me
P: Asked for preferred subject
A: Operating System
P: What are the major projects you have done in OS, or what work you have done related to OS
A: I haven't done any major projects in OS, but I have made programs to emulate various activities of O.S. like scheduling algorithms, calculating cache misses, calculating various cache sizes, etc.
P: In which language you wrote these emulators
A: I said mostly C but have used python for some complex ones.
P: Why have you used Python
A: Because it's relatively easier to write a program in Python than in C.
Then a few general questions about Python like why it is slow etc, I answered correctly.
NOW COMES THE MAJOR QUESTION
P: Suppose you have an already compiled program as an object file and you have to run it in this laptop and what I did is that I removed OS from it, will you be able to run it?
A: No sir[I was thinking correctly like running such a program would require O.S. support but got tricked in his next statement]
P: OS is also a program right, written in C and Assembly, How does it run?
A: Explained about the bootloader.
Some discussion on how bootloader will run, what is firmware code[I'm not describing it much because it went quickly and I don't remember exactly]
P: So coming back to the original question- we can run this program without OS rt?
A: Yes sir, we just need to place it in the disk at the location where O.S. normally reside and it will run
P: But this program is compiled in an environment with OS, i.e, Virtual memory and for address translation and some other stuff it'll need OS, right?
A: Yes sir, It'll not be able to run without OS support.
P: What will happen exactly- tell me that
A: It'll try to access virtual address which can be invalid.
P: What will happen exactly when it'll try to do so?
A: A trap would be generated[I wasn't sure so I kinda said in a low tone]
P: What?
A: Sir the Hardware will generate a trap
P: Okay, He asked with other Professor if he wanted to ask, but they agreed that it's ok, and they asked me to leave.

At that time I wasn't sure whether it was a good interview or bad[I still don't], but the only thought in my head was - What about threading, implementation of scheduling algorithms etc- the stuff I read so much about, why didn't they asked anything on that, but that's the thing these Interviews don't need you to do/know a lot- just make sure you really understand what you know and be smart[like adaptable to different situations]

Pro tip: Decide your subjects(At least 2) from now and for that, you need to decide which type of work you want to do, It'll help you a lot if you have done some work related to this subject/field. At least I would say for these two subjects you should study proofs[If theory based] or Implementation code and some tools[System side]. If you want to be in AI/ML, among other things, prepare Maths definitely and don't just practice blindly- try to get an understanding of things like what is matrix multiplication, what is the reason for calculating things like Eigenvalues, Eigen-vectors, etc. Do visit the IITs CS department website

IIT, Kanpur GATE Overflow Interview Experience Blog Links: 2015 to 2020

IIT, Kanpur Other Interview Experience Blog Links: 2011 to 2019

This is the rough work I did during the interview, the question were added in a separate post (https://gateoverflow.in/blog/10800/iisc-csa-research-interview-questions)  as I did not want to reveal hints in the original post (perhaps open the questions side by side to make sense of the following rough work)

CSA prof 1 (not everything is correct in my solution): 

CSA prof 2 (not everything is complete in my rough work):
 

Feel free to ask in the comments, I am sure, some of the answers are not complete as the prof. just asked to explain some bits instead of writing everything down. 

I scored 806 in GATE CSE 2018 and got rank 176.
I applied to IITD(MTech and MS both), IITK(MTech), IITB(TA and RA both), IITKgp, IITM and IISC.

IITKgp, IITM and IITB(TA) offer direct admissions. I received an offer from IITKgp in the 2nd round of COAP and I chose to Retain and Wait. I did not participate in the 4th round to find out if I received an offer from IITM. No offer from IITB(TA).

I received Interview calls from IITD(both MTech and MS, cutoff 800 for both GEN source), IITK(MTech cutoff 725 GEN source), IITB(RA). I did not receive any interview calls from IISC even though the cutoff was 800 source.

IITK Onsite Experience (Admissions Website with all info)
The onsite exams for MTech consisted of-

1. Written Test (Syllabus)
2. Programming Test (Syllabus)

For MS, there was an additional Interview round scheduled on the next day.
There is a detailed GO post listing the questions of the Written test and the Programming test. Also a post for MS Interview experience.
I prepared the Theory Section for the written test, although it is advisable to prepare for Systems, since it has only 6 topics(compared to 11 for Theory) and they are exclusively from the GATE Syllabus. I think my written test went well, but I do not remember any of the questions. Both sections had some common questions from Algorithms, Data Structures, Logic, Math.

The Programming test was way too easy this year. I was able to finish it in half an hour, where the alloted time was two hours. But do not expect the programming test to be this easy next year. There is no fixed pattern whatsoever in case of Onsite exams. Until last year, Onsites for MTech included an Interview as well, but this time that was not the case.
Overall I was confident that my Onsite exams went well.

Results came out on 23rd May, and around 77 people were offered MTech admissions and 20 or so were offered MS admssions. For exact numbers visit the results section of the IITK PG admissions site.
I was waitlisted at the 2nd position in the General Category.

After COAP Round-2 ended on 9th June, my name was shifted from the waitlist and I was offered admission for MTech at IITK. 2 other General Category students got shifted from the waitlist alongwith 2 OBC and 2 SC/ST category students, for a total of 7. Follow this link for information on further rounds.

Edit: IITK MTech Last Waitlist Number 2018-
1. GEN- 15
2. OBC- 9
3. SC- 7

IITD Interview Experience
The interviews for MS and MTech at IITD were scheduled on 23rd and 24th May. My interview was scheduled on 23rd May. Prof. Sarangi told us that this year the intake for MS and MTech will be less than last year. Needless to say the anxiety level in the room rose manifold.
The Interview started with them (3 Professors) asking me a few things about myself. Then they moved on to the questions-

1. Proof of Correctness of Kruskal's Algorithm
2. Proof of "Divisibility by 3 test"
3. They provided a Code and asked to find errors.
4. Asked Binary Search Recursive Code, and questions on that.

Please note that while preparing for interviews at IIT's, it is important to focus on the Basics and Technical aspects rather than having an intuition of how things work. For Example, having a general idea of the algorithms will not take you very far in the interviews, What they need is Proof of Correctness, Time Complexity derivations and other relevant stuff. Focus more on knowing Why and How an Algorithm works, taking into consideration all the data structures used.

IITD released their offers for MCS(code for MTech) in the 3rd round of COAP(source at the end there is a list of offers released in each round). Around 40 people have been offered admissions in MTech at IITD, 0 MSR offers(source). I received the offer letter for MCS(MTech) at IITD after COAP 2nd round ended on 9th June.

I did not attend IITB(RA) interviews scheduled on 17th May, since I wanted to complete my Masters in 2 years.

Overall I had to choose between IITD, IITK and IITKgp for MTech Admission. These were the offers I received in the 3rd Round of COAP on 16th June-



Final Decision - IITD MTech

This Year IIT Delhi kept the same cutoff for MTech and M S students, and the Interview was conducted in two days i.e on 23^rd May and 24^th May,Around 200 students were called according to the list given by them,the candidates with even registration number were called on 24^th May and mine one was even too, 

Pre-Interview Introduction to MCS and MSR course:

It was given by Smruti Ranjan Sarangi sir, he told us how the procedure of interview will be going, he mentioned that

"70% of the total marks assigned will be on the basis of GATE Score and remaining 30% will be on the basis of how well you perform in the interviews,since majority of you have almost same score, so interview will be a deciding factor for your admission"

"Interview scores will be given internally on the scale of 10 and to eligible you must have at least a score of 7"

"MSR will be our premier course so whoever have appeared must have the score of 9 to get eligible for MSR"

"Interview can long from 2 minutes to 20 minutes depending on the response of the student" 

"Interview will be conducted on different panels according to the alphabetic order"

Interview

My panel was examined by Prof. Rijurekha Sen mam and Prof. Parag Singla Sir.

Our conversation went on like this

Prof.1(Looking to the records of mine):So,You are in Final year right?

Me:Yes mam.

Prof.1:What is your favourite subject?

Me:Networking and Algorithms.

Prof.1: Okay, can you tell me what all problems can be faced in a LAN in data link layer?

Me:Collision and channel access related problems might be there.

Prof.1: Can you tell me how collison can be detected and solved?

Me: Explained about the increase in frequency and jamming signal.

Prof.1:Okay what is this technique called?

Me:CSMA/CD.

Prof.1:Do wireless LANs use the same?

Me: No,mam I think it uses CSMA/CA.

Prof.1:Do you want to answer some questions on probablity?

Me(shaking head to say no as I was not confident about that subject:p):No mam.

Prof.1 saying to prof. 2:"Algorithms aur networking bola tha isne to topic of interest me" (means he said he is interested in Algorithms and networking)

(Now Prof. 2 started asking the questions)

Prof.2: can you make a program to find weather the number is prime?

Me(given whiteboard and made the program like this):

boolen isprime(int n){

for(int i=2;i*i<=n;i++)

if(n%i==0)

return false;

return true;

}

 

Prof.2: why did you wrote i*i?

Me:sir,since we only need to check till square root of n.

Prof.2:Can you prove it?

.....................................................Thinking for a while but couldn't answer it....................................................

Prof.2(Coming near to the blackboard and drawing crossroad)

:

he gave me the problem like this

• you are given a task to find treasure that is situated in any one of the direction, and you need to devise an efficient algorithm.
• you are currently at the centre of the crossroad.
• all the paths are infinitely long,so you need to take that in mind, travelling in any one one direction won't work.

Me(Thinking for a while and thinking deep inside that what kind of problem is this suddenly an idea came into my mind): Sir can we perform an operation in Breadth first manner?

Prof.2:can you explain?

Me(drawing lines on the diagram like this)

:

if we divide the road into uniform length partitions and traverse a unit distance at the first time,in each direct and 2*unit distance at the second time and so on.....

Prof:Okay, can you find its complexity, if the treasure is at k distance from centre?

Me(On blackboard): 

8*(1+2+3+.......+k)=4k(k+1)=O(k²)

Prof.2: Can you make it more efficient?

Me:(NO CLUE TILL 2-3 minutes then he gave me some hint that to increase it exponentially) and I got the catch,and now it was like

8(1+2+4+8+16+32+.....+2^logk)=16*2^logk =O(k)

Prof.2 :yes, this how it is solved.

I was happy that interview was good enough

Things which I noted during IITD interview:

• you should be good enough with algorithms, to deal with problems they give.
• even if you say CSO or Networking is your favourite subject they will ask question from algorithms so, better say algorithm from your side too.
• they emphsize on formal mathematics proofs,so be prepared for that.
• profs. are friendly enough so no need to get tensed.

Verdict:-Selected :) 

Interview Experience for M.Tech. RA A.I. in I.I.T. Hyderabad

My interview was in July, 2020. It was conducted on google meet online due to COVID-19 pandemic. There were two rounds of interview. the first round was in the morning and second round was conducted on the same day after 3:30 pm.

Round 1:

I don’t remember the faculty name but there were 2 teachers in my panel.

P1: Introduce yourself and tell the topics of your interest in basic mathematics.

I was confused with basic mathematics and told Linear Algebra. But then the clarified and asked mathematical topics from class 9th and 10th like lines, triangles, etc. Then I choose geometry.

Ques1. Draw a graph of mod(x) + mod(y) = 1

Initially I drew it wrong as a circle but later I corrected it as a square.

They asked if I was comfortable in probability, though i never revised after GATE but had no other option and said yes

Ques 2: If you are given a bag in which you have 6 white balls and 4 black balls and you draw a ball and it is known as black and you throw it away. Now tell the probability of getting a black ball.

I tried solving it using Bayes theorem initially, but prof confused me if I already know that the ball was black then why are we using conditional probability. At that moment I got confused and choose 3/9 as my answer.

Ques 3: what is uniform distribution?

I defined both continuous and discrete distributions as I could not remember uniform distribution so later prof asked me to draw the graph of uniform distribution between -a to a. I could not draw at that time.

Later result was out around 2pm and I got selected for round 2

Round 2 Panel included 3 teachers: Prof Maunendra, Prof P. K. Srijith and Prof P. RAJALAKSHMI.

I was asked about my educational background and any project or course that I have done in BTech or otherwise related to Artificial Intelligence or Machine Learning.

I told about my BTech final year project as an application of NLP and they asked further details about the same.

I also mentioned doing one course on NLP so he asked me about my learning from the course and few questions related to that.

Later he gave me a question on probability which was as follows:

Ques1: If a company decides to have a lottery and distributes 50 tickets at Rs 10 each and there is a probability of winning as 0.2, also on winning the company gives Rs 40 to every winner (there can be more than one winner) then what is the total profit for the company and Is that profit fixed or can be changed?

I answered 100 and fixed( which i later guess was wrong ans this 100 would be the max probable value for profit but it can change).

Ques 2: The next question was to tell the difference between quicksort, insertion sort, selection sort and mergesort

I told that Merge sort is not in-place and uses O(N) space complexity while other algorithms change in the same data structure and has O(1) space complexity.

After 2 days we got the list of available projects and we filled our preferences. The selection was based on preference and performance in the interview.

Result: Not selected

Tip: Prepare probability and at least know few names of algorithms in ML. That will show your interest in the field. I only prepared Data structures and Algorithms and they asked only 1 question from that.

2020 GATE Overflow Interview Experience Links.

2020 Other Interview Experience Links

Greetings to all, I am Jay Gorakhiya and this blog is about my MS Interview experience. Below is my GATE result details

Rank : 229

Score: 757

Category : GEN

First of all, with this score one can get admission in MTech in IIT G / KGP / R but still I had applied for MS (Research) in IIT Madras , Bombay and Delhi and had given interviews of Bombay and Madras.

This year (2023), IIT Madras had 2 rounds of Interviews, First round ( shortlisting criteria was GATE score ) was like a common round where interview was on one of the topics from Discrete Maths OR C programming ( or Programming )in general. Students were shortlisted for round2 on the basis of performance in round1. Second round was panel specific round (3 panels; A. Theoritical Computer Science, B. Computer Systems, C. Intelligent Systems ) and students shortlisted from round1 were given a google form to fill their preference of panels. Interview in first 2 panels of preference was to be conducted. Final selection was made on the basis of performance in round2. Both rounds were online through Google Meet.

=================================== ROUND 1 ===================================

There was only 1 professor who interviewed me in round 1. The prof. was very nice and kind to me. He asked my name and from where i was and how was i feeling etc. Overall, he was very polite and quiet and made me feel comfortable before starting the interview. Interview went like this :

Prof. : What is your choice of subject? between Discrete Maths & Programming.

Me : As such there’s no preference but I’ll go with Programming.

Prof. : Write a program that tells whether a number is perfect number or not? (He then shared a link of an editor to write the code, which he could also see without me sharing the screen.)

Me : what is the definition of a perfect number? (I asked for definition, even though i knew it)

Prof. : a number is a perfect number if sum of its divisors (less than the number) is equal to the number itself.

Me : Okay (then I started writing the code, which was fairly simple)

( always speak aloud what you are thinking and what code you are writing while writing the code to interviewer )

Prof. : What is the Time Complexity of the Code?

Me : O(N) ( as the code had linear time complexity)

Prof. : Can you reduce the Number of Comparisions? or Can you eliminate redundant Comparisions??

Me : ( I gave some ans which was not 100% correct, was just beating around the bush )

( Actual ans was, we can run for loop upto n/2 instead of running it upto n as no divisor of n is greater than n/2 , which i realized after the interview 🙂 )

He then asked me some Questions on basic data structuers like arrays.

Prof. : You know array data structuers, right?

Me : Yes sir.

Prof. : What is the time complexity to find an element from the array?

Me : there are 2 algos, if linear search if the array is not sorted O(n) and binary search if the array is sorted O(logn).

Prof. : We do not know, if it is sorted or not i.e not neccasarily sorted array then what will you use?

Me : Linear Search.

Prof. : Can you decrease number of comparisons done in linear search while TC remains same O(N)?

Me : (first i explained the normal code of linear search )…( thought for some seconds, then he reframed the question )

Prof. : There are  2 key comparisons; first is whether we have reached array end or not? and second whether the current element is the element we are looking for? Can you eliminate any one of the comparision??

Me : we cannot eliminate second comparison because if we removed it then we wont be able to ‘search’ for a particular element, so we can try to eliminate first one. ( then i was thinking and then prof gave me a hint)

Prof. : What if we can change the input a little? What if we add the element which we are looking for at the end of the array then can we eliminate end of array comparison?

Me : (I gave some ans here and there but they were not correct) 

Finally, professor told me to think on the question afterwards and my round1 interview was over. Interview was around 10-15 mins. Round 1 results were out by the night and i was shortlisted for round 2. I had selected panel B (Computer Systems) and panel C (Intelligent Systems) but gave interview only for panel B as i was more confident in that.

=================================== ROUND 2 ===================================

In round2, there were 2 professors but only one of them asked questions. My choice of subject in computer systems panel was Operating Systems. Again, the professor was very nice to me, made me feel comfortable. I don’t remember all the questions exactly, so i am listing down questions which i remember.

1. What different types of OS do you know and have used?
   (from there he jumped to uniprocessor multiprogramming OS ; as in GATE syllabus)
2. What is scheduling? What are the CPU scheduling algorithms you know?
3. What is context switch? How does it happen? (asked me to explain step by step what happens during a context switch)
   He went to ask in much detail like:
   1. who loads and save PCBs of the processes?
   2. before the context switch a user process is runnning on processor, so how does OS takes control of the processor during context switch? ans : through interrupt.
   3. who / which component interrupts the processor? etc
      (from there he jumped to Interrupts and System Calls)
4. What is ISR, vectored interrupt? How does the Computer know which routine is for which interrupt?
5. What is System call? Difference between an interrupt and a system call?
6. Do we need an interrupt for executing a system call? etc

From there on the prof. began I got a bit confused and afterwards he ended my interview. Interview went for around 15-20 minutes. At last the prof. gave me a remark that first part of my answers were good (scheduling and context switch ones), that made me feel good that IIT professor thinks my ans is good 😄.  After few days, results were out and I was selected for MS (Research) in computer systems at IIT Madras. I eventually rejected the offer as I finally accepted MTech RA IITB.

So, this was my interview experience. Hope you find it helpful. Kudos to you if you’ve reached this far reading as the blog was a bit long. 

ALL THE BEST.

IITD MS CSE Interview Experience.
 

There was a programming test before the interview – 5 questions, Codechef style. Here are the questions:

https://docs.google.com/document/d/1Okxf7GKKIuoxLUZzmNfVsAIv8EDaUrtXTwzT_8L27Es/edit?fbclid=IwAR0fugnsW9-Gb4tCzNCUa0fuim1BzOSoa_BQIQ0FSTjYBwXUTZAwSB9T3VA

Out of 300 odd people who appeared for the test, 80 were shortlisted for the interviews. I managed to solve two problems completely (200/500), and my rank was 31 out of the 300 odd people and hence was called for the interview. 




The meeting was on Microsoft Teams, they had said they might call anytime between 3 pm to 5:30 pm. My turn came around 4:15 pm.

There were 8 professors, out of which 4 asked me questions. They were:

Prof Smriti Sarangi (CompArch), Prof Sorav Bansal (Compilers, OS), Prof Priti Ranjan Panda (Embedded Systems) and Prof Subodh Kumar (HPC, Parallel Programming).

They read out my bio, my interests (Computer Architecture, Operating Systems) and started asking one by one.

SS: So you're interested in COA, what all topics are comfortable in?

Ans: Sir, caches, pipelining, performance metrics etc.

SS: How do you define performance? How is it related with frequency?

Ans: Performance is inversely proportional to execution time, but in overall performance frequency is one component - we need to know insts, CPI and frequency - which I elaborated with the standard equation.

Then he asked me a bunch of questions related to pipelining (how do stalls affect CPI, how do you mitigate them,etc etc), which I don't remember as they were mostly extensions of one question after another.

SS: Okay, if I want to increase performance, what's stopping me from using a 1000 GHz processor?

Ans: Sir, if you increase the frequency, the amount of time will decrease so in a small unit of time, I guess much work can't be done. It'll also lead to increase in power, for which you'll need an efficient cooling system.

SS: Okay, your answer is 75 % right. What else could be the reason?

Ans: [Thought for a while] Sir, latching would be a problem too. In too small a clock cycle, you won't be able to latch to take it from one stage to another.

[He was satisfied now.]

SS: Okay, suppose you have a computer which only has a processor and RAM, can you still make it work without a disk, from some other computer's memory?

Ans: I said yes sir, I've read about how you can remotely boot an OS so in a similar way, maybe we can use a protocol which might allow you to access the data from a remote location.

SS: Yes, you are correct. Such a protocol exists and it's called RDMA.

SS: Okay, I'll ask you one last trick question, just say yes or no, don't elaborate - suppose you have infinite physical memory, do you still need virtual memory? Ans: Yes sir, because we still need isolation which is an important component of modern day OSes.

SS: Okay, elaborate that [wtf? you said don’t elaborate] Ans: Then I explained him VAS, PAS and all that stuff.

Next, Prof Sorav started asking questions. He asked a bunch of questions about how the page table, cache and memory interact with each other, which I was able to answer well. Then he asked some convoluted question, which I think I was unable to understand properly as I gave him some other answer, then he realised okay I think we’re not able to get through the question properly.

SB: Have you heard about huge pages? What are they?

Ans: Yes sir, huge pages are used when you need pages which are much larger than 4 KB or the default size. Linux uses something called as THP (Transparent Huge Pages).

SB: Okay, can you elaborate what is that?

Ans: Sir, the TLB stores VA-PA mappings and since it’s a cache, it has to be small. But at the same time, we want to increase our TLB reach, so that we have lesser thrashing of the TLB itself.

As I was further explaining, he stopped me and said Okay, I’ve got the answer that I need.

Then Prof Priti Panda.

PP: You mentioned critical path somewhere when we were talking about caches, can you elaborate what is that?

Ans: it’s the path which takes the longest time to execute in a circuit etc etc.

PP: Okay, so suppose we need to formulate this is a problem and design an algorithm to find the critical path, how would you do that?

Ans: I was a bit stumped, and suggested some methods, then I asked if he wants a particular data structure to which he said yes, then I said maybe we can use graphs sir where the nodes are the gates and the weights of the edges are the timing delays of that particular gate.

PP: So do you mean all the outgoing edges of a gate will have the same delay?

Ans: Not sure, but I guess yes sir.

He didn’t seem much satisfied, but whatever, he said I am done and we moved on to professor Subodh. He only asked me one question - given a BST and [a.b], how will you print all the numbers between it? (yes, the same GATE 2020 question.) We had a 10 minute discussion on it as I knew the overall approach, but not the fine details of it.

And that was it.

Overall, it was an okay interview - I guess average. Some questions were hit, some were miss.

They did ask me which subjects I was interested in (could be also because I had talked to Smriti sir before the interviews and he had told me he’ll ask me CompArch)

Platform: Hackerearth

Maximum Score: 50.0

7 General MCQs (5.0 marks each)

1. There is lockdown due to covid.

   Ram and Gopal have decided to meet at a bus stop between 2PM to 3PM. At the bus stop a person can wait only upto 15 minutes.

   If a person comes to the bus stop, he will wait for 15 minutes, or upto 3 PM, or till the other person comes up, whichever event happens earlier.

   What is the probability that Ram gets covid given that Gopal is covid positive?

   a. 3/4

   b. 3/16

   c. 1/4

   d. 13/16

2. Consider 3 equations -

   $x-y+2z = 1$

   $2x-y+7z=2$

   $-x+2y+z=b$

   where 'b' is an integer. Which of the following is true?

   a. The system has no solution if b=-1

   b. The system has more than one solution if b=-2

   c. The system has no solution if b=3

   d. None of the above

3. Given a spam email detector. It detects if the email is spam or not by checking the subject line "Read this email!". If the subject line matches then the email is detected as a spam.

   It is known that 4 out of 10 emails are spam.

   1 percent of the spam emails have the subject line "Read this email!"

   1 out of 250 non-spam emails have the subject line "Read this email!"

   Find the probability that an email is spam given that spam detector marked it as spam?

   a. 0.33

   b. 0.625

   c. 0.25

   d. 0.0125

4. Given two column vectors u and v of size n each.

   $W = uv^T + vu^T$

   $X=u^Tv+v^Tu$

   Which of the following statement is true?

   a. The matrix W and matrix X are scalar.

   b. The matrix W is a scalar and X is nxn.

   c. The matrix W is always symmetric and nxn and X is a scalar.

   d. The matrix W is nxn and X is a scalar.

5. Given a program to print the nth fibonacci number.

   *A simple program to print the nth fibonacci number was given.*
   

   What is the time complexity to find fib(n)?

   a. O(n)

   b. O(n^2) – This was an error in the options, it should be O(2^n)

   c. O(logn)

   d. O(nlogn)

6. Given $u=[a \ b \ c]^T$ and $A=\begin{bmatrix} a^2 & ab & ac \\ ab & b^2 & bc \\ ac & bc & c^2 \end{bmatrix}$is a 3x3 matrix $A=uu^T$. Given that a, b, c are all non zero real numbers. Which of the following statement is true about matrix A?

   a. The matrix has three nonzero eigen values.

   b. The matrix has two complex and one real eigen value.

   c. The matrix has exactly two nonzero eigen values.

   d. The matrix has exactly one nonzero eigen value.

7. Given a graph of a function f(x).

   The graph of $f(x-1) + f(x-4)$ will be:

2 Programming Questions

1. Write a program to print the given matrix in clockwise spiral order. (10 marks)

2. Write a program to check if a matrix is diagonally dominant. (5 marks)

   A matrix is diagonally dominant if for every row of the matrix, the magnitude of diagonal element is greater than or equal to the sum of magnitude of all non-diagonal elements of that row.

   Note: The matrix contains values of type float.