Google Interview Question Software Engineers
Country: United States
Interview Type: In-Person
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;
}
}
}
}
//check row discarding invalid columns
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++;
}
}
return total;
}
}
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
return total
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()
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;
}
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;
}
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;
}
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;
}
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()
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)
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));
}
}
#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;
}
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;}
- acoding167 April 22, 2019Looking 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.