## Google Interview Question for SDE1s

Country: United States

Comment hidden because of low score. Click to expand.
5
of 7 vote

This solutions takes O(1) time for query, O(Lamps) time for initializing and O(n) space, being n the size nxn of the grid. It just stores which columns, rows and diagonals are iluminated.

``````public class Lamps{
private boolean[] columns, rows, diagonalsLeft, diagonalsRight;

public Lamps(int size, int[][] lamps){
this.columns = new boolean[size];
this.rows = new boolean[size];
this.diagonalsLeft = new int[(size - 1) * 2 + 1];
this.diagonalsRight = new int[(size - 1) * 2 + 1];

for(int[] lampcoor : lamps){
int x = lampcoor[0];
int y = lampcoor[1];

this.columns[x] = true;
this.rows[y] = true;
this.diagonalsLeft[x + y] = true;
this.diagonalsRight[x - y] = true;
}
}

public boolean query(int x, int y){
if(columns[x] || rows[y] || diagonalsLeft[x + y] || this.diagonalsRight[x - y])
return true;
}

}``````

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

I think this is incorrect in two ways:

1. assignment to `rows` and columns` from `lamps` is incorrect (it doesn't matter for the `query` function though since the read usage is consistent with the write usage)
2. assignment to `diagonalsRight` will result in a negative index when x < y

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

``````// ZoomBA
// preprocessing :: generate the n X n grid
n = 8
// create grid
grid = list ( [0:n] ) -> { list( [0:n] ) -> { 0 } }

// basic function to put the lamp
def put_lamp( x, y ){
fold ( [0:n] ) -> { grid[ x ][ \$.item ] = 1 }
fold ( [0:n] ) -> { grid[ \$.item ][ y ] = 1 }
// left top -> bottom right diagonal
i = x ; j = y
while ( i >= 0 && j >= 0 ) { grid[i][j] = 1 ; i -=1 ; j-=1 ; }
i = x ; j = y
while ( i < n && j < n ) { grid[i][j] = 1 ; i +=1 ; j+=1 ; }
// top right -> bottom left
i = x ; j = y
while ( i >= 0 && j < n ) { grid[i][j] = 1 ; i -=1 ; j+=1 ; }
i = x ; j = y
while ( i < n && j >= 0 ) { grid[i][j] = 1 ; i +=1 ; j-=1 ; }
}

put_lamp ( 5, 1 )
// print the grid
fold ( grid ) -> { printf('%s\n' , str( \$.item , ' ' ) ) }``````

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

Attached a full example in C#. Maybe a bit of an overkill but I was sick today so... Anyways, maybe somebody finds this useful. :-)

``````using System;
using System.Collections.Generic;
namespace Lamps
{

/// <summary>
/// This class will hold the position of lamps in an N x N array and provided
/// </summary>
public class allLamps
{
# region Fields

/// <summary>
/// The "playing field" we use to put lamps into.
/// </summary>
bool[][] fPlayingField;

# endregion

# region Properties

/// <summary>
/// The size of the field we are putting lamps into.
/// </summary>
public int sizeOfField
{
get
{
return fPlayingField.Length;
}
}

/// <summary>
/// The list of lamps we have placed into the field.
/// </summary>
public List<Lamp> Lamps
{
get;
private set;
}

# endregion

# region Construction

public allLamps(int N)
{
// Initialize playing field.
fPlayingField = new bool[N][];
for(int index = 0; index < N; ++index)
{
fPlayingField[index] = new bool[N];
}

// Initialize lamps.
Lamps = new List<Lamp>();
}

# endregion

# region Public Support

public bool TryAddLamps(int numLamps, int arraySize)
{
try
{
Random rnd = new Random();
for(int lampIndex = 0; lampIndex < numLamps; ++lampIndex)
{
int xCoord = rnd.Next(0, arraySize - 1);
int yCoord = rnd.Next(0, arraySize - 1);

Lamp lamp = new Lamp(xCoord, yCoord);
}
}
catch(Exception exception)
{
Console.WriteLine(\$"Caught exception. Details: {0}", exception.ToString());
return false;
}

return true;
}

{

IlluminateFieldFromLamp(lamp);
}

public void IlluminateFieldFromLamp(Lamp lamp)
{
// Update illumination...
// Horizontal left.
Illuminate(lamp.X, lamp.Y, x => x-1, y => y);
// Horizontal right.
Illuminate(lamp.X, lamp.Y, x => x+1, y => y);
// Vertical top.
Illuminate(lamp.X, lamp.Y, x => x, y => y+1);
// Vertical bottom.
Illuminate(lamp.X, lamp.Y, x => x, y => y-1);
// Top left.
Illuminate(lamp.X, lamp.Y, x => x-1, y => y+1);
// Top right.
Illuminate(lamp.X, lamp.Y, x => x+1, y => y+1);
// Bottom left.
Illuminate(lamp.X, lamp.Y, x => x-1, y => y-1);
// Bottom right.
Illuminate(lamp.X, lamp.Y, x => x-1, y => y+1);
}

public void Illuminate(int x, int y, Func<int, int> doActionX, Func<int, int> doActionY)
{
if(x < 0 || y < 0 || x >= sizeOfField || y >= sizeOfField )
{
return;
}
Console.WriteLine(\$"Illuminating {x}, {y}");
fPlayingField[x][y] = true;

Illuminate(doActionX(x), doActionY(y), doActionX, doActionY);
}

public bool isIlluminated(int x, int y)
{
return fPlayingField[x][y];
}

# endregion
}

public class Lamp
{
///<summary>
/// This class represents a lamp.
///</summary>
# region Properties

public int X
{
get;
set;
}

public int Y
{
get;
set;
}

# endregion

# region Construction

///<summary>
/// Construct an instance of a lamp with provided x and y coordinates.
///</summary>
public Lamp(int x, int y)
{
X = x;
Y = y;
}

# endregion

}

public class lamps
{
static void Main()
{
int arraySize = 100;
int numLamps = 3;

Console.WriteLine(\$"Lamp lamp...");
Console.WriteLine(\$"------------");
Console.WriteLine(\$"Will construct a {arraySize} x {arraySize} array of lamps.");

var allLamps = new allLamps(arraySize);
{
Console.WriteLine("Failed to create lamp array. Quitting.");
return;
}

// Keep the console window open in debug mode.
Console.WriteLine("What are the coordinates you want to query for illumination? Expected format is {x}, {y}");

// Do not do fancy user input checks here.
var queriedX = int.Parse(userInputString[0]);
var queriedY = int.Parse(userInputString[1]);

bool isIlluminated = allLamps.isIlluminated(queriedX, queriedY);
string interjection = isIlluminated ? "" : "not ";

Console.WriteLine(\$"Position {queriedX}, {queriedY} is {interjection}illuminated.");
}
}
}``````

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

``````/* Approach
1) makae a bool-field and store for every light the rays.
Simple to code
takes O(N) to insert a light
take O(1) to query light (with very small constant factor)
Need to know size of grid in advance (which is given)
takes O(N*N) space and thus O(N*N) time to initialize

2) Just store which columns and rows are illuminated (e.g. in a set)
Do the same with diagonals, store which diagonals (up and down, looking from the left boarder) are illuminated
takes O(1) to insert light
takes O(1) to query light (with higher constant factor than solution 1)
takes O(1) to initialize field
do not need to know field dimensions

So I choose approach 2

(saw later it matches the exisitng solution...)
*/

#include <unordered_set>
#include <cassert>

class LightGrid
{
private:
std::unordered_set<int> lightRow_;
std::unordered_set<int> lightCol_;
std::unordered_set<int> lightDiagDown_;
std::unordered_set<int> lightDiagUp_;

public:
void placeLight(int col, int row)
{
lightRow_.insert(row);
lightCol_.insert(col);
lightDiagDown_.insert(getDiagonalDownId(col, row));
lightDiagUp_.insert(getDiagonalUpId(col, row));
}

bool checkLight(int col, int row)
{
return lightRow_.find(row) != lightRow_.end() ||
lightCol_.find(col) != lightCol_.end() ||
lightDiagDown_.find(getDiagonalDownId(col, row)) != lightDiagDown_.end() ||
lightDiagUp_.find(getDiagonalUpId(col, row)) != lightDiagUp_.end();
}

private:
inline static int getDiagonalUpId(int col, int row) { return row + col; }
inline static int getDiagonalDownId(int col, int row) { return row - col; }
};

int main()
{
LightGrid grid;

grid.placeLight(1, 1);
grid.placeLight(10, 50);

assert(grid.checkLight(1, 1) == true);
assert(grid.checkLight(1, 999) == true);
assert(grid.checkLight(8812, 1) == true);
assert(grid.checkLight(15, 15) == true);
assert(grid.checkLight(2, -2) == false);
assert(grid.checkLight(10, 22) == true);
assert(grid.checkLight(10, 50) == true);
assert(grid.checkLight(11, 51) == true);
assert(grid.checkLight(8, 48) == true);
assert(grid.checkLight(8, 52) == true);
assert(grid.checkLight(12, 52) == true);
assert(grid.checkLight(12, 48) == true);

std::cout << "passed all" << std::endl;
}``````

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

There are two solutions

Solution 1 is to have a temporary internal matrix and populate it with the lamps queue info (horizontal, vertical and diagonals), we just need to check a given coordinate, for this problem Time O(M) and space O(NxN).

``````foreach (var coor in coordinates)

Solution 2 is for a given coordinate compare with the lamps and do some cells Math, if they are located in the same row, column or diagonal the coordinated is iluminated. Time O(NxM) N = num of lamps M num of coordinates.

``````foreach (var coor in coordinates)
{
foreach (var lamp in lamps)
{
int diffX = Math.Abs(lamp.X - coor.X);
int diffY = Math.Abs(lamp.Y - coor.Y);

if (diffX == 0 || diffY == 0 || diffX == diffY)
{
break;
}
}

}``````

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

First, illuminate the lamps (preprocessing), so that new grid point lookup is constant time O(1).

``````public class LampIlluminationGrid {

private static class Lamp{
private int row;
private int col;

public Lamp(int row, int col){
this.row = row;
this.col = col;
}
}

private boolean[][] grid;

public LampIlluminationGrid(int n, Lamp[] lampsCoordinates){
grid = new boolean[n][n];

for(Lamp lamp : lampsCoordinates){
int targetRow = lamp.row;
int targetCol = lamp.col;

// illuminate row.
for(int c = 0; c < n; c++){
grid[targetRow][c] = true;
}

// illuminate col
for(int r = 0; r < n; r++){
grid[r][targetCol] = true;
}

// illuminate diagonal.
int r = targetRow;
int c = targetCol;
while(r >= 0 && c >=0){
grid[r][c] = true;
r--;
c--;
}
r = targetRow;
c = targetCol;
while(r < n && c < n){
grid[r][c] = true;
r++;
c++;
}

r = targetRow;
c = targetCol;
while(r >= 0 && c < n){
grid[r][c] = true;
r--;
c++;
}

r = targetRow;
c = targetCol;
while (r < n && c >= 0){
grid[r][c] = true;
r++;
c--;
}
}
}

public boolean isGridPointIlluminated(Lamp targetPoint){
if(targetPoint == null || targetPoint.row < 0 || targetPoint.col < 0
|| targetPoint.row >= grid.length || targetPoint.col >= grid.length){
throw new IllegalArgumentException();
}
return grid[targetPoint.row][targetPoint.col];
}

public static void main(String[] args) {
Lamp[] lamps = {new Lamp(2, 1)};
//                , new Lamp(2, 2)};
int N = 5;
LampIlluminationGrid lampIlluminationGrid = new LampIlluminationGrid(N, lamps);

for(int row = 0; row < N; row++){
System.out.println(Arrays.toString(lampIlluminationGrid.grid[row]));
}

Lamp target = new Lamp(0,1);
System.out.println("targetPoint: "+lampIlluminationGrid.isGridPointIlluminated(target));

}

}``````

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

``````public class Lamp {

private boolean[][] matrix;

public Lamp(boolean[][] matrix){
this.matrix = matrix;
}

public boolean isIlluminated(int x, int y){
if(matrix[y][x]){
return true;
}

int len = matrix.length;

for(int i = 0; i < len; i++){
if(matrix[y][i] || matrix[i][x]){
return true;
}

if(y-i >= 0 && x-i >= 0 && matrix[y-i][x-i]){
return true;
}

if(y-i < len && x-i < len && matrix[y+i][x+i]){
return true;
}
}
return false;
}
}``````

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

``````//Assuming that the rest of the question is --when checking a query, all lights that are adjacent or on the same diagonal as a query position will turn off.
//Time O(N^2). Space O (N^2).
public void checkLights(Point[] lamps, int n, Point[] queries){
if(lamps == null || queries == null || lamps.length == 0 || queries.length == 0 || n <= 0){
throw new IllegalArgumentException();
}

boolean[][] board = new boolean[n][n];
int[][][] visited = new int[n][n][8];
for(int i = 0; i < lamps.length; i++){

board[lamps[i].x][lamps[i].y] = true;
}
for(int i = 0; i < queries.length; i++){
System.outprintln(board[queries[i].x][queries[i].y]?"Yes":"No");
for(int i = 0; i < 8; i ++){
dfs(quries[i],m,i,visited);
}

}

}
private boolean dfs(Point q, boolean[][] m, int dir,int[][][] visited){
if(q.x < 0 || q.x == m.length || q.y < 0 || q.y == m[0].length){
return false;
}
if(visited[q.x][q.y][dir] != 0){
return;
}
m[q.x][q.y] = false;
visited[q.x][q.y][dir] = 1;
switch(dir){

case 0:
dfs(new Point(q.x -1, q.y),m,dir,visited);
case 1:
dfs(new Point(q.x + 1, q.y),m,dir,visited);
case 2:
dfs(new Point(q.x,q.y -1),m,dir,visited);
case 3:
dfs(new Point(q.x,q.y + 1),m,dir,visited);
case 4:
dfs(new Point(q.x -1, q.y -1),m,dir,visited);
case 5:
dfs(new Point(q.x - 1, q.y + 1),m, dir,visited);
case 6:
dfs(new Point(q.x + 1, q.y - 1),m, dir, visited);
case 7:
dfs(new Point(q.x + 1, q.y + 1),m,dir,visited));
}
}``````

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

``````lamps = [(0,0), (2,3), (1,5)]
rows = set([i for i, j in lamps])
cols = set([j for i,j in lamps])
pos_diags = set([i + j for i,j in lamps])
neg_diags = set([i - j for i,j in lamps])

points = [(1,1), (8,1), (5,6), (8,9), (9,8)]
for i, j in points:
if i in rows: print True
elif j in cols: print True
elif i + j in pos_diags: print True
elif i - j in neg_diags: print True
else: print False``````

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

The loop body can be simplified to one line with four "or" conditions.

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

``````def solve(n, lamps):
'''Solve the grid illumination problem.

T(n, l) = O(l)
S(n, l) = O(n)
'''
rows = [False for _ in range(n)]
cols = [False for _ in range(n)]
pos_diags = [False for _ in range((2*n)-1)]
neg_diags = [False for _ in range((2*n)-1)]
for i, j in lamps:
rows[i] = True
cols[j] = True
pos_diags[i+j] = True
neg_diags[n-1+i-j] = True
return lambda x, y: rows[x] or cols[y] or pos_diags[x+y] or neg_diags[n-1+x-y]

if __name__ == '__main__':
dim = 6
is_lit = solve(dim, [(0, 0), (2, 3), (1, 5)])

for i in range(dim):
for j in range(dim):
if (i, j) in [(3, 1), (5, 2), (5, 4)]:
assert not is_lit(i, j)
else:
assert is_lit(i, j)

is_lit = solve(dim, [(2, 3), (1, 5)])

for i in range(dim):
for j in range(dim):
if (i, j) in [(0, 0), (0, 2), (3, 0), (3, 1), (4, 0), (4, 4), (5, 2), (5, 4)]:
assert not is_lit(i, j)
else:
assert is_lit(i, j)``````

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.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.