## Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: In-Person

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

``````public class Solution {
public static void main(String[] args) {

int[][] A = new int;

int cnt = 0;
int cur_cnt = 0;

for(int x=0; x<A.length; x++) {
for(int y=0; y<A[x].length; y++) {
A[x][y] = (int) Math.round(Math.random());
}
}

for(int x=0; x<A.length; x++) {
for(int y=0; y<A[x].length; y++) {
if (A[x][y] == 1) {
cur_cnt = 0;
cnt = cnt + clean_block(A,x,y, cur_cnt);
}
}
}

System.out.println(cnt);
}

public static int clean_block(int[][] A, int x_in, int y_in, int cur_cnt) {
A[x_in][y_in] = 0;
if (coordinate_exists(x_in-1,y_in  , A.length, A.length) == 1 && A[x_in-1][y_in  ] == 1) {clean_block(A,x_in-1,y_in  ,cur_cnt); cur_cnt = 1;}
if (coordinate_exists(x_in+1,y_in  , A.length, A.length) == 1 && A[x_in+1][y_in  ] == 1) {clean_block(A,x_in+1,y_in  ,cur_cnt); cur_cnt = 1;}
if (coordinate_exists(x_in  ,y_in-1, A.length, A.length) == 1 && A[x_in  ][y_in-1] == 1) {clean_block(A,x_in  ,y_in-1,cur_cnt); cur_cnt = 1;}
if (coordinate_exists(x_in  ,y_in+1, A.length, A.length) == 1 && A[x_in  ][y_in+1] == 1) {clean_block(A,x_in  ,y_in+1,cur_cnt); cur_cnt = 1;}

return cur_cnt;
}

public static int coordinate_exists(int x_in, int y_in, int A_x_length, int A_y_length) {
if (x_in >= 0 && x_in <= (A_x_length-1) && y_in >= 0 && y_in <= (A_y_length-1)) {
return 1;
}
else
{
return 0;
}
}
}``````

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

This is what is known as floodfill, an application of DFS. For each element in the array that is a 1 you attempt to recursively search all 4 neighbors for 1s, the search continues till you either hit the boundaries or see 0s. Also as and when you find 1s you make them 0s so that they are not counted again. Repeat this search for every element
Code

``````public static int countIslands(int[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int result = 0;
for (int i=0; i<matrix.length; i++) {
for (int j=0; j<matrix[i].length; j++) {
if (matrix[i][j] == 1) {
result++;
doFill(matrix, i, j);
}
}
}
return result;
}
public static void doFill(int[][] matrix, int row, int col) {
if (row < 0 || col < 0 || row >= matrix.length || col >=matrix.length || matrix[row][col] == 0) {
return;
}
matrix[row][col] = 0;
int dr[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};
for (int i=0; i<dr.length; i++) {
doFill(matrix, row + dr[i], col + dc[i]);
}
}``````

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

To make this work for extremely large matrices, you would replace recursion with an explicitly maintained stack or queue (rather than using the recursion stack). Instead of recursing you would add candidates to this data structure and keep popping them off and processing them till the stack is empty

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

can you please explain a little more on the explicitly maintained stack and how would it be more efficient than the recursive stack? is it just because the recursive stack will maintain local variables at each recursion?

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

What is the time complexity?

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

For every element in array check 2 things:
1. whether it is a 1?
2. whether the element just above it or just behind is 1?
If answer to step 1 is true and step 2 is False increase the count else continue.

Complexity O(n2).

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

Similar to grassfire algorithm.
could go through the matrix from left top and check if the value is 1, then call grass fire algorithm to recursively find adjacent 1s. remember to be more efficient put a flag on each node that is visited.
in this case run time would be o(n + m) which n is the number of elements in matrix and m is the number of 1s. in the worst case o(2n) which is linear

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

One could have a collection of Groups, each Group containing a set of [x,y] points.
scan from top-left by rows, visiting each cell only once.
when you find a 1 at [x,y], see if Points [x-1,y] or [x, y-1] belong to any existing group,
if so, add [x,y] to that group;
if the two query points belong to two different groups, then merge those two groups.
if the new point [x,y] is not adjacent to an existing group, start a new group to contain it.

In a single scan of the matrix (visit/evaluate each cell only once)
you get the collection of [disjoint] groups, each with a set of adjacent point.
The space complexity is proportional to the number of 1s in the matrix,
the time complexity depends on the layout, but worst case you are looking up the 1s in each of the disjoint groups, so O(n*g) for n 1s in g Groups.
If you have a large sparse-matrix representation, this is quite efficient.

[i also used this algorithm for analyzing a Go board...]

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

``````/*	Ref: en.wikipedia.org/wiki/Flood_fill, youtube.com/watch?v=kV-l8Gnwtkk
* 		 geeksforgeeks.org/find-number-of-islands/
*/
int rowMax;int colMax;
//boolean visited[][]= null;
public int countIslands(int[][] arr, int m, int n){
boolean visited[][] = new boolean[m][n];
rowMax = m; colMax=n;
for(int i =0; i<=m; i++){ //make a boolean array to mark the visited cell
for(int j =0; j<=m; j++){
visited[i][j]= false;
}
}
int count =0; //cluster count
for(int i =0; i<=m; i++){
for(int j =0; j<=m; j++){
if(arr[i][j] == 1 && ! visited[i][j]){// cell value =1 and cell not visited
traverseDFS(arr, i, j, visited); //completes a patch / cluster / island / fill a shape recursively
++count;
}
}
}
return count;

}
class Grid{
int x;	int y;
public Grid(int x, int y) {
this.x =x; this.y=y;
}
}
public Map<Integer,List<Grid>> getAllIlands(int[][] arr, int m, int n){
boolean visited[][] = new boolean[m][n];
rowMax = m; colMax=n;
for(int i =0; i<=m; i++){ //make a boolean array to mark the visited cell
for(int j =0; j<=m; j++){
visited[i][j]= false;
}
}
int clusterId =0; //cluster count
List<Grid> cluster = new ArrayList<Grid>();
Map<Integer,List<Grid>> map = new HashMap<Integer,List<Grid>>();
for(int i =0; i<=m; i++){
for(int j =0; j<=m; j++){
if(arr[i][j] == 1 && ! visited[i][j]){// cell value =1 and cell not visited
traverseDFS(arr, i, j, visited, cluster); //completes a patch / cluster / island / fill a shape recursively
++clusterId;
map.put(clusterId, cluster);
cluster = new ArrayList<Grid>();
}
}
}
return map;

}
// To go for {8 - fill} or {4-fill} as per situation
private void traverseDFS(int[][] arr, int i, int j, boolean[][] visited,
List<Grid> cluster) {
int dx[] = {-1, -1, -1,  0, 0,  1, 1, 1}; // 0 <= |x-x'| <= 1
int dy[] = {-1,  0,  1, -1, 1, -1, 0, 1}; // 0 <= |y-y'| <= 1
visited[i][j]= true;
for(int k= 0; k<8; k++){
if(canVisit(arr, i+dx[k], j+dy[k], visited)){
traverseDFS(arr, i+dx[k], j+dy[k], visited, cluster) ;
}
}

}
// reduce the number of arguments - recursion is heavy
private void traverseDFS(int[][] arr, int i, int j, boolean[][] visited) {
int dx[] = {-1, -1, -1,  0, 0,  1, 1, 1}; // 0 <= |x-x'| <= 1
int dy[] = {-1,  0,  1, -1, 1, -1, 0, 1}; // 0 <= |y-y'| <= 1
visited[i][j]= true;
for(int k= 0; k<8; k++){
if(canVisit(arr, i+dx[k], j+dy[k], visited)){
traverseDFS(arr, i+dx[k], j+dy[k], visited) ;
}
}
}

private boolean canVisit(int[][] arr, int i, int j, boolean[][] visited) {
return (i >= 0) && (i < rowMax) && // row number is in range
(j >= 0) && (j < colMax) && // column number is in range
((arr[i][j]==1) && !visited[i][j]); // value is 1 and not yet visited
}``````

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

Javascript implementation using disjoint set with linked lists

``````var input = '5\nYYNNN\nYYYNN\nNYYNN\nNNNYN\nNNNNY'
console.log(input);
//above solution should be 3 because the components are
//{0,1,2}, because {0,1} and {1,2} therefore {0,1,2}
//{3}
//{4}

//MIT license, authored by Ling Qing Meng

//'4\nYYNN\nYYYN\nNYYN\nNNNY'

var reformat = input.split(/\n/);
var N = reformat;
for (var i = 1; i < reformat.length; i++) {
}

//for (each person x from 1 to N) CREATE-SET(x)
var sets = [];
for (var i = 0; i < N; i++) {
sets.push(s);
}

//populate friend potentials using combinatorics, then filters
var people =  [];
var friends = [];
for (var i = 0; i < N; i++) {
people.push(i);
}
var potentialFriends = k_combinations(people,2);
for (var i = 0; i < potentialFriends.length; i++){
friends.push(potentialFriends[i]);
}
}

//for (each pair of friends (x y) ) if (FIND-SET(x) != FIND-SET(y)) MERGE-SETS(x, y)
for (var i = 0; i < friends.length; i++) {
var x = friends[i];
var y = friends[i];
if (FindSet(x) != FindSet(y)) {
sets.push(MergeSet(x,y));
}
}

for (var i = 0; i < sets.length; i++) {
//sets[i].traverse();
}
console.log('How many distinct connected components?',sets.length);

//Linked List data structures neccesary for above to work
function Node(){
this.data = null;
this.next = null;
}

this.tail = null;
this.size = 0;

// Add node to the end
var node = new Node();
node.data = data;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
};

this.contains = function(data) {
return this;
while (next !== null) {
if (next.data === data) {
return this;
}
next = next.next;
}
return null;
};

this.traverse = function() {
var toPrint = '';
while (current !== null) {
//callback.call(this, current); put callback as an argument to top function
toPrint += current.data.toString() + ' ';
current = current.next;
}
console.log('list data: ',toPrint);
}

this.merge = function(list) {
var next = current.next;
while (next !== null) {
current = next;
next = next.next;
}
this.size += list.size;
return this;
};

this.reverse = function() {
return;
return;

while (nextNode != null) {
currentNode = nextNode;
nextNode = currentNode.next;
currentNode.next = prevNode;
prevNode = currentNode;
}
return this;
}

}

/**
* GENERAL HELPER FUNCTIONS
*/

function FindSet(x) {
for (var i = 0; i < sets.length; i++){
if (sets[i].contains(x) != null) {
return sets[i].contains(x);
}
}
return null;
}

function MergeSet(x,y) {
var listA,listB;
for (var i = 0; i < sets.length; i++){
if (sets[i].contains(x) != null) {
listA = sets[i].contains(x);
sets.splice(i,1);
}
}
for (var i = 0; i < sets.length; i++) {
if (sets[i].contains(y) != null) {
listB = sets[i].contains(y);
sets.splice(i,1);
}
}
var res = MergeLists(listA,listB);
return res;

}

function MergeLists(listA, listB) {
listA.merge(listB);
listC = listA;
return listC;
}

//access matrix by i,j -> returns 'Y' or 'N'
function isFriend(matrix, pair){
return matrix[pair].charAt(pair);
}

function k_combinations(set, k) {
var i, j, combs, head, tailcombs;
if (k > set.length || k <= 0) {
return [];
}
if (k == set.length) {
return [set];
}
if (k == 1) {
combs = [];
for (i = 0; i < set.length; i++) {
combs.push([set[i]]);
}
return combs;
}
// Assert {1 < k < set.length}
combs = [];
for (i = 0; i < set.length - k + 1; i++) {
tailcombs = k_combinations(set.slice(i + 1), k - 1);
for (j = 0; j < tailcombs.length; j++) {
}
}
return combs;
}``````

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

``````public class MatrixClass {

public static void main(String[] args) {
int[][] arr = new int[][] {
{1,1,0,1},
{1,1,1,0},
{1,1,0,0},
{1,1,0,0}
};
checkMatrix(arr);
}

public static void checkMatrix(int[][] matrix) {
int row  = matrix.length;
int col = matrix.length;
int count_1s = 0;
int count_0s = 0;

for(int i=0; i<row; i++)
{
int temp = matrix[i];
int count=0;

for(int j=0; j<col; j++) {
if(temp == matrix[i][j]) {
count++;
}
}
if(count == col && temp == 1) {
count_1s++;
} else if(count == col && temp == 0) {
count_0s++;
}
}

for(int i=0; i<col; i++)
{
int temp = matrix[i];
int count=0;

for(int j=0; j<row; j++) {
if(temp == matrix[j][i]) {
count++;

}
}
if(count == row && temp == 1) {
count_1s++;
} else if(count == row && temp == 0) {
count_0s++;
}
}

System.out.println("O's: " + count_0s + " , 1's: " + count_1s);
}
}``````

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

It works but can someone tell me if its a good way to work around the solution. Thanks..

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

I solved through DFS approach

``````public class NumberOfGroupOf_1 {
public static int row =0;
public static int col =0;
public static void main(String[] args) {
int matrix[][]=  new int[][]{
{1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}
};
row = matrix.length;
col = matrix.length;
boolean [][] visited= new boolean[row][col];
System.out.println(groupOfOne(matrix, visited));
}
private static int groupOfOne(int [][] matrix, boolean [][] visited){
int groupOfOne =0;
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
if(matrix[i][j]==1 && !visited[i][j]){
dfs(matrix, i, j, visited);
groupOfOne++;
}
}
}
return groupOfOne;
}
private static void dfs(int [][]matrix, int i, int j,  boolean [][] visited){
int rowNbr[] = new int[] {-1,  0,  0,  1};
int colNbr[] = new int[] { 0, -1,  1,  0};
visited[i][j] = true;
for(int k=0; k<4; k++){
int x = rowNbr[k]+i;
int y = colNbr[k]+j;
if(isSafe(matrix, visited, x, y)){
dfs(matrix, x, y, visited);
}
}
}
private static boolean isSafe(int [][] matrix, boolean [][] visited, int i, int j){
if((i>=0 && i<col) && (j>=0 && j<row) && !visited[i][j] && matrix[i][j]==1){
return true;
}else {
return false;
}
}
}``````

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

int main() {
int m,n;
int a ;
bool found = false;

cout << " m & n :" ;
cin>>m >>n;

cout<<" Enter matrix elements : ";
for (int i = 0; i < m; i++) {
for (int j = 0 ; j < n ; j++) {
cin>>a[i][j];
}
}

int xiter [] = { 1, 0 , -1 ,0 };
int yiter [] = { 0, 1 , 0 ,-1 };

int island_count = 0;

for (int i=1 ; i < m -1; i++)
for (int j = 1; j < n-1; j++)
if (a[i][j] == 1) {
found = true;
for (int k =0 ; k < 4; k++) {
int x = i + xiter[k];
int y = j + yiter[k];
if (a[x][y] != 0) {
found = false;
break;
}
}
if (found) {
cout << "Island found at "<<i <<", "<<j<<endl;
}
}

// Count number of islands - 1 surrounded by 0

for (int i =0 ; i < m; i++)
for (int j = 0; j < n; j++) {
if (a[i][j] == 1) {
bool island = true;
a[i][j] = 2;
for (int k = 0; k < 4; k++) {
int x = i+ xiter[k];
int y = j + yiter[k];
if (x < 0 || y < 0 || x >=m || y>= n)
continue;
if (a[x][y] == 1) {
a[x][y] = 2;
} else if (a[x][y] == 2) {
island = false;
}
}
if (island)
island_count++;
}
}
cout << " Number of islands : " <<island_count <<endl;

return 0;
}

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

C++ Implementation:

#include <iostream>
using namespace std;

int main() {
int m,n;
int a ;
bool found = false;

cout << " m & n :" ;
cin>>m >>n;

cout<<" Enter matrix elements : ";
for (int i = 0; i < m; i++) {
for (int j = 0 ; j < n ; j++) {
cin>>a[i][j];
}
}

int xiter [] = { 1, 0 , -1 ,0 };
int yiter [] = { 0, 1 , 0 ,-1 };

int island_count = 0;

// Count number of islands -
for (int i =0 ; i < m; i++)
for (int j = 0; j < n; j++) {
if (a[i][j] == 1) {
bool island = true;
a[i][j] = 2;
for (int k = 0; k < 4; k++) {
int x = i+ xiter[k];
int y = j + yiter[k];
if (x < 0 || y < 0 || x >=m || y>= n)
continue;
if (a[x][y] == 1) {
a[x][y] = 2;
} else if (a[x][y] == 2) {
island = false;
}
}
if (island)
island_count++;
}
}
cout << " Number of islands : " <<island_count <<endl;

return 0;
}

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

int main() {
int m,n;
int a ;
bool found = false;

cout << " m & n :" ;
cin>>m >>n;

cout<<" Enter matrix elements : ";
for (int i = 0; i < m; i++) {
for (int j = 0 ; j < n ; j++) {
cin>>a[i][j];
}
}

int xiter [] = { 1, 0 , -1 ,0 };
int yiter [] = { 0, 1 , 0 ,-1 };

bool** land = new bool*[m];
for (int i=0; i < n; i++ )
land[i] = new bool[n];

for (int i = 0; i < m ; i++)
for (int j = 0; j < n; j++)
land[i] [j] = false;

int island_count = 0;
for (int i =0 ; i < m; i++)
for (int j = 0; j < n; j++) {
if (a[i][j] == 1 && !land[i][j]) {
bool island = true;
land[i][j] = true;
for (int k = 0; k < 4; k++) {
int x = i+ xiter[k];
int y = j + yiter[k];
if (x < 0 || y < 0 || x >=m || y>= n)
continue;
if (a[x][y] == 1) {
if (land[x][y]) {
island = false;
} else {
land[x][y] = true;
}
}
}
if (island)
island_count++;
}
}

cout << " Number of islands : " <<island_count <<endl;
Return 0;
}

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

``````import java.util.Scanner;

//6 5
//1 1 1 0 0
//1 1 1 0 0
//1 1 1 0 0
//0 0 0 1 1
//0 0 1 0 1
//1 1 0 1 0
//5
//
//2 2
//1 0
//0 1
//2

public class 在01矩阵中找到1块 {
public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int m = sc.nextInt();
int n = sc.nextInt();
int[][] a = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = sc.nextInt();
}
}
System.out.println(count(a));
}
sc.close();
}

private static int count(int[][] arr) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
count += (mark(arr, i, j) >= 1) ? 1 : 0;
}
}
return count;
}

private static int mark(int[][] arr, int i, int j) {
int count = 0;
if (i >= 0 && j >= 0 && i < arr.length && j < arr[i].length && arr[i][j] == 1) {
count++;
arr[i][j] = -1;
count += mark(arr, i + 1, j);
count += mark(arr, i - 1, j);
count += mark(arr, i, j + 1);
count += mark(arr, i, j - 1);
}
return count;
}
}``````

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

``````matrix = [
[0, 0, 1, 0, 0, 1],
[0, 0, 1, 0, 0, 1],
[0, 1, 1, 1, 0, 1],
[0, 0, 1, 0, 0, 1],
]

# first, convert the 1/0 matrix into an adjacency matrix represented by a map
graph = {}

def get_key(row, column):

return f'a{row}{column}'

for row in range(0, len(matrix)):
for column in range(0, len(matrix)):
key = get_key(row, column)
if key not in graph:
graph[key] = []
if column < len(matrix) - 1 and matrix[row][column] == 1 and matrix[row][column + 1] == 1:
graph[key].append(get_key(row, column+1))
if column >= 1 and matrix[row][column] == 1 and matrix[row][column - 1] == 1:
graph[key].append(get_key(row, column - 1))
if row < len(matrix) - 1 and matrix[row][column] == 1 and matrix[row+1][column] == 1:
graph[key].append(get_key(row+1, column))
if row >= 1 and matrix[row][column] == 1 and matrix[row-1][column] == 1:
graph[key].append(get_key(row-1, column))

print(graph)

visited = set() # Set to keep track of visited nodes.

# You can also use BFS, too.
def dfs(visited, graph, node):
if node not in visited:
print (node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)

# counting the connected components
counter = 0
for node in graph.keys():
if node not in visited and len(graph[node]) > 0:
counter += 1
print(f"connected_component: #{counter}")
dfs(visited, graph, node)``````

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.