IIT Delhi interview was held on 18th and 19th May. Mine was on 18th. 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 :)