IIT Madras MS(CSE) Interview Experience(July 2020)

Question

I-Interviewer, M-Me

Subject Chosen- Design and Analysis of Algorithms

I- You are comfortable with C right?

M- Yes.

I- You’ve an matrix, find the first occurrence of six consecutive ones in a row and replace by 101010, write a complete code including the declaration, skip taking the inputs maybe…

M- #include <stdio.h>

int main()
{
int i,j,n,c;
for(i=0;i<n;i++)
{ c=0;
  for(j=0;j<n;j++)
  {
    if(j!=(n-1)&&a[i][j]==1&&a[i][j+1]==1)c++;
    else c=0;
    if(c==5)break;
  }

( The code is incomplete, but due to time constraint which I guess they said to be 4-5 minutes, he said just tell me what you’re trying to do and then tried to explain.)

I- Given an array P with each element P[i] being a point in geometrical space, where consecutive array elements form a line,i.e., (P[0],P[1]), (P[1],P[2])…...(P[n-2],P[n-1]), (P[n-1],P[0]) are lines. Overall array P forms a polygon, you’ve libraries which can calculate intersection of lines and angle between lines in constant time. How’ll you check if they form a convex or concave polygon?

M- For all three consecutive point triplets (x,y,z) taken from the array, the angle formed by the line (x,y) and (y,z) should be less than 180 degree for convex.

I- For the same polygon, how will you check if they form a simple polygon or not?

M- calculate all possible lines and see if for all possible cases, any line other than adjacent ones intersect.

I- What’s the complexity?

M- exponential.(but I was wrong I guess)

I- Find in O(n^2), can show a pseudocode of what you’re doing...

M- gave a little vague pseudocode with mistakes.

The correct pseudocode might be:

for(i iterates over n lines)

    for(j iterates over lines starting from first to (i-1)th line and non adjacent to ‘i’th line)

        if(intersect(i,j))//intersect takes constant time

         { printf(“not a simple polygon”);

         break;}

        if(i==n) printf(“simple polygon”);

I- I think you get the logic, say it orally?

M- Since lines are formed by consecutive points, and there are ‘n’ lines in total, will iterate over all the n lines and check if it intersects the previous ones using the constant intersect checking function from the pre built library, this will give n^2.

(P.S.:- All of my algo questions were centered around this polygon thing, apology if I might have missed some questions)