CareerCup

For every 2 points, find the slope of the points and store in the hash table. Now go through the hash table and print all the sets that are having the same key value(i.e
slope). The complexity will be O(N^2).

Make sure the value of the hashtable is represented as a set, to avoid duplicates.

Idea being, if two points are having the some slope, then the third point which is collinear will also have the same slope with either of the two points.

Please correct me if I am wrong.

For every point, calculate the slopes with all the n-1 points. Sort them to see if any two are equal. n^2logn .
In this case collinearity can be decided based on slope, since two slopes involves one common point

1. Take any two Point - Find thier Slope , x2-x1/y2-y1
2. for the above Points find the Equation of line y=mx+c
if 1 & 2 are same then any point who's line equations is same to 2 is collinear
[Above is bad algo, need to optimise]- as this would require N^2[to calculate the Slope of Line+Line EQ] +N[to find the 3rd Point on same Slope+EQn] computation.

You can't expect the slope to be exactly the same. When the two slopes are very close to each other, i.e., Math.Abs () of the the difference is smaller than a set small value, you can say that the two slopes are the same. so the hashtable approach may not work well.

Take a point p and calculate the angle of all point with respect to that by using
y2-y1/x2-x1(slope) sort them and find the points with same slope.
DO it for other point .. we can skip as we iterate the point to avoid recalculation

Calculate the area of determinant between the three points:
|1 x1 y1|
|1 x2 y2|
|1 x3 y3|

if the area is zero, then points are collinear. However, I am not sure how to optimize it, I have a O(n3) brute-force solution

// I need some modification while printing because its printing same set again but logic is fine

import java.util.Arrays;


public class Amazon3 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Point[] p = new Point[6];
		Angle[] angle;
		p[0]=new Point(19000, 10000,'A');
		p[1]=new Point(18000, 10000,'B');
		p[2]=new Point(32000, 10000,'C');
		p[3]=new Point(21000, 10000,'D');
		p[4]=new Point(1234, 5678,'E');
		p[5]=new Point(14000, 10000,'F');
		
		for(int i=0;i<p.length-1;i++)
		{
			int k = p.length-i-1;
			angle = new Angle[k];
			
			for(int j=i+1;j<p.length;j++)
			{
				angle[j-i-1] = new Angle();
				double temp = (p[j].y-p[i].y)/(p[j].x-p[i].x);
				angle[j-i-1].angle = Math.atan(temp);
				angle[j-i-1].p = p[j];
			}
			Arrays.sort(angle);
			Angle previous = angle[0];
			System.out.println();
			System.out.println("Colinear Points Set");
			System.out.print(p[i].name+","+previous.p.name);
			for(int n=1;n<k;n++)
			{
				if(previous.angle==angle[n].angle)
				{
					System.out.print(","+angle[n].p.name);
				}
				else
				{
					System.out.println();
					System.out.println("Colinear Points Set");
					System.out.print(p[i].name+","+angle[n].p.name);
				}
				previous=angle[n];
			}
	
		
		}
	}
	
	
}
class Point{
	double x;
	double y;
	char name;
	Point(double x, double y,char n)
	{
		this.x =x;
		this.y =y;
		this.name=n;
	}
}

class Angle implements Comparable<Object>{
	Point p;
	double angle;
	public int compareTo(Object o) {
		Angle in = (Angle)o;
		if(this.angle<in.angle)
			return -1;
		else if(this.angle==in.angle)
			return 0;
		else
			return 1;
	}

	
}

I like the idea of calculating the Angle Mayank. Nice.

I like the idea of calculating the Angle Mayank. Nice.

1.form a 2-d matrix of x-cord to y-cord. Mark elements[x,y] of matrix 1, if a point with those x,y co-ordinates exists.
2. Go through all the "diagonals" of the matrix. If a diagonal contains 3/more points, the points are collinear. Also search the the reverse diagonals.

http [] stackoverflow.com/questions/2734301/given-a-set-of-points-find-if-any-of-the-three-points-are-collinear

// This method will return the collinear points set
// pass array of of coordinate points to the the method
public static List<Set<Point>> getCollinearPointSet(Point points []){
int i =0 ;
int j =0 ;
int k = 0;
List <Set<Point>> listCollinearSets = new ArrayList<Set<Point>>();
for ( i=0 ; i < points.length ;i++){
for (j=i+1 ; j < points.length ; j++){
//Skip the combination of points[i] and points[j] if these two points
// are already present in previously calculated collinear set.
if (CollinearUtil.hasPoints(points[i], points[j], listCollinearSets)){
break;
}
Set <Point>collinearPoints = new HashSet<Point>();
for (k = j+1 ; k< points.length ; k++){
if (CollinearUtil.isCollinear(points[i],points[j],points[k])){
collinearPoints.add(points[i]);
collinearPoints.add(points[j]);
collinearPoints.add(points[k]);
}
}
if (!collinearPoints.isEmpty()) listCollinearSets.add(collinearPoints); ;
}

}
return listCollinearSets;
}

// This method will check if given 3 points are collinear.

public static boolean isCollinear(Point p1, Point p2 ,Point p3){
if(((p1.y -p2.y) * p3.x + (p2.x-p1.x)*p3.y + (p1.x*p2.y -p2.x*p1.y))==0){
return true;
}
return false;
}

public static boolean hasPoints(Point p1 ,Point p2 , List<Set<Point>> lisCollinerSets){
for (Set<Point> points : lisCollinerSets) {
if (points.contains(p1) ||points.contains(p2)) return true;
}
return false;
}

// This method will return the collinear points set
// pass array of of coordinate points to the the method
public static List<Set<Point>> getCollinearPointSet(Point points []){
int i =0 ;
int j =0 ;
int k = 0;
List <Set<Point>> listCollinearSets = new ArrayList<Set<Point>>();
for ( i=0 ; i < points.length ;i++){
for (j=i+1 ; j < points.length ; j++){
//Skip the combination of points[i] and points[j] if these two points
// are already present in previously calculated collinear set.
if (CollinearUtil.hasPoints(points[i], points[j], listCollinearSets)){
break;
}
Set <Point>collinearPoints = new HashSet<Point>();
for (k = j+1 ; k< points.length ; k++){
if (CollinearUtil.isCollinear(points[i],points[j],points[k])){
collinearPoints.add(points[i]);
collinearPoints.add(points[j]);
collinearPoints.add(points[k]);
}
}
if (!collinearPoints.isEmpty()) listCollinearSets.add(collinearPoints); ;
}

}
return listCollinearSets;
}

// This method will check if given 3 points are collinear.

public static boolean isCollinear(Point p1, Point p2 ,Point p3){
if(((p1.y -p2.y) * p3.x + (p2.x-p1.x)*p3.y + (p1.x*p2.y -p2.x*p1.y))==0){
return true;
}
return false;
}

public static boolean hasPoints(Point p1 ,Point p2 , List<Set<Point>> lisCollinerSets){
for (Set<Point> points : lisCollinerSets) {
if (points.contains(p1) ||points.contains(p2)) return true;
}
return false;
}

public class Point {

public int x ;
public int y ;
public String name ;

Point (String name ,int x,int y){
this.name = name ;
this.x = x;
this.y = y;
}

@Override
public boolean equals(Object obj) {
Point p =(Point)obj ;
if (this.name.equals(p.name)) return true;
if ((this.x == p.x) && (this.y==p.y)) return true ;
return false ;
}

@Override
public String toString() {
StringBuffer coordinates = new StringBuffer();
return coordinates.append(this.name).append(": (").append(this.x).append(",").append(this.y).append(")").toString();

}

Employers should consider if a question actually tests and informs the interviewer if the candidate would perform well on a job. Any job that expects you to come up with a good answer to a complex question without research is not a place you want to work.

The algorithm presented above is n3. I'm pretty sure there is a better algorithm with n2 complexity

The algorithm presented above is n3. I'm pretty sure there is a better algorithm with n2 complexity