CareerCup

I think , all solutions are wrong .
Correct Idea is :
1) Find convex hull of points
2) Print it
3)Remove these points from current set of points
4) Do steps 1,2,3 while number of points > 0

Please throw your ideas. I am waiting if someone could throw some light on this.

This is similar to traversing a martix in spiral form. I was asked this questions for my Facebook interview. Solution is as follows:

#include <stdio.h>

#define N 5
#define M 3

int min(int a, int b)
{
return a < b ? a : b;

}

void spiral(int mat[M][N])
{
int n = N, d = +1, i = 0, j = -1;
int s, segl = N + M - 1;
for (s = 0; s < min(N, M); s++, d = -d, segl -= 2, n--) {
int c, *ip = &j;
for (c = 0; c < segl; c++) {
if (c == n)
ip = &i;
*ip += d;
printf("%3d", mat[i][j]);
}
}

}

I got this solution from :
http://discuss.joelonsoftware.com/default.asp?interview.11.575151.3

Credits to Sandeep NL who got it from C groups.

This is similar to traversing a martix in spiral form. I was asked this questions for my Facebook interview. Solution is as follows:

#include <stdio.h>

#define N 5
#define M 3

int min(int a, int b)
{
return a < b ? a : b;

}

void spiral(int mat[M][N])
{
int n = N, d = +1, i = 0, j = -1;
int s, segl = N + M - 1;
for (s = 0; s < min(N, M); s++, d = -d, segl -= 2, n--) {
int c, *ip = &j;
for (c = 0; c < segl; c++) {
if (c == n)
ip = &i;
*ip += d;
printf("%3d", mat[i][j]);
}
}

}

I got this solution from :
http://discuss.joelonsoftware.com/default.asp?interview.11.575151.3

Credits to Sandeep NL who got it from C groups.

Not sure what the post about Matrix is about, seem irrelevant to the problem, which I interpreted as, "You are given n 2D points in the plane, give a sequence of those n points, P1, P2, ..., Pn, such that when you go from P1 to P2 to P3 etc, if forms a 'spiral'".

The following approach might work:

Take convex hull repeatedly, forming convex shells. Start with the innermost shell and spiral outward.

This should be worst case O(n^2 logn). (Finding convex hull is O(nlogn)).

sundarvenkat2 is close. But, the correct answer is.

1. Find the distance of all points to the mean.
2. Sort them in increasing order
3. You should be able to form a spiral joining these points in that order. (say moving clockwise)

This is a Fibonacci series question. To plot every new point, use sum of distances of last 2 points from a fixed center.

Nix: will you mind spending 10 seconds to re-read the question and understand what exactly has been asked. you moron, people like you are wasting this great website.

Rather than anything else, the question deals with finding the slope of the points such that no point les above or below that line.

4 points need to be maintained always, these would be Max X, Min X, Max Y, Min Y.

We check none above if line is between Min X and Max Y or Max Y and Min X and we check none below otherwise.

This requirs sorting on the basis of two variables, Once n X and other time on Y.

1. sort the vertices on X.. for same X sort them on Y...
2. find MaxX, MaxY, MinX, MinY...
3. create a matrix of dimensions MaxX-Minx, MaxY-Miny..
4. store the points in the matrix
5. print the matrix in spiral fashion...

enjoy life king size

The question doesn't seem to be clear. It could be interpreted in more than one way. Most importantly, I don't understand : What should be the output of the algorithm? (A spiral printed on screen or a particular order of vertices or boolean value denoted possibility of a spiral ...)

Find convex hull
The find convex hull off remaining points recursively...
Linking up convex hulls is trivial

The matrix approach is crap...

hw abt sort co-ordinates in 1d matrix on x axis basis and if it matches then compare y.
After that, print it using following loop:
for(int i=0, j=n/4, k=n-1, l=3n/4-1; i<n/4, j<n/2, k>=3n/4, l>=n/2; i++, j++, k--, l--)
{
arr[i]
arr[j]
arr[k]
arr[l]
}
NOTE: I considered case where no of points is multiple of 4 :)