Sometimes, as they say, time is not on your side (Beta, abhi waqt tumhara nahi hai :P). Things
don’t seem to be going your way, no matter how hard you seem to be trying. It
is in such times, that some instances light up your path ahead. Even though the
situation in itself may not be successful, but they do inspire you to look
straight ahead into the future you always wanted.
There is one such unforgettable experience that I had in
Mumbai recently. I had been among the shortlisted candidates for interview at
TIFR, Mumbai for PhD in Computer Science, GS-2013. IT was a time in April, when
we had only got over with our placement scenario wherein an underperforming
student (read me) is bound to be an underachiever!! So I was not in the best of
moods emotionally when this happened. For those of you who are unfamiliar with
TIFR, Tata Institute of Fundamental
Research is supposed to be one of the best institutes for fundamental
research (physics, chemistry, biology, mathematics, computer science) in India.
The interview process for selection into the graduate
program at TIFR is also reputed to be among the toughest and the most rigorous
interview processes known. And all I can say is that it truly lived up to its
reputation!
The first stage of the selection process was a national
level entrance exam taken by approximately 10,000 people, based on which 20
candidates were invited for the interview, out of which around 12-15 turned up
as most of the others , being IIT graduates, had already been offered a good
job, or an admit from some US university. All computer science interviews were
scheduled across 3 days, 25th to 27th of April. I was
among the applicants invited on the 2nd day, i.e. the 26th.
Therefore, I got myself all fired up and turned in for the interview at the
scheduled time, 9:00 AM on the 26th April.
The first phase of the interview was a personal interview.
The selection committee comprised 5 panel members – Dr. Jaikumar Radhakrishnan,
Dr. Paritosh Pandya, Dr. N. Raja, Dr. Arkadev Chattopadhyaya and Dr. Kavitha
Telikepalli, all of whose information can be found here.
So, here's a description of the interview:
Dr. Raja: where are you staying in Mumbai?
Me: Sir, with my aunt in Powai.
Dr. Raja: so, how often do you visit Mumbai?
Me: not very often, sir, maybe once in 2 years…
Dr. Raja: so, have you done some sight-seeing- Elephanta
Caves, Marine drive, etc.…
(this continued for about 5-10 minutes, Dr. Pandya also
joined in and shares a light-hearted conversation about tourism in the city of
Mumbai)
Dr. Jaikumar (getting started with business): you have
mentioned that you are interested in cryptography. Are you aware of the
concepts of number theory that from the background of cryptography?
Me: Yes, sir I am aware
Dr. Jaikumar: I notice you have taken a course under Prof.
Rajat Tandon on the same. So tell me, do you know what is the Fermat’s little
theorem?
Me (Beta, mann mein laddoo phoonta!!): Yes sir.
Dr. Jaikumar: Can you write the statement on the board?
Me: Of course sir. (I described the statement of the
theorem)
Dr. Jaikumar: can you prove it?
Me (Beta, mann mein doosra laddoo phoonta!! :D): I can try,
sir.
(And I prove the theorem, at the same time pretending I
didn’t know it already!)
Dr. Jaikumar: cool!!
(Well begun is half done!!)
Dr. Arkadev: I believe you have done good amount of group
theory as part of your curriculum. Can you state the Lagrange’s theorem?
Me: yes sir… (I state that in any finite group, order of
an element divides the order of the group)
Dr. Arkadev: Great, so now can you use this theorem to prove
the Fermat’s theorem.
Me: I will try, sir.
(I thought for a while and realized that it was pretty
trivial, and completed the alternate proof quickly)
Dr. Arkadev: Okay, so I have a kind-of puzzle for you:
Say there are 1000 boxes numbered 1 to 1000, and 1000
people. In the beginning, all boxes are closed. Then each person goes and opens
or closes some boxes, following the rule: the ith person only touches the boxes
that have multiples of i on it, and closes it if it is open and vice-versa.
You have to tell me which boxes will stay closed after the
1000th person has done his job.
Me: For a box to be closed in the end, it has to be touched
even number of times, i.e it should have even no. of factors. As factors always
exist in pairs, perfect squares are the only numbers that have odd no. of
factors. Thus, all the numbers that are not perfect squares will remain closed
in the end.
Dr. Arkadev: That is right, have you heard this question
before?
Me: Not exactly this, but I have done similar problems.
(wicked smile!!)
Dr. Kavitha: you mentioned gcd(a,p)=1 as a pre-condition for
Fermat’s theorem. Can you write a pseudocode to compute the gcd of given 2
natural numbers?
Me (wondering why I was being given such a basic problem):
Yes, ma’am, I would use the Euclidean algorithm to compute the gcd, as it is
the most efficient algorithm for this task.
Dr. Kavitha: Okay, write the algorithm.
(I write the recursive code to compute gcd(a,b) assuming
b<=a.
Dr. Pandya: what will happen if a<b.
Me: Sir. I will call the function after ensuring that the
second argument is at most equal to the first argument.
Dr. Pandya: No no, think that the function can be called
with any 2 arbitrary values. Then what will you do? Write in the code.
Me (unable to completely understand what he wanted): Ok sir…
(And I wrote the magical one-line swap, courtesy our branch topper Shaik Allauddin, just after entering the function, forcing b
to be less than or equal to a).
(Dr. Pandya looked unsatisfied for some time but then nodded
towards Dr. Kavitha)
Dr. Kavitha: what is the runtime of this algorithm, suppose
‘a’ has log(a) bits and ‘b’ has log(b) bits of input size, then what will be
no. of operations in terms of a and b?
Me: It will be O(log(b)) runtime, ma’am.
Dr. Kavitha: can you prove it?
Me (stumped): I can only point out the recursive algorithm
that reduces the arguments to the smaller number in every step, but that does
not significantly contribute to the run-time reduction)
Dr. Kavitha (Hinting): what do you need to show in order to
show that some algorithm runs in logarithmic time?
Me (Trying to catch the hint): there must be some step after
which the input size reduces to half..
(And carrying this forward, I proved the existence of some rk
at some kth step which will be less than b/2 in all cases, and therefore, after
every k steps, the input reduces to half its size)
Dr. Kavitha: That’s right.
Dr. Pandya: Have you done a course on theory of computation?
Me: yes sir, I studied some introductory TOC as a part of
the Algorithms course.
Dr. Pandya: so what part of TOC do you find most
interesting?
Me (trying to bring in some creativity, unaware that I am
going to regret it deeply later :-/ ): Mostly everything that I have studied,
sir, especially the open problems and the more philosophical part of TOC is
something that interests me more.
Dr. Pandya (smiling): cool… even I like the philosophical
part of TOC… one thing that always puzzles me is the concept of
non-determinism. You can implement a deterministic finite automaton as a
program, but can you do the same for a non-deterministic finite automaton?
Me (starting to regret my answer!): Not as a NFA, but maybe
we can convert every NFA to a DFA, and then implement it in a program?
Dr. Pandya: okay, you can do that, but what about a
non-deterministic push-down automaton? Can we do the same for it?
(I think on it for quite some time, regretting more than
ever about mentioning philosophy here)
Dr. Pandya: It’s all right, you can think on it later and
answer me whenever you want, Now, you are given 2 lqnguages:
L=( xy | number of zeros in x = no. of 1s in y}
M=( x$y | number of zeros in x = no. of 1s in y}
What kind of languages are they? Regular, context free,…
Me (After thinking a while): Sir, both of them are context
free languages.
Dr. Pandya: how can you say that just by looking at them?
Me: sir, there is some counting involved in deciding these
languages, which cannot be done by a finite automaton, and a push down automata
is required.
Dr. Pandya: But that is only intuition, is there any other
way to prove it?
Me: Sir, we can write a grammar in Chomsky normal form for
the languages. That will prove that they are context free. Then we know that
regular languages are a subset of CFLs, and we will prove that they are not
regular using pumping lemma.
Dr. Pandya: Okay do that. First state the pumping lemma,
write it clearly on the board.
(I write the pumping lemma using all logic and predicate
notations carefully)
Dr. Pandya: Okay. That’s correct. Now prove that M is not a
regular language.
(It was simple and similar to a lot of solved examples, so I
did it without a problem)
Dr. Pandya: Good. I’m done.
Dr. Raja: Okay, so you must have studied a lot of
algorithms. I will ask you a shortest path problem.
(Comes across to the board and draws this figure:
Dr. Raja: Let’s say this is a network of roads. What is the
length of the shortest path from A to B?
Me (Confused as to why I was being asked such a silly
question): Sir, 11, (6+5, which are the dimensions of the grid.)
Dr. Raja: And the shortest path is not unique, right? So How
many shortest paths are possible here?
Me: Sir, 11C6, 11!/(6!5!)
Dr. Raja: Right. How do you get that?
Me: Sir, I can conclude from the figure that all those paths
in which we are not allowed to move backwards or upwards, will be the shortest
paths. Therefore, as we can move only right (looking at it as a 2-D figure) and
down, we can reduce the problem to making 11 moves and choosing 6 of them to be
right and the rest will be down. Thus, 11C6.
Dr. Raja: Ok, now I modify the problem.
(He modified the figure, and asked me to solve it during the
break. So,the problem is discussed in the other half of the interview)
(All the 5 people come together, take out a sheet of lots of
questions, and discuss for some time. I had seen people coming out from the
interview with lots of sheets in their hands, so I knew what was coming)
Dr. Jaikumar: Ok, these are some problems for you. Think
about them for about an hour. 1’o’clock we will have lunch, please do join us
for lunch. And after lunch, we will discuss your solutions. You may use these
rough sheets for your answers, and in case of any doubts with the questions,
call me on this number.
Thus, I was given a separate table, pen and paper to work,
and this was the second phase of the interview. The first phase lasted around 1
hour, from around 11 to 12. And now, I had one hour before lunch to solve
another set of problems. There were 4 questions, which I will discuss later, as
the third and final phase of the interview mostly involved discussions on these
4 problems.
I worked on the questions for about an hour, then someone
comes and tells us the professors are waiting for us to start their lunch.
Surprised and impressed, we get down to the canteen where food is laid out and
all the professors, computers and system sciences, are standing there. We take
our food and sit down at the table. This is the first time I talk to my fellow
interviewees. Every one of us has a funny feeling inside, knowing that we are
competing for very limited seats but sympathetic towards each other after
having spent last few hours on those mind-boggling problems. The professors are
also sitting at the same table, smiling and having a general discussion with
the students, probably enjoying a lot within, seeing our puzzled
faces. It reminded me of Prof. Jawahar’s wicked smile when he has the same
feeling as that of an executioner before your punishment.
I don’t remember finishing my lunch as quickly as that day,
as we couldn’t concentrate on the food or anything other than the questions
that lay ahead of us waiting to be solved. We went upstairs, back to our
tables, and within a few minutes the candidate were being called again to the
conference room. I was the last to give the first stage therefore I expected to
be called in last this time too. So, I continued working.
After about an hour or two around 3:30, I was called in for
the final round.
Prof. Jaikumar: So, have you had enough time to solve the
questions?
Me: Yes sir, I have solved most of the parts of the
questions, not all complete. (I actually wanted to tell them that no amount of
time is actually enough for these kind of problems, but held back my thought!!)
Prof. Jaikumar: Okay, so in any order of your choice,
describe the questions that you were asked to solve, and what answers have you
come up with. Remember that all the members here do not know the questions, so
explain the questions first.
Me: Okay, sir. So, the first question I solved was the
following recurrence relation:
T(n) = T(n/k) +
T(2n/3) + 2n, for k=2,3,4, T(1)=T(2)=1
(so, I started describing my solution by recursion tree
method taking k=2 for the time-being, and showed them my intermediate
expressions, such as t(n) after m depths of recursion)
Dr. Kavitha: So, when will this tree terminate, what will be
the longest branch of recursion.
Me (Looking at the expression): the 2n/3 branch, ma’am. It
is the slowest branch and will terminate at the end. (By termination of a
branch, we mean the branch reaching T(1) or T(2) whose values we were given)
Dr. Kavitha: Okay, continue with your solution.
Me: So, when all branches have terminated, there will be two
terms, one will be the summation of all the T(1)s and T(2)s, and the other will
be a constant term.
Dr. Kavitha: Ok, so let’s ignore the other term and tell me
what will be the value of the constant.
(I wrote the value that I had computed in my answer, there
were some mistakes and with a few hints, I corrected it, which made it much
simpler than I had computed)
Dr. Kavitha: In asymptotic notation, order of?
Me: this would be O(n2), ma’am.
Dr. Kavitha: Now, for k=3 and 4?
(I substituted the value of k in place of 2 and wrote the
other 2 answers)
Dr. Jaikumar: Ok,
that’s good. Next question?
Me: Uh sir, the grid problem, finding the no. of shortest
paths. (This was the problem asked earlier)
Dr. Raja: Now, say there is a pit like this in the middle of
the roads, where it is not possible to drive through. Now, can you find the no.
of possible shortest paths?
Me: I plot some
points that mark the points of possible entry into the pit area, and some
possible points of exit from the area. So, there are 4 possible points of entry
(2 to the right of the pit and 2 above), and 4 corresponding points of exit. I
compute all possible combinations of entry and exit points and subtract this
from the total no. of paths that was 11C6.
Dr. Jaikumar: That wouldn’t exactly be right as there are
many ways to reach from A to the points of entry, there is a multiplication
factor involved.
Me: Yes sir (disappointed with myself, and still not taking
the larger hint :-/). So, let’s label the 4 points of entry as Si
and the 4 points of exit as Ti, where i varies from 1 to 4. Now, I
find no. of ways to reach Si from A, say it is Li, and
no. of ways to reach from Tj to B, say it is Mj….
(at this point I see some frowning faces, when I should have
realized something was wrong, but I carried on)
Also, I had already found no. of ways to each from Si
to Tj, let’s call it nij. Now, my answer would be 11C6
- Ʃ Li nij Mj.
Dr. Jaikumar: Again, isn’t the product (nij Mj)
simply equal to Mi, no. of ways to reach from Si to B?
Me: Ohh, yes sir.
Dr. Pandya: But
simply replacing it will include many repetitions, if you see closely at the
points. Once you enter the area through one of the 4 points, you can exit
through any point. So, you need not account for the exit at all. And the entry
points can be reduced to the points in the area, since you have entered. That
leaves you with just 3 points. Are you getting what I am saying?
Me: Yes sir, I understand. (shaking my head in shame). So,
we just need to compute Ʃ Li Mi for the three points and
subtract from the total paths. That will be the correct answer. (sigh)
Dr. Arkadev: All right. Next?
Me: Next was the pebbling problem, sir.
The aim is to place a pebble on the root of a binary tree,
while following the given rules:
1. You
can place a pebble on a node only if both its children are pebbled at that
moment.
2. You
can remove a pebble from any node anytime.
Thus, you have to keep placing pebbles and then reusing
them. Thus, I was to find the minimum pebbles required to pebble the root of a
tree of height h.
I have found the answer to be equal to h+1 sir.
(I proved it using some induction and generalizations. Also
I was required to prove that it cannot be done on less than h+1)
Dr. Jaikumar: great. That is correct. Next?
Me: I could not solve the ;ast one sir, he group theory
question.
Dr. Arkadev: Oh that is a good one. Did you understand what
was asked?
Me: Yes sir.
Dr. Arkadev: well, then can you explain it to the rest of
the panel.
Me: There is a subset of elements from a group that has more
than half the elements there are in the group. i.e G is a group of order N and
S is a subset of G having order greater than N/2. We have to prove that for
every element g in G, there will exist 2 distinct elements a and b in S such
that g = ab-1
Dr. Kavitha: So, how did you try to proceed on this.
Me: ma’am, I know that the subset could not be a subgroup
because a subgroup with more than half the elements could only be the group
itself (lagrange’s theorem). So, if it is not a subgroup, I couldn’t think if
any properties that connects a simple subset with the group.
Dr. Arkadev: can you rearrange the statement to be proved,
so that we have no inverse?
Me: yes sir, it will be gb = a.
Dr. Arkadev: so now, can you think of anything? What is gb
for any element g in G?
Me: (realizing the beauty of the question): it means the
element can be multiplied with any element of the subset. Thus sir, we will
multiply it to every element and name the result as gS. It is analogous to a left
coset of S. Now, as all elements in S are distinct their products with g will
also be distance. So order of gS equals order of S. both orders are greater
than N/2, therefore there must be overlapping elements, lets call one of them
b. Thus, for any given group element g, there will be one such way of writing
it as g = ab-1 where a and b belong to the set S.
Dr. Arkadev: Right. Well done. Are there any other
questions?
Me: no. sir.
Dr. Pandya: And did you think about the non-deterministic
push down automata problem? How do you write a code for it?
Me: (remembering my past blunder had come back to haunt me)
Yes sir, I could only think of implementing it using structures and hashmaps
STL in C++. I mean we can store all possible states in a dictionary, and all
possible operations as a graph where every node is a structure element. But it
will be quite complicated.
Dr. Pandya(smiling): ya it will be, that’s why it hasn’t
been done yet. Good brave attempt.
Dr. Jaikumar: Well, its time when you can take your
vengeance from us :D Do you want to ask us anything?
Knowing this was a standard question to end the interview, I
asked some basic things about the study culture and people at TIFR. They
answered and interacted nicely, and finally asked me to leave, stating that the
interviews will go on for about a week, so you can expect a result on the
website then. Selected students would be intimated by mail.
So, that was the end of a wonderful enriching day. And even
though I was not selected for the program (they selected 4 candidates), the
above rigorous account of the interview process stands proof that I obviously
am going to try again and again to be in such an environment, full of dedicated
minds. No wonder 10,000 people attempt the written exam for this Phd Program,
even though it is very well known that it is among the most rigorous PhD
programs there can be. This is surely good news for theoretical computer
science research in India J
