InMobi Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
Hey Vinode, I think that that solution is order n(n -1)/2 not n^2. Distinct pairs in an array is not n^2. Anyway Heres some c++ code:
int main(int argc, const char * argv[])
{
vector<Point> * points = make_a_bunch_of_points();
for (auto i : *points)
{
cout << i.x << " " << i.y << endl;
}
map<Line, int> lineCounts;
int maxCount = 0;
Line * maxLine;
for (int i = 0; i < points->size(); i++) //order n(n-1)/2
{
Point point1 = points->at(i);
for (int j = i + 1; j < points->size(); j++)
{
Point point2 = points->at(j);
Line newLine(point1, point2);
if (lineCounts[newLine])
{
if (++lineCounts[newLine] > maxCount)
{
maxCount = lineCounts[newLine];
maxLine = &newLine; //this will be a stack address but that is OK for now.
}
} else
{
lineCounts[newLine] = 1;
}
}
}
cout << maxCount << endl;
// insert code here...
std::cout << "Hello, World!\n";
return 0;
}
More clarifications : Hash key "Line" means two coordinates of line, Now you have to tell how the hash function actually determine whether the given line is already present or not ?
certainly not by "slope", and obviously not by two coordinates, So How ?
another thing is that in worst case there can be O(n*n) many lines present, similar solution is given by(most trivial one) @USTChucat(complexity : O(n*n*n))
but anyways, good starting..!
@Benjamin Luke - O(n(n -1)/2) = O(1/2(n^2 - n)) = O(n^2 - n) = O(n^2)
worst case space complexity is O(n^2) if all lines between all pair of points are distinct.
@vinod K
How does lineCounts() counts how many points pass through that line? I think counting might take O(n) time.
@ sonesh - the line is in slope y intersect form, so we can calculate the hash value using this two. may you need to take care about the infinite slop also. one Eg:
@slope and intercept are float values:
int hashCode() {
int sl = (int)(slope * 1000);
int in = (int)(intercept * 1000);
return ((sl & 0X0000FFFF)| (in << 16));
}
@USTChucat - no need to count the max line using a function like lineCounts(). Since we need to find the max line, we can keep a variable for keep track of max line. whenever we are inserted to the hash table check for max line also eg:
@ line_count - Hash Table
@ bestLine - keeps track of the max line
Line line = new Line(points[i], points[j]);
if (!line_count.containsKey(line)) {
line_count.put(line, 1);
} else {
line_count.put(line, line_count.get(line) + 1);
}
if (bestLine == null ||
line_count.get(line) > line_count.get(bestLine)) {
bestLine = line;
}
draw lines between any two points and count how many points pass through that line. Time complexity could be O(n^3)
class Point{
public double x;
public double y;
public Point(double x, double y)
{
this.x = x;
this.y = y;
}}
class Line{
private Point p1;
private Point p2;
private double slope;
private double intercept;
public Line(Point p1, Point p2)
{
this.p1 = p1;
this.p2 = p2;
slope = (p1.y - p2.y) / (p1.x - p2.x);
intercept = p1.x - p1.y / slope;
}
public boolean contains(Point pt)
{
if(slope == Double.NEGATIVE_INFINITY || slope == Double.POSITIVE_INFINITY) return pt.x == p1.x;
else return p1.y - slope * (p1.x - pt.x) == pt.y;
}
public double getSlope()
{
return slope;
}
public double getIntercept()
{
return intercept;
}}
public Line getLine(List<Point> points)
{
Line line = null;
int max = -1;
int n = points.size();
for(int i = 0; i < n - 1; i++) {
for(int j = i + 1; j < n; j++) {
Line l = new Line(points.get(i), points.get(j));
int m = 0;
for(int k = j + 1; k < n; k++)
if(l.contains(points.get(k))) m++;
if(m > max) {
max = m;
line = l;
}
}
}
return line;
}
Out of N points, we can draw N(N-1)/2 lines.
1. For each of the lines, find their slope m and the y-intercept c. Make them a pair (m.c)
2. Use a stable sort algorithm like merge sort to first sort the pair by m - complexity O(N^2 * logN)
3. Sort the pair again by c - complexity O(N^2 * logN)
4. Scan the array to compute which (m,c) pairs are in maximum number.Complexity: O(N^2).
Overall complexity: O(N^2 * logN)
This is a problem of constructing Best Fit line through all the points(so that the line passes through maximum number of points) using Least Squares Method in regression analysis.So that constructed line is the required line through which we can find the slope and y-intercept easily :)
great solution. But I have a doubt though, does this line gives the approximated line which in average is closest to all the points. Does this line confirms maximum number of points passing through it ?? Say we have 17 points, 10 of them can be drawn in a line but rest of the 7 points will lie way below the line then. In this case I don't think the line will pass through those 10 points but it tries to find the minimum error from all the points if I am right ??
This can be solved in O(n^2) time and O(m) space. where m is the distinct number of lines among all given points.
- Vin November 24, 20121. use a hash table - key is line and number of appearance of line as value.
2. for each pair of points find the line in slope y intercept form
3. if the line is not there in hash table, add it to the hash table with appearance value 1
4. if the line is already in hash table, increment the appearance value
5. line with the max number of appearance in the hash table is the result.