# Given points on a 2D plane, find line that passes through the most points

Could someone give some feedbacks from perspective of oo design and coding style on the following codes:

Question: Given n points on a 2D plane, find the Line with maximum number of points that lie on it. Similar to https://leetcode.com/problems/max-points-on-a-line/description/. I was given Point interface, empty Line class, empty Solution class and was asked to fill in some functions.

My codes:

public interface Point
{
public double getX();
public double getY();
}

public class Line
private Point p1, p2;
public Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
}

public class Solution
{
// Write the function here
public Line maxPointsLine(Point[] points) {
if(points == null) return null;
if(points.length==1) return new Line(points[0], new Point(p));//
Map<Double, Integer> map = new HashMap<>();// O(n), n = points.length. n-1
Line result;
int maxPoints = 0;
for(int i = 0; i < points.length; i++) { // One Point
map.clear();
int overlap =0;
int countSameX = 1;
for(int j = i+1; j < points.length; j++) { // the second Point
double x = points[j].getX() - points[i].getX(); // x intersect
double y = points[j].getY() - points[i].getY(); // intersect on y coordinate

if(x==0 && y==0) {
overlap++;
}
if(points[j].getX()==points[i].getX()) {// slope is infi,
// slope (1) finite, (2) infinite,
countSameX++;
continue;
}
double slope = y/x;
if(map.contains(slope)) map.put(slope, map.get(slope)+1);
else map.put(slope, 2);
if(map.get(slope)+overlap > maxPoints) { // each line slope and points[i]
// update result and maxPoints
maxPoints = map.get(slope)+overlap;
result = new Line(points[i], points[j]);
}
}
if(countSameX>maxPoints) { // line parallel to Y coordinate
// update result and maxPoints
maxPoints = countSameX;
result = new Line(points[i], points[j]);
}
}
return result;// null
}
}


(I did this coding question long ago. just came into my mind. ) In fact, the interviewer told me that didn’t have good coding style and lack of OO design. suggestions are welcomed for me to improve myself. Thanks.

By the way, as for coding style, there are plugins following standards like https://google.github.io/styleguide/javaguide.html. I just did not fix coding style issues manually due to lack of time.

As for OO design, I was given empty classes. I just added some functions to solve problem I was given.

I really did not find any big issues in my codes. Confused and frustrated.

• – Dannnno Mar 5 '18 at 21:46
• @Dannnno description added. – BAE Mar 5 '18 at 21:52

Disclaimer
I'm a C# dev, not a Java dev. It's possible I make minor syntax mistakes in this answer, but the intention of the answer is to argue the intention of OOP, not the exact syntax of Java.

## Adherence to OOP - part 1

Other than having defined a Line and Point class, there is no OOP approach in this solution. This is the biggest red flag:

public class Solution


If your solution is implemented in a single class, then it's not really making the best of an OOP approach. You'd expect an OOP solution to be a collection of classes.

When you start with OOP, the first thing you should do is split responsibilities. As you have put everything into a single class with a single method; that implies that you think there is only a single responsibility. I disagree. There are several independent parts of logic needed for this problem:

• Defining a line by supplying two points (point A and point B => line AB)
• Checking if another point is on the same line (C and line AB => boolean)
• Tracking which points are all on the same line.
• Testing the entire collection of points to find the line with the highest point count.

4 responsibilities suggests that you are likely going to need at least 4 classes, each with a single responsibility.
Note: That's a theoretical estimate. The interview question is simple for the sake of example, so many of these can arguably be condensed. I can definitely see an argument for combining the last two bullet points.

We'll get back to this point when we address the math itself.

## Coding style

I'm having trouble following your approach. I've grown a bit rusty in math over the years, but I feel like the bigger issue here is your coding style. It's horribly unreadable. Some examples:

• There is one empty line in your entire method.

This doesn't really make things easily readable. Line breaks don't have an effect on program performance, so use them freely. Separate smaller logical "chapters", such as declarations, initializations, and flow logic (if, for, etc.)

In your defense, the style guide you referenced also seems to avoid line breaks. However, their code usually consists of very terse and very simple examples.
As you can see, "real" code isn't as neat as example code. You need to pay more attention to readability if the code becomes more complex (alphanumerically, not necessarily logically).

Some examples:

Map<Double, Integer> map = new HashMap<>();// O(n), n = points.length. n-1

if(points[j].getX()==points[i].getX()) {// slope is infi,
// slope (1) finite, (2) infinite,


At a guess, I'd say you wrote these comments for yourself during development. And that's fine, I do that too.

But try to put yourself in my shoes now. I'm looking at your code, and all I see if a bunch of complicated mathematical logic. There is no explanation of the intention of the algorithm, and the existing comments make things more confusing instead of explaining it.

This doesn't need to be done via comments (external documentation takes more effort but can be as helpful); but comments are an easy first attempt at documenting the code.

• You have defined a Line class, but you are not using it until after you've established that a given pair of points defines the line with the most points on it.

That's putting the cart before the horse. You should be using the Line class to handle the logic of checking if a point is on it.

You've basically "faked" OOP by putting the result of your (non-OOP) method in a class, while leaving the method devoid of any real OOP principles.

## The math

I can see hints that you understand the mathematical side of things. You've e.g. avoided the symmetry trap (checking A,B and then B,A).

The slope calculation is a clever approach. I would've solved it differently, i.e. by calculating the equation of the AB line (y = ax + b, you can essentially define a line by storing the values of a and b), and then testing to see if other points fit the equation.

I'm going to use your approach (slope calculation), but I'm reshuffling the approach. I'm trying to focus on easy OOP principles.

## Adherence to OOP - part 2

Here's my countersuggestion for a better OOP approach:

• Take two points (the same way you did it, avoiding symmetrical operations)
• Define a Line based on these two points.
• Store the two points in a list (instead of two separate fields)
• For all remaining points, check if they are on the same line.
• If so, then add this point to the point list in the Line.
• Store the lines for later retrieval
• At the end, take the line with the longest list of points.

You'll find that the underlying mathematics are exactly the same as yours, but the order of operations is changed to a more segregated design:

• We contain line-specific logic in the Line class.
• We can separate the overarching logic (starting from a given pair AB) from the inner logic (checking all other points to see if they are on AB).

A quick implementation example:

Take two points (the same way you did it, avoiding symmetrical operations).

List<Line> listOfLines = new List<Line>();
for(int a = 0; a < points.length; a++) //point A
{
for(int b = a+1; b < points.length; b++) // point B
{


Define a Line based on these two points.

var lineAB = new Line(points[a], points[b]);


Store the lines for later retrieval

listOfLines.Add(lineAB);


Note the changed Line class:

public class Line
{
public List<Point> Points;
public Line(Point a, Point b) {
this.Points = new List<Point>();
}
}


For all remaining points, check if they are on the same line. If so, then add this point to the point list in the Line.

for(int c = b+1 ; c < points.length ; c++) //point C
{
if(lineAB.ContainsPoint(points[c])
{
}
}


Note the methods in the Line class:

public bool ContainsPoint(Point c)
{
var a = this.Points[0];
var b = this.Points[1];

//If all X values are equal, they are on the same line:
if(a.GetX() == b.GetX() && a.GetX() == c.GetX())
return true;

//If all Y values are equal, they are on the same line:
if(a.GetY() == b.GetY() && a.GetY() == c.GetY())
return true;

//If AB and AC have the same slope, they are on the same line:
return CalculateSlope(a,b) == CalculateSlope(a,c);
}

private double CalculateSlope(Point p1, Point p2)
{
double xDiff = p2.GetX() - p1.GetX();
double yDiff = p2.GetY() - p1.GetY();

return yDiff / xDiff;
}


At the end, take the line with the longest list of points:

Line lineWithMostPoints = null;

for (Line l : listOfLines) {
if (
lineWithMostPoints == null
|| l.Points.Length > lineWithMostPoints.Points.Length
)
lineWithMostPoints = l;
}

return lineWithMostPoints;


## Summary of changes

This is just a quick-fire list of why this reworked example uses a lot more OOP:

• Most calculation logic operates in scope of the smaller possible module, e.g. two points, or a line and a point. During these calculations, there is no additional hassle from having to use collections, thus unburdening the code complexity.
• The calculation of slopes is a separate method.
• The logic (which checks if point C lies on line AB) is separated, and much more intuitive (compared to storing int countSameX and Map<Double, Integer> map and then using those to calculate your result).
• Comments explain why certain code exists (ContainsPoint() is a good example of this) and help with readability.
• Variable names have been slightly improved. Yours weren't too bad, but condensing everything into the same method caused you to suffer from persistent variable names. E.g. notice how ContainsPoint() refers to A,B,C as specific point with specific meanings, but the underlying CalculateSlope() method simply uses P1 and P2 because it doesn't care about whether you passed A, B or C. Using separate methods gives you the option to rename parameters to better suit the scope of the current method.
• Overall, the code is more self-documenting than before. Though more verbose, it's easier to understand the intention of a method by looking at its body.
• Notice that it's not just a matter of comments and variable names. The method names of the additional methods also help to divide the logic into chapters. I did not need to use comments to explain the CalculateSlope() method, as its name inherently reveals its purpose.

• Ideally, you may want to make the Points in the Line class private, and add specific methods to add extra points to it and retrieve its length.
• You could change ContainsPoint to immediately add the point if it fits on the line. Rename the method's name according, if you do this!
• Even though you're skipping the simple symmetry pitfall (AB,BA), there is a similar pitfall for lines with already established points (e.g. ABDE, DE).
• Let's say you first check line AB. As it turns out, C is not on AB, D and E are both on AB.
• A few iterations later, you're checking line BD. Based on your earlier calculations, you already know that E is on BD. You don't really need to check that again; but the current code still does it anyway.
• This is a minor performance thing, but its importance can increase as the collection of points increases.
• Ideally, whenever you start checking a new line (e.g. DE), you should first check your existing results for a line which contains both these points (e.g. line AB contains points A,B,D,E so it contains information that is relevant to you now). Instead of creating a line DE, you could instead skip the calculation because AB(+DE) is already more complete than the new line DE will ever be (as it won't check A and B again, we already passed those).
• A similar performance gain can be made by stopping the iteration early.
• Let's say you have 26 points (A to Z). You're now starting on the calculations for lines where the first point is X.
• At best, these calculations can only yield a maximum of 3 points (X,Y,Z), since the calculations never checks the other points again.
• Suppose that you already have a line in your collection which has 5 points on it (ABCDE). There's no point to doing further calculations, because even if every remaining point is on the same line (XYZ), it'll still contain less points than the existing line with ABCDE.
• Similarly, if you find a line with more than half of the point list on it (and you've tested all points for compatibility with this line), you can be sure that this is the longest line possible, since it's impossible for two distinct lines to share more than a single point.

Most of these improvement would make the existing code more complex, which would suggest either separating it further, or documenting it better. Or, preferably, both.

• Thank you very much. I learned a lot. By the way, I did the coding in a phone interview. I just had 30 mins to write the codes. I added the comments to explain my logic and explain to the interviewer. and I really mentioned I can move some codes to other classes. due to lack of time, I did not do it from beginning. and then I was rejected due to lack of oo design and coding style – BAE Mar 6 '18 at 14:11

i think your task was to use the given classes Point and Lineand extend them...

public class Line{

public Line (Point a, Point b);

public boolean contains(Point p);

}


Lines lines = getAllLines();//easily iterate over the permutated Point matrix

for(Line line: lines){
int amountOfPoints = 0;
for (Point p: points){
if (line.contains(p) {
amountOfPoint = amountOfPoint + 1;
}
}


## NOTE

this is just an explanation of OO-Programming, i didn't include the subtaks, e.g. how to get the max of the lines, or how contains() works, but it surely gives a hint on where the questions aims at...