## Google Interview Question for Software Engineers

• 0

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

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

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]);
}
}
}``````

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);
}
}
}

}``````

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 )

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

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

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]);
}
}
}``````

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 )``````

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

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

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

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.