The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
1,139 views

                   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 May 22, 2017 in Interview Experience by Loyal (9,085 points)
edited Jun 6, 2017 by | 1,139 views
0
Like
0
Love
0
Haha
0
Wow
0
Angry
0
Sad

10 Comments

Do share the results please!
yes, I will update it
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?
Thanks for sharing your interview experience. :)

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

Did you get an offer from IITD on the TCS iON COAP portal ?
not yet, but it is also possible that I am not selected
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?
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.
How did you convert general tree to adjacency list?Can you share that approach?
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

42,556 questions
48,547 answers
155,290 comments
63,498 users