Recent posts in Interview Experience

I wrote a blog on quora about my written test and interview experience at IIT Madras. Hope it helps next year aspirants.
https://sktdt.quora.com/IIT-Madras-MS-CSE-Written-test-and-interview

Edit: IIT Delhi M.Tech. in Computer Technology(EET) Interview

https://sktdt.quora.com/IIT-Delhi-M-Tech-in-Computer-Technology-EET-Interview

IISc CSA Intelligent Systems (M.Tech Research) Written Test and Interview

https://sktdt.quora.com/IISc-CSA-Intelligent-Systems-M-Tech-Research-Written-Test-and-Interview

IIIT-Sricity conducted written test and interview for MS (Research) and Ph.D. programme.  I applied for MS (Research). The selection for written was based on Academic Records and work experience.

 

 

Written Test:
The written test had 6 question from CSE and 6 questions from ECE. CSE questions were from Maths (LA, Probability) and Core Computer Science (Programming, Recursion, Database, Logic). The questions were descriptive and we had to explain the solution in detail. I was surprised by the fact that the question paper for MS and Ph.D. was same.

Around 30 students have attended the interview. After the written test, 7 students were shortlisted for interview in CSE, 11 for ECE.

 

 

Interview:
1. Introduce yourself
2. What are you good at?

3. What is Machine Learning?

4. Given a system with 8GB RAM, how many linked-list elements comprising of an int and char can you dynamically create?

(I answered this in number and later realized that it was a trick question to see concepts of OS, so I immediately changed my answer)

5. Write the solution of the classic GCD problem using recursion?
6. Now write it without recursion (because I did mistake in question 4)

7. We know that the merge procedure takes O(n) space-time? Can you give a solution to improve it further from O(n) to something less than O(n)?

8. At what pivot position do you think the Quicksort will work best? (trick again)

9. Explain some sorting algorithm that sorts in less than O(nlogn), preferably O(n) or O(1)

10. Given a set of words, sort them and assign ranks to them. Find the word with 7th rank.

(I don't remember this question exactly, but I tried solving it using python dictionary data structure. They were not impressed and told that there is no data structure called dictionary when it comes to research. Which means I had to solve it using standard data structures. I tried using hash-table etc. But they were not impressed with it either )

11. What is supervised and unsupervised machine learning?

Okay, you can go now. Thank you.

M.Tech. in Computer Technology is offered by Department of Electrical Engineering IIT Delhi.You can check the course structure here.

Since the course offers many Computer Science subjects and even Machine Learning as its major component ,many cs students opt for this course.

Now, coming  to the interview day.We were required to report there at 8:30 am.First our documents were verified and then we were called for the interview one by one.

Since,it is somewhat an interdisciplinary course the interview panel was sort of divided.I think there were 4 professors taking the interviews and they were the ones who taught M.Tech. students there.Out of four,1 professor was majorly asking questions in Electrical and Electronics field,1 was asking System subjects in CS like Operating system and CO & architecture,1 was asking majorly in Machine Learning plus question on the subjects you mention that you have prepared and last one in Data structures and algorithms plus Discrete Maths.

Students in interview mainly came from 4 branches : Electrical,Electronics,Computer Science and Instrumentation.

Now, the interview was conducted in a room where the 4 professors were sitting separately and there was a chair for the candidate to sit.Out of the four we had to appear for the interview to any one of the professors,here I would really like to thank the TAs there ,they were very helpful and were assigning the candidates to the professors ,so they made sure that you get the professor of you area only.

Before the interview each one of us was given a blank sheet of paper in which we were required to write our Name and Application number,this sheet was to be used for doing the work during the interview.

My interview started around 7p.m. and lasted for about 30-35 minutes.I was allotted to Sumit Sir,who was asking questions in Data Structures and Algorithms plus Discrete Maths.Before going for the interview we were even handed over our application form.

As I entered the room ,sir first asked for my Application and gave it a look.He noted the stream I graduated in,my GATE score and year,my B.Tech.percentage and since I graduated last year he asked me what I did the previous year. 

After this he asked the following questions:

PS : He wrote the questions in the rough sheet given to us earlier and we were required to write neatly our solutions there.This sheet was later kept by them.

For each question he gave me sufficient time.

Q1) P&C Consider the numbers {2,4,6,8}.How many 6 digits numbers can be formed from them that are divisible by four and repetition is allowed.We were required to compute the exact answer.

Q2) Probability Consider we have 3 doors A, B and C.Out of the three doors 2 have goat behind them and one have a car.We are playing a game here,

1) The contestant comes and picks up a door.

2) Out of the remaining two doors,the game in-charge eliminates one door and that door is sure to have a goat behind it.

3)Now, the contestant has 2 options either stick to the door he choosed initially or switch to the other door that was left after the game in-charge eliminated one door.We were required to calculate the probability of wining the car in each of the cases and then tell in which case the probability of wining a car is more.

//In end sir said to me that sir has been asking this question in interviews since 2-3 years but till now nobody gave the correct answer except me :D

Algorithms and Data Structures

Q3) What all Data Structures you know?

Q4) Define Heap and tell the applications of Heap.

Q5) Consider the elements : 2,4,21,98,2,4

Sort them using Heap sort and show all steps.

Q6)How to do insertion in Heap?

Q7)Can we delete an in between element in the heap,If yes then show how ,so that Heap property is not violated?

Q8)Array can be used to implement Heap.Explain how will you implement a Heap using an array.

That's it ! Hope this helps :)

 

 

Many people have asked me to share my interview experience at IIIT Hyderabad. So I'll just paste what I shared privately with some.

 

It wasn't the best of interviews :P. But I'll share what they asked
Introduce
I did. I had work experience, so mentioned about the job and company. My company actually recruits a lot from IIIT hyderabad, so they started asking on my past work etc.

Then the interviewer asked a question, which is my fav algo.? I said merge sort. Naturally, I expected a follow up question to explain merge sort in detail, however they asked why merge sort, a sorting algo?? I got nervous and said I like the divide and conquer paradigm it follows. I also explained the details on how merge sort works. But I just felt they weren't looking for the working. Anyways, they gave me a scenario where I have 1 billions elements, but memory which can hold only 1 million. How would I sort it using merge sort? I explained, but I was perhaps wrong as they didn't seem to be convinced.
As I mentioned I liked divide and conquer paradigm, they asked why do you like it!!(again a question which made no sense to me :P). I truly love D & C, but putting in words was difficult for me. The main reason why I like it is, that it forms a building block for Dynamic Programming, by giving us sub problems. This is what I replied to their question, however their expressions were not at all convincing. I felt embarrassed. Difference between D&C and DP, I explained about unique and overlapping subproblems(didn't affect their expressions!)

They asked about which other subject. I said OS. Now comes the most confusing question, Why does OS and DBMS have their own synchronisation mechanisms, when OS can alone do it and it sits at the bottom of DB? I googled for the same after the interview, couldn't find one anywhere. Although I did answer that OS works at process level for Critical Section, and DB is for concurrency and transaction. They said its not the reason.

Finally they gave me a scenario where I have to design Google Maps :P(this was probably asked as they made us submit SOP during application last year, although this year they havent asked!). So the prof said, you have some nodes where I give you Lat Long pairs, how will you represent the nodes on the map. What if I want to find the shortest path from A to B?

I think I answered it correctly, but the prof again was not convinced. I also mentioned about absence of negative weights as there are distances(can never be neg), so I can use Dijkstras.

Anyway, I just felt, my luck wasn't there!

Some other candidates said they were asked questions from discrete maths with more focus on graph theory.
Proving theorems of bipartite, deriving expression for number of graphs.
They generally dont ask from TOC, even if you mention TOC, they'll just ask basic finite automata, and move on to next.
They also ask some basic protocol questions from Networks.

 

Result: Not selected!

PRE-INTERVIEW:

• Gate Score Cut-off was around 625-630 (that' what I have heard)
• MTECH CSE Intake: 40 Vacancies
• Around ~400 students were shortlisted for the process, out of which only 170-180 students attended.
• The process was meant for two days, but they finished it on the first day itself (Interviews were taken till 2200).
• Reporting Time: 0830, Everyone was seated in Auditoriums and Dean of Academics presented their college. At around 0900 tea-coffee-biscuits were offered, and around 0930 Written Test commenced.
   

WRITTEN-TEST/ PROGRAMMING TEST:

• Written Test, 60 Mins, 30 Ques. Marking Scheme: +2, -1
  I found Written Test to be quite challenging, Approximately 1/3rd questions were from Discrete Mathematics. I attempted 23 questions, out of which I think at most 15 would've been correct.
   
• Programming Test: 60 Mins, 5 Questions.
  Platform: Hackerrank
  This part of the test was very easy. 5 Questions in 60 Minutes, might seem very challenging at first, but 2-3 questions consumed just 15-20mins in total. I did 4 questions completely and passed 7/14 TestCases for the last one.
  
  All this process got over by 1230 and the shortlisted candidates for Interviews were to be announced at 1400-1430, with Interviews starting from 1445. 

INTERVIEW:

• Students were shortlisted marked on the combined performance of Written/Programming Test, and I don't think GATE Score played any role in shortlisting procedure.
• 75 Students were selected for Interviews, divided into 3 Interview Panels. Each panel had 3 professors.
• Interview Experience ( There were 3 Professors, I'll address all three as P)
  
  (Resume wasn't needed for Interview, so they didn't knew much about background of work that I've been doing)
  
  P: Tell us about Yourself.
  Me: Did.
  P: How many questions did you do in Programming Test?
  Me: I did 4.5
  They seemed quite impressed by it (all three panelists started looking at each other)
  
  P: What are your favorite subjects?
  Me: DS, Algo, CN.
  P: So should we start with DS?
  Me: Yes.
  P: Ok, can you tell us, what is a Hamiltonian path?
  Me: (I was shocked at first, that they targeted the theoretical part of Data-Structures, I was a bit fumbled)
         I  don't know the exact definition, but I know it's like         Spanning Tree.
  P: No no, they both are entirely different.
  After fumbling a bit,
  P: If you don't know it, you can tell us, we can move on to other question.
  Me: Yes
  
  P: Suppose you're given a polynomial expression, what data-structure would you use for storing it?
  Me: (Me moving over to whiteboard) I'd definitely not use an array. I'd go with vecor...as I'
  P: (Interrupts me) I don't know vectors.
  Me: (This got me nervous) Ok, I'd switch to using a Hashmap, as I
  P: (Interrupts again) I don't know hashmap either
  Me: (They were looking for specific answers only), I'd use a linked list.
  P: Yes, that's what I know.

  P: Now suppose there' another polynomial expression, and you have to add both, how would you do it?
  Me: I'd keep Linked List in sorted order for this and explained further on the whiteboard. (they seemed ok with my solution)
  Me: But this structure would face issues if I'd have to lots of issues in insertions, and if possible, I'd have used Hashmap (No reaction from their side)

  P: I see that you've selected Machine Learning as your field of study.
  Me: Yes, during filling my form, this was the most viable option that I understood, the other two fields I wasn't much sure about.
  P: What do you know about clustering?
  Me: (Shocked at first, as I wasn't ready for ML questions, but since I knew about clustering, I took a go at it), clustering, how it's an unsupervised form of learning
  P: Ok, so you know. Suppose that you have a straight line and two cluster centers, C1 and C2, how would you minimize it. (These were the exact words, I didn't understood the question at all)
  Me: Sir, I don't undertsand what you're trying to ask.
  P: He repeated the same line again.
  Me: (I drew a slanted x = y line on board)
  P: No no, a straight line
  Me: Like an X-Axis
  P: Yes
  Me: (Drew x-axis, and two cluster centers)
  P: Yes, now minimise it.
  Me: By minimise, do you mean optimizing it?
  P: Yes, yes that's optimising (as if he was trying to say this word all along)
  Me: Sir, I don't know much about this.
  P: You'd take Difference between points
  Me: Yes, I'd take dataset points and take difference between points and centers, and take a square again, to keep values positive, ahhh
  P: But how do you know that you've minimised the cluster centers? How do you verify it?
  Me: I don't know, Sir.

  That's it. I don't have any chance in it. But learnt a thing or two about IIT Interviews, and shared it.
   

My sole purpose of writing this post is that the previous interview experiences given here by our seniors have been a great help for me so I just wanted to carry forward the tradition. Moreover , take it as a token of thanks to all our seniors who have contributed to GO in any possible manner and a help for all the people who would be aiming for IITK in future. You can even read this post  just for the love of CS and because you like to do new and challenging problems.

There were 2 tests this year:

(1)Written Test (30 Marks) :

      1) 30 questions

      2) 2 hours duration

      3) We were required to choose one out of the two groups ‘Systems’ or ‘Theory’.

      4) Each question carried 1 mark each.

      5) There was no negative marking.

      6) MCQs can have multiple write answers , marks are given when all the answers are marked correctly.

      7) There were fill in the blanks and Numerical answer type questions , mostly one liners.

PS: We are not given back the question paper in IITK so I have tried to mention as many questions as I can recollect after the exam. In some of the questions I have not mentioned the exact question but just the concept the question was asked from ,an obvious reason being you cannot expect someone to remember the exact numerical values.I attempted the ‘System’ section so can’t recollect the questions from ‘Theory’section(I can add to this post if any of my friends tell me the questions in ‘Theory’section).

Q1) Address Resolution Protocol(there were 4-5 options we were required to mark all the right choices about ARP).

Q2)We were given Bandwidth,RTT,Packet Size,etc ,it was required to calculate the optimal window size.

Q3)There are two relations R1 with tuples r1 and R2 with tuples r2, r2 > r1 Minimum number of tuples in R1 Union R2.

Q4)printf -> system call or not

Q5)If we increase the pipeline depth , the time to execute a single instruction decreases.(T/F)

Q6)One program given in C language, it used string and stack, we were required to tell the correct output out of the choices given.

Q7)Given a function ,we were required to tell whether it computed a*b or a*(b+1).

Q8)Given page size and #bits in physical and logical address.We were required to calculate the size of the page table in Bytes.Each page table entry contained the translation bits,dirty bit,valid bit,etc.

Q9)There are 65 different instructions available in syatem,one instruction s1 uses a shift field based on word length and 2 registers. #registers=519. 64 bit processor .Calculate #bits used for s1.

Q10) Heap in array form given ,we were required to extractmin() and then report the resulting arrary.

Q11)Mini. #nodes in height 10 , Height balanced BST.

Q12) R1(A) PK ,R2(B) B PK references A on update cascade,R3(C) C PK references B on update cascade

R1: 1 2 3 4 5 6 7

R2: 2 4 6 7

R3: 2 4 6

Update R1 set A=A+10 where A<5;

Select sum(C) from R3;

I will add more questions here.

(2) Programming Test(30 Marks):

      1) 2 questions.

      2) 2 hours duration.

      3) Ques 1 (10 Marks) and Ques 2 (20 Marks).

      4) Language : C

      5) We were required to code on Prutor(Online web-browser based IDE for program preparation and submission developed at IITK).

       6) There were 4 visible test cases and 10 hidden test cases. 

Q1) Print the second minimum element in the given integer array.(10 Marks)

Q2)Given an input in String format. We are considering base as 15(Allowed digits : 0,1,2,…,9,a,A,b,B,….,e,E).From the input string first take out the valid base 15 digits and then print its decimal equivalent and Zero if no valid base 15 digits).(20 Marks)

Eg1:

Input : IITKanpur@CSE

Output:2444

Valid base 15 digits: ace

Eg2:

Input : IITK

Output:0

Valid base 15 digits: none

Some useful materials : Syllabus Written Test

Sample Test Written

Prutor

Syllabus Programming Test

Any of my good friends who attended the IITK test and would like to suggest any corrections and additions in the questions provided here is most welcome.

Last time ECIL recruited was in 2012–2013 and I was not able to get any info about the interview procedure. So I decided to write it down to help future aspirants. ECIL GET 2017 written was held on 21st January 2018 nation wide. 40 people were selected for interview against 10 posts.

Location : CLDC ECIL,Nalanda Complex, near TIFR Hyderabad

Time: 8:45 AM onwards

Duration: 30 mins on avg.

Process : 2 round document verification followed by interview.

Interview Experience

The panel consisted of 6 members.Each of them were the master of their own field. Some said they were not from ECIL but from outside. (maybe from BARC, TIFR or IITs).The panel was very humble and friendly. No certificates or resume or cv was needed to be taken to the interview room (certificate verification will be carried out before).

They asked me my name , college where I did my engineering, year of passing. They might even ask few general queries about your home or college placements.

They asked me if I was prepared for the interview to which I replied “only few subjects”. They asked me to write down those subjects and a programing language along with that.

I wrote :

1. CO

2. OS

3. DS

4. C language

Few of the questions as far as I remember.

1. Draw the diagram of the architecture of a computer.
2. What are the speeds of your CPU and Main Memory?
3. How does the computer manage the speed difference between Processor and RAM ?
4. What is a cache memory? Which concept is the reason because of which the cache memory works effectively? How read and write operation occurs in cache memory (Write through and Write Back).
5. What is the size and speed of a cache memory in general?
6. Draw the memory hierarchy diagram and tell us the relative speed of each memory type.
7. Explain how cache memory works in detail ?
8. What is an interrupt? What are the types of Interrupt ? Explain interrupt cycle in detail? Is the interrupt executed after finishing of current cycle or current instruction or current program ? Where is the current states of a process stored when an interrupt occurs?
9. What are the types of Interrupt pins in 8085 microprocessor? What is 5.5, 6.5,7.5 in RST 5.5,RST 6.5 and RST 7.5 ?
10. How many pins are there in 8085 microprocessor. Can you draw them ?
11. What is paging ? Explain it in detail in paper.
12. What is inside a page table? Are all the entries in a page table valid ?
13. What is virtual memory?
14. Explain any process synchronization technique in pen paper. Why there is a need of synchronization? What is a critical section ?
15. Do you know about windows server edition 2015 ? (I answered No and later I found that there is no server edition 2015)
16. What is a stack ? What are the applications of stack ?
17. Which type of program is better, Iterative or Recursive ?
18. Pros and cons of iterative and recursive programming methods.
19. Write a program to find the factorial of a number using recursion? ( Asked me to explain it step by step, they made changes to the program and asked me what will happen to the output etc etc)
20. Draw the activation record diagram of the above program and explain it.
21. How will you know that stack overflow has happened ?
22. How can we know the size of the stack for a program ?
23. Write a program to check a leap year and explain it line by line.
24. Why can’t we use the desktop’s windows 10 on your smartphone?
25. What is a kernel in OS and how does it work?

In the end they asked me how was the interview and I replied “It was a great experience”.

They will ask you “what”,”why”,”how” to every new thing you speak. These were the overall questions. They asked many small questions in between my explanation to other questions.

Interview was at ISRO Guest House, Chennai.

Preparation Advice for written test :(most of you already know this) Do not prepare solely for ISRO written test, rather prepare for GATE only. I mean it seriously although it sounds like little arrogant!

Coming to the interview part, We were asked to report at 8:00 AM. There was some document verification which started at around 8:30 or so. After that candidates done with their verification were called for interview parallely.. My turn was second/third..

I entered the Interview room, it was quiet big with around 10 people sitting on 1 side of table with 1 chair in opposite side and a whiteboard at some distance behind the chair. Now, I don't know the name of the Prof/Scientist in the middle, but he was very polite, he greeted me and asked me to sit, then asked to tell a little bit about myself.

 

Following are the questions(not all, but to the best I remember), and the responses I gave there:

Q: What is the project that you have mentioned ?

me: Handwritten Digit Recognition.

Q: How does it work ?

me: told the whole process.

Q: How are the weights of Neural Network adjusted ?

me: told the Gradient descent algorithm. Then they asked Backpropagation algorithm. I told them what I knew but it seemed they wanted to listen something else. They again asked it and I again said the same thing. (Later I came to know that what I was saying was right but I could have been more precise with my terminology).

Tip: Try to be precise with words and terminologies.

Q: Does Gradient Descent always converge ?

me: told them no with the reason.

Q:In what cases it does not converge ?

me: told.

Q: Can you draw sigmoid function on board?

me: Drew. (For those wondering what it is ? It is a useful function in ML especially with Neural Networks)

Tip: Now I don't want you to get that you have to study Machine Learning and do some Machine learning project in order to get through (although It will be good) but the more important thing here is to mention a project which you have seriously studied, because they will dig deep into it. (And according to me, the project part was responsible for my selection! )

The main thing is that with this level of knowledge (which most of you are at) they don't expect you to solve some great real world problem or build a ISRO project , they just expect you to be thorough with your Project (as mentioned above) and with the GATE syllabus (as will be clear below).

The GATE syllabus part.

Q. What are your favourite subjects ?

me: Theory of Computation, Mathematics, Algorithms, Data Structures (I wanted to stop here and not go into system subjects but they kept saying and and...) so I had to say all i.e.,Network, OS, DBMS.

Q: Suppose a user wants to send Application data to another computer. How will the data go?

me: told the process of segmentation, then how the headers are applied etc.

Q:Do you know fields in TCP and IP header ?

me:told

Q:Do you know VPN?

me: I had never studied VPN, but I remembered something from somewhere and answered "It is used to group ports on different switches so that broadcasts can be done to only members of certain group rather than all the hosts on the switch...." I didn't realize that I was telling about VLAN,, so here came the next question :

Q: What is VLAN ? :O

me: Fortunately I remembered by now. I smiled and said that what I just told was VLAN.

Then came some Mathematics questions, but not much.

Q. What is rank of a matrix ?
me: told

Q. What are the applications of rank of a matrix ?

me: told them about its applications in Solving system of equations.

Pretty much that was all.

Final status : Selected!

#Feb23  #Interview Experience   #Chennai

Hello friends !! Good morning..
This post is for those who may give ISRO interview in the coming months . I am going to share my interview experience in the below lines . I will try to cite the questions that were being asked to me as far as my memory goes.

My interview was scheduled at 3rd from the last. So I had lunch and Friday prayers then waited patiently and tried to stay calm and confident. It was roughly 4:45 pm when my name was called for the interview. So here the experience goes(I am mentioning the questions along with the answers which I gave) :

Interviewer : Introduce urself
Me : Introduced myself to all.Told about my graduation college and about my current job i.e. in BSNL.

Interviewer : Tell me about the subjects u have learnt in ur B.tech
Me : I mentioned Mathematics , Computer Architecture and Theory of Computation

Head Interviewer : What is Flynn's classification of architecture.Name them.
Me : Answered each of the types .

Interviewer : How does out of order execution occurs in pipe lined environment ?
Me : Answered.

Interviewer : What are the types of the hazards which are there in pipelining ?
Me : Answered.

Interviewer : What are the different types of data hazards ?
Me : Answered with elaboration.

Interviewer : What are the ways to reduce or eliminate control(branch hazards) ?
Me : Answered with elaboration.

Then questions on Maths were asked.They are as follow :

Interviewer : Explain about lattice.
Me : Explained properly

Interviewer : Some mathematical modelling problem.
Me : With a bit of hint from their side , I could come to the conclusion and answered rightly that it was related to bipartite graph.

Interviewer : What is Taylor's Theorem ?
Me : I clearly admitted to them that I was unable to recall as I studied about it way back in 2nd semester.

Interviewer : What is bijective and surjective function ?
Me : Explained

Then some questions about Theory Of Computation.

Interviewer : What are the types of grammars ?
Me : Answered and elaborated [ Type-0 to Type-3 ].

Interviewer : What is the practical use of regular and context free grammars ?
Me : Answered.

Other interviewer : Which programming language u r comfortable in ?
Me : I was very straightforward in this and told "C" bcoz I do not know each and every things of OOPS in C++ and also as far as Python is concerned , I know the basics of it only.

Interviewer : What r the command line arguments in int main()
Me : Answered.

Interviewer : To read or write from an arbitrary location from file , which function we need to use ?
Me : Answered(It was fseek() function)..

Interviewer : What does ls command do ?
Me : Answered.

Then some project related questions are asked regarding working and some basic terminologies behind it .

Interviewer : Tell me the pros and cons of collaborative and content based filtering .
Me : Answered .[My project was based on content based filtering]

Then the head interviewer took notice of the fact that I know six languages via the bio data form that they provided to fill prior to the interview.

Head Interviewer [In an appreciating tone] : How do you know so many languages ?
Me : Explained the reason behind each of them.

Finally some non tech question to conclude.

Interviewer : You are currently working in BSNL and that too in ur home state.. So what has made you think to join ISRO ?
Me : As a responsible citizen of our country , we are obliged to serve anywhere throughout the country.

Interviewer(Counter question) : That BSNL also does..So why ISRO ?
Me : Beyond doubt BSNL is also obliged to serve countrywide.But as far as ISRO is concerned , it is based on space science which has wider implications on the society.

[To add on] I got the inspiration to work in ISRO from Honble Late Dr. A.P.J Abdul Kalam with whom I interacted personally while I was in Class 10th..His zeal , simplicity and enthusiasm to work selflessly for the country has inspired me to move on..And hence if I am given a chance to serve ISRO in case I am selected , then I will give my best to serve my nation and the society.

The interviewers appreciated my answer and responded positively.The interview lasted for around half an hour.[By and large , others had around 15-20 minutes of interview].

In a nutshell , this interview was one of the nice interviews I ever had irrespective of the result which is yet to come..Though I look forward to it positively as the reaction of the interviewers was positive as far as I have felt.

All the best to you all..N plz pray for me as well so that I get selected in ISRO finally..

 

Based on the gate score shortlisted some students and on the day of interview we were introduced about RA program, they cleared our doubts there is no difference between TA and RA program in terms of coursework and placements. There are 4 professors who introduced about their projects and what are their requirements.

Followed by a written test consisting of 16 questions (CO, OS, DS, Algorithms,Math’s mainly)

Then called for the interview, there were 8professors inside the room. It covered General subjects interview (CO, OS, DS, Algorithms,MATHS) followed by Project specific interview.

Subject’s interview

First question was tell about yourself - told

Started with CO

Professor: What is difference between Cache and TLB

Me: Cache used to store words, TLB used to store entries.

Professor: What is Temporal Locality and Spatial Locality. Given some references of pages and block size, use LRU. Will it be an advantage for Temporal Locality or Spatial Locality – Told.

Professor: Will there is an integer greater than every integer. Is true or false

Me: Told it is not a proposition

Professor: Why and what is the definition of proposition?

Me: Proposition is statement we can say true or false. Here I assumed integers are Universe set of Disclosure so we can’t give a number greater than any number and say true or false, so it is not a proposition.

Professor: If we have an array with all numbers same except one number. Tell me an algorithm to find different number.

Me: Told a algorithm and they asked me to find the time complexity for the same algorithm

Professor: Asked about basic concepts of threads – told. They have given a case study assume we have linked list and want to do basic operation (Insert, Delete, Min), want to perform parallel operation by using threads. Tell me your approach.

Me: As linked list is like a critical section we can’t perform the operations parllely as it will lead to inconsistency problem. They asked me what is Critical section.- Told. They said there exists an approach we can work parallel

. I have been thinking for some time- not getting idea.

They stopped me and we will come to that later and asked some more questions couldn’t remember. Finally they asked me to wait, there is another round of interview at afternoon 3:00.

Project specific interview:

They asked me tell me set associative cache and what is its format- told

Explained and given the format as

Tag

Set No

Offset

 

Asked me about what is miss in cache – told.

Professor: Let’s assume Tag and Set No are interchanged.

Assume offset is 2Bytes, set no is 3bits, and remaining tag. And the references are 0 to 16(each 1 Byte). Then how many no of misses.

Me: Written references on board 0000 0000

                                                                   0000 00001 …………………………………………..till 16

                                                                    0001 0000

New format is  

Set No

Tag

Offset

 

I told all the references will be mapped to the same block of cache because all the references having the same set no “000”. For every reference we are getting 2Bytes in  cache. So for every two references 1 miss. So totally 8 misses.

Professor: Satisfied with my answer. I was happy.

Professor: Came back to the Threads question parallel operation

Me: Actually thinking about same question during my lunch got some idea, told some.

They asked me to wait for another interview.

General Interview:

They asked me to tell about my self- told

What are the things you have done apart from your course work of B.Tech – told.

They asked what your interests of learning are- I said ML/AI, I just heard the terminologies, I want to learn full time under professor guidance.

Professor: project is related to ML/AI with computer architecture. – I was happy that I can learn the new things (ML/AI).

Finally completed my interview.

After 2 days Professor called me and confirmed that I didn’t applied for other IIT’s and willingness to join

On that day itself I came to know I was selected for RA before results.

Hope this post helps somebody to get interview exposure.

                                                                                               

 

1st Round Interview:

T: Introduce yourself

Me :Gave small introduction

T:subjects in which you are comfortable to answer

Me: Data structure and Algorithm

T:How to find maximum element in a Binary Search tree

Me:first i told general approach(similar to find max in array) then they sent  me to  board then i explained efficient way (logn complexity)

T:can u write pseudo code for what you explained

Me:I wrote

T:There is an integer which is greater than every integer. Is this statement  true or false?

Me:false

T:why??

Me : explained

T:write first order  logic of what you explained.

Me:$\forall x,\exists y,y>x$

T:negate the above statement

Me:done

T:what is this statement mean

Me:explained

T:why deadlock will occur here(questions from the written test)

Me:explained

They told me to wait because there may be another round of interview

After 3-4 hours ,they called me again for another round of interview

Interview Round 2(for formal method project):

T:what are the sorting algorithm you know

Me:told all 7 to 8 algorithm name which i knew

T:which algorithm you think is better

Me :answered

T:why you are saying this and why not this and few more question

Me:i replied all

T:Let G(V,E) be a graph. Let w(ei) is weight of edge i. w(e1)<w(e2)<w(e3).........<w(emax). Let T is MST of G.

 i) w(e1) ∈ T, ii)w(e2) ∈T , iii)w(e3)∈ T ,iv)w(emax) ∈ T

Me:Explained for first two case(easy one)

T:What about iii ?

Me:In somecases w(e3)∉T

T:why??

Me:Explained

T:what about iv ?

Me :In somecase w(emax) ∈ T

T:why?

Ans:Explained

T:what is the time complexity to find 3rd max element in max heap?

Me:I went to board and explain clearly (O(1) time complexity).they were looking satisfied by answer.

T:Sorted array is given .You have to find two number from array which is equal to C(given number)

Me:first i explained algorithm which takes $n^{2}$ time

T:Even if array is not sorted we can do in $n^{2}$ time .can we do in better way because we have sorted array

Me:I gave nlogn algorithm.

T:what you told is correct but can you optimise it more

Me :tried but not getting  

T:they gave hint like $a_{1}+a_{n}>c(given number)$$a_{1}(first number of array)+a_{n}(last number of array)>c(given number)$

Me:after thinking little bit i got O(n) algorithm.they satisfied by answer

T:Draw an automata for language having as many occurence of 10 as 01?

Me:I started drawing but in the mid they stopped me

T: 3 red ball(identical) and 5 green ball(identical) .no of ways we can arrange such that no two red ball are adjacent

Me:Answered

They told i am done. I was happy because i answered almost every question and feeling satisfied.

After 15-20 mins

3rd Interview(for parallel processing project):

T:why mutual exclusion will occur here(question is from written test)

Me :Explained in detail on board

T:Another question from written test regarding synchronization

Me:not able to answer but made me to think then they gave hint and at last they explain me the answer

After coming out of interview room i was very happy .

I hope this post may help at least someone who are preparing for gate 2018

My gate rank is 527 and score is 728

Friends ,today i am going to share with you, the interview experience of IITH.But before that let me  give you a brief picture

About IIT h Mtech RA:

Okay,this is the Best scope for Low GATE scorers,and here low means really low.Such a score,where you can't even think about getting an IIT.But your CGPA has to be really high. As this is research oriented ,so faculties stress on CGPA more,which reflects our consistency.So with this hope i filled a form there.

FIRST PHASE:

At first they shortlisted some candidates where cuttoff was like 590 GS AND cgpa >8.8.And after some days they again revised it to 8.6+ and 560+(GENERAL CATEGORY) . So here i got a chance as my score was 575 (worst !!) and 8.78.

INTERVIEW DAY:

i turned up for the interview, and found that almost 70 people got shortlisted in which 52+ turned up. And guess what, i was the lowest score among General to turn up there.people with score 700+ was there ,as they turned up for TA and continued to stay till RA. So i understood that i have no chance Here.

For this large candidate at first they conducted a written test. the questions were

1.if we toss 100 coins ,what is the probability of getting AT LEAST one Head?

2.Write a program to find two maximum numbers of array.

3.an algo like DFS

as the questions were very easy so i thought chance gone..but then they conducted technical interview ,for ALL..

6-8 panels was there..in my panel there was 3 teachers, and questions were like...

T=teacher M=Me here

T: Introduce yourself

M: told

T:so why you dropped a year ,while you had a job?

M:told

T: but your score have not improved

M: but i don't regret to give one year for concept

T: great!

 

T: what is your favourite subject

M:Database,OS

T: tell me how may Keys in DB you know, as much as you can.

M:told all .Primary,candidate,unique,super and many more

 

T:what is B tree and B+ tree

M:told

T:why we need Both of them , write a query in two different way and explain where we should use B and B+

M:told

T:how can i know the 3rd last node of Linked list in One pass

M:(ab aya uth pahar ke niche) Told

then there wer some questions from algo.

Lesson: whatever subject you choose,algorithm Ds is the king of interviewer's choice.

 

so after one hour results came, Depending on Written+interview  25 people got shortlisted. many 650,700 scorer was not able to crack it.

then there was a HR type interview where we had to write our project preference and all faculties were present in a single panel.they asked me question like Why mtech RA,why Machine Learning etc.

then after a week results published 17 people selected, i was not...i was disappointed ,then on 24th July i got a mail,

"dear candidate ,congratulation !..." Best lines of My life

SO, the lowest scorer to turn up there , has got selected..

 

LESSON: GATE is just an examination.You have other ways to find success

 

PS: as i am superstitious, so when GATE gone bad, i opened this account in GO, my original account is aboveallplayer in Gateoverflow :)

Thanks

Gate 2017 AIR 572

Category Open

Graduated in 2014 (BE Computers)

Work Experience of 2.5 years @TCS

After goofing up Gate 2017 exam by making some gruesome mistakes, I landed up at 572. I had no hope for any good old IITs for obvious reasons. Of all, IISc was never on my mind, until the interview happened :P

I received a call letter for interviews in following three departments.

• CDS-Computational Science (CDS-CP)
• CDS-Computer and Data Systems
• COMPUTER SCIENCE AND AUTOMATION (CSA)

Day 1 5^th June 2017, Morning session: CSA Interview

We first had a written test (subjective) consisting of 10 questions of one mark each with time limit 30mins. The questions touched subjects like Math, simple algorithms, digital and COA. The test was pretty simple and slightly tricky.

For the written test questions please follow below blog post by Stanly.

https://stanlysamuel.quora.com/Indian-Institute-of-Science-Bangalore-interview-experience-June-8th-2016-which-made-me-an-IIScian

Soon after the results were announced. Total 11 candidates were selected of approx. 25-30 who appeared for the test that day and I was one among them :)

My selected choices for interested Research area are as follows:

Main Research Area	Computer Systems and software
Sub-Areas	1. Databases 2. Programming languages
Background Subjects	1. DSA 2. Engg Maths

I was 9th in the order and my interview started at around 4.20 PM.

The interview panel consisted of six professors.

After a brief introduction, I was asked to approach the white board. According to my research areas and subjects of interests that I filled in the form, my interview started with basic Math.

Interviewer: What is a powerset? If there are n elements in a given set then how many elements are there in its powerset? I answered..

Interviewer: Prove it.

I took a few seconds and then started to prove it by induction.

Interviewer: Is there any other method to prove?

I again took a few seconds and replied we can prove it by combinatorics and wrote out the series for 2^n and explained it.

Interviewers seemed to be impressed by this point.

Maths was wrapped up with few more questions on equivalence relation and reflexive property.

Next up was a question from algorithms. I was given a simple binary tree whose leaf nodes were filled by some values. The question was about designing an algorithm to fill all the internal nodes in bottom up manner such that each internal node is max of its child/children.

I spoke of the ideas I had in mind. The interviewers were very helpful and gave in few hints to steer me in the right direction. I partially answered it.

The wheels now turned towards database.

I was asked a number of questions here ranging from write a query in relational algebra..table decomposition..lossy decomposition..dependency preservation..serializability.. 2PL.. phew!

I faired decently in simple questions though I realised I could not meet the set expectations.

And the interview ended here..and it lasted for almost 40 mins.

Day 2 6^th June 2017, Morning session: CDS-Computational Science (CDS-CP) Interview

Again we had a written test with 5 questions of 2 marks each. This time the questions were only from math( graph, probability, combinatorics) and algorithm.

I was shortlisted for the interviews.

We were asked to fill out three research labs of interest in specific order. I was unclear about the labs but I filled these labs in given order.

1. Computational Mathematics
2. Stable, Accurate, Fast, Robust Algorithms & Numerics (SAFRAN)

Totally 8 candidates were selected and I was 4th in order.

The interview panel consisted of 3 professors.

I gave a brief introduction about myself and I was asked the subject of my interest and I said linear algebra and matrices.

The interview started with simple questions like what is the order of the matrices A, B, X in the equation AX=B. Answered..

Followed by questions on rank, define rank, give the relation between the number of solutions with rank of A and [A,B] matrices. Answered..

Given equation C=AB, what is the relation between rank of C with that of A,B. Answered..

Now given order of A mxn and order of B is nxn, then what is the relation between rank(C) and rank(A). Tried but couldn’t get this one right.

The interview ended here. It lasted for nearly 20 mins.

Overall the experience of being interviewed at one the prestigious institute by renowned professors was indeed overwhelming. I did not care much about the results, as I had surpassed my own expectations and felt happy about it in the end.

Within a week, the tentative shortlist was out and I had my name in both the lists (CSA and CDS-CP) and eventually I sailed to the final list of CDS-CP :)

The mantra that I followed during both the interviews is to “Keep calm and think out loud”. This applies to any interview for that matter. I felt I was under prepared for the interviews so did it happen that I got stuck at some of the crucial questions. The only chance I had to make the interview look engaging was to think out loud and strike the right chord.

P.S. Life always gives you a second chance. Keep your eyes open and seize the very next opportunity.. Cheers!

 

They called approximately $80-90$ people for interview. For interview cut off follow this link: http://cse.iith.ac.in/?q=node/491

 
Date: July $11,\ 2017$. Venue: IIT H BUILDING, Room Number $318$. 

We had a written test $(1 \ hour)$ as the first step. Following are the test questions :

1. Solve  recurrence Relation  $T(n) = T(n-1) + 2n, \ \  T(1) = 1$

2. Let $G(V,E)$ be a graph. Let $w(e_i)$ is the weight of edge i.e. $$w(e_1)<w(e_2)<w(e_3).........<w(e_n)$$.
Let T is MST of G. State given statements are true or false. Give counter example also.
a. $w(e_2) ∈ T$
b. $w(e_{max}) ∉ T$

3. A sorted array is given. Write efficient c code for searching an element. Also, find time complexity and correctness too.

No written based shortlisting. Everyone needs to attend the interview.  There were four interview panels. 

 

 

Interview Part :

Room no $311$.

Professor Antony and Professor Sakethnath (https://cse.iith.ac.in/?q=People/Faculty) were my interviewers.

Professor Antony: Introduce yourself.
Me: Answered.

Professor Antony: What was your answer regarding question $2b$? TRUE or FALSE?
Me: FALSE.

Professor Antony: can you prove this?
Me : (Took marker explained why it is false). My $1^{st}$ argument was if $G$ itself is a tree so $e_{max}$ must be in T.
$2^{nd}$ argument: Even if G is graph but not the tree and let there is a cut edge then irrespective of weight we need to select that edge in MST.

Professor Antony: can you prove your second argument?
Me: Explained everything with a diagram.

Professor Sakethnath: You are good at maths?
Me :

Professor Antony: There were $25$ teams, and we have $5$ processors. At any point in time, we can select 5 sides, and that will give a winner. So how many matches we need to find a winner?
Me: 6. I guess.

Professor Sakethnath: Guess or sure?
Me: Sure ☺

Professor Sakethnath: Let me modify this question. There were $16$ teams. A match between any two sides will give the winner. So how many games do we need to find a winner and second winner?
Me: can I explain it on board?
Professor Sakethnath: yes go ahead.
Me: Explained everything with the divide and conquer approach. Total matches will be $n+ logn -2$. Still, they weren't convinced.

Professor Sakethnath: can you explain again how you got $logn$ term?
Me: Question was the same as 'Finding max and second max element from an array of n elements.' Explained with divide and conquer approach. They were trying to trick me here and there, but I was confident. Finally, they agreed.

Yes, that gave me some confidence!!!

Professor Antony: You have two coins with head probability $p_1$ and $p_2$ respectively. Just select any one currency randomly and toss. What will be the probability of getting head if the previous attempt was also head ??

Me : (Took marker) Wrote the conditional probability formula. $P(A/B) = P(A∩B)/P(B)$. I forgot how to proceed further

Professor Sakethnath: Just tell me what will be the probability of getting a head?
Me: Answered.

Professor Sakethnath: Now tell me what will be the answer to the previous question?
Me: Again I wrote same formula

Professor Antony: You know the linked list?
Me: Yes.

Professor Sakethnath: A linked list with the head pointing to the first element is given. How will you implement the Queue with this linked list? I mean where should be insertion and from where you will delete?
Me : (After drawing linked list I thought if I delete at the end, it will take $O(n)$ time, but enqueue and dequeue operation in a queue must take constant time) Acted like I am thinking something.

Professor Sakethnath: Why are you taking so much time? Just tell us where should be insertion and from where you will delete?
Me: Insertion will be at the head that will take constant time but, deletion at the end will take $O(n)$ time. That's why I am thinking some other way such that delete operation should also take constant time.

Professor Antony: Who told you insertion-deletion will take constant time?
Me: Read it somewhere. (don't know where )

Professor Sakethnath: No, $O(n)$ is ok. Can you tell me what will be if I delete at the head and insert at the end?
Me: Still it will be a queue, but in this case, the insertion will take $O(n)$, but deletion will take constant time.

Professor Sakethnath: Can you tell me recursive $C$ code for checking two trees are equal or not?
Me: Sir, trees or Binary trees?

Professor Antony: Binary Tree.
Me: Wrote the whole algorithm. I asked to allocate memory dynamically. I did. I was also asked for termination condition, node structure, return type of malloc. I explained everything.

Professor Antony: Ok done.
Me: Sir any question from graph, tree, linked list?

Professor Antony : (smiled) You want some more questions?
Professor Sakethnath: No, you are done.
Me: Thank you.

Both professors were amiable. And this was my one of the best interview (obviously after BARC) of the year 2017. I enjoyed it.

 

Finally on July $13,\ 2017$. Got an e-mail from IIT H.

 

I would say that please do keep hope if you face a lot of failures. One day will be yours, and you will shine like a star.

National Institute of Technology, Tiruchirappalli invited 30 aspirants for interview/counselling on 7th July 2017. They released this notification on 15th June 2017 on their website, with very limited information. It was not at all clear what will exactly happen on 7th July until we reached the campus.

I reached Trichy a day before, just to be on safer side. My brother was accompanying me and we had a booking in Breeze Residency, a hotel which was less than a kilometre away from TPJ (station code) railway station. However, later I learned that the retiring rooms of the station were equally good. You can make your pre-bookings of the retiring room from IRCTC website.

We decided to spend our day visiting tourist places in Trichy. We learned from the housekeeping staff that Trichy is full of places with religious significance. First, we visited Sri Ranganathaswamy temple in Srirangam, which is the largest active Hindu temple in the world. Later, we visited Rockfort temple which was situated on huge rock mountain at a height from where the entire city was visible. We were done by late afternoon. For the rest of the day, I just relaxed and prepared myself for the next day.

The admit card released by NIT Trichy mentioned interview/counselling timings as 3:30 pm to 5:30 pm. However, the notification of shortlisted student said that the reporting time is 10:30 am. We decided to reached there before 10:30 am, again just to be on safer side. Later, it turned out to be a right decision. It takes roughly 45 mins to reach NIT Trichy Campus from railway station/bus stand. When I reached the department, they directed me towards the conference hall and asked me to wait there with others. Two persons from the Institute entered the room and asked all of us to show them our documents one by one. I was asked to be the first.

The objective of this phase was to award marks to students in different categories. Different categories include our score in undergraduate, GATE score, any award or research paper published and lastly the interview. They had predefined criteria, based on which they were awarding marks to each student in each category except for the Interview.

Later, we were taken to their meeting room for the interview. This time I was fourth in sequence. Finally, they called out for me. I entered the room, and my heart sank seeing more than 15 professors and associate professors in front of me. However, calmness of their face made me feel comfortable. HOD on the far end of the conference table asked me to take the seat. And the series of questions began.

HOD: What is your GATE Score?
Me: 651

HOD: Please introduce yourself.
Me: I wasn't expecting this question, but I tried to confidently introduce myself. 

HOD: Have you got any offer of admission in M.Tech from any institute?
Me: No ma'am, not yet.

HOD: What is your research interest?
Me: Algorithms and Data Structures.

And just when those words came out of my mouth Dr K Viswanathan Iyer turned toward me and with a pause started to ask questions

K: Are your familiar with Graph Algorithms?
Me: Yes Sir.

K: Explain Depth First Search.
Me: Explained, in simple words without using any jargons.

K: Applications of DFS?
Me: We can use DFS to find the paths from point A to B in a graph.

K: Please be more specific.
Me: Finding all possible paths between two nodes in a graph.

I was disappointed by myself for giving such a simple and obvious application. I should have given a much better application that was a bit research oriented.

K: Explain Breadth First Search.
Me: Gave my explanation in a comparative style. Comparative to the explanation given for DFS.

He looked convinced.

K: It is given that there is a negative edge weight cycle in the path between two nodes. Why there cannot be a shortest path between these two nodes?
Me: Gave an argument that there will always be a shorter path between those two nodes by going around the negative edge weight cycle one more time.

He acknowledged my answer by nodding.

K: What is Dynamic Programming?
Me: Explained the crux of Dynamic Programming.

K: There exists a shortest path between two nodes 's' and 't'. There is a node in that path, say 'x'. The path from 's' to 'x' will be the shortest path or not.

I asked him to repeat the question for me, as I could not get it with clarity. He did it with patience. But I took time more than their expectation to understand the question. So they decided to move one. Had it been the case, I could understand the question a bit more quickly, I could have answered that as well. 

HOD: What would you choose if you get an offer for both M.Tech and M.S (by research)
Me: Answered

HOD: That would be all. Thank you, Prateek.
Me: Thank you, ma'am. Thank you, everyone.

It was a very short interview of 7-10 mins. When it was all done, they asked us to leave and said that they will update the result on the website in a week or so.

It was a really nice experience. Here are my takeaways from this experience.

1. Learn about at least one important application of a theoretical concept. It should come out from the top of your head whenever asked for.
2. Take your time to answer the questions but learn to understand questions as quickly as possible.
3. Be very very clear with your explanation. We were not asked to explain our concepts on board. Thus, it has to be just what it is, nothing more nothing less. 
4. Lastly, do not be very hard on yourself. They very well understand the gap of knowledge between a teacher and a student. They never expect you to fill it, but just to bridge it.

This year IITB decided to completely change the pattern. There was no written test (objective test). There was only 2 hours programming test. They extended the time by around 15-20 minutes during the coding test. So the total time was around 2 hours and 15 minutes.

There were 6 questions - 2 questions of 5 marks, 2 questions of 10 marks and 2 questions of 20 marks. The programming language allowed were C/C++. It was on a homegrown platform. They provided systems with Ubuntu. Editor was gedit. Basic instructions were provided on how to use the platform and to compile and submit the code.

 

These were the questions - 

 

1) Election (5 marks)

 

There are N number of people who are voting for leaders who are represented by numbers ranging from 1 to 100. So basically the input was like this:

Example input -

5
3
3
1
2
10

Output -

3

Here N is 5 (first line). Then the next five lines is the number of a particular leader. The output should be the leader with maximum number of votes.

 

2) Salary increment (5 marks)

 

I did not attempt this one so I don't remember the exact question. First line of the input was the number of lines to follow, say N. Then N lines following it in the following form - employee id, boss id, salary. After that the employee id of the employee whose salary has to be incremented is provided. I am not sure if the increment was provided with the input or if it was fixed. Let as assume that it was provided with the input.

 

This is an example input - 

3

100 200 10000
200 300 15000
400 800 5000
100 10000

 

Here employee id 100 has a boss whose id is 200 and employee id 100 has a salary of 10000. The constraint was if the salary of the employee increases the salary of the boss, then the salary of the boss has to be incremented by the same amount. So this will have a cascading effect where multiple employee's salary will have to be incremented.

 

3) Remove duplicates (10 marks)

 

In this problem, duplicate characters had to be removed (or compressed into single character). If there was any other character than a-z, "error" should be appended to the end after removing duplicates and invalid characters.

 

Single line was provided in the input. For example -

 

Input -

xxxyyyyyy

Output -

xy

 

Another input example -

Input - 

xxxxx1yy23

Output -

xy error

 

4) Reverse word in sentence (10 marks)

 

Given a string, reverse only the words in the string. Fist line of the input were number of inputs, say N. Then N inputs were on the next N lines.

 

Example input - 

3
this is a test
foo bar
i love CS

 

Output -

siht si a tset
oof rab
i evol SC

 

5) Line intersection (20 marks)

 

x, y coordinates of two line segments were provided. Output should be 1 if they intersect, otherwise 0. There were 4 lines in the input. First two lines were x and y coordinates of the fist line's end points. Third and fourth line were the coordinates of the end points of the second line segment.

 

Sample input - 

1 2
4 6
-3 5
10 12

 

6) Graph (20 marks)

 

In this problem, we had to remove all the nodes whose degree is greater than k. The value of k will be provided with the input. If a node has a degree greater than or equal to k, the node will be removed and all of its edges will be removed as well. The output should be the number of edges remaining in the graph after all the edges from the nodes of degree >= k is removed. The graph is an undirected graph. Self edges were allowed.

 

Sample input - 

5
1 2
2 3
2 5
4 4
5 6
2

 

First line is N, the number of edges. It is 5 in this sample input. Then N number of edges. In the end, the value of k which is 2 here. In this sample input, only node 2 and 5 have degree greater than or equal to 2. So we have to remove edges (2,3), (2,5), and (5,6). Therefore output would be - 2

 

---

 

After the coding test, I think 67 students were shortlisted. The number of positions available for RA were 28. I have listed the groups with the relevant skills. For most of the groups, they are not compulsory, but having those under your belt would certainly help you. Each group will give a presentation after you have been shortlisted. Then you will have to fill a form where you will order these groups according to your preference. This year a student was allowed to interview with exactly 2 reasearch groups. Depending on the results of programming test, the groups were allotted. So if you did well in the programming test, you will likely get your first two preferences.

 

These groups had RA positions available this year -

 

1) CSE SysAd (~5 positions)

• Unix, Computer Networking

 

2) CC SysAd (~2-3 positions)

• Unix, Computer Networking

 

3) Asynchronous Helpline (not sure about the number of positions. Probably 2)

• Prof Kameswari Chebrolu
• Relevant skills: Django/Python, Android

 

4) Center for Formal Design and Verification (3 positions)

• Prof. Shetal Shah, Prof. Hrishikesh Karmarkar
• Relevant skills: C, C++, Boost C++, OpenMPI

 

5) NVLI (5 positions)

• Prof. Deepak B Phatak
• Relevant skills: Ubuntu, OpenVstorage, Open_edX, Python, Django, Hadoop+, R etc

 

6) eYantra (2 positions)

• Prof. Kavi Arya
• Relevant skills: Machine learning

 

7) CFILT Lab (1 position)

• Prof. Preethi Jyoti
• Relevant skills: ML, NLP, CV

 

8) Information Security Research and Development (4 positions)

     

9) Smart Energy Informatics Lab (again not sure about the number of positions (Probably 2)

• Prof. Krithi Ramamritham
• Relevant skills: SQL, JS charting library

IIT Bombay (MTech RA) written test this time has only Programming test. No GATE based aptitude test was conducted. There were a total of 28 RA positions (including institute RA's).

Test date : 18th May, 2017

Language : C or C++

Q-1: A table of employees with their respective salaries and supervisors was given. Now, we want to increment the salary of an employee but the new salary of the employee must be less than his boss's salary, otherwise either the boss's salary has to be incremented, or else we cannot increment that particular employee's salary.  [5 marks]

Q-2: 'N' people cast their votes for an election. Number of contestants were given. Find the winner of the election.  [5 marks]

Q-3: Assume a string consists of only small alphabets. Print only the distinct alphabets in the given string. And if there is something else except letters, print "error".   e.g  If string is "xxxx22yy" , output should be " xy error".  [10 marks]

Q-4: To print the reverse of a complete sentence.  [10 marks]

Q-5: A graph question was there. We have to have everything as input, like Number of vertices, number of edges, end vertices of each edge etc, and a number 'n'. Then in the undirected graph so formed, remove all vertices having degree larger than 'n' and output the remaining number of vertices.  [20 marks]

Q-6: A question about finding line intersection or something.  [20 marks]

P.S: Anybody who gave the test and remembers the exact questions, please feel free to edit or suggest.

 

Solution:

https://drive.google.com/drive/folders/1045xTCSgG-lPKHEOQAiz1v6PrNpb4p3o?usp=sharing

My interview was on 18th may as my registration number was even. People with odd registration number were called on 19th may.

Students were called for MS and M.tech. Prof. Sarang said that MS is their premier course.  Interview will be conducted accordingly. MS interview will be difficult as compared to M.tech. According to him the difficulty of M.tech interview will be 5/10. and for MS it's 9/10.

they took interview in 2 slots. a.) 10:30- 1:00      b.) 2:30- 5:00.

they called in alphabetical order. so mine was in the 2nd slot.

Average interview duration was around 15-20 min. but if someone was not able to answer questions then it got over in less than 10 minutes too. my panel consisted of 2 profs.

prof: whats your fav subject.?(they asked this question to everyone.)

me: algorithms

prof: do you know quick sort?

me: yes.

prof: how it works? time complexity? recurrence relation?

me: I explained partition algorithm. explained all the cases. and recurrence relation too and also solved that.

prof: ok good. now do you know what is the median of an array?

me: yes. middle element of a sorted array.

prof: ok good. sorting takes O(N log N). but we have to find the median in linear time. how to do that?

me: use count sort algorithm for sorting and then find middle of array.(this is not appropriate answer in all cases)

prof: what is count sort and why quick sort is considered to be the best sorting algorithm.

me: explained count sort. and told its limitation.

prof: now assume that count sort cant be applied there. i.e applying count sort is costly for given array.now find median in linear time.

me: (after thinking for around 10-20sec.) we can use partition algorithm.

prof: they asked me to explain.

me: i explained it. i also explained recurrence relation as they asked for it too.

then they gave me a recurrence relation. and i solved that using recursion tree method. i got stuck while writing its general term. but they helped me in solving that problem.

prof: write structure of binary tree.

 i wrote that.

prof: write a program to find product of leaves of a binary tree using recursion.

=>it was simple problem, initially i explained them how to find that. then i wrote the code. i missed one step which they pointed out. actually, I got nervous. I wrote the major steps(like the return statement, branch checking, whether the node is leaf or not, etc) but messed up in recursion step. Code was around 75-80% correct.

(their remark:

prof 1: programming thoda dheere  krta hai.

prof 2: yha to bhut programming krni hogi.)

prof: you have an array in which initially elements are in increasing order and after that elements are in decreasing order. find the point where change occured.

=>i told them that i will use modified binary search here. they asked what is it?. i told them that instead of dividing n(size of the array) by 2. i will start with first element and keep multiplying it by 2. i.e i will search for 1,2,4,8,16 .....  they asked some que related to it. i.e how will you keep your search within array.? I explained all that.

this logic was ok. then they gave me a situation where the change occurred at a distance of (3/4)n. they asked me to run the algorithm which i suggested. They asked for its recurrence relation and time complexity.

i said O(logn). but they were not convinced and they gave me its recurrence relation acc to which ans was O(logn^2).

(but acc to me its still O(logn).)

note: applying simple binary search would have been better and conventional answer for above problem. I made my life difficult by using modified binary search.

prof: ok. we are done. send next student.

#mine interview went for around 30min.

As mentioned in IIT Delhi brochure, weightage is 70:30. (70% for gate score).

#they said that result will be announced in a week.

After interview i can say these things:

1. Profs are really cool. they will help you if you got stuck anywhere.

2. If you are preparing for IITD interview then algorithms and Mathematics is must. even if you say that your fav subject is COA they will definitely ask problems from DS or algorithms. So it's better to chose algorithms as your fav subject.

3. Only basic problems are asked. So its better to focus on basics.

4. Dont get nervous and try to answer problems in hurry. Take your time ,they provide enough time.

5. Your gate score is not a guarantee that you will get IITD for sure. you have to perform in interview too. they dont publish any formal sheet where interview marks and gate score are added in specified ratio.

 

Result: I got selected for M.tech. :)

                   IIT Delhi interview was held on 18^th and 19^th May. Mine was on 18^th. I think around 300 people were invited for it. This year they have given 70% weightage to GATE score and 30% weightage to Interview. Interview panel consist of 2 professors and generally interview went on for 15-20min. So for me the professors in panel were Saroj Kaushik mam and one sir were there but I dont know their name, but I am 100% sure that the mam was Saroj Kaushik. So I will share the conversation that went between us.

Prof :- What is you favorite subject?

Me :- Data structure and Algorithm

Prof :- What is Binary search tree ?

Me :- Explained

Prof :- How will u check whether the tree is a BST ?

Me :- (Thought for a while) We will do inorder traversal and if it is sorted that means the given tree is BST.

Prof :- Complexity of inorder traversal ?

Me :- O(n)

Prof :- Write Structure for binary tree

Me :- I wrote it

Prof :- Now write for generalized tree ( Generalized tree means a tree having max degree n )

Me :- I wrote it.. Basically I wrote array of pointer instead of two pointers in case of binary tree.

Prof :- But your implementation will cause memory wastage because not every node will have n children that means you will have to store null in the array in that case, which will cause memory wastage.

Me :- ( Thought for 5min ) Sir we can use concept of adjacency list. Basically converting generalized tree to Binary tree.

Prof :- Explain the process to convert generalized tree to Binary tree

Me :- Explained

Prof :- Complexity of Binary search

Me :- O(logn)

But they told me that I should also tell it with base 2.

Prof :- Difference between binary search and ternary search ?

Me :- Explained

Prof :- What is the complexity of ternary search ?

Me :- (This time) O(logn) with base 3.

Prof :- which is bigger logn with base 2 or logn with base 3

Me :- logn with base 2

Prof :- Then why we prefer binary search over ternary search ?

Me :- ( was not able to answer )

Prof :- write recurrence relation for binary search and ternary search.

Me :- I wrote it

Prof :- Now find the complexity using those recurrence relation

Me :- while finding the complexity I found out that for ternary search time complexity was O(2logn) with base 3 and for binary search it is O(logn) with base 2. So after comparing these 2 you will find out that complexity of ternary search is greater than binary search.

Prof :- Draw an example of heap tree fast

Me :- (puzzled, how can they ask such an easy question) I drew the tree.

Prof :- Ok you are done

Me :- (I was happy that it went well)

 

So what I learnt from this interview was that they give some hint if we stuck somewhere. For me I was stuck on comparison between binary and ternary search, So they told me to write there recurrence relation and then evaluate it.

 

Verdict :- Selected :) 

 

 

                My GATE 2017 rank is 101 and I was targeting IIT Kanpur and IIT Delhi for admission. So in this blog I am writing about my tests experience at IIT Kanpur.

                This year they called around 400 people for the test. They conducted 3 tests(Objective, Programming and Subjective). They conducted Objective and Programming test on 13^th May. On the basis of these 2 tests, they shortlisted around 180 people for Subjective test which was conducted on 14^th May. Among all these 3 tests, Objective test was the easiest one.

 

•  Objective Test

                Objective test consist of 3 sections(Theory, Systems and Statistics & Data science). Each section was of 50 marks and we have to attempt any 2 sections in 3 hours. There were some fill in the blanks and one line answer questions too and for the questions with options, more than one option can be correct. There was no negative marking. Some of the questions asked in this test are :

1) Theory

i) 8a + 19b = 1. So find out the possible values of a and b.

ii) one dfa was given and we have to choose the correct regular expression for it from the options given

iii) DFA was given and the probability of each link in DFA was also given. So we have to find the probability to reach a particular state using the given 2 strings.

2) Systems

i) A question on semaphore to find initial value of semaphore variable

ii) To find number of hosts in a network given the subnet mask

iii) Difference between clustered and non-clustered indexes

iv) Number of clustered and non-clustered indexes

v) A query is given with EXIST clause and we have to rewrite it without using EXIST

vi) A question on finding accuracy of Branch prediction. A DFA was given for it and program sequence was also given telling whether it will take the branch or not

 

• Programming Test

                    I am not able to recall questions from Statistics & Data science because I attempted only theory and Systems section. Next was the programming test. There were 4 programs to solve in 3 hours. Marks of each program were 30, 40, 60 and 75. The questions asked where :

1) Question to check anagram ( 40 marks )

2) Starting index of leaves and value of leaves of complete binary tree where given, with the property that parent will have min(left child, right child). We have to return the the contents of indices asked for the tree. ( 30 marks )

for example,

starting index = 3 and

leaves values are 1, 9, 5 and 2

above 2 information will be given, So the tree will be like

    min(1,2)=1

    /               \                                                      1

min(1,9)    min(5,2)          =>                       /     \

  = 1           = 2                                                1        2

 /     \        /     \                                           /   \      /  \

1     9      5      2                                           1     9    5    2

3) There are p prisoners and c ( > p) cell blocks. c and p will be given as input. Also a sorted list of c integers will be given. You are required to choose p integers from c integers such that the minimum distance between adjacent prisoners is maximized. You have to output this minimum distance. ( 60 marks )

4) We have to find addition factors of a number in lexicographic order for n<15. ( 75 marks )

for example if n=4 then output will be

1 1 1 1 

1 1 2

1 3

2 2

 

• Subjective Test

                     Finally there was a subjective test similar to objective one. We have to attempt questions from any 2 sections in 3 hours. There were 3 questions from theory and 3 questions from Systems. Questions asked where :

1) Theory

i)  

a) if degree of vertices < 3, then prove that the graph will be union of vertex disjoint path and cycle.

b) Graph Matching was explained. Let S and R be the matching graph, then a new graph G=(S-R) ∪ (R-S), will be union of vertex disjoint path and cycle. Also prove that the cycle obtained will be of even length.

ii) Consider a grammar G with productions P. Let INIT(G) be the grammar with production P' such that

    P' = P ∪ ( A->B | such that A->BC belongs to P ) ∪ ( A->epsilon | such that A->b belongs to P )

    prove that:

a) Prefix(G) is subset of INIT(G)

b) INIT(G) is subset of Prefix(G)

iii) Algorithm to find strongly connected components in the graph

2) Systems

i) Question on semaphore. A program was given which was incrementing variable y. 8 processes where allowed to execute the program. Initial value of y was given. We have to find possible values of y after all 8 processes complete their execution.

ii) Information about main memory and cache was given. We have to find number of bits for tag and index for direct mapped, set associative and fully associative cache. We also have to find cache capacity including tag overhead for each cache. Also explain the working of each cache mechanism.

iii) I didn't understood this question.

 

                                I have written as many questions that I recall. If you guys remember any more questions especially for objective one, write in the comment, I will add it.

Verdict :-  Selected :)