## Microsoft Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
2
of 2 vote

I think that the easiest thing to do is to go over each vertex( point i ) and draw the line with point i+2(mod n) until going overall the points. By this, we draw the star whether it is odd or even.
For example, the 5 pointed star can be drawn as follows:
- draw a line between point 0 and 2
- draw a line between point 1 and 3
- draw a line between point 2 and 4
- draw a line between point 3 and 0
- draw a line between point 4 and 1

and the 6 pointed star:

- draw a line between point 0 and 2
- draw a line between point 1 and 3
- draw a line between point 2 and 4
- draw a line between point 3 and 5
- draw a line between point 4 and 0
- draw a line between point 5 and 1

Comment hidden because of low score. Click to expand.
0

Excellent idea hamza. simple but efficient.

Comment hidden because of low score. Click to expand.
0

excellent idea!

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a very easy problem. Just start from the first point in the array...now move 2 points counter clockwise (i-2)mod N. As you keep moving, join points if they are not visited. If after moving you reach a visited point (you completed a cycle), so you can just move to the next element in the array.

For(n = 5, 7, 9 etc) you never end up moving to a visited point until the whole star is drawn.

For (n=6,8,10 etc.) you do come to a point which is already visited and then you have to move to the next element in the array and repeat.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Actually it is a simple problem only if the star has odd number of points. Here is the code.

//not sure how it works for an even number pointed star
if(n/2 == 0)
return;

for(i = 0; i < n; i++)
{
int j = (i + 2 > n - 1) ? (i + 2) - n : i + 2;
drawLine(i, j);
}

Comment hidden because of low score. Click to expand.
0

Seshagiri,

that is a wrong assumption, you can draw a star with 6 points...try it

Comment hidden because of low score. Click to expand.
0
of 0 vote

For an even number of points, I think you'll want to do the odd drawing and then repeat starting at 1 instead of at 0.

Comment hidden because of low score. Click to expand.
0
of 0 vote

"SomeCoder" your idea is not clear to me. Only with an odd number of points it is possible all the points will have two edges.

Comment hidden because of low score. Click to expand.
0
of 0 vote

that's stupid. When you have an even number of points, just do the same thing, but jump over two points at a time...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Try n=5.

0%5=0
2%5=2
4%5=4
6%5=1
8%5=3
10%5=0.

Try n=6.
0%6=0.
2%6=2
4%6=4
6%6=0.
1 triangle. Do same, starting at 1, for other triangle. Star of David, my favorite star :o)

Try n=7.
0%7=0
2%7=2
4%7=4
6%7=6
8%7=1
10%7=3
12%7=5
14%7=0. Print.

There seems to be a pattern. When is odd, do modulo iteratively. When n is even, you draw separate triangles. Since the case for odd is easy to do, let's exam even more closely and see what's up...

We know that a triangle has 3 points. Two triangles have a total of 2*3 pts. Three triangles have a total of 3*3 points. Hence if n%3==0, then we draw separate triangles. 8 is even but 8%3 != 0 so let's try n=8...

0%8=0
2%8=2
4%8=4
6%8=6

1%8=1
3%8=3
5%8=5
7%8=7

Again it seems that odds are easy to draw, but evens are trickier. Based on this evidence, if n%3==0, you can draw separate triangles iteratively. You know how many triangles to draw by n/3. Each triangle's vertex is 1 apart from the prev triangle. Continuing, if n%2==0 and n%3!=0, do the same as for n%3==0 except that you will be different shapes.

Comment hidden because of low score. Click to expand.
0
of 0 vote

assume n >= 3.
n = 4, 6 are special cases.

<pre>

int k = 2;
if( n % 2 == 0){
k = 3;
}

for(i = 0 ; i <= n * k; i += k){
drawLine(i % n , (i + k) % n );
}

</pre>

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we are forgetting what a star is. look at the five pointed star for an example. You are basically drawing a line from the start to an adjacent point accross from the starting point in some sort of pattern. The basic pattern is (number_points - 1)/2. Now lets look at special cases (6, 10, 14, 18, 22, etc). Each of these special cases would require to stars. The reason is that the number of points is even and the number of points skipped(based on previous equation) are both even. So in these cases we would need to draw two stars. So my algorithm would be to store my number of points to skip: (number_points -1)/2. store my starting point: head_of_star, initialize both points (int indexOne to head_of_star (starting point), int indexTwo ((number_points - 1)/2) ). I then draw the line, check to see if indexTwo is equal to head_of_star, if not set indexOne to indexTwo and indexTwo to indexOne plus my jump value and draw another line.

Once this is done, I check to see if my number of points and my jump value are both even. If so I add one to my head_of_star, reset my indexes and draw the second star. Problem solved and you actually have something that will still look like a star no matter how many points.

code:
given: intNumPoints

int intStartHead = 0;
int intJumpValue = (intNumPoints - 1) /2;
int indexOne = intStartHead;
int indexTwo = indexOne + intJumpValue;

{
drawLine(indexOne, indexTwo);
indexOne = indexTwo;
indexTwo = indexOne + intJumpValue;
}
if (intNumPoints % 2 == 0 && intJumpValue % 2 == 0)
{
int indexOne = intStartHead;
int indexTwo = indexOne + intJumpValue;

{
drawLine(indexOne, indexTwo);
indexOne = indexTwo;
indexTwo = indexOne + intJumpValue;
}
}

I believe this should work.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we are forgetting what a star is. look at the five pointed star for an example. You are basically drawing a line from the start to an adjacent point accross from the starting point in some sort of pattern. The basic pattern is (number_points - 1)/2. Now lets look at special cases (6, 10, 14, 18, 22, etc). Each of these special cases would require to stars. The reason is that the number of points is even and the number of points skipped(based on previous equation) are both even. So in these cases we would need to draw two stars. So my algorithm would be to store my number of points to skip: (number_points -1)/2. store my starting point: head_of_star, initialize both points (int indexOne to head_of_star (starting point), int indexTwo ((number_points - 1)/2) ). I then draw the line, check to see if indexTwo is equal to head_of_star, if not set indexOne to indexTwo and indexTwo to indexOne plus my jump value and draw another line.

Once this is done, I check to see if my number of points and my jump value are both even. If so I add one to my head_of_star, reset my indexes and draw the second star. Problem solved and you actually have something that will still look like a star no matter how many points.

code:
given: intNumPoints

int intStartHead = 0;
int intJumpValue = (intNumPoints - 1) /2;
int indexOne = intStartHead;
int indexTwo = indexOne + intJumpValue;

{
drawLine(indexOne, indexTwo);
indexOne = indexTwo;
indexTwo = indexOne + intJumpValue;
}
if (intNumPoints % 2 == 0 && intJumpValue % 2 == 0)
{
int indexOne = intStartHead;
int indexTwo = indexOne + intJumpValue;

{
drawLine(indexOne, indexTwo);
indexOne = indexTwo;
indexTwo = indexOne + intJumpValue;
}
}

I believe this should work.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry, I do have a small edit to that.

Whenever you are setting your second index it should look like this:

indexTwo = (indexOne + intJumpValue) % intNumPoints;

It's late and I forgot.

Comment hidden because of low score. Click to expand.
0
of 0 vote

the above answer seems to be correct and most likely to be the answer.
(i+2)(mod n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

private void DrawStar(int n)
{
int i = 0;
int[] Points = new int[n];
for(i = 0 ; i <= n-1 ; i ++)
{
if(Points[i] != 2)
{
Console.WriteLine("Draw Line From" + i.ToString() + " To " + ( (i+2) % n));
Points[i]++;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

As i understand it:
if we have 2 vertexes than the lines will be:
0 to 1
if we have 4 vertexes than the lines will be:
0 to 2
1 to 3
if we have 6 vertexes than the lines will be:
0 to 3
1 to 4
2 to 5

Meaning, the rule might be (for even n)
0 to n/2
1 to n/2+1
2 to n/2+2
etc.

in case of odd number of edges we will leave the last one unconnected.
Anyway, its a case to deal alone (need to be clarify in the interview). Line takes 2 edges, therefore in case of odd number of edges, you will always get one that is unconnected

the code in that case is:

oddFlg = FALSE;
if ((N%2)==1) than
{
oddFlg = TRUE;
N--;
}

int count = (N-1)/2;
int destIndx;
for (int =0; i<count; i++)
{
destIndx=count+1;
drawLine(index[count],index[destIndx]);
}
if oddFlg connect it as instructed (if any)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hamza's solution is the most elegant.

Although you don't know what rule a child follows when drawing a five or six point start. Because it is both 1) connecting every 2 vertices and 2) connecting a vertex with j = floor( (n-1) /2 ) away from it. For larger n, any value between 2 and j could possibly work as the distance bewteen two vertices to connect. There is no standard way to form a star. For example, I could form a 8 vertice star by connectiong 0 and 3, 1 and 4 and so on.

Comment hidden because of low score. Click to expand.
0
of 0 vote

if(n<5)
return;
for(i=1;i<=n;i++)
drawLine(i, (i+2)%n);
return;

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hamza's Algo:

void drawStar( int n ){
int index = 0;
while( index < n )
drawline( index, (index+2)%n )
}

Other Algo:

void drawStar( int n ){
int index = 0;
while( index < n ){
for(int i=0; i<n-2; i++)
drawline( index, (index+i+2)%n]
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

void DrawStar(int starPt)
{
if (starPt > 5 )
{
throw new invalidOperationException("Need minimum of 5 pts);
}

int placeHolder = 0;

if(!((startPt % 2) == 0))
{
for(int i = 0; i < starPt; i++)
{
drawLine(placeHolder, (placeholder + 2));
placeHolder += 2;
}
}

if((startPt % 2) == 0)
{
placeHolder = 0;
for(int i = 0; i < starPt/2; i++)
{
drawLine(placeHolder, (placeholder + 2));
placeHolder += 2;
}

placeHolder = 1;
for(int i = 0; i < starPt/2; i++)
{
drawLine(placeHolder, (placeholder + 2));
placeHolder += 2;
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

(i+2)%n

Comment hidden because of low score. Click to expand.
0
of 0 vote

The increment to add to i is a function of n:

int increment = n / 2 + (n + 1) % 2;
for(int i = 0; i < n; i++)
{
drawline(points[i], point[(i + increment) % n];
}

Comment hidden because of low score. Click to expand.
0

The parameters of drawline should have had the indices of the points as parameters (i and (i + increment) % n) instead of the actual points in an array.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my solution. The goal here is to draw each line without redrawing it. Imagine a three pointed star. Imagine further that all lines from point 0 have been drawn to all other points i.e. (0,1) and (0,2) have been drawn. We are drawing lines from point 1. Therefore, we only need to draw lines to points which are greater than current. Once we hit point 2, we have no points greater so we know all lines have been drawn. Fortunately we don't have to worry about the x,y location of the points. :)

void DrawStar(int howManyPoints)
{
if (howManyPoints < 3)
{
// error, exception, return, whatever
}
for (int i = 0; i < howManyPoints; i++) // outer loop. For each point...
{
for (int j=i+1; j < howManyPoints; j++)
{ // inner loop, for each point > currentPoint, draw line
DrawLine(i, j);
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

<2 minutes later>

Shoot my answer is wrong, i just realized you don't want to draw lines to any neighboring point.

lets try this instead :)

void DrawStar(int howManyPoints)
{
if (howManyPoints < 5)
{
// error, exception, return, whatever
}
for (int i = 0; i < howManyPoints; i++) // outer loop. For each point...
{
for (int j=i+2; j < howManyPoints; j++)
{ // inner loop, for each point > currentPoint, draw line
DrawLine(i, j);
}
}
}

Comment hidden because of low score. Click to expand.
0

Bah, this draws a line from point 0 to point n which is incorrect (if easy to avoid). :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

How can you guys assume that the points are in a clockwise or counter-clockwise order?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.