## Dropbox Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

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_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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

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.

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