## InMobi Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Written Test

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

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.

1. 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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}``````

Comment hidden because of low score. Click to expand.
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..!

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

@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.

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

@vinod K
How does lineCounts() counts how many points pass through that line? I think counting might take O(n) time.

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

@ 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));
}``````

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

@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;
}``````

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

draw lines between any two points and count how many points pass through that line. Time complexity could be O(n^3)

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

``````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;
}``````

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

Obviously O(n^3) will not be accepted

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

If possible please make " max points from those specified pass through the line." a little more clear.

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

can we do like
1) find slope of all two points
2) maximum number of slops which are same can be either parallel or in same line, so now finding equation and checking for those points only
this sol can give in less complexity
O(n^2M) where M=maximum number of same slope line segments

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

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)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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 :)

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

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 ??

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

@nirojpokhrel : yes, you are right, the methods only give the best possible approximation(having least square error), but does not always give us the required solution.

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.