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()) {
        answer = Math.max(answer, counter.get(key));
    }

    return answer;
}

- techinterviewquestion.com February 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 12, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ritikashah017 February 12, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- techinterviewquestion.com February 13, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if you wanted( n^2 log n)

- ritikashah017 February 13, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- techinterviewquestion.com February 13, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Asif Garhi February 18, 2016 | Flag Reply
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?

- techinterviewquestion.com February 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ritikashah017 February 12, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- techinterviewquestion.com February 12, 2016 | Flag
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(-2, 1));
		points.add(new Point(0 , 2));
		points.add(new Point(0 ,-1));
		points.add(new Point(1 ,-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++) {
				result.add(new Line(points.get(i), points.get(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++) {
				result.add(new Line(lines.get(i).midPoint, lines.get(j).midPoint));
			}
		}
		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); }
			slopeLines.add(l);
			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); }
			slopeLines.add(l);
			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+")";
		}
	}
}

- ikoryf February 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ritikashah017 February 12, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- raghu.aok February 13, 2016 | Flag
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)?

- ritikashah017 February 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what an irritating question

- Brock August 12, 2016 | 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