The Gateway to Computer Science Excellence

They called approximately $80-90$ people for interview. For interview cut off follow this link:

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 ( were my interviewers.

Professor Antony: Introduce yourself.
Me: Answered.

Professor Antony: What was your answer regarding question $2b$? TRUE or 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.

posted Jul 16, 2017 in Interview Experience by Veteran (60,905 points) | 9,401 views


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 :-)

@Digvijay Pandey can you please explain answer of probability question Thanks :)

Was the selection purely based on interview performance?

Or was it also dependent on the gate score?
For the question 16 teams : first 8 matches(16 teams) will decide 8 winners,

next 4 matches(previous 8 winners) will give 4 winners,

next 2 matches(previous 4 winners) will give 2 winners,

next 1 match(between previous 2 winners) will give first and second winner.

so total 8+4+2+1=15 matches. but by the formula you have given n+logn-2 will give 16+4-2=18 matches.

Where I am getting wrong ?

@Saikumar_Baalu ; in the last step, you assumed that first & 2nd winner will always play the finals.
The second winner will only lose to first, this can happen in any of the 4 stages(16, 8, 4, 2), for example, 1st and 2nd faced each other at the first stage where there were 8 matches and 2nd got eliminated. Thus we need 3 additional matches between the 4 teams who lost to 1st to get the 2nd winner.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,365 users