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

 

 

posted in Interview Experience May 22, 2017 edited Jun 6, 2017 by
3,202 views
1
Like
0
Love
0
Haha
0
Wow
0
Angry
0
Sad

11 Comments

11 Comments

Like
Do share the results please!
Like
yes, I will update it
Like
In the case of ternary search, the list would be divided into three equal parts. Isn't it?. Would the approach then be similar to that of binary search?
Like
Thanks for sharing your interview experience. :)
Like

yeah, the list will be divided into 3 equal parts and as a result recurrence relation will be

T(n)=T(n/3)+2

n/3 is becoz every time over search space reduced to (1/3)rd and +2 is becoz we are comparing 2 times

Like
Did you get an offer from IITD on the TCS iON COAP portal ?
Like
not yet, but it is also possible that I am not selected
Like
Actually, my gate score was 869, and my interview didn't go too bad, but even then I haven't received any offer from IIT D. I've mailed them. Hope they provide a list on their website or through mail. I don't seem to trust the portal.
Why do you think you won't be selected? You got selected at Kanpur, maybe here too?
Like
I mean to say that it is possible that they have uploaded the list on COAP, but since I didn't got the offer, I thought maybe I am not selected.

My GATE score is 852 and my interview went good, so I am also hoping to get selected there.
Like
How did you convert general tree to adjacency list?Can you share that approach?
Like
please anyone who has idea of this reply