Twitter Interview Question


Country: United States
Interview Type: Phone Interview




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

1> You first pick one point p1, and calculate the distance to other three points d12, d13, d14.
2> two of these three points should be the same, otherwise fails to be square. Suppose they are d12=d13, and d14 should be bigger than d12, otherwise, fails.
3> Check inner product of vector(p2-p1) and (p3-p1), should be zero. Otherwise they fails.
4> If the middle point of p1 and p4, should be the same of middle point of p2 and p3, it is square. Otherwise it is not.

For the points, people should not assume their order in the real coordinate, but should find out through the calculation. Otherwise, you may only to calculate two sides and make sure they are the same.

- chenlc626 March 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No need for step <4>, in <2>, check if d14 * d14 == d12*d12*2;

- Charlie July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Or maybe I can check your step 1 for three times. If every time two of the three points are the same, then it is a square

- wangwenusa11 September 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

You can calculate the distance between each point and check if they are all equal.

#include <stdio.h>
#include <math.h>

typedef struct{
  int x;
  int y;
}Point;

double distance(const Point *p1, Point *p2){
  return sqrt(pow((p1->x - p2->x),2) + pow((p1->y - p2->y),2));
}

int is_square(Point *a, Point *b, Point *c, Point *d){
  double ab, bc, cd, ad;
  ab = distance(a,b);
  bc = distance(b,c);
  cd = distance(c,d);
  ad = distance(a,d);
  if((ab == bc) && (ab == cd) && (ab == ad))
    return 1;
  else
    return 0;
}
int main(){

  Point a = {0,0};
  Point b = {0,1};
  Point c = {1,1};
  Point d = {1,0};

  printf("They %s form a square.",(is_square(&a,&b,&c,&d))?"do":"don't");
  
  return 0;
}

- srdjan March 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution will not work because you do not work the order of a, b, c, d. For example ab can be diagonal, if((ab == bc) && (ab == cd) && (ab == ad)) will be false, and your method will return 0.

- Anonymous June 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Along with checking whether the sides are equal, check whether the dialgonals are equal. Coz just sides equal property satisfies rombus too.

- Babu January 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Transform co-ordinate system to one of these points. The remaining will fall on x-axis, y axis and the other would have one coordinate each from those points.
After transformation
(0,0),(x,0),(0,y),(x,y) (if square)

- Anonymous March 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but to conversion might take much time, we might need to rotate the axis..which will add more time consumption.

- sapy April 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I took a different direction. The properties of the points of all four points of the square are covered by checking min/max x/y. So, multipass through the points.
1. Pass 1: Get all mins and maxes.
2. Create an array of 4 bools and check for all four points.
3. Check to make sure all 4 bools are set. If someone rants about the cost of scanning an array of 4 items, I'll laugh. If a programming language is that bad, why use it?
I'm kinda into maintainable and readable over compact. That took ten minutes to write and test.

import java.awt.Point;
import java.util.Arrays;

public class PointsAreSquare {

	/**
		given 4 points, whose x and y coordinates are both integers. 
		they are all different. write a function to check if they form a square. 
		i forgot to point out that the points can be given in any order	 
	*/
	public static void main(String[] args) {
		Point[] points = new Point[4];
		points[0] = new Point(3, 1);
		points[1] = new Point(-1, 1);
		points[2] = new Point(3, -2);
		points[3] = new Point(-1, -2);
		
		int minX = Integer.MAX_VALUE;
		int maxX = Integer.MIN_VALUE;
		int minY = Integer.MAX_VALUE;
		int maxY = Integer.MIN_VALUE;
		// Find min/max x/y
		for (Point p : points ) {
			minX = Math.min(minX,  p.x);
			maxX = Math.max(maxX,  p.x);
			minY = Math.min(minY,  p.y);
			maxY = Math.max(maxY,  p.y);
		}
		// Array of booleans to mark if 
		// we find points in cc direction starting at UL
		boolean[] found = new boolean[4];
		for (Point p : points) {
			//UL:minX, maxY
			if (p.x == minX && p.y == maxY) found[0] = true;
			//UR:maxX, maxY
			if (p.x == maxX && p.y == maxY) found[1] = true;
			//LR:maxX, minY
			if (p.x == maxX && p.y == minY) found[2] = true;
			//LL:minX, minY
			if (p.x == minX && p.y == minY) found[3] = true;
		}
		for (boolean b : found) {
			if (!b) {
				System.out.println("Points don't represent a square.");
				return;
			}
		}
		System.out.println("Points " + Arrays.toString(points) + " are a square.");
	}
}

- FredCycle May 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry, it's not enough to check he distances, you should also check if the angles are 90 degrees each. If the scalar product of the two vectors (points) is 0 then the angle between them is 90 degrees.

- srdjan March 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The concept: diagonals in a square are at 90 degrees and opposite sides are parallel.

#include<iostream>

using namespace std;

typedef struct point
{
	double x;
	double y;
}point;

double find_slope(point A, point B)
{
	return (A.y-B.y)/(A.x-B.x);
}

int main()
{
	point A, B, C, D;
	A.x = 1.0;
	A.y = 1.0;
	B.x = 2.0;
	B.y = 1.0;
	C.x = 2.0;
	C.y = 2.0;
	D.x = 1.0;
	D.y = 3.0;

	double slope_A_B = find_slope(A,B);
	double slope_C_D = find_slope(C,D);
	bool is_square = false;
	if(slope_A_B == slope_C_D)
	{
		double slope_A_C = find_slope(A,C);
		double slope_B_D = find_slope(B,D);
		if(slope_A_C * slope_B_D == -1)
			is_square = true;
		if(!is_square)
        	{
                      double slope_A_D = find_slope(A,D);
                      double slope_B_C = find_slope(B,C);
                      if(slope_A_D * slope_B_C == -1)
                                   is_square = true;
        	}
	}
	else if(slope_A_B * slope_C_D == -1)
	{
		double slope_A_C = find_slope(A,C);
		double slope_B_D = find_slope(B,D);
		if(slope_A_C == slope_B_D)
			is_square = true;
	}
	if(is_square)
		cout << "They form a square" << endl;
	else
		cout << "They dont form a square" << endl;

	return 0;
}

- aasshishh March 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step 1 : take any point as the starting point and calculate the distance of the rest three. At least two distance should be equal else return not square.
Step 2. If Step 1 is true, check the square of the distance which is not same is equal to the sum of the remaining two (or twice the square)

Psedo code :

Dist d1, d2, d3;	// double comparison can be a bit tricky
d1 = dist(P1, P2);
d2 = dist(P1, P3);
d3 = dist(P1, P4);

boolean compare (d1, d2, d3)  // true if any two of d is same, else false

if (compare == true)
	d2 (say is the one that is different) 
if (sq(d2) == sq(d1) + sq(d3))
	return isSqaure = true
else 
	false

- raj April 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

(0,0) (0,1)(1,0) (- sqrt(2)) (- sqrt(2)) satisfies ur condition but is not a square if you pick (0,0) as starting point. Only distance is not enough. Angles need to be considered.

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

public class IsSquare {

	static class Point {

		int x;
		int y;

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

	}

	public static double dist(Point p1, Point p2) {

		int x = p1.x - p2.x;
		int y = p1.y - p2.y;

		return Math.hypot(x, y);
	}

	public static void main(String[] args) {

		Point p1 = new Point(1, 1);
		Point p2 = new Point(1, 3);
		Point p3 = new Point(3, 1);
		Point p4 = new Point(3, 3);

		double dist1 = dist(p1, p2);
		double dist2 = dist(p1, p3);
		double dist3 = dist(p1, p4);

		double a, b, c;
		if (dist1 == dist2) {
			a = dist1;
			b = dist2;
			c = dist3;
		} else if (dist1 == dist3) {
			a = dist1;
			b = dist3;
			c = dist2;
		} else if (dist2 == dist3) {
			a = dist2;
			b = dist3;
			c = dist1;
		} else {
			System.out.println("Not square");
			return;
		}
		double d = Math.pow(a, 2) + Math.pow(b, 2);
		double e = Math.pow(c, 2);
		if (Math.abs(d - e) < 0.01) {
			System.out.println("Square");
		} else {
			System.out.println("Not Square");
		}
	}

}

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

1. Check if there are 4 points.
2. Find the distances of the other coordinates to the first coordinate.
3. Find the furthest distance which is the opposite corner and the two equal distances which are the two sides.
4. The two sides should be equal length and the furthest distance should be sqrt(2) * side.

Python version:

def determine_if_square(coords):
	def distance(pair1, pair2):
		return ((pair1[0]-pair2[0])**2 + (pair1[1]-pair2[1])**2)**0.5

	def approx_equal(a, b):
		return abs(a-b) / (abs(a) + abs(b)) * 2 < 0.001

	if len(coords) != 4:
		return False

	selected = coords[0]
	distance_to_selected = [distance(coord, selected) for coord in coords[1:]]

	furthest_distance = max(distance_to_selected)

	adjacent = []
	for i in range(len(distance_to_selected)):
		if distance_to_selected[i] == furthest_distance:
			furthest = i
		else:
			adjacent.append(i)

	if len(adjacent) != 2 or not approx_equal(distance_to_selected[adjacent[0]], distance_to_selected[adjacent[1]]):
		return False

	return approx_equal(furthest_distance, distance_to_selected[adjacent[0]]*(2**0.5))

- yokuyuki June 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def issquare(p):
  if len(a) != 4:
    return False
  return math.sqrt((a[0][0]-a[1][0])**2+(a[0][1]-a[1][1])**2) == math.sqrt((a[2][0]-a[3][0])**2+(a[2][1]-a[3][1])**2)

- harry389 June 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

points = [
[0, 0],
[0, 5],
[5, 0],
[5, 5]
]


def distance(a, b)
Math.sqrt( ( (a[0]-b[0])**2).abs + ((a[1]-b[1])**2).abs )
end

pointA = points[0]
pointB = points[1]
pointC = points[2]
pointD = points[3]

distanceAB = distance(pointA, pointB)
distanceAC = distance(pointA, pointC)
distanceAD = distance(pointA, pointD)

if distanceAB == distanceAC
puts "is a square" if Math.sqrt( (distanceAB**2).abs + (distanceAC**2).abs ) == distanceAD
elsif distanceAB == distanceAD
puts "is a square" if Math.sqrt( (distanceAB**2).abs + (distanceAD**2).abs ) == distanceAC
else
puts "not a square"
end

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

points = [
  [0, 0],
  [0, 5],
  [5, 0],
  [5, 5]
]


def distance(a, b)
  Math.sqrt( ( (a[0]-b[0])**2).abs + ((a[1]-b[1])**2).abs )
end

pointA = points[0]
pointB = points[1]
pointC = points[2]
pointD = points[3]

distanceAB = distance(pointA, pointB)
distanceAC = distance(pointA, pointC)
distanceAD = distance(pointA, pointD)

if distanceAB == distanceAC
  puts "is a square" if Math.sqrt( (distanceAB**2).abs + (distanceAC**2).abs ) == distanceAD
elsif distanceAB == distanceAD
  puts "is a square" if Math.sqrt( (distanceAB**2).abs + (distanceAD**2).abs ) == distanceAC
else
  puts "not a square"
end

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

1. sort by x and then y
2. after sort the first two points should have the same x different y, the last two points should have same x and different y.
3. first and third should have same y, second and fourth should have the same y

- Ben October 20, 2014 | 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