Twitter Interview Question
Country: United States
Interview Type: Phone Interview
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;
}
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.
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)
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.");
}
}
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;
}
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
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");
}
}
}
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))
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
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
1> You first pick one point p1, and calculate the distance to other three points d12, d13, d14.
- chenlc626 March 24, 20132> 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.