Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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;
}
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]);
}
}
}
/* 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);
}
}
}
}
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 )
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;
}
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;
}
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]);
}
}
}
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 )
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;
}
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;
}
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;
}
}
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!
- aonecoding September 22, 2017