ISI MTECH CS 2019 INTERVIEW EXPERIENCE

Question

I qualified the written exam of Mtech CS and selected for interview and my interview was scheduled on 15th june 2:30-5:00 pm.
There were 4 professors (as the day was saturday thats why less professor otherwise there can be more on week days) in the class. As I entered in the class they greeted me and offered me to sit, then they asked me about my college and university as they don't know about that, then they asked me about the city also and i told them all these stuffs, then they asked me about my favourite topics in maths and favourite subject , i told them number theory and combinatorics, for cs i said toc, but they said that if they asked from ds and algo will that be a problem for me? Now, as i prepared only for toc but now i can't say also that no don't ask from ds and algo, so i said yes you can ask.
Questions
1) Combinatorics:-As due to rain, the match between the teams in icc world cup got cancelled , So lets the total team be 10, exclude semi finals and finals , consider only league match, tell me the total number of matches that played between the teams such that each team has get exactly one match get cancelled due to rain among them.(I answered this but after hints).
2)34x=43y
Prove that x+y is a composite number.(I solved this but after hints).
3) Graph of cosx vs sinx( I draw the graph and gives correct answer, now they were shocked as i draw within 10 seconds).
4)3cosx vs 4sinx.( After think for 30 seconds, i draw this also and that was also correct).
5)prove that i raise to the power i is a real number( one professor said skip this question.) Still i tried but don't get the answer and skipped that one.
6)Given the array of numbers such that A[i]=i, for all i except when i=t, and A[t]=t+1, Find the t.( I first started writing algo then they asked me to explain my approach first i told that my algo will take O(n), so then they asked can i optimized the algo , then i took some examples and then told them that i will apply binary search which will take O(log n). Then said OK Thank you leave now.

End game:- My rank was 36(general category but seats are 17) in the merit list as i qualified for the interview also, but don't think that only getting name in merit list will give you admission in isi ( as i don't know about this earlier, My only advice to juniors who are giving isi 2020 mtech cs is that just try to score maximum in mma and pcb).

Comments

Thanks Vipul for sharing your experience. These are some truly insightful questions. Do you know how to solve the 6th one?

(I don't think you can do better than an O(n) solution)

---

yup you have to look at every index, cannot skip any

---

Actually we can solve it by Binary search as the array is initially sorted. Let me explain:

suppose the array is A[ ]={0,1,2,3,4,5}(Because array number assign like A[i]=i)

But as per question instruction we must have a index t where A[t]=t+1;

suppose in the above array :

Example 1:  we chose t=2, then the array looks like:

A[ ]={0,1,3,3,4,5}

Example 2:  suppose we chose t=1, then

A[ ]={0,2,2,3,4,5}

So observing above two example I find out that if we chose the value of t=0 to N-2, (where N= size of the array) there always only one repeating element present in the array and if we chose t=N-1 then there are no repetition. So we can easily find out the only one repeating element using binary search.

Here is my code:

int Find_Repeating_element(int a[], int n){

    int lo = 0;

    int hi = n - 1;

    int mid;

     

    while(lo <= hi){

        mid = (lo+hi)/2;

         

        if(a[mid] <= mid){

            hi = mid-1;

        }

        else{

            lo = mid + 1;

        }

    }

     

    return lo;

}

// this function return the repeating element so final answer will be index of (lo-1)

// if there is no repeating element then answer will the last element's index.

// time complexity is O(logN)

//I hope it Helps