Microsoft Interview Question for Software Engineer / Developers


Country: Serbia
Interview Type: Written Test




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

I have used the following algorithm described by - IntwPrep.MS

Way to test a point (p,q) is within a triangle is by checking if the area of the triangle is equal to the sum of the three triangles formed with (p,q).

Now to return points within a triangle
- Get a point (p,q) which is within the triangle
- Use flood-fill to generate next points by using the above mentioned condition

#include <iostream>
#include <set>
#include <utility>
#include <cstdlib>
using namespace std;

double t_area;		//area of the triangle given
set<pair<int, int> > res;	//set of pairs, only unique pairs are stored

double area(int x1, int y1, int x2, int y2, int x3, int y3)
{
	double val = abs(x1*(y2 - y3) + x2*(y3 - y1) + x3*(y1 - y2));	
	val = val / 2.0;
	return val;
}
	
bool is_inside(int x[], int y[], int a,int b)
{	
	double ar = 0;
	ar += area(x[0], y[0], x[1], y[1], a, b);
	ar += area(x[0], y[0], a, b, x[2], y[2]);
	ar += area(a, b, x[1], y[1], x[2], y[2]);	
	if ( ar == t_area)
		return true;
	else
		false;
}

void find_pts(int x[], int y[], int a, int b)
{
	if (res.count( make_pair(a,b)) == 1)
		return;
	cout<<a<<" "<<b<<endl;
	res.insert( make_pair(a,b));
	
	if (is_inside(x, y, a-1, b-1))
		find_pts(x, y,a-1 , b-1);
	if (is_inside(x, y, a, b-1))
		find_pts(x, y,a , b-1);
	if (is_inside(x, y, a+1, b-1))
		find_pts(x, y,a+1 , b-1);
	if (is_inside(x, y, a-1, b))
		find_pts(x, y,a-1 , b);
	if (is_inside(x, y, a+1, b))
		find_pts(x, y,a+1 , b);
	if (is_inside(x, y, a-1, b+1))
		find_pts(x, y,a-1 , b+1);
	if (is_inside(x, y, a, b+1))
		find_pts(x, y,a , b+1);
	if (is_inside(x, y, a+1, b+1))
		find_pts(x, y,a+1 , b+1);
}

int main()
{
	int x[3], y[3];
	
	for (int i=0;i<3;i++)
	{
		cin>>x[i]>>y[i];
	}
	t_area = area(x[0], y[0], x[1], y[1], x[2], y[2]);
	cout<<"---------------\n";
	find_pts(x,y,x[0],y[0]);
}

- LAP December 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thank you, if you can, write it in java please. If not ok, it will still help others.

- BB December 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The points are probably int types, otherwise it would be infinite points.
Any constructive opinion?

- BB December 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Way to test a point (p,q) is within a triangle is by checking if the area of the triangle is equal to the sum of the three triangles formed with (p,q).

Now to return points within a triangle
- Get a point (p,q) which is within the triangle
- Use flood-fill to generate next points by using the above mentioned condition

- IntwPrep.MS December 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

More BS.

- Anonymous December 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ok i've done the first part, but i don't understand how to add flood fill part in my code. Can you help me?

public static boolean isItInTriangle(int x1, int y1, int x2, int y2, int x3, int y3) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x4 = 0;
        int y4 = 0;
        try {
            System.out.println("Write the x coordinate for point P");
            x4 = Integer.parseInt(br.readLine());
            System.out.println("Write the y coordinate for point P");
            y4 = Integer.parseInt(br.readLine());
        } catch (Exception e) {
        }

        int ABC = Math.abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))/2;
        int PBC = Math.abs(x4 * (y2 - y3) + x2 * (y3 - y4) + x3 * (y4 - y2))/2;
        int APC = Math.abs(x1 * (y4 - y3) + x4 * (y3 - y1) + x3 * (y1 - y4))/2;
        int ABP = Math.abs(x1 * (y2 - y4) + x2 * (y4 - y1) + x4 * (y1 - y2))/2;
        if (ABC == PBC + APC + ABP) {
            System.out.println("P in inside the ABC");
            return true;
        } else {
            System.out.println("P is not inside the ABC");
            return false;
        }
    }

- BB December 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Triangles {

public static void main(String[] args) {
int[]a={0,0};
int[]b={0,2};
int[]c={3,0};
int[]d={0,2};
System.out.println(getArea(a,b,c));
System.out.println(ptInside(a,b,c,d));
}
static double distance(int[]a,int[]b){
if(a.length>2 || b.length>2){
System.out.println("Not a valid coordinate");
return 0;
}
else{//a0a1x1y1 b0b1x2y2
double dis=Math.sqrt((Math.pow((b[1]-a[1]),2)+Math.pow((b[0]-a[0]),2)));
return dis;
}

}
static double getArea(int[]a,int[]b,int[]c){
double x=distance(a,b);
double y=distance(b,c);
double z=distance(c,a);
double semi=(x+y+z)/2;
double area=Math.sqrt(semi*(semi-x)*(semi-y)*(semi-z));
return area;

}
static boolean ptInside(int[]a,int[]b,int[]c,int[]d){
if(getArea(a,b,c)==getArea(a,b,d)+getArea(b,c,d)+getArea(d,c,a)){
return true;
}
else{
return false;
}
}

}

- Surya Rekha December 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sides a,b,c. Point m to be verified if it's coordinates found within the triangle
Calculated the sum of all the areas of the triangles abm,bcm,cam. If their areas' sum is equal to area of abc, the point's within the triangle.

- Surya Rekha December 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This does exactly the same my code does. Check if some point is inside the triangle. We need to return ALL the points inside.

- BB December 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Find the Max and Min value of X and Y coordinates from 3 given x1,x2,x3 and y1,y2,y3 points respectively. Label them as Xmax and Xmin and Ymax and Ymin. Use a m*n for loop with m limit from Xmin to Xmax and n loop from Ymin to Ymax and for each point m,n check whether this point is outside or inside the triangle using sum of 3 triangles = 1 complete triangle

- Niket January 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This seems like a simple problem, and flood-fill etc seems overkill. (assuming we are only dealing with integers, otherwise agree with the BS comments).

Say points are P1, P2 and P3.

Find the leftmost point of the triangle (smallest x coordinate). If there are two, then it is a different case easily dealt with.

Say the sorted x coords are x1 <= x2 <= x3 (and Pi = (xi, yi)

Now for all integers M in x1 to x2, find intersections of x = M with the two sides of the triangle P1P2 and P1P3.

For integers N in range x2 to x3, find the intersections of x = N with the two side P2P3 and P1P3.

- Anonymous December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This formula for calculating the area, only works for the 1st quadrant of the coordinate system.

Math.abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))/2

You need to shift the coordinates to pull them to the Q1 before applying the formula.

- Arif December 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There is a more computational efficient solution to this by using vector operations.
Each vector is the 2D point P1=(x1,y1) P2= (x2,y2) P3=(x3,y3).
A random point inside the triangle is given by:
p=a1*P1+(1-a1)*a2*P2
OR:
p=a1*P2+(1-a1)*a2*P3
p=a1*P1+(1-a1)*a2*P3

where a1 and a2 are uniform variates in the interval [0,1].
This will give you a non uniform distribution inside the triangle but will be much faster. There is also a way to generate a uniform distribution by using a quadrilateral composition.

- epokh January 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please read completely before calling BS.

In scanline rasterizer, we try to color all pixels that is covered by the triangle given by the coordinates (x1,y1) (x2,y2) and (x3,y3) . Ignoring the z-coordinates.

If we just use the math of the scanline rasterizer then we can get what are the points which are present inside the triangle . which is pretty much the (x,y) we need.

This is my idea.

- Pras January 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a different solution in Java.

// List every point inside (or exactly on the line) the triangle ABC.
import java.util.*;

public class Solution
{
	private static class XCoordinateComparator implements Comparator<Point>
	{
		@Override
		public int compare(Point p1, Point p2)
		{
			return p1.getX() - p2.getX();
		}
	}

	private static class Point
	{
		private int x;
		private int y;

		public Point(int x, int y)
		{
			this.x = x;
			this.y = y;
		}

		public int getX()
		{
			return x;
		}

		public int getY()
		{
			return y;
		}

		@Override
		public String toString()
		{
			return String.format("(%d,%d)", x, y);
		}
	}

	// line between two points A and B
	private static class Line
	{
		private Point A;
		private double slope;

		public Line(Point A, Point B)
		{
			this.A = A;
			if (A.getX() == B.getX())
				throw new RuntimeException("division by zero");

			slope = (B.getY() - A.getY()) / ( (B.getX() - A.getX()) * 1.0);
		}

		public double valAtX(int x)
		{
			return slope * (x - A.getX()) + A.getY();
		}

	}

	static List<Point> pointsInTriangle(Point P1, Point P2, Point P3)
	{
		Point[] triangle = {P1, P2, P3};
		Arrays.sort(triangle, new XCoordinateComparator());

		Point 	A = triangle[0], // left most point on x axis
				C = triangle[1],
				B = triangle[2]; // right most point on x axis

		List<Point> points = new ArrayList<>();
		Line AB = new Line(A,B);
		Line AC = new Line(A,C);
		Line CB = new Line(C,B);

		// iterate from left most x value to right most x value
		// while x is smaller or equal to C.x calculate the y value
		// of the AB at x and AC at x and list all the points between
		// once x is bigger than AC.x, to the same for AB and CB until
		// x is bigger than B.x
		for (int x = A.getX(); x <= B.getX(); x++)
		{
			double y1 = AB.valAtX(x);
			double y2;
			if (x <= C.getX())
				y2 = AC.valAtX(x);
			else
				y2 = CB.valAtX(x);

			int yBottom = (int) Math.ceil(Math.min(y1, y2));
			int yTop = (int) Math.floor(Math.max(y1, y2));
			for(; yBottom <= yTop; yBottom++)
				points.add(new Point(x, yBottom));
		}

		return points;
	}
}

- jay January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Suppose we have three points A, B, C such that A - the leftmost point, B - middle point, C - the rightmost point. Also recall that the equation of the line passing through the two points, as follows: (Y - Y1) / (Y2 - Y1) = (X - X1) / (X2 - X1).

Then an algorithm for finding points with integer coordinates what inside the triangle as follows:
1) Find the equation of segments AB, AC, BC
2) Determine which side will be incremented Y coordinate (if B is greater than A, then up, otherwise down)
3) Move from point A to point C on the segment AC
4) For each X will move up (down) from function AB to AC, after to BC. On each point (x, y) check, whether this point is above (below) the points on the function AB and AC

Code on F#:

type Point = {x : int; y : int}

let fst (x, _, _) = x
let snd (_, x, _) = x
let thd (_, _, x) = x

let FindMoveStrategy (leftPoint : Point) (middlePoint : Point) = 
    match leftPoint, middlePoint with
        leftPoint, middlePoint when leftPoint.y < middlePoint.y -> ((fun x -> x + 1), (fun curY yTo -> curY < yTo), (fun (y : float) -> (int)y + 1))
        | _, _ -> ((fun x -> x - 1), (fun curY yTo -> curY > yTo), (fun (y : float) -> (int)y))

let LineEquation (point1 : Point) (point2 : Point) = 
    fun (x : int) -> (float)(point2.y - point1.y) * (float)(x - point1.x) / (float)(point2.x - point1.x) + (float)point1.y

let FindPoints (xFrom : int) 
               (xTo : int) 
               (equationFrom : int -> float) 
               (equationTo : int -> float) 
               (fMove : (int -> int) * (int -> int -> bool) * (float -> int))
               (state : Point list) =
    let rec InnerFindPoints (curX : int) (state : Point list) = 
        match curX with
            curX when curX < (xTo + 1) -> 
                let rec InnerY (curY : int) (state : Point list) = 
                    match curY with
                        curY when (snd fMove) curY ((int)(equationTo curX)) -> InnerY (fst fMove curY) ({new Point with x = curX and y = curY} :: state)
                        |_ -> state
                InnerY ((thd fMove) (equationFrom curX)) state
                |> InnerFindPoints (curX + 1)
            | _ -> state
    InnerFindPoints xFrom state

[<EntryPoint>]
    let main argv =
        let A = {new Point with x = 1 and y = 1} 
        let B = {new Point with x = 3 and y = 5} 
        let C = {new Point with x = 5 and y = 3}
        let sortedPointList = List.sort (A :: B :: C :: [])
        let leftPoint = sortedPointList.Item(0)
        let middlePoint = sortedPointList.Item(1)
        let rightPoint = sortedPointList.Item(2)
        let moveStrategy = FindMoveStrategy (leftPoint) (middlePoint)
        let equationFrom = LineEquation leftPoint rightPoint
        let equationTo1 = LineEquation leftPoint middlePoint
        let equationTo2 = LineEquation middlePoint rightPoint
        let res = FindPoints leftPoint.x middlePoint.x equationFrom equationTo1 moveStrategy [] 
                    |> FindPoints (middlePoint.x + 1) rightPoint.x equationFrom equationTo2 moveStrategy

        printfn "%A" res
        0

- sattar.imamov January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

let our original triangle be ABC, and Point P. Consider three different triangles,

PAB PBC PCA

,,
now,

if Area(ABC) == sigma( all three )

then point is inside.
For area, you can use herons formula, and for comparison of floating point values set an epsilon value of something like 10^^-6

- NaMo January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

let our original triangle be ABC, and Point P. Consider three different triangles,

PAB PBC PCA

,,
now,

if Area(ABC) == sigma( all three )

then point is inside.
For area, you can use herons formula, and for comparison of floating point values set an epsilon value of something like 10^^-6

- NaMo January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

I call BS on this.

- Anonymous December 28, 2013 | 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