# IIT Delhi CSE MS(R) Interview Experience- July 2020

[ Prior to interview there was coding round containing 5 questions to be solved in 2 hours, I remember 3 of them as given,

1)Finding nth number in a tribonacci series(not given directly that it is tribonacci series but based on initial 7 numbers given, you’ll guess that) and also to take care of overflow for calculating with large values of ‘n’ to score full 100 marks.

2)You’ve a square $n\times n$ chess board, where each entry is either a building or empty, each entry can store 1 unit water when empty. If water is surrounded by buildings from all sides then only it is stored if there is any opening on any side then water will leak and water stored is zero unit, now given such an input square matrix with buildings on it represented by ‘*’, empty entries by ‘.’, calculate the amount of water stored. e.g.,

$\begin{bmatrix} .&*&*&.\\ *&.&.&*\\ *&.&*&.\\ .&*&.&.\\ \end{bmatrix}$would store 3 units of water. $\begin{bmatrix} .&*&*&.\\ *&.&.&*\\ *&.&*&.\\ .&.&*&*\\ \end{bmatrix}$would store 0 units of water.

3)There is an adjacency matrix of a graph, for any vertex, calculate absolute value of difference between in-degree and out-degree, print the larger value and the vertex that possess it. ]

Got the mail for clearing the coding test the same night and the interview was scheduled 2 days after.

I-Interviewer, M-Me

I- You’ve a complete ternary tree, number of leaf nodes are ‘n’, what’s the number of internal nodes?

M- We’ve this relation, $L=I\times(n-1)+1$  ($L$ and $I$ are number of leaf and internal nodes respectively, ‘$n$’ is the ary of the tree)

$n=I\times(3-1)+1$

$I=\frac{n-1}{2}$

The interviewer wasn’t satisfied with me using the direct formula so then I derived the expression and calculated,

Suppose the height of the tree is h, $L=3^h$

$Total Nodes=L+I=3^0+3^1+3^2+.......+3^h=3^0\times\frac{3^{h+1}-1}{3-1}$

$L+I=\frac{3\times3^{h}-1}{2}=\frac{3\times L-1}{2}$

$2\times (L+I)=3\times L-1$

$I=\frac{L-1}{2}=\frac{n-1}{2}$  (No of leaf nodes are ‘n’)

I- Do you know there are some proof techniques (in algorithms or Computer science, don’t remember exactly which one he said)?

M- No.

I- You’ve two dice, probability that one is even, other is odd?

M- (I asked him if they’re identical, first he said yes then no)

In identical dice, pair (dice1,dice2)$\rightarrow$(a,b) & (b,a) are considered one event while in distinct they’re counted as two events.

For identical,

favourable cases=$dice1\times dice2=(1,3,5)\times(2,4,6)=3\times3=9$

total cases=$(1)\times(1,2,3,4,5,6)+(2)\times(2,3,4,5,6)+(3)\times(3,4,5,6)+(4)\times(4,5,6)+(5)\times(5,6)+(6)\times(6)$

$=1\times6+1\times5+1\times4+1\times3+1\times2+1\times1=21$

$P=9/21$

For distinct,

favourable cases=$dice1\times dice2=(1,3,5)\times(2,4,6)+(2,4,6)\times(1,3,5)=3\times3+3\times3=18$

total cases=$(1,2,3,4,5,6)\times (1,2,3,4,5,6)=6\times 6=36$

$P=18/36$

I- Probability that one is even given that one is odd?

M- Let $A$ be the probability than one dice is even and $B$ be the probability that one dice is odd,

$B$ will exclude only three cases (2,2),(4,4) and (6,6) so $P(B)=\frac{33}{36}$ [ B will also exclude (2,4),(2,6),(4,6),(4,2),(6,2),(6,4) cases which I forgot to include that time. ]

$A\cap B$ means one dice is even and one dice is odd which excludes six cases, (1,1),(2,2),(3,3),(4,4),(5,5) and (6,6), so [ will exclude 18 cases in total, (1,3,5)$\times$(2,4,6)+(2,4,6)$\times$(1,3,5)=3$\times$3+3$\times$3=18, I also didn’t take this into account during interview ]

$P(A\cap B)=\frac{30}{36}$

$P(A/B)=\frac{P(A\cap B)}{P(B)}$

$=30/33$  Ans.

I- How did you calculate?

M- I gave him the explanation and there were some more discussions and questions into the same and later the professor said that I missed some even even case or something like that, I guess the missed cases that I’ve mentioned before, don’t remember exactly.)

I- You said your research interest as Deep learning right?

M- Yes

I- Draw an AND gate with a single perceptron with activation function as

$f(x)= +1, x>0$

$-1, x<0$

M-

I- Draw an XOR Gate with single perceptron?

M- (after some calculation and thinking) not possible with single perceptron.

I- Why?

M- Because there are complementary kind of cases like in AND (1,1) producing higher Σwx+b and remaining all cases produce lower but in XOR not like that.

[   the following answer I found on a webpage is quite appropriate- A "single-layer" perceptron can't implement XOR. The reason is because the classes in XOR are not linearly separable. You cannot draw a straight line to separate the points (0,0),(1,1) from the points (0,1),(1,0). ]

(A professor I showed interest in took my interview on phone call after some day of official interview, also he asked me if I can mail my CV)

I- You’re interested in medical applications of AI?

M- Yes.

I- Why you didn’t go for job having a high CGPA?

M- told about something being interested in research and what kind of research I like.

I- Have you done good coding things?

M- Yes.

I- Then, why is your score low in coding test?

M- I told about that there were too many questions with good difficulty level and even solving questions like that on codechef takes quite amount of time for me.

I- So given enough time you would’ve done all?

M- Hopefully more of them.

I- Then he asked me about what was asked in the interview, and since he wasn’t there on the interview panel that day he asked me if he can ask me questions and asked the following.

I- What is the max and min height of a binary tree, I want exact values?

M- (n-1) and $log_2 n$, Skewed tree for max and balanced tree for min.

I- What’ll be the answer if we put the following constraint, at any node, number of nodes in right subtree should be atleast half of the nodes in left subtree?

M- Same answer (n-1) and $log_2 n$, Right skewed tree for max and balanced tree for min still satisfy the given constraint.

I- What about the following constraint, at any node, number of nodes in right subtree should be atleast half of the nodes in left subtree as well as number of nodes in left subtree should be atleast half of the nodes in right subtree?

M- Min height is still same. Max height is $log_{(\frac{3}{2})} n$

[ $R\geq\frac{L}{2}\rightarrow L\leq2R$………….(i)

$L\geq\frac{R}{2}$…………..(ii)

From (i) and (ii) we get, $\frac{R}{2}\leq L\leq2R$, so L can have min $\frac{R}{2}$ nodes, now choose one node as root out of ‘n’ nodes, let L and R be the number of nodes in left and right subtree

respectively for the root then,L+R=n-1, L=$\frac{R}{2}\rightarrow L=\frac{n-1}{3}, R=\frac{2\times(n-1)}{3}$

For max height again check splitting at the right subtree and so on...which give max height  $log_{(\frac{3}{2})} n$. Although this answer might be wrong and the professor wasn’t enough satisfied it seemed.]

I- What is the proof that your answer is correct, maybe distributing nodes half-half in both left and right tree at some points or as a whole produces max height?

M- Proof I don’t know. but this seems to be correct.

I- In a throw of a dice (a,b), $X$ is a random variable, that takes the larger value, i.e.,

$X=a,a\geq b$

$=b,a<b$

calculate $P(X=i)$ in terms of ‘i’.

M- $X=1$ only in (1,1), $X=2$ only in (1,2),(2,2),(2,1), $X=3$ only in (1,3),(2,3),(3,3),(3,2),(3,1) and so on…

In general, $X=i$ only in $2\times i-1$ cases.

so $P(X=i)=\frac{2\times i-1}{36}$ (first did silly mistake and told $P(X=i)=\frac{i}{36}$ and then gave the correct answer.)

I- What if you’ve an ‘$n$’ faced dice?

M- Then, $P(X=i)=\frac{2\times i-1}{n^2}$

(P.S.:- Some my answers may not be correct so do check on that. My gate score-744, rank-460, so got shortlisted for coding test then for interview, and finally got the offer.)

posted Jul 31
edited Aug 1
5
Like
0
Love
0
Haha
0
Wow
0
Angry
0