## Microsoft Interview Question for Software Engineers

• 0
of 0 votes

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

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

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!

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