I- Interviewer, M- Me
I- What are your favorite subjects?
M- Linear Algebra, Probability, DS/Algo.
I- Given a matrix $A^2$=0, what can you infer from this?
M- A is nilpotent matrix, eigen values are zero.
I- What about determinant of A?
M- $A^2$=0 =>$|A|^2$=0 =>2*|A|=0 =>|A|=0
I- What about $A^{-1}$?
M- won’t exist.
I- How do you define inverse?
M- A matrix when multiplied by original matrix produces identity matrix is inverse.
I- Can you prove inverse won’t exist without using any of determinant things (I guess he didn’t wanted to hear things like |A|=0, so inverse won’t exist)
M- Sir assume $A^{-1}$ exists.
$A^2$=0
$A^{-1}$$A^2$=$A^{-1}$0
($A^{-1}$A)A=0
A=0
so even if assumed $A^{-1}$ exists in that case, A has to be null matrix but even the inverse of null matrix doesn’t exist because any matrix multiplied by null matrix produces null matrix always and never an identity matrix, so A can’t have inverse in all cases.
I- What’s volume of a n-dimensional cube?
M- couldn’t answer.
I- In 3D, suppose $0\leq x \leq 1$, $0\leq y \leq 1$, $0\leq z \leq 1$and $x \leq y \leq z$, what will be the volume enclosed by the set of points?
M- couldn’t answer.
I- Let’s simplify for understanding purpose, In 2D, suppose $0\leq x \leq 1$, $0\leq y \leq 1$ and $x \leq y$, how’ll the set of points look like?
M- Area of triangle with vertex as (0,0), (1,0), (1,1).
I- What’s it’s area?
M- ½
I- Now come back to the 3D problem I asked, how’ll the shape look like?
M- Tetrahedron.
I- How will you approach to find the volume?
M- will use calculus and find a small enclosed volume then integrate over it.
I- Obviously calculus can be used but we’re talking about linear algebra, so tell me something in that regard?
M- still thinking so then he moved to the next question.
I- Suppose we’ve set of functions with domain {1….m} and range {1….n} (considering only integers in the intervals), suppose you’ve two functions f(x) and g(x), what is the expected number of values in domain for which f(x)=g(x)?
M- thinking….(interviewer starting to simplify)
I- Tell me the probability of f(x) (or g(x)) taking any one value from range, more precisely probability that f(x)=1?
M- 1/n
I- So probability that f(1)=g(1)=1?
M- 1/$n^2$
( can think of it as prob{f(1)=1&&g(1)=1}= prob{f(1)=1}*prob{g(1)=1} ::Since f(x) and g(x) are independent.
= (1/n)*(1/n)= 1/$n^2$
I- Probability that f(1)=g(1)?
M- $\sum_{x=1}^{n}prob(f(1)=g(1)=x)=\sum_{x=1}^{n}1/n^2=n/n^2=1/n$
I- So now what’s the expected number of values where f(x)=g(x)?
M- m/n
I- How did you do?
M- Told them approximately the below thing but got confused later…
Expected Value= $\sum_{x=1}^{m}prob(f(x)=g(x))$= $\sum_{x=1}^{m}(1/n)=m/n$
Now comes the Algo Question...
I- You’ve an unsorted array of ‘n’ elements, minimum number of comparisons to find the second minimum element?
M- 2(n-1)
I- Are you sure, I can tell you that there is much more smaller value possible, let me give you an hint, consider ‘n’ teams playing against each other, how’ll you find the winner and the second winner?
M- We’ll first compare pairs of elements and choose the minimum and then compare the next set of minimum and so on until we find the last minimum element.
Number of comparisons = $\frac{n}{2}+\frac{n}{4}+\frac{n}{8}.........+\frac{n}{n}$
= n-$\frac{1}{2}$
(did wrong calculation during the interview.)
I- How’ll you find the next minimum?
M- The next minimum would be the element that was last compared with the minimum element.
I- Consider the sorted array 1,2,3,4,5,6,7,8 what would you say now?
M- Yes, sir it won’t work that way.
I- Try to relate with the analogy of the teams playing matches?
M- The second minimum would’ve definitely lost against the first minimum at some point, so we can keep track of the entire path for the winner starting from first comparison to last and can find the second minimum in this path itself.
(Interviewers weren’t much satisfied it seemed, I guess they were hinting towards the tournament tree algo which I didn’t remembered that time.)
I- Why did you moved from Mechanical to CSE stream after first year?
M- Sir, I started to develop quite a bit of interest in coding in my 2nd sem and seniors and everyone used to say about the job scopes and ever growing opportunities in CS. So all these biased my mind with entering into CS.
I- Are you satisfied with your decision about jobs and all?
M- Sure sir, but recently I’ve started to develop more interests in research than jobs, in fact I didn’t go to placements in my college and prepared for entrance exams instead.
I- Why so much interest in research?
M- It came out of my research internship at ISI Kolkata last year, I did comparative analysis of corporate jobs and research life and found the later to be more exciting and learning new and creative things everyday on the way while corporate job seems to me like doing more or less the same thing everyday.
I- What all entrance exams you gave?
M- TIFR, GATE and JEST.
I- You can leave now, we’ll contact you later if something required.
(P.S.:- It might be possible that my answers written to above questions are wrong at many places, but the questions are very close to what I could remember. Overall TIFR being very good at Theoretical Computer Science research seemed to be much more focused on mathematics at depth. At TIFR, CS is only there at Mumbai Campus as of now.)
