CareerCup

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-TO-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

SOLUTION

//O(N) time and space for processing the board and lamps
//O(1) for finding if a cell is illuminated
public class GridIllumination {

    int N; //board size
    Set<Integer> illuminated_x = new HashSet<>();
    Set<Integer> illuminated_y = new HashSet<>();
    Set<Integer> illuminated_diag0 = new HashSet();
    Set<Integer> illuminated_diag1 = new HashSet();


    //@param lamps - a list of (x,y) locations of lamps
    public GridIllumination(int N, int[][] lamps) {
        this.N = N;
        for(int[] lamp: lamps) { //this lamp illuminates 4 lines of cells
            illuminated_x.add(lamp[0]);               //the entire column
            illuminated_y.add(lamp[1]);               //the entire row
            illuminated_diag0.add(lamp[1] - lamp[0]); //diagonal line with a slope of 1
            illuminated_diag1.add(lamp[0] + lamp[1]); //diagonal lines with a slope of -1
        }
    }

    public boolean is_illuminated(int x, int y) {
        if(illuminated_x.contains(x) ||
            illuminated_y.contains(y) ||
            illuminated_diag0.contains(y - x) ||
            illuminated_diag1.contains(x + y)) {
                return true;
        }
        return false;
    }
}

Thanks a lot for the soln. . But why are we referring the diagonals as y-x and x+y ? Similarly adding diagonals with +1 and -1 slope, you used (lamp[1] - lamp[0]) and (lamp[0] +lamp[1]) ? I am not clear with the diagonal logic?

Thanks a lot for the soln. . But why are we referring the diagonals as y-x and x+y ? Similarly adding diagonals with +1 and -1 slope, you used (lamp[1] - lamp[0]) and (lamp[0] +lamp[1]) ? I am not clear with the diagonal logic?

The solution is totally wrong!!!
I suggest you delete it

Given the query (x, y), we will know in O(1) if there is any light in the horizontal line that passes (0, y) and if there is any light in the vertical line that passes (x, 0).

Basically, we keep two hash sets:
one that has x coordinates where there is at least one light above or below
one that has y coordinates where there is at least one light on the right or left

This might not work intuitively when we see if there is any light in any diagonal direction.. but looks like there's a trick.

We can diagonally project all the rights to the X axis, and use the x coordinate as the key. There are two "diagonal" directions, so we would have two more hash sets.

For each query (x, y), we can simply check if this belongs to any of the four hash sets.
x in S(X)?
y in S(Y)?
x - y in S(Diagonal 1st)?
x + y in S(Diagonal 2nd)?

If anything is true, then it has light. If not, it doesn't.