Google Interview Question SDE1s
Country: United States
// 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 , ' ' ) ) }
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
/// information about point illumination.
/// </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);
Console.WriteLine($"Adding lamp at {lamp.X}, {lamp.Y}");
AddLamp(lamp);
}
}
catch(Exception exception)
{
Console.WriteLine($"Caught exception. Details: {0}", exception.ToString());
return false;
}
return true;
}
public void AddLamp(Lamp lamp)
{
Lamps.Add(lamp);
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);
if(!allLamps.TryAddLamps(numLamps, 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 userInputString = Console.ReadLine().Split(',');
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.");
}
}
}
/* 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;
}
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)
resilt.Add(matrix[coor.X, coor.Y]);
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)
{
result.Add(true);
break;
}
}
result.Add(false);
}
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));
}
}
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;
}
}
//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));
}
}
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
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)
import java.util.HashMap;
import java.util.HashSet;
public class GridIllumination
{
public static void main(String args[])
{
int A = 7;
int B[][] = { { 0, 1 }, { 0, 4 }, { 6, 5 }, { 0, 5 }, { 5, 5 }, { 3, 6 }, { 2, 3 }, { 2, 6 }, { 0, 4 },
{ 6, 1 }, { 1, 4 }, { 3, 2 } };
int queries[][] = { { 5, 1 }, { 4, 4 }, { 2, 4 }, { 3, 4 }, { 2, 2 }, { 5, 3 } };
int D[] = solve(A, B, queries);
for (int ele : D)
System.out.println(ele);
}
public static int[] solve(int A, int[][] B, int[][] queries)
{
HashSet<String> lamps = new HashSet<>();
HashMap<Integer, Integer> row = new HashMap<>();
HashMap<Integer, Integer> col = new HashMap<>();
HashMap<Integer, Integer> major = new HashMap<>();
HashMap<Integer, Integer> minor = new HashMap<>();
for (int b[] : B)
{
int x = b[0];
int y = b[1];
lamps.add(x + ":" + y);
}
for (String s : lamps)
{
int x = Integer.parseInt(s.substring(0, s.indexOf(":")));
int y = Integer.parseInt(s.substring(s.indexOf(":") + 1, s.length()));
if (row.containsKey(x))
row.put(x, row.get(x) + 1);
else
row.put(x, 1);
if (col.containsKey(y))
col.put(y, col.get(y) + 1);
else
col.put(y, 1);
if (major.containsKey(x + y))
major.put(x + y, major.get(x + y) + 1);
else
major.put(x + y, 1);
if (minor.containsKey(x - y))
minor.put(x - y, minor.get(x - y) + 1);
else
minor.put(x - y, 1);
}
int D[] = new int[queries.length];
for (int j = 0; j < queries.length; j++)
{
int x = queries[j][0];
int y = queries[j][1];
if (lamps.contains(x + ":" + y))
D[j] = 1;
else if (major.containsKey(x + y) || minor.containsKey(x - y))
D[j] = 1;
else if (row.containsKey(x))
D[j] = 1;
else if (col.containsKey(y))
D[j] = 1;
else
D[j] = 0;
if (lamps.contains(String.valueOf(x) + ":" + String.valueOf(y - 1)))
{
lamps.remove(String.valueOf(x) + ":" + String.valueOf(y - 1));
off(row, x);
off(col, y - 1);
off(major, x + y - 1);
off(minor, x - y + 1);
}
if (lamps.contains(String.valueOf(x) + ":" + String.valueOf(y + 1)))
{
lamps.remove(String.valueOf(x) + ":" + String.valueOf(y + 1));
off(row, x);
off(col, y + 1);
off(major, x + y + 1);
off(minor, x - y - 1);
}
if (lamps.contains(String.valueOf(x + 1) + ":" + String.valueOf(y)))
{
lamps.remove(String.valueOf(x + 1) + ":" + String.valueOf(y));
off(row, x + 1);
off(col, y);
off(major, x + 1 + y);
off(minor, x + 1 - y);
}
if (lamps.contains(String.valueOf(x + 1) + ":" + String.valueOf(y - 1)))
{
lamps.remove(String.valueOf(x + 1) + ":" + String.valueOf(y - 1));
off(row, x + 1);
off(col, y - 1);
off(major, x + 1 + y - 1);
off(minor, x + 1 - y + 1);
}
if (lamps.contains(String.valueOf(x + 1) + ":" + String.valueOf(y + 1)))
{
lamps.remove(String.valueOf(x + 1) + ":" + String.valueOf(y + 1));
off(row, x + 1);
off(col, y + 1);
off(major, x + 1 + y + 1);
off(minor, x + 1 - y - 1);
}
if (lamps.contains(String.valueOf(x - 1) + ":" + String.valueOf(y)))
{
lamps.remove(String.valueOf(x - 1) + ":" + String.valueOf(y));
off(row, x - 1);
off(col, y);
off(major, x - 1 + y);
off(minor, x - 1 - y);
}
if (lamps.contains(String.valueOf(x - 1) + ":" + String.valueOf(y - 1)))
{
lamps.remove(String.valueOf(x - 1) + ":" + String.valueOf(y - 1));
off(row, x - 1);
off(col, y - 1);
off(major, x - 1 + y - 1);
off(minor, x - 1 - y + 1);
}
if (lamps.contains(String.valueOf(x - 1) + ":" + String.valueOf(y + 1)))
{
lamps.remove(String.valueOf(x - 1) + ":" + String.valueOf(y + 1));
off(row, x - 1);
off(col, y + 1);
off(major, x - 1 + y + 1);
off(minor, x - 1 - y - 1);
}
if (lamps.contains(String.valueOf(x) + ":" + String.valueOf(y)))
{
lamps.remove(String.valueOf(x) + ":" + String.valueOf(y));
off(row, x);
off(col, y);
off(major, x + y);
off(minor, x - y);
}
}
return D;
}
public static void off(HashMap<Integer, Integer> map, int num)
{
if (map.containsKey(num))
{
int count = map.get(num);
if (count > 1)
map.put(num, count - 1);
else
map.remove(num);
}
}
}
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.
- libertythecoder October 17, 2016public 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; } }