Interview Question for Software Engineer at Google:

just google for skyline.

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

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 1<= M < N-1 either xM = x{M+1} or yM = y{M+1} and xM < x{M+1}, xM >0,yM > 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.

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 < maxX; i++){
            for (int j = 1; j < maxY+1; j++){
                if (! cells[i][j]) {
                    s[i][j] = 0;
                    continue;
                }
                int maxHSize = 1;
                int maxVSize = 1;
                int i1 = i+1;
                int j1 = j-1;

                // Add one to the maximum horizontal size for
                // each cell that is true towards the right.
                while (cells[i1][j]){
                    i1++;
                    maxHSize++;
                }

                // Add one to the maximum vertical size for each
                // cell that is true towards the bottom.
                while (cells[i][j1]){
                    j1--;
                    maxVSize++;
                }
                int max = maxHSize * maxVSize;
                s[i][j] = max;
                if (max > 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<Point> list = new ArrayList<Point>();

        // The maximum x-value will be that of the last point.
        maxX = Integer.parseInt(points[points.length-1].split(" ")[0]);
        maxY = 0;
        for (int i = 0; i < points.length; i++){
            String[] s = points[i].split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            if (y > 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 < list.size(); k++){
            Point p = list.get(k);
            //System.out.println("Next point: " + p);
            int x = p.x;
            int y = p.y;
            int j = y;

            // If y is zero, ignore the point.
            if (y == 0){
                // Do nothing.
            }
            // If x is zero, this is the first cell. Its value and the value
            // of the cells below it is true.
            else if (x == 0){
                m[x][y] = true;
                while (j > 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 > 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 && (x - prevX > 1)){
                        int i = x-1;
                        while (i > prevX){
                            j = y;
                            while (j > 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 > 0){
                        m[x][j] = false;
                        j--;
                    }
                }
            }
            prevX = x;
            prevY = y;
            //System.out.println("After " + p + ", matrix is: ");
            //this.printBooleanMatrix(m,maxX,maxY);
        }
        return m;
    }

(cont'd)

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

    private void printBooleanMatrix(boolean[][] b, int maxX, int maxY){
        for (int j = maxY; j >=0; j--){
            for (int i = 0; i <= 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 && 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).

Found bug:

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

(obviously)

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

For others' reference:

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

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 < n; i++){
            int x = i-1; // Look left
            int count = 0;

            // Until we have passed the leftmost building and while the
            // height of the next left building is at least as high as our
            // building
            while ((x >= 0) && a[x] >= 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 < n; i++){
            int x = i+1; // Look right
            int count = 0;

            // Until we have passed the rightmost building and while the
            // height of the next right building is at least as high as our
            // building
            while ((x < n) && a[x] >= 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 < n; i++){
            int totalWidth = 1 + leftWidths[i] + rightWidths[i];
            long nextArea = totalWidth * a[i];
            if (nextArea > maxArea) {
                maxArea = nextArea;
            }
        }
        return maxArea;
    }

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<Building> stack = new Stack<Building>();
        int n = a.length;
        long maxArea = 1;

        // Process the buildings in left-to-right order.
        for (int i= 0; i < 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;
            }

(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 > 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 > 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 > 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,

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

@logimech

Right. :) Thanks.

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

Isnt this the convex hull problem?