## Microsoft Interview Question for Software Engineers

• 0

Country: United States
Interview Type: In-Person

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

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

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

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

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'])

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

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

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].x;
int y1 = points[i].y;
int x2 = points[i].x;
int y2 = points[i].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], points[i], 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;
}
}``````

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

Could you please explain what 'st' and 'en' mean? Also, if you could explain in brief about the methods, it'll be easier to follow.

Thanks!

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.