Microsoft Interview Question for Software Engineers


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

- Javascripter October 13, 2017 | Flag Reply
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))

- Alireza October 13, 2017 | Flag Reply
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][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;
    }
  }

- sudip.innovates October 14, 2017 | Flag Reply


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