Google Interview Question for SDE1s


Country: United States




Comment hidden because of low score. Click to expand.
4
of 4 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;
	}


}

- libertythecoder October 17, 2016 | Flag Reply
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 , ' ' ) ) }

- NoOne October 16, 2016 | Flag Reply
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
/// 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.");       
        }
    }    
}

- diskuss October 18, 2016 | Flag Reply
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;
}

- ChrisK October 21, 2016 | Flag Reply
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)
	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);
}

- hnatsu October 24, 2016 | Flag Reply
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));

    }

}

- jsayyy October 30, 2016 | Flag Reply
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;
    }
}

- JosephEl November 08, 2016 | Flag Reply
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));
	}
}

- divm01986 November 17, 2016 | Flag Reply
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

- Nitish Garg December 26, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

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.

Learn More

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.

Learn More