## Amazon Interview Question for Interns

Country: United States
Interview Type: Phone Interview

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

A pair is valid when a line connects the origin point and the middle point of this pair is also midperpendiculars, so the problem will become finding a line go through origin point and also midperpendiculars of as much as possible pairs.
So we will solve this problem by following below steps:
+ Find all middle of two points have equal distance from origin.
+ Two points is line up if they cotangent is equal, so we will find the maximum number of points have equal cotangent, this is the result

``````public class Point {
public double x;
public double y;

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

// calculate distance without sqrt
public double distance(Point other) {
return (this.x - other.x) * (this.x - other.x) + (this.y - other.y) * (this.y - other.y);
}
}

public int countPairs(Point[] points) {
// create a counter
Map<Double, Integer> counter = new HashMap<Double, Integer>();

int n = points.length;

Point origin = new Point(0.0, 0.0);

for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// get the middle point if point[i] and point[j] have equal distance with origin
if (points[i].distance(origin) == points[j].distance(origin)) {
Point middle = new Point((points[i].x + points[j].x) / 2, (points[i].y + points[j].y) / 2);
double cot = middle.x / middle.y;

if (cot == 1.0) {
int x = 0;
}

int value = 0;
if (counter.containsKey(cot)) {
value = counter.get(cot);
}
counter.put(cot, value + 1);
}
}
}

// finding the maximum middle point have same cotangent value
int answer = 0;
for (double key : counter.keySet()) {
}

}``````

Comment hidden because of low score. Click to expand.
0

How do you justify the complexity is O( n^2 logn)

Comment hidden because of low score. Click to expand.
0

How will you justify the complexity is O(n^2 log n)?

Comment hidden because of low score. Click to expand.
0

Actual my solution has the complexity is O(n^2) because in the worst case there will be n ^ 2 middle points generated and I use a HashMap for counting all cotangent value with cost only O(1).

Comment hidden because of low score. Click to expand.
0

What if you wanted( n^2 log n)

Comment hidden because of low score. Click to expand.
0

If you want the complexity O(n^2 logn), instead of using HashMap, you store all cotangent value in a list and sort this list. After that, using a loop to find the longest continues equal value, this is the answer.

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

Ritika shah can you please explain the question a bit more?

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

Excuse, I have some questions. We can fold many times or only one time? Is it required the folding line must go through the origin or not?

Comment hidden because of low score. Click to expand.
0

Input is this format:
8
-2 1
0 2
0 -1
1 -2
2 0
2 1
1 2
2 2

Output is 3

May be this will help.

Comment hidden because of low score. Click to expand.
0

Thanks you, I'll assume that we can only fold one time and this line must go through the origin.

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

The idea is the following:
1. Create an array of lines between each point
2. Group lines with the same slope
3. For each line in the "same-slope" group
3.1 Create an array of lines between each of the midpoints
3.2 Find the max number of collinear midpoints

Below is implementation in Java

``````import java.util.ArrayList;
import java.util.HashMap;

public class FoldingPlane {

public static void main(String[] args) {
ArrayList<Point> points = new ArrayList<>();
points.add(new Point(0 , 2));
points.add(new Point(2 , 0));
points.add(new Point(2 , 1));
points.add(new Point(1 , 2));
points.add(new Point(2 , 2));

int max = maximumNumberOfPairsWhenFolded(points);

System.out.println("max="+max);
}

static int maximumNumberOfPairsWhenFolded(ArrayList<Point> points) {
// 1. Create an array of lines between each point
ArrayList<Line> lines = constructLinesfromPoints(points);
// 2. Group lines with the same slope
HashMap<Double, ArrayList<Line>> mapFromSlopesToLines = constructMapfromSlopesToLines(lines);

int max = 0;
// 3. For each line in the group
for (ArrayList<Line> slopeLines : mapFromSlopesToLines.values()) {
// 3.1 Create an array of lines between each of the midpoints
ArrayList<Line> linesFromMidPoints = constructLinesfromMidPoints(slopeLines);
// 3.2 Find the max number of collinear midpoints
max = Math.max(max, maxNumberOfCollinearMidPointsInLines(linesFromMidPoints));
}
return max;
}

static ArrayList<Line> constructLinesfromPoints(ArrayList<Point> points) {
ArrayList<Line> result = new ArrayList<>();
for (int i = 0; i < points.size(); i++) {
for (int j = i+1; j < points.size(); j++) {
}
}
return result;
}

static ArrayList<Line> constructLinesfromMidPoints(ArrayList<Line> lines) {
ArrayList<Line> result = new ArrayList<>();
for (int i = 0; i < lines.size(); i++) {
for (int j = i+1; j < lines.size(); j++) {
}
}
return result;
}

static HashMap<Double, ArrayList<Line>> constructMapfromSlopesToLines(ArrayList<Line> lines) {
HashMap<Double, ArrayList<Line>> map = new HashMap<>();
for (Line l : lines) {
ArrayList<Line> slopeLines;
if (map.get(l.slope) == null) { slopeLines = new ArrayList<>(); }
else { slopeLines = map.get(l.slope); }
map.put(l.slope, slopeLines);
}
return map;
}

static int maxNumberOfCollinearMidPointsInLines(ArrayList<Line> linesFromMidPoints) {
HashMap<Double, ArrayList<Line>> map = new HashMap<>();
for (Line l : linesFromMidPoints) {
ArrayList<Line> slopeLines;
if (map.get(l.slope) == null) { slopeLines = new ArrayList<>(); }
else { slopeLines = map.get(l.slope); }
map.put(l.slope, slopeLines);
}
int max = 0;
for (ArrayList<Line> lines : map.values()) {
max = Math.max(max, lines.size());
}
return max;
}

static class Point {
double x;
double y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
public String toString() {
return "("+x+","+y+")";
}
}

static class Line {
double slope;
Point midPoint;
public Line(Point p1, Point p2) {
if (p1.x != p2.x) {
slope = (p2.y - p1.y)/(p2.x - p1.x);
} else {
slope = Double.MAX_VALUE;
}
midPoint = new Point((p1.x + p2.x)/2, (p1.y + p2.y)/2);
}
public String toString() {
return "(sl="+slope+", mp="+midPoint+")";
}
}
}``````

Comment hidden because of low score. Click to expand.
0

How will you justify the complexity is O(n^2 log n)?

Comment hidden because of low score. Click to expand.
0

May be we can also add something along with slope like distance from origin.
It will be easy to make it unique.

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

How will you justify the complexity is O(n^2 log n)?

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

what an irritating question

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.

### 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.