Google | Onsite | Apartment Hunting

2901

This question was asked in Google interview.

Assume there is a street of blocks and each block has apartment available to rent out. You're hunting for an apartment in that street and each block has a set of amenities that you want to have easy access to from your new home. Each block has zero or more amenities. How would you pick the block to live in such that the farthest distance to any amenity in your list is minimized?
Example: The blocks array has the list of blocks and respective amenties availability:
blocks = [
{ “gym” : false, “school” : true, “store” : false } ,
{ “gym” : true, “school” : false, “store” : false } ,
{ “gym” : true, “school” : true, “store” : false } ,
{ “gym” : false, “school” : true, “store” : false } ,
{ “gym” : false, “school” : true, “store” : true } ]
requirements = [ “gym”, “school”, “store” ]
Answer: The answer is the third block such that the distance to the gym(G), school(S) and store(St) are 1, 0, 1 respectively. The same distance from other blocks would be:
G S St
Block 0: 1 0 4
Block 1: 0 1 3
Block 2: 0 0 2
Block 3: 1 0 1
Block 4: 2 0 0

Java Solution with time and space complexity: O(mn) where n is number of blocks and m is the number of required amenities.
Explanation: Imagine the blocks are left to right in a street. We traverse the blocks from left to right and keep minimal distance of respective amenity in array dp[n][m+1] where 0 to m-1 is for respective amenity and mth column keep the max distance from the distance of all amenities in that block. For example, if in zeroth block the dp[0]=M 0 M M then it means the distance for gym is M(Max_INT) i.e. no gym here, distance for school is 0 means school is in this block, and similarly no store in this block. The last colums is max(M,0,M) = M and once we populate the array we get this:

Then we traverse backward from n-2 to zeroth row as we would compare with right side block this time while going right to left. We need not start with n-1th row as this is already populated with smallest distance from left side comparison in first round and as there is no right side block it would not make any change. Once we are done and updating the same dp we get:

Now we can see the third block has the smallest value for the last column which is the max distance for any of the amenity if we take apartment in this block. Hence this is the answer.

import java.util.Arrays;
/***
 * blocks = [
 * { “gym” : false, “school” : true, “store” : false } ,
 * { “gym” : true, “school” : false, “store” : false } ,
 * { “gym” : true, “school” : true, “store” : false } ,
 * { “gym” : false, “school” : true, “store” : false } ,
 * { “gym” : false, “school” : true, “store” : true } ]
 *
 * requirements = [ “gym”, “school”, “store” ]
 * Answer: third block.
 */
public class ApartmentHunting {
    private int[][] populateBlocks()
    {
        int[][] blocks = new int[5][3];
        blocks[0] = new int[]{0,1,0};
        blocks[1] = new int[]{1,0,0};
        blocks[2] = new int[]{1,1,0};
        blocks[3] = new int[]{0,1,0};
        blocks[4] = new int[]{0,1,1};
        return blocks;
    }

    private int[][] initiateDp(int blocksCount, int reqsCount) {
        int[][] dp = new int[blocksCount][reqsCount + 1];           // last column would store the distance of the farthest amenity when staying in this block
        int AMENITY_UNAVAILABLE = Integer.MAX_VALUE;
        for (int i=0; i<blocksCount; i++)
            Arrays.fill(dp[i], AMENITY_UNAVAILABLE);
        return dp;
    }

    public int huntAndGetResult(int[] requirements)
    {
        int[][] blocks = populateBlocks();
        int blocksCount = blocks.length, reqsCount = requirements.length, result = Integer.MAX_VALUE;
        int[][] dp = initiateDp(blocksCount, reqsCount);
        int AMENITY_UNAVAILABLE = Integer.MAX_VALUE, AMENITY_AVAILABLE=0;

        for (int j=0; j<reqsCount; j++) {
            if(blocks[0][j] == 1) {
                dp[0][j] = AMENITY_AVAILABLE;   // amenity available so distance 0;
            }
        }

        for(int i=1; i< blocks.length; i++) {
            dp[i][reqsCount] = 0;
            for (int j=0; j<reqsCount; j++) {
                if(blocks[i][j] == 1) {
                    dp[i][j] = AMENITY_AVAILABLE;
                }
                else {
                    if(dp[i-1][j] != AMENITY_UNAVAILABLE)
                        dp[i][j] = Math.min(dp[i][j], dp[i-1][j]+1);
                }
                dp[i][reqsCount] = Math.max(dp[i][reqsCount], dp[i][j]);
            }
        }

        // printArray(dp);
        /*  dp
            M  0  M  M
            0  1  M  M
            0  0  M  M
            1  0  M  M
            2  0  0  2
         */

        for(int i=blocksCount-2; i>=0; i--) {
            dp[i][reqsCount] = 0;
            for(int j=0; j<reqsCount; j++) {
                if(blocks[i][j] == 1) {
                    dp[i][j] = 0;
                }
                else {
                    if(dp[i+1][j] != AMENITY_UNAVAILABLE)
                        dp[i][j] = Math.min(dp[i][j], dp[i+1][j]+1);
                }
                dp[i][reqsCount] = Math.max(dp[i][reqsCount], dp[i][j]);
            }
            result = (dp[i][reqsCount] <= result) ? i : result;
        }
        /*  dp
                1  0  4  4
                0  1  3  3
                0  0  2  2
                1  0  1  1
                2  0  0  2
         */
        // printArray(dp);
        return (result+1);      // Take index of the block as i+1 bcz we started from idx 1.
    }

    private void printArray(int[][] dp) {
        for (int i = 0; i <dp.length; i++) {
            int[] entry = dp[i];
            for (int j = 0; j < entry.length; j++) {
                System.out.print(entry[j] == Integer.MAX_VALUE ? "M" + "  " : entry[j] + "  ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        ApartmentHunting apartmentHunting = new ApartmentHunting();
        int[] requirements = new int[]{0,1,2};
        int result = apartmentHunting.huntAndGetResult(requirements);
        System.out.println("Block: " + result + " is the answer.");
    }
}

Comments (12)