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