## Google Interview Question for Software Engineers

• 1
of 1 vote

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 4 vote

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

}
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.

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

Slightly different approach from aonecoding.

``````public class Sample {
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}
}));
}

private static int lonelyPixelCount(int[][] picture) {
int m = picture.length, n = picture[0].length;

int total = 0;
//First traversal sum up the count of black pixels by column if sum > 1 tag column as invalid: -1
for(int j = 0; j < n; j++){
int sum = 0;
for(int i = 0; i < m; i++){
sum += picture[i][j];
}
if (sum > 1) {
for(int i = 0; i < m; i++){
if (picture[i][j] > 0) {
picture[i][j] = -1;
}
}
}
}

for(int i = 0; i < m; i++){
int count = 0;
for(int j = 0; j < n; j++) {
if (picture[i][j] == -1 || count > 1) {
break;
}
if (picture[i][j] > 0) {
count++;
}
}
if (count == 1) {
total++;
}
}

}

}``````

Comment hidden because of low score. Click to expand.
-2

Why did you assume only black pixel can be a lonely pixel.
Your code will output 0 if you replace all existing 0s by 1s and all existing 1s by 0s.

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

Similar approach to guilhebl's solution but without modifying the original image

``````def lonely_pixel():
def count_lonely_pixels(matrix):
rows,total={},0
for r in xrange(len(matrix)):
cnt,lastpixelcol=0,None
for c in xrange(len(matrix[0])):
if matrix[r][c]==1:
cnt+=1
if cnt>1:
break
lastpixelcol=c
if cnt==1:
rows[r]=lastpixelcol
for c in xrange(len(matrix[0])):
cnt,lastpixelrow=0,None
for r in xrange(len(matrix)):
if matrix[r][c]==1:
cnt+=1
if cnt>1:
break
lastpixelrow=r
if cnt==1 and rows.get(lastpixelrow)==c:
total+=1

matrix=[[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]]

print str(count_lonely_pixels(matrix))
lonely_pixel()``````

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

I have tried a recursive approach, i have not compiled it yet

int countAllLonelPix(vector<int> *pix){
count =0;

for(int row=0; row < pix.size();row++){
for(int col = 0; col< pix[i].size(); col++)
{
if(pix[row][col] == 1)
countLonePixel(pix,row, col,count);
count++;
}
}
return count
}

int countLonePixel(vector<color> * pix,int row, int col,count){

if (count > 1) return 0;

count ++;
countLonePixel(pix, i, j-1,count);
countLonePixel(pix, i, j+1,count);
countLonePixel(pix, i-1, j,count);
countLonePixel(pix, i+1, j,count);
}
}

return count;

}

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

I have tried a recursive approach, i didn't compiled the code yet :

``````int countAllLonelPix(vector<int> *pix){
count =0;

for(int row=0; row < pix.size();row++){
for(int col = 0; col< pix[i].size(); col++)
{
if(pix[row][col] == 1)
countLonePixel(pix,row, col,count);
count++;
}
}
return count
}

int countLonePixel(vector<color> * pix,int row, int col,count){

if (count > 1) return 0;

count ++;
countLonePixel(pix, i, j-1,count);
countLonePixel(pix, i, j+1,count);
countLonePixel(pix, i-1, j,count);
countLonePixel(pix, i+1, j,count);
}
}

return count;

}``````

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

``````int countAllLonelPix(vector<int> *pix){
count =0;

for(int row=0; row < pix.size();row++){
for(int col = 0; col< pix[i].size(); col++)
{
if(pix[row][col] == 1)
countLonePixel(pix,row, col,count);
count++;
}
}
return count
}

int countLonePixel(vector<color> * pix,int row, int col,count){

if (count > 1) return 0;

count ++;
countLonePixel(pix, i, j-1,count);
countLonePixel(pix, i, j+1,count);
countLonePixel(pix, i-1, j,count);
countLonePixel(pix, i+1, j,count);
}
}

return count;

}``````

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

fix of few details of my previous solution :), sorry for duplicates it is my first time

``````int countAllLonelPix(vector<int> *pix){
count =0;

for(int row=0; row < pix.size();row++){
for(int col = 0; col< pix[i].size(); col++)
{
if(pix[row][col] == 1)
countLonePixel(pix,row, col,count);
count++;
}
}
return count
}

int countLonePixel(vector<color> * pix,int row, int col,count){

if (count > 1) return 0;

count ++;
if(row < pix.size()-1 && row > 0 && col < pix[row].siz()-1 && col > 0){
countLonePixel(pix, row, col-1,count);
countLonePixel(pix, row, col+1,count);
countLonePixel(pix, row-1, col,count);
countLonePixel(pix, row+1, col,count);
}
}

return count;

}``````

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

Should be wrong, the count make no sense to put into recursive, and I cannot understand what you try to do in the recursive.

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

``````class lonelyPixel:
def __init__(self):
self.matrix = [
[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],
]
self.row = len(self.matrix[0])
self.col = len(self.matrix)

def isNotSameRow(self, row, col, rng):
if rng < 0:
return True
if col != rng and self.matrix[row][col] == self.matrix[row][rng]:
return False
return self.isNotSameRow(row, col, rng - 1)

def isNotSameCol(self, row, col, rng):
if rng < 0:
return True
if row != rng and self.matrix[row][col] == self.matrix[rng][col]:
return False
return self.isNotSameCol(row, col, rng - 1)

def find(self):
for i in range(self.col):
for j in range(self.row):
if self.isNotSameRow(i, j, self.row-1) and self.isNotSameCol(i, j, self.col-1):
print(i, j)

if __name__ == '__main__':
lonely = lonelyPixel()
lonely.find()``````

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

For a m x n matrix

Define arrays RowWhite[size m], RowBlack[size m], ColumnWhite[size n] & ColumnBlack[size n]

Set them intially to 0

Traverse the matrix one by one and for each pixel (i, j), if the pixel is white, update the count of RowWhite[i] & ColumnWhite[j], else update the count of RowBlack[i] & ColumnBlack[j].

Case 1: White Lonely pixels is equal to
The Minimum of number of entries in RowWhite[i] that has a value 1 and the number of entries in ColumnWhite[i] that are 1

Case 2: Black Lonely pixels is equal to
The Minimum of number of entries in RowBalck[i] that has a value 1 and the number of entries in ColumnBlack[i] that are 1.

TimeComplexity O(n^2)

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

create two array rowSum[] and colSum[] to indicate the sum of pixel of current row and col, then loop the rowSum, if current rowSum==1, get the pixel col, and check whether the colSum ==1.

The time complexity is O(m*n) Technically at most loop the all the nodes twice.

``````public class LonelyPixel {
public static int getLonelyPixelCount(int[][] val) {
int[] rowsSum = new int[val.length];
int[] colsSum = new int[val[0].length];
for (int i = 0; i < val.length; i++) {
for (int j = 0; j < val[0].length; j++) {
if (val[i][j] == 1) {
rowsSum[i]++;
colsSum[j]++;
}
}
}
int count = 0;
for (int i = 0; i < rowsSum.length; i++) {
if (rowsSum[i] == 1) {
for (int j = 0; j < colsSum.length; j++) {
if (val[i][j] == 1) {
if (colsSum[j] == 1) {
count++;
break;
}
}
}
}
}
return count;
}

public static void main(String[] args){
int[][] val = 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}
};
System.out.print(getLonelyPixelCount(val));
}

}``````

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

``````#include <vector>
#include <iostream>

using namespace std;

class Pixel {
public:
Pixel(int row, int col) {
this->row = row;
this->col = col;
}
bool operator==(const Pixel& in) const {
return in.col == this->col && in.row == this->row;
}
int row;
int col;
};

int main()
{
vector<vector<int>> pixels = {
{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 }
};

// Keep track of the location of black pixels in rows and columns.
// Then iterate through the list of lonely row and column pixels to see
// if they match.

vector<Pixel> lonelyPixelsFromRows;

for (size_t row = 0; row < pixels.size(); row++) {
int sum = 0;
Pixel temp(-1,-1);
for (size_t col = 0; col < pixels[0].size(); col++) {
if (pixels[row][col] == 1) {
sum++;
if (sum == 1) {
temp = Pixel(row, col);
}
else {
break;
}
}
}
if (sum == 1) {
lonelyPixelsFromRows.push_back(temp);
}
}

vector<Pixel> lonelyPixelsFromCols;

// Create a sum of each column

for (size_t col = 0; col < pixels[0].size(); col++) {
int sum = 0;
Pixel temp(-1, -1);
for (size_t row = 0; row < pixels.size(); row++) {
if (pixels[row][col] == 1) {
sum++;
if (sum == 1) {
temp = Pixel(row, col);
}
else {
break;
}
}
}
if (sum == 1) {
lonelyPixelsFromCols.push_back(temp);
}
}

// We have candidate lonely pixels from rows and cols
// Iterate through each pixel in lonely pixels from rows and locate
// them in the lonely pixels from columns.
// If located, that's truly a lonely pixel.

vector<Pixel> lonely;

for (const Pixel& rowpix : lonelyPixelsFromRows) {
for (const Pixel& colpix : lonelyPixelsFromCols) {
if (rowpix == colpix) {
lonely.push_back(rowpix);
}
}
}

cout << "Lonely pixels are: " << endl;
for (Pixel pix : lonely) {
cout << "(" << pix.row << "," << pix.col << ") ";
}
cout << endl;

}``````

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.