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.

- Vin November 24, 2012 | Flag Reply
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;
}

- Benjamin Luke November 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sonesh November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Vin November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- USTChucat November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Vin November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Vin November 25, 2012 | Flag
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)

- USTChucat November 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- dgbfs November 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Obviously O(n^3) will not be accepted

- sonesh November 25, 2012 | Flag
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.

- sachinagarwala251 November 23, 2012 | Flag Reply
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

- dhavaldevildave November 23, 2012 | Flag Reply
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)

- Murali Mohan June 02, 2013 | Flag Reply
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 :)

- Karthik Vvs November 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nirojpokhrel November 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sonesh November 25, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More