## Google Interview Question for SDE1s

Country: United States

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

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

``````#include <vector>
#include <unordered_set>
#include <iostream>

using namespace std;

using ull = unsigned long long;
constexpr ull key(int x, int y) noexcept {
return static_cast<ull>(x) << 32 | static_cast<unsigned int>(y);
}

ull find_max_area(const vector<pair<int, int>> points) // vector of (x,y)
{
ull max_area = points.size() > 0 ? 1 : 0;
unordered_set<ull> points_ht;
for (auto& p : points) points_ht.insert(key(p.first, p.second)); // could remove doublets here
for (int i = 0; i < points.size() - 1; ++i) {
for (int j = i + 1; j < points.size(); ++j) {
ull area = static_cast<ull>(abs(points[i].first - points[j].first)) // subtraction's can still lead to overflow
* static_cast<ull>(abs(points[i].second - points[j].second));
if (area > max_area
&& points_ht.count(key(points[i].first, points[j].second)) > 0
&& points_ht.count(key(points[j].first, points[i].second)) > 0) {
max_area = area;
}
}
}
return max_area;
}

int main()
{
cout << find_max_area({ {0,0}, {0,3},{0,6},{2,0},{2,3},{2,6},{5,6},{6,0},{6,4} }) << endl; // 12
}``````

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

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;
}``````

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

``````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;
}
}``````

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

@ChrisK. Looks like there is a bug in your code. The result for the given points should be 12, not 21.

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

@ChrisK. Where does 7 come from? :)

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

@ChrisK. If there is a point, and its x = 6, and there is another point with x = 0, the length of the segment is 6 - 0 = 6.

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

@ChrisK. Ok. And what is the length of the rectangle in your picture? Isn't it 6? :)

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

@ChrisK. It's definitely part of the line. But finding an area, we operate on length of segments (width and height of the rectangle). And in case of length of the segment, it's always x2 - x1. Unless you have a new geometry :)

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

@ChrisK. Sure. Private messaging would be cool. Every day I'm waiting for the task to rewrite the engine of the website :)

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

@Alex, I was more thinking in terms of pixels, geometrically correct is your definition. Anyways, remove the 2 time "1 + abs(...)" from the code, it then should return 12 ;-)

nice solution you created!

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

@ChrisK. Yes, if we assume that area is number of points in integer coordinates, then you are right.

Thank you!

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

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) {
}
return set;
}

public static ArrayList<Point> GetMockPoints() {
ArrayList<Point> points = new ArrayList<Point>();

return points;
}

}``````

Output:
C(2,1) D(5,1)

A(2,4) B(5,4)
Area = 9

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

convex hull

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.