Google Interview Question: Given the list of points of t... | Glassdoor

Interview Question

Software Engineer Interview(Student Candidate) Mountain View, CA

Given the list of points of the skyline of a city in order

(from East to West) Find the maximal rectangle contained in this skyline. I was asked to write the code. I managed to find the algorithm but was not sufficient.
Tags:
geometry, skyline

9

just google for skyline.

Interview Candidate on Dec 3, 2009
1

@Interview Candidate

Have you found any particularly clear explanations? I'm working on a solution - I'll post it later tonight - but it'd be nice to confirm my understanding. Thanks.

ellemeno on Dec 7, 2009
4

Clear? Well, to be more exact: Given N points on 2-plane: (x1, y1), (x2,y2), ... , (xN, yN) s.t. x1=0, xN= 0 and for all 10,yM &gt; 0. Find the maximum value of the area of a rectangle inside the region bounded by these points and the x-axis. You can assume that the rectangle's edges are going to be parallel to the x,y axes.

Anonymous on Dec 7, 2009
0

Here's an O(n^3) dynamic programming solution. It's pretty ugly, but it seems to work. More elegant/efficient solutions would be greatly appreciated.

--------------------------------------------

import java.util.ArrayList;

public class Skyline {

private int maxX;
private int maxY;

public String[] findLargestRectangle(String[] points){
// First translate the points into a boolean matrix.
// The cell [i][j] in the matrix should be true if
// it appears under the skyline and false otherwise.
boolean[][] cells = this.pointsToMatrix(points);
System.out.println("Matrix is: ");
this.printBooleanMatrix(cells,maxX,maxY);

// Now we calculate rectangle size. Define
// s[i][j] to be the size of the rectangle
// with (i,j) at its upper left corner.
int[][] s = new int[maxX+1][maxY+1];
int maxSizeX = 0;
int maxSizeY = 0;
int maxSize = 0;
for (int i = 0; i maxSize){
maxSize = max;
maxSizeX = i;
maxSizeY = j;
}
}
}
System.out.println("Size matrix is: ");
this.printIntegerMatrix(s,maxX,maxY);
System.out.println("Maximum rectangle has size " + maxSize + ".");
System.out.println("Its upper left corner is (" + maxSizeX + "," + maxSizeY + ").");
return null;
}

// Points to be given as "1 0", "2 5", etc.
private boolean[][] pointsToMatrix(String[] points){
ArrayList list = new ArrayList();

// The maximum x-value will be that of the last point.
maxX = Integer.parseInt(points[points.length-1].split(" "));
maxY = 0;
for (int i = 0; i maxY) maxY = y;
list.add(new Point(x,y)); // Assume there are no duplicates
}
System.out.println("Points are: " + list);
System.out.println(" maxX = " + maxX + ", maxY = " + maxY);
boolean[][] m = new boolean[maxX+1][maxY+1];
int prevX = 0;
int prevY = -1;
for (int k = 0; k 0){
m[x][j] = true;
j--;
}
}
else {
// Look left. If the cell to the left is false, then this cell
// is true (start of rectangle top). The value of the cells below
// is also true.
//
// If the cell to the left is true and the previous point had the same value
// of x, then this cell represents the start of another rectangle. Set its value
// to true and the values of the cells below to true.
if ((! m[x-1][y]) || (prevX == x)){
m[x][y] = true;
while (j &gt; 0){
m[x][j] = true;
j--;
}

// If the previous value of y is the same as this value of y and the
// difference between x values is greater than 1, fill in the cells
// in between.
if (prevY == y &amp;&amp; (x - prevX &gt; 1)){
int i = x-1;
while (i &gt; prevX){
j = y;
while (j &gt; 0){
m[i][j] = true;
j--;
}
i--;
}
}
}
// If the cell to the left is true and the previous point had a different
// value of x, then this cell is false (end of rectangle top). Set it and
// the cells below it to false. This cell may be inside another rectangle,
// in which case its value will be reset to true.
else {
m[x][y] = false;
while (j &gt; 0){
m[x][j] = false;
j--;
}
}
}
prevX = x;
prevY = y;
//System.out.println("After " + p + ", matrix is: ");
//this.printBooleanMatrix(m,maxX,maxY);
}
return m;
}

ellemeno on Dec 7, 2009
0

(cont'd)

private void printIntegerMatrix(int[][] b, int maxX, int maxY){
for (int j = maxY; j &gt;=0; j--){
for (int i = 0; i =0; j--){
for (int i = 0; i &lt;= maxX; i++){
System.out.print(String.format("%8b",b[i][j]));
}
System.out.println();
}
}

class Point implements Comparable{
int x;
int y;

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

public int compareTo(Object o){
Point p = (Point) o;
return (this.x != p.x ? this.x - p.x : this.y - p.y);
}

public boolean equals(Object o){
if (! (o instanceof Point)) return false;
Point p = (Point) o;
return (this.x == p.x &amp;&amp; this.y == p.y);
}

public int hashCode(){
return x*37 + y*19 + x*11 + y*7;
}

public String toString(){
return "(" + x + "," + y + ")";
}
}

/**
* @param args
*/
public static void main(String[] args) {
String[] points = {"0 2","1 2","1 1","2 1","2 3","3 3","3 0"};
Skyline s = new Skyline();
s.findLargestRectangle(points);
System.out.println();
String[] points1 = {"0 1","1 1","1 4","2 4","2 3","3 3","3 6","4 6","5 3","7 3","7 7","8 7"};
s = new Skyline();
s.findLargestRectangle(points1);
}
}

Output:

Points are: [(0,2), (1,2), (1,1), (2,1), (2,3), (3,3), (3,0)]
maxX = 3, maxY = 3
Matrix is:
false false true false
true false true false
true true true false
false false false false
Size matrix is:
0 0 3 0
2 0 2 0
3 2 1 0
0 0 0 0
Maximum rectangle has size 3.
Its upper left corner is (0,1).

Points are: [(0,1), (1,1), (1,4), (2,4), (2,3), (3,3), (3,6), (4,6), (5,3), (7,3), (7,7), (8,7)]
maxX = 8, maxY = 7
Matrix is:
false false false false false false false true false
false false false true false false false true false
false false false true false false false true false
false true false true false false false true false
false true true true false true true true false
false true true true false true true true false
true true true true false true true true false
false false false false false false false false false
Size matrix is:
0 0 0 0 0 0 0 7 0
0 0 0 6 0 0 0 6 0
0 0 0 5 0 0 0 5 0
0 4 0 4 0 0 0 4 0
0 9 6 3 0 9 6 3 0
0 6 4 2 0 6 4 2 0
4 3 2 1 0 3 2 1 0
0 0 0 0 0 0 0 0 0
Maximum rectangle has size 9.
Its upper left corner is (1,3).

ellemeno on Dec 7, 2009
0

Found bug:

public *int* findLargestRectangle(String[] points){
...
*return maxSize*;
}

(obviously)

ellemeno on Dec 7, 2009
1

I don't mean to discourage you but there is no way that you can get away with an answer that works in O(N^3) for this question and even if the interviewer was happy with this performance, it would be impossible for you to write this kind of code given a reasonable time limit for the interview (which is around 45 minutes, and that's the entire interview which includes introduction and possibly some other easy questions) You can solve this in O(N). I don't have time to write a solution right now, I strongly recommend looking at Topcoder's skyline problems and contestants' solutions for an insight.

best of luck to you

Anonymous on Dec 8, 2009
4

For others' reference:

http://www.topcoder.com/stat?c=problem_statement&amp;pm=7473&amp;rd=10661
http://www.topcoder.com/tc?module=Static&amp;d1=match_editorials&amp;d2=srm337
https://www.spoj.pl/problems/HISTOGRA/
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html

ellemeno on Dec 8, 2009
1

Here's a much nicer O(n^2) solution. As Anonymous said, there's an O(n) solution, too.

/*
* In this input array a, the ith building
* has height a[i], which means its lower left
* corner is at (i,0) and its upper right corner
* is at (i+1,a[i]). All buildings have width 1.
* The total width of the skyline is n.
*/
public long getMax(long[] a){
int n = a.length;
int[] leftWidths = new int[n];
int[] rightWidths = new int[n];

// For each building, check how many units width to the left of the
// top block of this building we can move before we are no longer
// in a building.
for (int i = 0; i = 0) &amp;&amp; a[x] &gt;= a[i]) {
x--;
count++;
}
leftWidths[i] = count;
}

// For each building, check how many units width to the right of the
// top block of this building we can move before we are no longer
// in a building.
for (int i = 0; i = a[i]) {
x++;
count++;
}
rightWidths[i] = count;
}

// Now find the maximum rectangle. The value of the ith building's
// rectangle is its horizontal width times its height, or
// (1 + leftWidths[i] + rightWidths[i]) * a[i].
long maxArea = 1;
for (int i = 0; i maxArea) {
maxArea = nextArea;
}
}
return maxArea;
}

ellemeno on Dec 8, 2009
1

O(n) solution:

/*
* Basic idea: use a stack to store the buildings. Look at
* the buildings in left-to-right order (west to east). If a
* building is taller than the building on the top of the stack
* (the tallest building to its left), push it onto
* the stack. If a building is equal in height to the building on the
* top, skip it. If a building is shorter than the building on the top,
* it is not part of the maximum rectangle that is topped by the tallest
* building to its left. Pop that tallest building, calculate its area and
* compare it to the current main area, then repeat the comparison
* procedure with the new tallest building.
*
* Along the way, track the number of buildings to the left and right of a
* given building that would participate in that building's maximum
* rectangle. The number to the left is equal to the number of buildings
* that are popped off the stack before this building is pushed - that is
* the number of buildings to the left of this building that are taller.
* We do not need to worry about the buildings that are equal in height
* since they are discarded (they are accounted for in the topBuilding's
* rightWidth count).
*
* The number of buildings to the right of this building that participate
* in this building's maximum rectangle is equal to the number of buildings
* that are discarded because they are equal to this building's height
* plus the number of buildings that are pushed onto the stack because they
* are taller than this building while this building is on the top of the
* stack.
*
* In this input array a, the ith building has height a[i], which means
* its lower left corner is at (i,0) and its upper right corner is at
* (i+1,a[i]). All buildings have width 1. The total width of the skyline
* is n.
*/
public long getMax_useStack(long[] a){
Stack stack = new Stack();
int n = a.length;
long maxArea = 1;

// Process the buildings in left-to-right order.
for (int i= 0; i &lt; n; i++){
Building nextBuilding = new Building(a[i]);

// Keep track of the number of buildings that we pop before we
// push nextBuilding. That number will be equal to the number
// of buildings to the immediate left of nextBuilding that are
// taller in size.
int popCount = 0;

// If the stack is empty, push the next building onto the stack.
// There are no buildings to its left, so we do not need to
// update nextBuilding.leftWidth.
if (stack.empty()) {
stack.push(nextBuilding);
continue;
}

ellemeno on Dec 8, 2009
1

(cont'd)

// Otherwise, compare the new building's height to the building on
// the top of the stack until the new building is either
// discarded (if it is equal in size) or pushed (if it is taller).
while (! stack.empty()){
Building topBuilding = stack.peek();
long heightDiff= nextBuilding.height - topBuilding.height;

// If the new building is equal in height, skip it. Increment
// the rightWidths count of topBuilding as its largest
// rectangle goes through the new building.
if (heightDiff == 0) {
topBuilding.rightWidth++;
break;
}

// If the new building is greater in height, push it onto the
// stack. The number of buildings to the immediate left of it
// that are taller is equal to the number of buildings that
// were popped before this point, its popCount. Set its
// leftWidth equal to its popCount. Increment the rightWidths
// count of the top building as its largest rectangle goes
// through the new building.
if (heightDiff &gt; 0) {
nextBuilding.leftWidth = popCount;
topBuilding.rightWidth++;
stack.push(nextBuilding);
break;
}

// If the new building is less in height, update the maximum area
// with regards to the element at the top of the stack.
long topArea = topBuilding.getArea();
if (topArea &gt; maxArea){
maxArea = topArea;
}

// Then discard the top element and repeat the comparison
// procedure with the current next building.
stack.pop();
popCount++;
}
}

// If all buildings have been processed and the stack is not yet empty,
// finish the remaining subproblems by updating the maximum area
// with regards to the building at the top of the stack.
while (! stack.empty()){
Building topBuilding = stack.pop();
long topArea = topBuilding.getArea();
if (topArea &gt; maxArea){
maxArea = topArea;
}
}
return maxArea;
}

class Building {
long height;
int leftWidth;
int rightWidth;

Building(long y){
this.height = y;
leftWidth = 0;
rightWidth = 0;
}

long getArea(){
return height * (1 + leftWidth + rightWidth);
}
}

ellemeno on Dec 8, 2009
0

ellemeno,

Nice solution/explanation.
However, maxArea should be initialized to 0.

logimech on Dec 9, 2009
0

@logimech

Right. :) Thanks.

ellemeno on Dec 9, 2009
0

ellemeno:

The program has bug. We need to store the building's x cordinate.

And when the nextbuilding is shorter than the top one, we need to update each popped building's rightwidth as topbuilding.x - nextbuilding.x

tabatabaye on Dec 10, 2009
0

Isnt this the convex hull problem?

Pratyus on Dec 13, 2009
0

The O(n) algorithm does not work. I have another solution for it, however.
Suppose we have the array of heights a of length n. We are looking for the smallest building index (let's say x and divide the problem in 2: the left part ( between 0 and i - 1) and the right part (between i + 1 and n - 1). Then we compute the area that can be build using the building indexed with i: a[i] * (n - 1 - 0 + 1) = n * a[i]. We compare this area with the ones obtained from the left and from the right part and return the result.

Therefore, the complexity will be:
N * time to find the index of the smallest building in a range - which is RMQ problem that can be solved in O(logn) and O(n) preporcessing time (and O(N) space). Therefore, the complexity is O( N log N).

It works for 3 6 5 6 2 4: the solution is 3 * 5 = 15. The problem is known as the biggest rectangle below a histogram.

Victor on Jan 19, 2011
0

An old question with my answer.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SkylineTest
{
class Program
{
static void Main(string[] args)
{

Point[] pointList = new Point{new Point(0, 1)
,new Point(1,1)
,new Point(1,2)
,new Point(2,1)
,new Point(2,2)
,new Point(2,0)
,new Point(4,0)
,new Point(4,6)
,new Point(5,6)
,new Point(5,0)};

Skyline sl = new Skyline(pointList);
Point maxPoint = sl.CalculateMaxRanctangle();

Console.WriteLine("MaxPoint:" + maxPoint.X + " " + maxPoint.Y);
Console.WriteLine("MaxArea:" + sl.MaxArea);
}
}

public struct Point
{
private int _x;
private int _y;

public int X
{
get { return _x; }
}

public int Y
{
get { return _y; }
}

public Point(int x, int y)
{
_x = x;
_y = y;
}
}

public class Skyline
{
private Point[] _pointList;
private int _maxArea=0;
private Point MaxRactanglePoint;

public int MaxArea
{
get { return _maxArea; }
}

public Skyline(Point[] pointList)
{ _pointList = pointList; }

public Point CalculateMaxRanctangle()
{
Point maxPoint = new Point(0, 0);
for (int index = 0; index 2)
{
for (int i = index - 2; i &gt;= 0; i -= 2)
{
if (_pointList[i].Y &gt;= _pointList[index].Y)
areaForPoint += (_pointList[i+2].X - _pointList[i].X) * _pointList[index].Y;
else
break;
}
}
if(index= _pointList[index].Y)
areaForPoint += (_pointList[i].X - _pointList[i-2].X) * _pointList[index].Y;
else
break;
}
if (areaForPoint &gt; _maxArea)
{
_maxArea = areaForPoint;
maxPoint = _pointList[index];
}

index += 2;
}

}
return maxPoint;
}
}

}

C# workout on Sep 10, 2013
2

i dont know if i understand the assignement correctly, but shouldnt ne sufficient to iterate all coorfinates and find min x, min y, max x, max and then calculate the area given by this rectangle?

Anonymous on Jan 21, 2015
0

Hi Guys, there is O(N) solution using STACK.
http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

AT on Oct 11, 2015
0

Psuedocode
//Iterate through points one time where a point further east is greater than a point farther west, a point higher up is greater than a point lower down.
//if x greatestX, greatestX = x
//if y greatestY, greatestY = y
//Equate (greatestX - smallestX) by (greatestY - smallestY)

Dave on Apr 13, 2016
0

For some reason that left out like half of my psuedocode

Dave on Apr 13, 2016