Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for private lessons by FB, Google and Uber engineers

Our ONE TO ONE class offers

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

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

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

public static void main(String[] args) {
        System.out.println(lonelyPixelCount(new int[][]{ //1: black, 0: white
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
        }));
    }

    static int lonelyPixelCount(int[][] picture) {
        int m = picture.length, n = picture[0].length;
        //First traversal sum up the count of black pixels by column
        for(int i = 1; i < m; i++){
            for(int j = 0; j < n; j++){
                picture[i][j] += picture[i - 1][j];
            }
        }
        int result = 0;
        //Then traverse row by row from the bottom, count the black pixels in current row.
        //If there is only 1 black pixel in current row, verify whether it is also the only in the column.
        for(int i = m - 1; i >= 0; i--) {
            int pixel_count_in_row = 0;
            boolean only_pixel_in_column = false;
            for(int j = n - 1; j >= 0; j--) {
                if(picture[i][j] > 0 && (i == 0 || picture[i - 1][j] + 1 == picture[i][j])) {	//verify if current cell number is a black pixel, by method in blue text above
                    pixel_count_in_row++;
                    if((i < m - 1 && picture[i + 1][j] == 1) || (i == m - 1 && picture[i][j] == 1)) {
                        only_pixel_in_column = true;
                    }
                }
                if(i < m - 1) {
                    //overwrite current cell with the number below it
                    picture[i][j] = picture[i + 1][j];
                }
            }
            if(pixel_count_in_row == 1 && only_pixel_in_column) {
                result++;
            }
        }
        return result;
    }

- aonecoding September 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static void main(String[] args) {
        System.out.println(lonelyPixelCount(new int[][]{ //0: black, 1: white
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
        }));
    }

    static int lonelyPixelCount(int[][] picture) {
        int n = picture.length;
        int m = picture[0].length;
        int[] row = new int[n];
        int[] column = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                row[i] += picture[i][j];
                column[j] += picture[i][j];
            }
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            if(row[i]!=1) continue;
            for (int j = 0; j < m; j++) {
                if (column[j] == 1 && picture[i][j] == 1){
                    result++;
                    break;
                }
            }
        }

        return result;
    }

- devsaki September 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

A solution with O(nm) that travel through the pixels "p" which has dimensions w x h.

void findLonelyPixels(int[] p, int w, int h) {
      
        int rowPixels[] = new int[h];
        int columnPixels[] = new int[w];
        
        for (int x = 0;x < w;x++)
            columnPixels[x] = -1;
        
        int i = 0;
        for (int y = 0;y < h;y++) {
            rowPixels[y] = -1;
            for (int x = 0;x < w;x++,i++) {
                if (p[i] != 0) {
                    rowPixels[y] = rowPixels[y] < 0 ? x : -1;
                    columnPixels[x] = columnPixels[x] < 0 ? y : -1;
                }
            }
        }

        for (int y = 0;y < h;y++) {
            int x = rowPixels[y];
            if (x >= 0 && columnPixels[x] >= 0) {
                System.out.println("Lonely pixel: " + x + "," + columnPixels[x]);
            }
        }
    }

- juha October 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* For each row and each column, first count number of white pixels.
    Print out those pixels that have value 1 and also their rows and column
    counts =1
     */
    static void findLonely(int[][] pixels) {
        final int ROWS = pixels.length;
        final int COLS = pixels[0].length;
        int[] r = new int[ROWS];
        int[] c = new int[COLS];
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                if (1 == pixels[i][j]) {
                    r[i]++;
                    c[j]++;
                }
            }
        }
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                if (pixels[i][j] == 1 && r[i] == 1 && c[j] == 1) {
                    System.out.printf("lonely pixel at %d %d %n", i, j);
                }
            }
        }


    }

- Makarand September 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1/N = lonely row
1/M = lonely column

lonelyPixels = 0;

foreach row
__if (lonely row)
____foreach column
______if (pixel @ row x column == black && lonely column)
________lonelyPixels++


( checking for a lonely row implies averaging the values of the row and if it's equivalent to 1/N // N-1/N then there's only one pixel off )

- DesmondWeindorf September 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time O(mn), space O(1), but the input gets destroyed.
First it checks if the first row contains a lonely pixel. Then, the first row is used for storing a flag per column. The flag indicates if the column contains a lonely pixel.

bool LonelyInColumn(vector<vector<bool>> const &m, int c)
{
	bool lonely = false;
	for (int r = 0; r < m.size(); ++r) {
		if (m[r][c]) {
			lonely = !lonely;
			if (!lonely) {
				break;
			}
		}
	}
	return lonely;
}

int LonelyPixelsCount(vector<vector<bool>> &m)
{
	int count = 0;
	if (!m.empty() &&
		!m[0].empty())
	{
		bool lonely = false;
		for (int c = 0; c < m[0].size(); ++c) {
			if (m[0][c]) {
				lonely = !lonely && LonelyInColumn(m, c);
				if (!lonely) {
					break;
				}
			}
		}
		if (lonely) {
			++count;
		}
		for (int c = 0; c < m[0].size(); ++c) {
			m[0][c] = LonelyInColumn(m, c);
		}
		for (int r = 1; r < m.size(); ++r) {
			bool lonely = false;
			for (int c = 0; c < m[0].size(); ++c) {
				if (m[r][c]) {
					lonely = !lonely && m[0][c];
					if (!lonely) {
						break;
					}
				}
			}
			if (lonely) {
				++count;
			}
		}
	}
	return count;
}

- Alex September 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I've just realized that overwriting input doesn't actually give us any difference in terms of O.
The code below is O(mn) (for each row we scan a column only once) time, O(1) space, the input is not destroyed.

bool LonelyInColumn(vector<vector<bool>> const &m, int c)
{
	bool lonely = false;
	for (int r = 0; r < m.size(); ++r) {
		if (m[r][c]) {
			lonely = !lonely;
			if (!lonely) {
				break;
			}
		}
	}
	return lonely;
}

int LonelyPixelsCount(vector<vector<bool>> const &m)
{
	int count = 0;
	if (!m.empty() &&
		!m[0].empty())
	{
		for (int r = 0; r < m.size(); ++r) {
			bool lonely = false;
			for (int c = 0; c < m[0].size(); ++c) {
				if (m[r][c]) {
					lonely = !lonely && LonelyInColumn(m, c);
					if (!lonely) {
						break;
					}
				}
			}
			if (lonely) {
				++count;
			}
		}
	}
	return count;
}

- Alex September 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple O(nm) solution that goes through the pixels "p" which with dimension w x h.

static void findLonelyPixels(int[] p, int w, int h) {
      
        int rowPixels[] = new int[h];
        int columnPixels[] = new int[w];
        
        for (int x = 0;x < w;x++)
            columnPixels[x] = -1;
        
        int i = 0;
        for (int y = 0;y < h;y++) {
            rowPixels[y] = -1;
            for (int x = 0;x < w;x++,i++) {
                if (p[i] != 0) {
                    rowPixels[y] = rowPixels[y] < 0 ? x : -1;
                    columnPixels[x] = columnPixels[x] < 0 ? y : -1;
                }
            }
        }

        for (int y = 0;y < h;y++) {
            int x = rowPixels[y];
            if (x >= 0 && columnPixels[x] >= 0) {
                System.out.println("Lonely pixel: " + x + "," + columnPixels[x]);
            }
        }
    }

- juha October 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If a black pixel has the value 1 and white pixel has the value 0, a O(mn) solution is:

BLACK = 1
WHITE = 0

def numLonleyBlackPixels( image ):
    numColumns = len( image )
    numRows = len( image[0] )
    columnSums = { }
    rowsSums = {}

    count = 0
    for i in range( numColumns ):
        columnSums[i] = [ 0, -1 ]
        for j in range( numRows ):

            if not rowsSums.has_key( j ):
                rowsSums[j] = 0

            columnSums[i][0] += image[i][j]
            if( image[i][j] == BLACK ):
                columnSums[i][1] = j
            rowsSums[j] += image[i][j]
    for i in range( numColumns ):
        if columnSums[i][0] == 1 and rowsSums[columnSums[i][1]] == 1:
            count += 1

    return count


if __name__ == "__main__":
    image = [ [ 0, 0, 0, 1 ], [ 0, 1, 0, 0 ], [ 0, 0, 0, 1 ], [ 0, 0, 0, 0 ] ]
    print numLonleyBlackPixels( image )

    image = [ [ 1, 1, 1, 1 ], [ 0, 1, 0, 0 ], [ 1, 0, 0, 0 ], [ 0 ,0, 0, 1 ] ]
    print numLonleyBlackPixels( image )

- TGoofnik October 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Projecting the black pixel counts column-wise in C++98.

#include <vector>
#include <iostream>

using namespace std;

#define N 10
#define M 10
#define BLACK 1
#define WHITE 0

vector<pair<int, int> > findLonelyPixels(vector<vector<int> > image){
	vector<pair<int, int> > count_index_array = vector<pair<int, int> >(M);
	for(int j = 0; j < M; j++){
		count_index_array[j] = make_pair(0, -1);
	}
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if(image[i][j] == BLACK){
				count_index_array[j].first++;
				count_index_array[j].second = i;
			}
		}
	}
	vector<pair<int, int> > lonely_pixels = vector<pair<int, int> >();
	for(int j = 0; j < M; j++){
		if(count_index_array[j].first == 1)
			lonely_pixels.push_back(make_pair(count_index_array[j].second, j));
	}
	return lonely_pixels;
}

void display(vector<pair<int, int> > pairs){
	for(int i = 0; i < pairs.size(); i++){
		cout << pairs[i].first << ", " << pairs[i].second << endl;
	}
}

int main(){
	vector<vector<int> > image = vector<vector<int> >(N);
	for(int i = 0; i < N; i++){
		image[i] = vector<int>(M);
		for(int j = 0; j < M; j++){
			image[i][j] = WHITE;
		}
	}
	image[3][3] = 1;
	image[4][3] = 1;
	image[5][5] = 1;
	vector<pair<int, int> > lonely_pixels = findLonelyPixels(image);
	display(lonely_pixels);
	return 0;
}

- Alireza October 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node {
        int row;
        int col;

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

    public static Map<Integer, Node> getLonelyPixel(int[][] image) {
        LonelyPixel pixel = new LonelyPixel();
        int[] rowOcurr = new int[image.length];
        int[] colOcurr = new int[image[0].length];
        HashMap<Integer, Node> blackRow = new HashMap<>();
        HashMap<Integer, Node> blackCol = new HashMap<>();

        for(int r = 0; r < image.length; r++) {
            for (int c = 0; c < image[r].length; c++) {
                if (image[r][c] == 1) {
                    if (rowOcurr[r] == 0 && colOcurr[c] == 0) {
                        blackRow.put(r, pixel.new Node(r, c));
                        blackCol.put(c, pixel.new Node(r, c));
                    } else {
                        Node node = blackRow.get(r);
                        blackCol.remove(c);
                        blackRow.remove(r);
                        if (node != null)
                            blackCol.remove(node.col);
                    }
                    rowOcurr[r] += 1;
                    colOcurr[c] += 1;
                }
            }
        }

        return blackCol;
    }

- TeoJunior November 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my solution! I hope it helps!

package sandbox;

public class Sandbox {

	public static void main(String[] args) {
		int[][] matrix = new int[][] { 
			{ 1, 0, 1, 0 }, 
			{ 0, 1, 0, 0 }, 
			{ 1, 0, 0, 0 } 
		};
		System.out.println("# lonely pixels: " + findLonelyPixel(1, matrix));
	}

	public static int findLonelyPixel(int pixelColor, int[][] matrix) {
		int total = 0;
		final int N = matrix.length; // size of row
		final int M = matrix[0].length; // size of column

		int[] rowCount = new int[N]; // index is row #, value is # of occurrences
		int[] colCount = new int[M]; // index is column #, value is # of occurrences

		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				if (matrix[i][j] == pixelColor) {
					++rowCount[i]; // Mark an occurrence for that row
					++colCount[j]; // Mark an occurrence for that column
				}
			}
		}
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				/*
				 * If we are currently at a black pixel and there is only 1 pixel in that
				 * row and column, then we know this is a lonely black pixel.
				 */
				if (matrix[i][j] == pixelColor && rowCount[i] == pixelColor && colCount[j] == pixelColor) {
					++total;
				}
			}
		}
		return total;
	}
}

- Logan April 24, 2019 | 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