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