## Interview Question

Country: United States

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

Here's my solution from leetcode

/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:

pair<double,double> SlopeAndnIntercept(Point P1, Point P2)
{
pair<double,double>pair1;
if (P1.x == P2.x)
{
pair1.first = numeric_limits<double>::max();

pair1.second = P1.x;
}
else
{
pair1.first = (double)(P2.y - P1.y) / (double)(P2.x - P1.x);
pair1.second = (double)(P1.y - (double)P1.x*pair1.first);
}
return pair1;
}

int maxPoints(vector<Point>& points) {

if(points.size() == 0) return 0;
if(points.size() == 1) return 1;
if(points.size() == 2) return 2;

double epsilon = 0.000000001;
pair<double, double>pair1;
map<pair<double, double>, int> dic;

for (int i = 0; i < points.size(); i++)
{
int nSame = 0;
bool bFirstSame = false;
for (int l = i + 1; l < points.size(); l++)
{
if (points[l].x == points[i].x && points[i].y == points[l].y)
nSame++;
}

if (nSame == points.size() - 1)
return nSame + 1;

for (int j = i + 1; j < points.size(); j++)
{
if (points[i].x == points[j].x && points[i].y == points[j].y)
{
if (bFirstSame)
continue;
else
bFirstSame = true;
}

pair1 = SlopeAndnIntercept(points[i], points[j]);
if (dic.find(pair1) == dic.end())
dic.insert(make_pair(pair1,2+nSame));
else
continue;

for (int k = j + 1; k < points.size(); k++)
{
if (points[i].x == points[k].x && points[i].y == points[k].y)
{
continue;
}

if(pair1.first == numeric_limits<double>::max() && points[k].x == pair1.second)
dic[pair1]++;
else
{
double temp = (double)abs((pair1.first*(points[k].x) + pair1.second) - points[k].y);
if (temp < epsilon)
dic[pair1]++;
}
}

}

}

int max = dic.begin()->second;
for (auto var = dic.begin(); var != dic.end(); var++)
{
if (var->second > max)
max = var->second;
}

return max;
}
};

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

A single point will always lie on a line
Two points will always have a line passing through them
So, unless given a single point or two points, we can use the
following strategy to find collinear pointsOnLine

Setup a a triple loop with point variable pt1, pt2 and pt3
Assume pt1, pt2 and pt3 are not the same (or else we may divide by 0)
Find slope using pt1 and pt2
Now pt3 will be collinear with pt1 and pt2 if slope (pt1, pt3) == slope(pt1, pt2)
Be careful with slope values that are very "close" to each other
Some python code below. Not thoroughly tested, and not very optimal!

``````import math

def pointsOnLine(points):
# one single point always can reside on a line
# any two points can also reside a single line
if len(points) <= 2:
return len(points)

max_points_on_line = 0;
for pt1 in points:
for pt2 in points[1:]:

if twoDifferentPoints(pt1, pt2):

slope = (pt2[1] - pt1[1]) / (pt2[0] - pt1[0])
pts = 0;
#  (assume) pt1, pt2, and pt3 are different points
#  add this check in actual code
for pt3 in points[2:]:
print(pt1, pt2, pt3)
if threeDifferentPoints(pt1, pt2, pt3) and math.isclose(slope, (pt3[1] - pt1[1]) / (pt3[0] - pt1[0])):
pts += 1

if (max_points_on_line < pts):
max_points_on_line = pts;

return max_points_on_line + 2;

def threeDifferentPoints(pt1, pt2, pt3):
return not (pt1[0] == pt2[0] and pt1[1] == pt2[1]
or
pt2[0] == pt3[0] and pt2[1] == pt3[1]
or
pt1[0] == pt3[0] and pt1[1] == pt3[1]
)

def twoDifferentPoints(pt1, pt2):
return not (pt1[0] == pt2[0] and pt1[1] == pt2[1])

def main():
points = [[0, 0], [1, 1], [3, 12],[6,24], [9,36]]
print(pointsOnLine(points))

if __name__ == "__main__":
main()``````

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

[ math.stackexchange.com/questions/20230/maximum-number-of-collinear-points ]
[ stackoverflow.com/questions/4386695/maximum-collinear-points-in-a-plane ]
Finally, the solution.
[ geeksforgeeks.org/count-maximum-points-on-same-line/ ]

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.