3,525 views
1st Round Interview:

T: Introduce yourself

Me :Gave small introduction

T:subjects in which you are comfortable to answer

Me: Data structure and Algorithm

T:How to find maximum element in a Binary Search tree

Me:first i told general approach(similar to find max in array) then they sent  me to  board then i explained efficient way (logn complexity)

T:can u write pseudo code for what you explained

Me:I wrote

T:There is an integer which is greater than every integer. Is this statement  true or false?

Me:false

T:why??

Me : explained

T:write first order  logic of what you explained.

Me:$\forall x,\exists y,y>x$

T:negate the above statement

Me:done

T:what is this statement mean

Me:explained

T:why deadlock will occur here(questions from the written test)

Me:explained

They told me to wait because there may be another round of interview

After 3-4 hours ,they called me again for another round of interview

Interview Round 2(for formal method project):

T:what are the sorting algorithm you know

Me:told all 7 to 8 algorithm name which i knew

T:which algorithm you think is better

T:why you are saying this and why not this and few more question

Me:i replied all

T:Let G(V,E) be a graph. Let w(ei) is weight of edge i. w(e1)<w(e2)<w(e3).........<w(emax). Let T is MST of G.

i) w(e1) ∈ T, ii)w(e2) ∈T , iii)w(e3)∈ T ,iv)w(emax) ∈ T

Me:Explained for first two case(easy one)

Me:In somecases w(e3)∉T

T:why??

Me:Explained

Me :In somecase w(emax) ∈ T

T:why?

Ans:Explained

T:what is the time complexity to find 3rd max element in max heap?

Me:I went to board and explain clearly (O(1) time complexity).they were looking satisfied by answer.

T:Sorted array is given .You have to find two number from array which is equal to C(given number)

Me:first i explained algorithm which takes $n^{2}$ time

T:Even if array is not sorted we can do in $n^{2}$ time .can we do in better way because we have sorted array

Me:I gave nlogn algorithm.

T:what you told is correct but can you optimise it more

Me :tried but not getting

T:they gave hint like $a_{1}+a_{n}>c(given number)$$a_{1}(first number of array)+a_{n}(last number of array)>c(given number)$

Me:after thinking little bit i got O(n) algorithm.they satisfied by answer

T:Draw an automata for language having as many occurence of 10 as 01?

Me:I started drawing but in the mid they stopped me

T: 3 red ball(identical) and 5 green ball(identical) .no of ways we can arrange such that no two red ball are adjacent

They told i am done. I was happy because i answered almost every question and feeling satisfied.

After 15-20 mins

3rd Interview(for parallel processing project):

T:why mutual exclusion will occur here(question is from written test)

Me :Explained in detail on board

T:Another question from written test regarding synchronization

Me:not able to answer but made me to think then they gave hint and at last they explain me the answer

After coming out of interview room i was very happy .

I hope this post may help at least someone who are preparing for gate 2018

My gate rank is 527 and score is 728
posted Dec 16, 2017 | 3,525 views
2
Like 0
Love 0
Haha 0
Wow 0
Angry 0
Sad Thank you for sharing. Beautiful questions asked from Data Structures.
thank you :)

Sorted array is given .You have to find two number from array which is equal to C(given number)

this can be done in log n time right ?

why O(n) ?

How ??
@A_i_\$_h What if all elements are equal ?
Actually it is to find 2 numbers whose sum equals C, right? @Indrajeet

yes @ Shivansh Gupta

3 red ball(identical) and 5 green ball(identical) .no of ways we can arrange such that no two red ball are adjacent.

For this did you answer 6C3?

Thank You Sir for sharing :)
@indrajeet

since the word "sum" was missing i misintrepreted the question sorry :)
time complexity to find 3rd max element in max heap is O(logn)

How it can be O(1)
what is the time complexity to find 3rd max element in max heap?

i think ans is o(logn).
even i have that doubt on how it can be found in O(1) time

@indrajeet can you help us :)
Sounds quite tough to me :-/
3rd maximum in max heap in worst case can be upto 2nd level(assuming root at level 0), and upto 2nd level you will have 7 elements only, now to find 3rd maximum among 7 elements it will take constant amount of comparisons, so it is O(1)
Yes @joshi nitish you are right
@joshi_nitish

We have to think all type of possibilities it can't be in only 2nd level it might be in 3rd or nth level like this...

this is a property of max heap that, kth maximum element will be present within k levels and similarly for min heap kth minimum is present within k levels.. you have given very trivial example, see here 3rd max is '7' which is present at level '2'...

no matter how big is your max heap, 3rd max will never go below level '2', and this was what i was telling in earlier comments.
Got it! @joshi_nitish

Thank you :)
@joshi

among 7 elements to find 3rd max is O(1) how ?
it is similar to an unsorted array with 7 elements and we have to find the 3rd max right

Congrats :) So you are really ready to join research. You can do it well and do even better than while taking a TA course. The only thing to consider is

1. Area of interest.
1. If you already have this, then most part is done. Otherwise think and finalize what yu want to do. Most of the areas wont be exactly mapping to a B.Tech. course -- Machine Learning, Security, Networks, Formal Methods, Numerical Analysis, Robotics -- there are the kind of areas one should look at. Then see their basic requirements which will be some Discrete Mathematics and algorithms.
2. Do not talk to fellow mates about "TA" and "RA". Only good RA people can guide you here. If you join "RA" with a mentality to just finish fast, it wont be good. If you join "RA" with a mentality to do good work, then you will do good and often finish faster.
Thanks sir.GO played an important role in my life specially your guidance.

I am interested in machine learning but i was interviewed for parallel processing and formal method(which is also interesting for me).i want to know along with research work can i learn machine learning there??

@indrajeet RA students are enrolled in December also? New session in December?

Dont they ask for why you are interested in MTECH RA and not TA?

I Got AIR 888 in GATE 2019.Categgory general.Will I get call for MTECH RA from IITH ?