**Disclaimer: Very Very Long!!**

* Exams*:

Gate: Score - 717

Jest: Part A - 44 marks. Part B - not disclosed

* Preparation*:

May 2016 holidays - Solved prev yr gate qns of Theory of Computation.

End of Dec 2016 - Jan Beg: Read few topics from Rosen Discrete Math, DS and algo and solved prev year Gate qns. Watched some videos of Shai Simson for revision of TOC.

Jan - Feb: Solved and revised prev yr qns of DBMS,OS,Digital Logic. Solved few topics from Computer organization. Skipped networking. Gave few mock tests but scored poorly. I was almost about to give up at this point but convinced myself that this preparation will be useful if I take a drop. I stopped giving Made easy tests because it was lowering my confidence. Gave some tests of virtual gate and Gate Overflow.

**Not many know about this exam. but it is one of the most challenging exams I have given. Topics are mainly Discrete Math, DS and algo, TOC, Linear algebra, Probability. There are 2 parts. Part A - MCQ. Part B - Subjective Questions. Unfortunately I don't remember those questions now. So I made it a point to note down all questions in my future inteviews.**

*About JEST exam*:In subjective part I attended 5 questions. More emphasis is given to proving the solution correct. I don't think I answered any of them completely correct. Yet I was called for the interview at IMSC. IISC considers the Part A score of JEST for M.Tech Research but cutoff is high. IMSC calls for interview based on Part B performance.

[The following description is based on my memory and the points I have noted after the interviews.]

**IMSC interview experience: **

IMSC is a totally peaceful place. I reached early and waited for a hour. I read the quotes in the walls and passed my time.

I was totally nervous. There was about 5-6 (or 7, I forgot) interviewers. They made me feel comfortable and were very friendly.

Initially they asked me to draw automata of few regular expressions. I drew it correctly but even I couldn't understand what I have drawn. So they asked me to draw again.Then they asked me can you say **WHY **they are correct. I started explaining but they were expecting a **FORMAL PROOF **which I realised only after the interview!! Then they asked me to draw a minimal automata for the language (a*b*)*. I said it is equal to (a+b)*. Then they asked me to prove it. I said any string x in (a*b*)* will be in (a+b)* because (a+b)* is set of all strings in alphabet {a,b}. So (a*b*)* is a subset of (a+b)*. Now any string x in (a+b)* will consist of a sequence of 0 or more a's, followed by sequence of 0 or more b's, followed by 0 or more a's, followed by sequence of 0 or more b's and so on. So it will be in (a*b*)*. So (a+b)* is also subset of (a*b*)*. So both are equal. Then they asked me to prove the same using Induction. I made terrible mistakes which I realised and said to them. However I was not able to correct them at the time of interview. It was quite simple but I got tensed at that time.

- The second question was: Given a simple graph having more than 1 vertices prove that atleast 2 vertex have the same degree.

Proved it using Pigeonhole principle.

- The third question was: Given a graph having a odd degree vertex prove that there exists another vertex having odd degree which is connected to it.

Proved it using Handshaking Theorem.

Finally we discussed about AVL trees. The discussion was not too detailed but only the basic ideas. (I must have revised it :( ). Then they asked why AVL tree over a simple BST? Why BST better than sorted array? Why sorted array better than sorted linked list. Finally they offered me a wonderful Coffee :)

I was happy after the interview despite making mistakes.

**IISC Interview Experience**

I was enjoying the beauty of IISC Campus and so reached the department just 5 minutes before the written test. I hurriedly filled up the forms and went to write the exam.

* Written Test*: 10 Questions, 30 Minutes. Most candidates were called for the interview.

*: [This description is more verbose than the IMSC since I noted down my experiences and feelings after the interview. The sandwich part is bit exagerated!] Much more challenging than IMSC interview. I made more mistakes than the IMSC interview. I was the 3rd person to be interviewed in morning session. Interview lasted for about 45 minutes or more. 9-10 interviewers were there. Despite getting IMSC I was tensed once again. First they read out my details and the background subjects which I had chosen (Discrete Maths, DS and algo). They asked me which area of Discrete maths I was comfortable with. I did not reply fearing they might ask too difficult question in that topic. I requested them to ask any question and said that I will try to solve them. Now the shock comes!*

**Interview**

['I' stands for a general interviewer.]

**I**: Given a d-regular graph how many colors are needed to color it.

**Me**: (I was almost sure I will fail, but yet decided to give it a try). Now since every vertex is adjacent to d other vertices at least d+1 colours are needed.

**I**: Can you come up with a upper bound on number of colors as a function of n,d where n is number of vertices?

**Me**: Trying to come up with a solution. Made so many mistakes. Finally to play safe I said: If there are n vertices, then for a d-regular graph atleast d+1 colors and atmost n colors will be needed (Wow!!)

I: (Some of them laughed I think) Can you come up with a better upper bound?

**Me**: I will try to draw some d-regular graphs and see.

I: Try with n = 3 and d = 5. (Please see the trick here)

**Me**: Trying to do that. Kept on drawing so many graphs. Finally I said I will try for n = 4

I: No, try for n = 3 with the graph you have just drawn.

**Me**: Trying again. Finally realized what I was doing. Sum of degrees of this graph is 3*5 = 15 which is odd. Sum of degrees must be even. So this graph is not possible.

**I**: You said that you need at least d+1 colors. d+1 is also the upper bound. How did you come up with that? Can you prove it? (This made things easier for me since they already said the upper bound is d+1)

**Me**: Thinking for a long time. I was telling them whatever I was thinking. Made mistakes again. So a d-regular graph will have atleast d+1 vertices. Take any vertex v, color it with c1. Color all it's d adjacent vertices with color c2,c3,...,cd+1. Then make a set for each color. Put vertices having color ci in set i. Now take any vertex which is not colored yet. It will be adjacent to exactly d-vertices. Which means there is atleast one set j to which it will not have any adjacent vertex. So we can reuse the color cj. So d+1 colors are sufficient.

**I**: OK, what can you say about any two vertex in the same set?

**Me**: They will not be adjacent.

**I**: In other words?

**Me**: They will be completely disconnected.

I: Yes they will form a independent set. Can you say anything about any two vertex which are in different sets?

**Me**: (Made a huge blunder) Each vertex in a set i will be connected to all vertices in set j.

**I**: One of the interviewers drew a 1-regular bipartite graph on the board.

**Me**: (Realized my mistake)Oh I was wrong!!

**I**: Can you now say the modified statement?

**Me**: For any two sets i and j there will be at least one vertex in set i which is connected to one vertex in set j

**I**: Why??

**Me**: Because if they were not connected then we could use the same color to color the vertices in both sets and this means we need less than d+1 colors.

**I**: Ok Now what can you say about a 2-colorable graph?

**Me**: It is a bipartite graph

**I**: Right, can you come up with an algorithm to find if a given graph is 2-colorable or not?

**Me**: (In my mind: Ohh my god!!) Thinking...took a lot of time. Take 2 empty sets. Start with a vertex. Put it in set 1. Put all vertices adjacent to set 2. Then take any vertex from set 1. At this point I started struggling. They asked me some questions. I got confused and I doubted my approach. Then I came up with a new approach. One of the interviewer gave me a graph where my new approach fails. Then I resumed the original strategy. Start with a vertex. Put it in set 1. Put its neighbors in set 2. Now pick a random unprocessed vertex from set 2. If any of its neighbors is already in set 2 then graph is not bipartite. Otherwise put those adjacent vertices which are not in set 1 into set 1. (However I did not state this as clearly as I have written it. )

**I**: Ok, Can you prove that this algorithm is correct?

**Me**: Struggled but could not come up with the proof!

**I**: Tried to help me. Offered me Sandwich and asked me to relax.

**I**: Alright you can solve this problem Offline. Thank you! We are done. You can have the sandwich.

**Me**: (About to take the sandwich)

**I**: Ok we will just ask a question on ds. Do you know about arrays?

**Me**: Yes

**I**: How will you find the intersection of two sorted arrays.

**Me**: May be we should use merge procedure of merge sort. Explained how to find common element (but not so clearly).

**I**: What will be the cost?

**Me**: Explained that. Linear time and Linear space.

**I**: What if we don't want the extra space?

**Me**: We can use binary search. for each element in Array A search it in B.

**I**: How much time will it take?

**Me**: mlogn. m - size of smaller array, n - size of larger array

**I**: What if we want to use constant space but also want linear time?

**Me**: (Thinking)

**I**: (Gave a hint) Think about the merge technique you first said

**Me**: (Got the idea)Yes we really do not need extra space. We just need two pointers into the array.

I: can you state what action must be performed if i is pointing to A[i] and j is pointing to B[j]?

Me: If A[i] == B[j] then it is a common element otherwise move the pointer pointing to the smaller element forward.

**I**: Thank you.

**Me**: Left without having the sandwich

Overall it was a wonderful feeling of being able to approach these problems, but I wasn't sure of getting selected since I made too many mistakes and was taking too long to think. I am happy that I got this year itself :)