## Microsoft Interview Question

Software Engineers**Country:**United States

**Interview Type:**In-Person

Solution for the first question based on an explanatory document on intersecting line segments.

Implementation in Python/3.6.1

```
def cross_product(v1, v2):
return v1['x'] * v2['y'] - v1['y'] * v2['x']
def dot_product(v1, v2):
return v1['x'] * v2['x'] + v1['y'] * v2['y']
def subtract(v1, v2):
return dict(x=v1['x'] - v2['x'], y=v1['y'] - v2['y'])
def add(v1,v2):
return dict(x=v1['x'] + v2['x'], y=v1['y'] + v2['y'])
def count(ls1, ls2):
p = dict(x=ls1['xs'], y=ls1['ys'])
q = dict(x=ls2['xs'], y=ls2['ys'])
r = dict(x=ls1['xe']-ls1['xs'], y=ls1['ye']-ls1['ys'])
s = dict(x=ls2['xe']-ls2['xs'], y=ls2['ye']-ls2['ys'])
rxs = cross_product(r, s)
q_p = subtract(q, p)
q_pxs = cross_product(q_p, s)
q_pxr = cross_product(q_p, r)
if rxs == 0 and q_pxr == 0: # two line segments are colinear
t0 = dot_product(q_p, r) / dot_product(r, r)
t1 = t0 + dot_product(s, r) / dot_product(r, r)
if (t0 >= 0 and t0 <= 1) or (t1 >= 0 and t1 <= 1):
return 'overlap'
else:
return 0
if rxs == 0 and q_pxr != 0: # two line segments are parallel and non-intersecting
return 0
t = q_pxs / rxs
u = q_pxr / rxs
if rxs != 0 and t >= 0 and t <= 1 and u >= 0 and u <= 1: # two line segments are intersecting at point p+tr = q + us
return 1
return 0 # not parallel non-intersecting
def count_intersects(l):
result = 0
for i in range(len(l) - 1):
for j in range(i+1, len(l)):
c = count(l[i], l[j])
if c != 'overlap':
result += c
else:
return 'overlap'
return result
if __name__ == '__main__':
l = [dict(xs=1.5, ys=2.5, xe=1, ye=3), dict(xs=1.5, ys=2.5, xe=1, ye=4), dict(xs=5, ys=5, xe=2, ye=3), dict(xs=5, ys=5, xe=5, ye=3)]
print(count_intersects(l))
```

O(n^2) soln.

O(nLog(n)) with sweep algo is also possible.

```
public static void main(String[] args){
Point[][] points1 = {{new Point(1,1), new Point(10,1)}, {new Point(1,2), new Point(10,2)}};
int n = intersections(points1);
System.out.println(n);
Point[][] points2 = {{new Point(10,0), new Point(0,10)}, {new Point(0,0), new Point(10,10)}};
n = intersections(points2);
System.out.println(n);
Point[][] points3 = {{new Point(-5,-5), new Point(0,0)}, {new Point(1,1), new Point(10,10)}};
n = intersections(points3);
System.out.println(n);
Point[][] points4 = {{new Point(10,0), new Point(0,10)}, {new Point(1,1), new Point(10,10)}, {new Point(0,0), new Point(10,10)}, {new Point(-5,2), new Point(10,10)}};
n = intersections(points4);
System.out.println(n);
}
// not handling same intersection for more than 2 lines
public static int intersections(Point[][] points){
int n = points.length;
Line[] lines = new Line[n];
for(int i = 0; i < n; i++){
int x1 = points[i][0].x;
int y1 = points[i][0].y;
int x2 = points[i][1].x;
int y2 = points[i][1].y;
double slope = 0.0;
if(x1 == x2)
slope = 0.0;
else if(y1 == y2)
slope = 1.0;
else
slope = (y2-y1)/(x2-x1);
lines[i] = new Line(points[i][0], points[i][1], slope);
}
sortslopes(lines, 0, n-1);
int intersects = 0;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
Line l1 = lines[i];
Line l2 = lines[j];
if(l1.st.x >= l2.st.x && l1.en.x <= l2.en.x && l1.st.y <= l2.en.y && l1.en.y >= l2.st.y)
intersects++;
}
}
return intersects;
}
public static void sortslopes(Line[] lines, int l, int h){
if(l >= h)
return;
double mid = lines[(h-l)/2 + l].slope;
int i = l;
int j = h;
while(i <= j){
while(lines[i].slope < mid)
i++;
while(lines[j].slope > mid)
j--;
if(i <= j){
swap(lines, i, j);
i++;
j--;
}
}
if(i < h)
sortslopes(lines, i, h);
if(l < j)
sortslopes(lines, l, j);
}
public static void swap(Line[] lines, int i, int j){
Line t = lines[i];
lines[i] = lines[j];
lines[j] = t;
}
static class Line{
Point st;
Point en;
double slope;
public Line(Point st, Point en, double slope){
this.st = st;
this.en = en;
this.slope = slope;
}
}
static class Point{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
```

In this approach I am not taking into consideration the two lines being collinear.

- Javascripter October 13, 2017/**

* Given list of line segments({x_start, y_start}, {x_end, y_end}) find out the maximum

* number of points they intersect.

* (interviewer said, he can make it simpler by assuming only vertical or horizontal

* lines with no overlapping lines).

*/

#include <vector>

#include <iostream>

#include <stdlib.h>

using namespace std;

/**

* Cross product of vectors returning a scalar

*/

double v_cross_product(vector<double> a, vector<double> b) {

return abs((a.at(0) * b.at(1)) - (b.at(0) * a.at(1)));

}

vector<double> v_sum(vector<double> a, vector<double> b) {

return {a.at(0)+b.at(0), a.at(1)+b.at(1)};

}

vector<double> v_sub(vector<double> a, vector<double> b) {

return {a.at(0)-b.at(0), a.at(1)-b.at(1)};

}

vector<double> v_prod(vector<double> a, double scalar) {

return {a.at(0)*scalar, a.at(1)*scalar};

}

class Line {

vector<double> p;

vector<double> p1;

public:

Line(double cx1, double cy1, double cx2, double cy2) {

p = { cx1, cy1 };

p1 = { cx2, cy2 };

}

vector<double> getStart() {

return p;

}

vector<double> getEnd() {

return p1;

}

/**

* t = (q − p) × s / (r × s)

* u = (q − p) × r / (r × s)

* vector A = p + r

* vector B = q + s

*/

bool intersect(Line *line) {

vector<double> q = line->getStart();

vector<double> q1 = line->getEnd();

vector<double> s = v_sub(q, q1);

vector<double> r = v_sub(p, p1);

double base = v_cross_product(r, s);

double t = v_cross_product(v_sub(q, p), s) / base;

double u = v_cross_product(v_sub(q, p), r) / base;

if(base != 0 && t >= 0 && t <= 1)

return true;

return false;

}

};

void print_lines_intersections(vector<Line*> lines) {

for(int i = 0; i < lines.size(); i++) {

int intersections = 0;

for(int j = 0; j < lines.size(); j++) {

if(i != j && lines.at(i)->intersect(lines.at(j))) intersections++;

}

cout << "Line " << i << " has " << intersections << endl;

}

}

int main(int argc, char **args) {

vector<Line*> lines = {

new Line(0.0, 0.0, 2.0, 2.0),

new Line(0.0, 1.5, 2, 1.5),

new Line(0.0, 1.5, 2, 1.5),

new Line(3, -1.5, 2, 1.5),

new Line(-8, 3, 4, -1.5),

};

print_lines_intersections(lines);

}