Google Interview Question
SDE1sCountry: United States
Worst case time O(n^2). When points are distributed uniformly on the plane, O(n * √n).
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
class Point {
public:
Point(int32_t x, int32_t y)
{
x_ = x;
y_ = y;
}
int32_t x_, y_;
};
uint64_t MaxArea(vector<Point> const &points)
{
uint64_t max_area = 0;
unordered_map<int32_t, vector<int32_t>> y_to_xes;
for (auto &p : points) {
y_to_xes[p.y_].push_back(p.x_);
}
unordered_map<uint64_t, pair<int32_t, int32_t>> x1x2_to_min_max_y;
for (auto &el : y_to_xes) {
int32_t y = el.first;
vector<int32_t> const &xes = el.second;
for (int i = 0; i < xes.size(); ++i) {
for (int j = i + 1; j < xes.size(); ++j) {
int x1 = xes[i];
int x2 = xes[j];
if (x2 < x1) {
swap(x1, x2);
}
int32_t min_y = y;
int32_t max_y = y;
uint64_t key = ((uint64_t)x1 << 32) | x2;
auto it = x1x2_to_min_max_y.find(key);
if (it != x1x2_to_min_max_y.end()) {
min_y = min(min_y, it->second.first);
max_y = max(max_y, it->second.second);
}
x1x2_to_min_max_y[key] = pair<int32_t, int32_t>(min_y, max_y);
max_area = max(max_area, (uint64_t)(x2 - x1) * max(y - min_y, max_y - y));
}
}
}
return max_area;
}
int main()
{
cout << MaxArea({{0,0}, {0,3},{0,6},{2,0},{2,3},{2,6},{5,6},{6,0},{6,4}}) << "\n";
return 0;
}
public static void main(String[] args) {
Point[] points = { new Point(0, 0), new Point(0, 3), new Point(0, 6), new Point(2, 0), new Point(2, 3),
new Point(2, 6), new Point(5, 6), new Point(6, 0), new Point(6, 4) };
int area = -1;
for (int i = 0; i < points.length; i++) {
area = Math.max(area, area(points, points[0], true, false, -1, -1,-1, Integer.MAX_VALUE, Integer.MAX_VALUE));
}
System.out.println(area);
}
public static int area(Point[] points, Point p, boolean matchx, boolean matchy, int l, int b, int area, int x, int y) {
if (matchx && matchy){
boolean r = matchXY(points, l, b, area, x, y);
if(r){
area = Math.max(area, l*b);
}
return area;
}
if (matchx)
area = matchX(points, p, l, b, area, x, y);
if (matchy)
area = matchY(points, p, l, b, area, x, y);
return area;
}
public static int matchX(Point[] points, Point p, int l, int b, int area, int x, int y) {
int n = points.length;
for (int i = 0; i < n; i++) {
Point pn = points[i];
if (pn.x == p.x && pn.y != p.y)
area = area(points, pn, false, true, Math.abs(pn.y - p.y), b, area, x, p.y);
}
return area;
}
public static int matchY(Point[] points, Point p, int l, int b, int area, int x, int y) {
int n = points.length;
for (int i = 0; i < n; i++) {
Point pn = points[i];
if (pn.y == p.y && pn.x != p.x)
area = area(points, pn, true, true, l, Math.abs(pn.x - p.x), area, p.x, y);
}
return area;
}
public static boolean matchXY(Point[] points, int l, int b, int area, int x, int y) {
int n = points.length;
for (int i = 0; i < n; i++) {
Point pn = points[i];
if (pn.x == x && pn.y == y)
return true;
}
return false;
}
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
Java implementation O(n^2) :
package com.cracking.google;
import java.util.ArrayList;
import java.util.HashSet;
public class RectangleFindLargestOptimized {
public static void main(String[] args) {
ArrayList<Point> points = GetMockPoints();
HashSet<Long> points_hash = ConvertIntoSet(points);
Rectangle maxRect = GetLargestRectangle(points, points_hash);
System.out.println(maxRect.toString());
}
public static Rectangle GetLargestRectangle(ArrayList<Point> points, HashSet<Long> points_hash) {
Rectangle maxRectangle = new Rectangle();
for(int i=0; i<points.size()-1; i++) {
Point a = points.get(i);
for(int j=i+1; j<points.size(); j++) {
Point d = points.get(j);
int currArea = Math.abs(d.x - a.x) * Math.abs(d.y - a.y);
long pointB = GetPointKey(d.x, a.y);
long pointC = GetPointKey(a.x, d.y);
boolean containPoints = points_hash.contains(pointB) && points_hash.contains(pointC);
if(currArea > maxRectangle.getArea() && containPoints) {
maxRectangle.SetData(a, new Point(d.x, a.y), new Point(a.x, d.y), d, currArea);
}
}
}
return maxRectangle;
}
public static long GetPointKey(int x, int y) {
return ((long)x<<32)| (long)y;
}
public static class Point {
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int x;
public int y;
@Override
public String toString() {
String msg = String.format("%d,%d", this.x,this.y);
return msg;
}
}
public static class Rectangle {
public Rectangle() {
this.area = 0;
}
public void SetData(Point a,Point b,Point c, Point d, int area) {
this.a = a;
this.b = b;
this.c = c;
this.d = d;
this.area = area;
}
private Point a,b,c,d;
private int area;
public int getArea() {
return this.area;
}
@Override
public String toString() {
String msg = String.format("C(%s)\t\tD(%s)\n\nA(%s)\t\tB(%s)\nArea = %d",
this.c.toString(),
this.d.toString(),
this.a.toString(),
this.b.toString(),
this.area);
return msg;
}
}
public static HashSet<Long> ConvertIntoSet(ArrayList<Point> points) {
HashSet<Long> set = new HashSet<Long>();
for(Point p:points) {
set.add( GetPointKey(p.x, p.y) );
}
return set;
}
public static ArrayList<Point> GetMockPoints() {
ArrayList<Point> points = new ArrayList<Point>();
points.add(new Point(1, 4));
points.add(new Point(2, 4));
points.add(new Point(1, 2));
points.add(new Point(2, 2));
points.add(new Point(3, 4));
points.add(new Point(5, 4));
points.add(new Point(2, 6));
points.add(new Point(2, 1));
points.add(new Point(5, 1));
points.add(new Point(3, 3));
points.add(new Point(5, 3));
return points;
}
}
Output:
C(2,1) D(5,1)
A(2,4) B(5,4)
Area = 9
1. Assumtions:
- coordinates are integers (no floating point)
- forming rectangles means I need the 4 edge points
- parallel to x,y means there is either no difference in x or in y direction between two points adjacent to each other (horizontal or vertical lines)
- points and lines count area 0
2. Put all points into a hashtable with key x << 32 | y
3. for each pair of point check if other edges exist, if so maximize on the area
This is O(n^2), I guess a better runtime is feasible.
in c++ with major overflow issues covered
- Chris November 01, 2017