Google Interview Question for Software Engineers


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.

- acoding167 April 22, 2019 | Flag Reply
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;
                    }
                }
            }
        }

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

- guilhebl April 23, 2019 | Flag Reply
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
        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()

- interestingqs April 24, 2019 | Flag Reply
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;

}

- Freewoman April 24, 2019 | Flag Reply
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;
  
}

- Freewoman April 24, 2019 | Flag Reply
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;
  
}

- FreeWoman April 24, 2019 | Flag Reply
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;
  
}

- FreeWoman April 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- flyingforce May 09, 2019 | Flag
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()

- Praveen Pandit April 27, 2019 | Flag Reply
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)

- Ajay Sharma May 06, 2019 | Flag Reply
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));
    }


}

- flyingforce May 09, 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