GATE CSE
First time here? Checkout the FAQ!
x
774 views

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 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(ei) is weight of edge i. w(e1)<w(e2)<w(e3).........<w(emax). Let T is MST of G. State given statements are true or false. Give counter example also.
a. w(e2) ∈ T
b. w(emax) ∉ 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 interview.  There were four interview panel. 

 

 

Interview Part :

Room no 311.

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

Professor Antony : Introduce yourself.
Me : Answered.

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

Professor Antony : can you prove this ?
Me : (Took marker explained why it is false). My 1st argument was if G itself is a tree so emax must be in T.
2nd argument : Even if G is graph but not 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 diagram.

Professor Sakethnath : You are good in maths ?
Me : (Silently accepted )

Professor Antony : There were 25 teams and we have 5 processors. At any point of time we can select 5 teams and that will give 1 winner. So how many matches we need to find winner ?
Me : 6. i guess

Professor Sakethnath : Guess or sure ?
Me : Sure sir ☺

Professor Sakethnath : Let me modify this question. There were 16 teams. A match between any two teams will give winner. So how many matches we need to find winner and second winner ?
Me : can i explain it on board ?
Professor Sakethnath : yes go ahead.
Me : Explained everything with 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 : Sir your question is same as 'Finding max and second max element from an array of n element'. Explained with Tree diagram. They were trying to trick me here and there but i was confident. Finally they agreed.

Yess and that gave me some confidence!!!

Professor Antony : You have two coins with head probability p1 and p2 respectively. Just select any one coin randomly and toss. What will be probability of getting head if previous attempt was also head ??

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

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

Professor Sakethnath : Now tell me what will be answer of previous question ?
Me : Again i wrote same formula

Professor Antony : You know linked list ?
Me : (ab aaye h sahi jagah ) Yesss sir.

Professor Sakethnath : A linked list with head pointing to first element of list is given. How will you implement 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 end it will take O(n) time, but enqueue and dequeue operation in 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 : Sir insertion will be at head that will take constant time but deletion at end will take O(n) time. Thats why i am thinking some other way such that deletion will also takes constant time.

Professor Antony : Who told you insertion deletion will take constant time ?
Me : Sir i 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 head and insert at end ?
Me : Sir still it will be a queue but in this case 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 whole algo. They asked me to allocate memory dynamically. I did. They 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 sir.

Both professors were very friendly. And this  was my one of the best interview of year 2017. I enjoyed it .

 

Finally on July 13, 2017 i got e-mail from IIT H.

 

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

posted Jul 16 in Interview Experience by Veteran (46,155 points)   | 774 views

7 Comments

Thanks for sharing, What was the cut off for Hyderabad?
Updated :-)
Awesome math questions. Thank you for sharing.
thanks for sharing all the questions, have a great memories in IITH and best of luck :-)

Congratulations  Digvijay Pandey for IIT Hyderabad.

Thanks everyone :-) All the best ☺
Hello digvijay! congratulations for getting into IIT and thanks for posting questions here. i was studying algorithms and at that time only i read ur post. one question u mentioned about implementing queue using linked list. I think enqueue and dequeue both can be implemented in O(1) time as there is also this question in cormen exercise 10.2.3, if we keep head as front and another pointer as rear, then we can dequeue from the front taking O(1) time and each time when we insert a newnode in the end we assign rear=newnode. so next time when we insert then insertion can be done in O(1) time.
Top Users Jul 2017
  1. Bikram

    4894 Points

  2. manu00x

    2888 Points

  3. Debashish Deka

    1870 Points

  4. joshi_nitish

    1776 Points

  5. Arjun

    1496 Points

  6. Hemant Parihar

    1306 Points

  7. Shubhanshu

    1128 Points

  8. Arnab Bhadra

    1114 Points

  9. pawan kumarln

    1114 Points

  10. Ahwan

    940 Points


24,089 questions
31,062 answers
70,677 comments
29,400 users