first search for how to apply for MS at IIT KGP. (it’s a complete different process)
There were different panelists with different domains, level questions keep increasing as you give the answers.
Q. What is BST?
Q. BST search complexity average and worst and when worst?
they’ll share a google doc with you to write on it as they can see it too.
Q. complexity of quicksort?
Q. write pseudo code for quicksort partition function?
Q write recursive call function of quicksort?
Q. Given this array, apply quicksort on this?
→ I totally did forget how to write partition, recursive code, even given a array I was not able to apply the quick sort on it, more because I tried to remember the quick sort solution I studied in coaching, but professors will keep supporting you, so I decided to build some new algorithm for it and developed a new algorithm for quicksort there.
Q. How to dynamically allocate 2D array in C?
→ I don’t code in C, so told them and they were fine with it,
Q. write on the doc big Oh notation of functions.
Q. what if they f(n) and g(n) are equal.
Q. write mathematically f(n) = O g(n)
→ f(n) =< C g(n) for all n>x , need to find x given a C
Q. lots of discussion on this finding x and C?
→ not how to find it or finding them, but what to do the f(n) is equal to g(n)
→ i think i messed up here too, gave a 50-50% sure not sure answer
Interview ended.
on the same day, I received an email stating my performance was decent but for satisfying and a 2nd round of interview is being scheduled for me after 2 days. I prepared well in those 2 days, there was no sorting, searching algorithm i can’t code now, jokes apart, prepare your gate notes for DS and algo, that’s enough.
Sad, this time they didn’t ask anything from i prepared , rather asked coding questions.
Q. Given an array find and X find pair in array whose sum is X?
→ i was happy it’s pretty standard question you would find in every preparation. they want you to start with a naive solution and then optimize it, I stated the naive solution and gave it’s complexity as n^2, and quickly wrote it’s code on the shared doc,
→ I knew the solution for O(n) but still din’t gave the answer right away
→ Then gave a optimized solution with hashmap and wrote its code which theoretically should give O(n) but was giving O(n^2) still because of searching in hashmap.keys() returns a list, I replaced it with set which again gives O(n^2) because of forming set everytime, you can use add element to set also which won’t give O(n^2), somehow we ended up to O(nLogn) as used binary search also, and i ended the discussion with the best solution i knew with O(n). believe me O(n) is the solution you’ll find in most of competitive course or website for this problem, but the professor gave me some more hints and was able to solve it in O(1), haha, shocking.
Q. asked I code for graphs, I told NO, he was happy i said NO so he can ask question on it only, Find the greatest distance can be covered in a given graph,
→ well i was not able to solve this and professor skipped it as i took lot of time.
Q. We have a problem of size N and it is divided into “b” subproblems and from those b problems we only solve “a” number of subproblems , and each problem take O(1) to solve, write recurrence relation for it.
→ never saw a question like this but as i prepared the gate notes just a day before I got the concept and solved it in seconds .
Q. In the formed recurrence relation give an example (name of algorithm) where a=b?
→ gave answer as quick sort.
Q. give an example (name of algorithm) where a!=b?
→ I had no ideas about it, after a hind i gave a right answer binary search.
Interview ended
this interview went nice. and got selected,
