I had my IISc Mtech(Research) interview from the CSA department scheduled on 25th may 2:00 PM.
The process consisted of written test followed by the interview on the chosen background subjects based on research area chosen.
We were given 30 mins for 10 questions,we had to attempt all of them. Questions were
(1)A simple C code. We need to tell the output.
(2)Given a grammar S->aSa | bSb | a|b. What language does it generate?
(3)Given a B+tree in which the maximum number of keys in any non-root node were told. We were asked to tell the minimum number of keys in any non-root node.
(4)Question-based on Unix Inode, finding maximum size of the file in file system.
(5)Cache size, block size, associativity and physical address length is given, find the length of tag bits.
(6)Some functions were given, arrange them in increasing order of asymptotic complexity.
(7)Given a max-heap representation as an array A, what would be worst case time complexity to search for an element?
(8)Two dices are rolled. Let Y be the maximum of two outcomes. The expectation of this random variable Y.
(9)Given a non-singular matrix A, with eigenvalues $\lambda _{1},\lambda _{2}....\lambda _{n}$.Given a non-singular matrix R, find the eigenvalues of RA2R-1.
Within 10 minutes results of the interview were declared and I was shortlisted for it.
Chosen areas:
Main Research Area-Computer Systems
Sub-Area: Database and Computer systems Security
Background subjects: Data Structures and Algorithms, Engineering Maths.
Interview: The interview panel consisted of three professors and they had my application form beforehand.
I will refer I for the Interviewers and M for myself.
Questions asked were
I: Given a binary tree and a traversal order can we construct it uniquely.?
M: To this, I replied that we need inorder and anyone from the postorder, preorder or levelorder.
I: why do you specifically need Inorder.Why not any other order?
M: I told them that Inorder provides us with the details of the elements present in left and right subtrees of an element.
Now came another question
I: Given an arithmetic expression, can you draw an expression tree?
M: Yes sir.(now got tricked!!)
I: But now only you said you need two orders for constructing a binary tree, now in this case how can you construct the expression tree.
M: Sir, because in the expression we know the associativity and precedence of various operators using which we can draw expression tree.
But the interviewers didn't seem to be impressed by this answer and they were expecting something else.
I: Okay Ayush. Let's take a linked-list and an integer n. Design a function which will delete the nth node from the last.
M: I thought and told them first we can count the number of nodes in the list and accordingly take pointers and make the delete operation.
I: You are not allowed to count the number of nodes in the list!!.
M: I got stuck now!. I thought a lot but was unable to answer.
I: You can take multiple pointers if you want.
M: Since I was completely blank at that moment, I didn't get to know how to use the above hint that was given.(Yes, Multiple pointers!!).
I: Okay Ayush! We'll ask you some other question.
I felt bad as it was the initial phase of the interview in which I failed to make an impact. Still, I waited for some good things to come.
I : You have a graph with n labelled vertices. How many undirected graphs on these labelled n vertices?
M: Answered as $2^{\frac{n(n-1)}{2}}$. Explained to them how this expression came. Whatever I was thinking, I was telling them. They guided me accordingly.
I:Okay. What this term $\frac{n(n-1)}{2}$ is called?
M: I told them this is half of the degree sum of the vertices or the maximum number of edges in a graph or result of handshaking lemma.
I: No no!!, it's something else!!.
M: I was puzzled. What more it could be now I was thinking inside.
I:aaahh it's $\binom{n}{2}$.!!
M: Yes sir. That evaluates to exactly this :D
I: And, what would be the result in case of directed graphs?
M:I replied it's $2^{n(n-1)}$
I: It's correct!. Do you know graph isomorphism?
M: I forgot that the adjacency matrix for an undirected isomorphic graph are similar and not equal always, but said they were equal.
I: No, they are not same. They could be permuted in some another way.(He gave a hint about the existence of a permutation matrix which can transform one matrix to another in case of isomorphic graphs).So, give me a mathematical expression for graph isomorphism?
M: I was again puzzled(Mathematical expression??), so I told them the definition of isomorphic graphs.
I: Okay, given a cycle on n vertices which is isomorphic to its complement. Can you find n?
M: I started to solve it, and was stopped in between as they said: "Yes, you can find n okay stop!".
I: Ayush, you have chosen your sub-area of research as computer systems security.
M: Yes sir.
I: So, what all do you know in that?
M: Sir, I know all the protocols that we have studied in network security.
I: Please name a few of them.
M:Diffie hellman, RSA, Digital Signature, DES.
I: Okay, what is the pitfall in Diffie Hellman?
M: I explained him the scenario of Man in the middle attack without actually naming this phenomenon.
I: What this phenomenon is called?
M: This is known as the man-in-the middle attack.
I: Yes, and what do you do to prevent this?
M: We can authenticate users before going for the process of setting up key.
I: How do you authenticate users?
M: We can use digital signatures.
I:Yes, we can use it.
Okay Ayush, let me give you a scenario based question.
(I was like OMG. What scenario it may be. Okay let's deal with it)
M: Yes sir Please say.
I: Given a Web-application that runs on a server, this Web-Application uses a database, makes some modification to it and at the end of the day saves the database to a hard disk present on some remote location. Now, an intruder comes up and corrupts this database. Next day when the Web-Application will start, how will it come to know that the database is corrupted?
M: I thought a bit and answered that we could save the last modified attribute of the database, store it in some encrypted format at both places the web-server and the hard-disk and when the next day Web-application starts up it can check whether this last update is same or not.
I: But the intruder can modify the database and can still keep the last modified attribute to be same.
They were expecting some different answer.
I: There are many approaches to this, tell anyone.(He gave me a further hint).
M: I thought of the checksum approach but then was sceptical about it because the database will be large. But, I told him this approach.
I: Yes this is a nice way. Good!!.
I: Okay Ayush, we are done.
Overall, I liked the experience at IISc.The professors were extremely helpful and were not in any hush-hush to get an answer. Enough time was given to think, correct and re-answer on each query. And the best part is they try to make you comfortable as in when you enter the interview room.
Final Status: Not Selected.
