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
}

- Chris November 01, 2017 | Flag Reply
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;
}

- Alex November 03, 2017 | Flag Reply
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;
		}
	}

- sudip.innovates November 01, 2017 | Flag Reply
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.

- Alex November 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK. Where does 7 come from? :)

- Alex November 04, 2017 | Flag Reply
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.

- Alex November 04, 2017 | Flag Reply
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? :)

- Alex November 04, 2017 | Flag Reply
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 :)

- Alex November 04, 2017 | Flag Reply
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 :)

- Alex November 04, 2017 | Flag Reply
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!

- Chris November 04, 2017 | Flag Reply
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!

- Alex November 04, 2017 | Flag Reply
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) {
			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

- ProTechMulti November 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

convex hull

- afroza.sultana.kakon November 02, 2017 | 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