Google Interview Question
Country: United States
Hey !
Line means slope and offset or you have the equation ax + by + c = 0.
So:
1. It should be a Map to enalbe you to save the offset for each slope in hashMap.
2. If the line is veritcal so slope in INF, and you get a problem, so either use another DS for special lines or check this special cases (x1 == x2) || (y1 == y2) and use some MAX_DOUBLE or something to indicate INF.
This breaks on:
1. Vertical lines. You'll be dividing by zero!
2. Hashing floating points. Double(0.00001).hashCode() != Double(0.0000100001).hashCode()
1. Divide by zero can be handled as a special case
2. Hashing floating is straightforward. why would it break if Double(0.00001).hashCode() != Double(0.0000100001).hashCode()?
Because of floating point rounding errors.
When you come up with two lines: one with the slope 5.00000001, and another with the slope 5.000000099, they should be treated as the same line. But if you just hash the two floats, you'll get different hash values.
import java.util.*;
public class UniqueLines {
public static final double EPSILON = 0.0001;
private static final String FORMAT = "%.4f";
public static class Point {
public final double x;
public final double y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
public boolean isEquivalent(Point other) {
return (Math.abs(other.x - x) < EPSILON) &&
(Math.abs(other.y - y) < EPSILON);
}
}
public static class Line {
public final double slope; // in the case of vertical lines: POSITIVE_INFINITY
public final double intercept; // in the case of vertical lines: the X-intercept
public Line(double slope, double intercept) {
// normalize -0.0/0.0
if (Math.abs(slope - 0.0) < EPSILON) {
this.slope = 0.0;
}
else {
this.slope = slope;
}
// normalize -0.0/0.0
if (Math.abs(intercept - 0.0) < EPSILON) {
this.intercept = 0.0;
}
else {
this.intercept = intercept;
}
}
@Override
public boolean equals(Object other) {
if (other instanceof Line) {
Line otherLine = (Line) other;
if (slope == Double.POSITIVE_INFINITY && otherLine.slope != Double.POSITIVE_INFINITY ||
otherLine.slope == Double.POSITIVE_INFINITY && slope != Double.POSITIVE_INFINITY) {
return false;
}
else if (slope == Double.POSITIVE_INFINITY && otherLine.slope == Double.POSITIVE_INFINITY) {
return String.format(FORMAT, intercept).equals(String.format(FORMAT, otherLine.intercept));
}
else {
return String.format(FORMAT, slope).equals(String.format(FORMAT, otherLine.slope)) &&
String.format(FORMAT, intercept).equals(String.format(FORMAT, otherLine.intercept));
}
}
return false;
}
@Override
public int hashCode() {
if (slope == Double.POSITIVE_INFINITY) {
return String.format(FORMAT, intercept).hashCode();
}
else {
return String.format(FORMAT, slope).hashCode() |
String.format(FORMAT, intercept).hashCode();
}
}
}
public static int numberOfUniqueLines(Point[] points) {
HashSet<Line> lines = new HashSet<Line>();
for (int i = 0; i < points.length; i++) {
for (int j = 0; j < points.length; j++) {
if (i == j) continue;
if (points[i].isEquivalent(points[j])) continue;
double slope, intercept;
// check for vertical line
if (Math.abs((points[j].x - points[i].x)) < EPSILON) {
slope = Double.POSITIVE_INFINITY;
intercept = points[i].x;
}
else {
slope = (points[j].y - points[i].y) / (points[j].x - points[i].x);
intercept = points[i].y - slope * points[i].x;
}
Line line = new Line(slope, intercept);
lines.add(line);
}
}
return lines.size();
}
}
Treat each point as a node in a graph and each node is connected to each other. For example, if we have 4 points, A, B, C, D then we have AB, AC, AD, BC, BD and CD. So we pick any node and do a DFS/BFS and each "step" is a line.
#include<iostream>
#include<map>
#include<vector>
using namespace std;
void create_list(int (*points)[2], int n) {
multimap<float,int *> map;
for (int i = 0; i < 4; i++) {
for (int j = i+1; j < 5; j++) {
float slope = (float)(points[i][1] - points[j][1]) / (points[i][0] - points[j][0]);
int *a = new int[2];
a[0] = i;
a[1] = j;
map.insert(pair<float, int *>(slope, a));
}
}
for (multimap<float, int *>::iterator iter = map.begin(); iter != map.end(); iter++) {
cout << "slope=" << iter->first << " " << "points = {{" << points[iter->second[0]][0] << "," << points[iter->second[0]][1] <<
"}, {" << points[iter->second[1]][0] << "," << points[iter->second[1]][1] << "}" << endl;
}
}
int main(void) {
int points[5][2] = { {1,2},
{2,3},
{3,4},
{1,3},
{2,5} };
create_list(points, 5);
getchar();
return 1;
}
Assuming that 'unique' refers to line slopes. That being said, store the Slope of every possible line in a Set and check the set before returning 2 points as a line. O(n^2) complexity and O(n^2) memory.
EDIT: Forgot in original version to account for the offset in the line equation (the c in y = mx + c). That's now accounted for. Thanks Boris
- zortlord August 19, 2015