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)