## Amazon Interview Question for SDE1s

Country: United States
Interview Type: Phone Interview

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

Model it as a graph, where each coordinate in the grid has a respective node. You can disconsider the coordinates containing no mine (= 0).

Add edges between neighboring 1s in the grid. After this step, you'll have the grid represented as an disconnected graph. Then, just find the number of graph components by using any graph traversal algorithm, such as DFS.

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

We have to find where the mines are first, don't we?

The example given is not clear.

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

The mines' positions are given in the grid. 1s indicate where mines are present.

But yes, the question is not perfectly worded.

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

That's a pretty good idea but you don't even need to do DFS.
We can do it in time O(mn) without using any excess memory.

We will change values in the original nxm 2d array of integers.
Set each component to a certain number. Then re-scan the grid and print out the indices. You could manipulate the output to be in the correct lines or you could use lists and then do it.

int currentValue = 2;

Scan the grid from the top left to the bottom right and only pay attention to values that have a value > 0.
If the value at the current position == 1 check all the immediately surrounding neighbors. If any of them are a higher value than 1, set the current node's value to this higher value. Otherwise set the current node's value to currentValue and increment currentValue by 1.
Repeat.

Now we have all the clusters with a different number >=2.
All we have to do now is output the data.

The easiest thing to do would be use some memory and add the nodes to lists. But you could also manipulate the output by maybe writing to a file on a certain line based on the cluster number.

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

``````public void printMineRegion(int[][] board) {
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == 1 && !visited[i][j]) {
dfs(board, i, j, visited);
System.out.println();
}
}
}
}

private void dfs(int[][] board, int i, int j, boolean[][] visited) {
visited[i][j] = true;
System.out.print("(" + i + "," + j + ")");
int[] dx = { -1, 1, 0, 0, -1, -1, 1, 1 };
int[] dy = { 0, 0, -1, 1, -1, 1, -1, 1 };
for (int k = 0; k < dx.length; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (x < 0 || x >= board.length || y < 0 || y >= board[0].length
|| board[x][y] == 0 || visited[x][y]) {
continue;
}
System.out.print(",");
dfs(board, x, y, visited);
}
}``````

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

I like this solution, dfs to seach mine cluster.

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

1. Traverse the board left to right, top to bottom.
2. When you find a mine do one of these:
- merge all the clusters the link to this mine into one cluster
- if no cluster links to it create a new cluster

Below is a working C++ implementation

``````#include <iostream>
#include <vector>
#include <set>
#include <utility>

using namespace std;
class Cluster {
private:
set<pair<int, int>> minePoints;

public:
int maxRow();
int maxCol();
void mergeWithCluser(Cluster &c);
void print() {
for (auto p : minePoints) {
cout << " (" << p.first << "," << p.second << ") ";
}
}
Cluster(pair<int, int> p) {
}
};
vector<Cluster> findClusers(vector<vector<bool>> &M) {
vector<Cluster> openClusters;
vector<Cluster> closedClusters;
for (int i = 0; i < M.size(); i++) {
for (int j = 0; j < M[0].size(); j++) {
auto isMine = M[i][j];
vector<Cluster> toMerge;
vector<Cluster> stillOpenClusters;
for (auto c: openClusters) {
if (isMine && c.addPoint({i, j})) {
toMerge.push_back(c);
} else {
if(c.maxCol() >= j ||  c.maxRow() >= i) {
stillOpenClusters.push_back(c);
}
}
}
if (toMerge.size() > 0) {
Cluster combined = toMerge[0];
auto begin = toMerge.begin() + 1;
while (begin != toMerge.end()) {
combined.mergeWithCluser(*begin);
begin++;
}
stillOpenClusters.push_back(combined);
} else {
if(isMine)
stillOpenClusters.push_back(Cluster({i,j}));
}
openClusters = stillOpenClusters;

}
}

for (auto &c : openClusters) {
closedClusters.push_back(c);
}
return closedClusters;
}
linkPoint.insert({p.first + 1, p.second - 1});
linkPoint.insert({p.first + 1, p.second + 1});
minePoints.insert(p);
return true;
}
return false;
}
int Cluster::maxRow() {
int max = -1;
for (auto p : linkPoint) {
if(p.first > max) {
max = p.first;
}
}
return max;
}
int Cluster::maxCol() {
int max = -1;
for (auto p : linkPoint) {
if(p.second > max) {
max = p.second;
}
}
return max;
}
void Cluster::mergeWithCluser(Cluster &c) {
for (auto p : c.minePoints ) {
minePoints.insert(p);
}
for (auto p : c.linkPoint ) {
}
}
int main(int argc, const char * argv[])
{
vector<vector<bool>> M = {{false, true, false, true},{false, false, true, true}, {false, false, false, false}, {true, true, false,false}};
auto res = findClusers(M);
for(auto c : res) {
c.print();
cout << endl;
}
return 0;
}``````

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

O(mn) solution with O(mn) memory usage:

``````public static ArrayList<ArrayList<Point>> getMineClusters(boolean[][] mineField){
if(mineField == null || mineField.length == 0 || mineField[0].length == 0){
return null;
}
ArrayList<ArrayList<Point>> results = new ArrayList<ArrayList<Point>>();
boolean[][] visited = new boolean[mineField.length][mineField[0].length];
for(int i = 0; i < visited.length; i++){
for(int j = 0; j < visited[i].length; j++){
checkMineField(mineField, visited, results, i, j, null);
}
}
return results;
}

private static void checkMineField(boolean[][] mineField, boolean[][] visited, ArrayList<ArrayList<Point>> results, int i, int j, ArrayList<Point> currentCollection){
if(0 > i  || i >= mineField.length || 0 > j || j >= mineField[0].length){
return;
}
if(!visited[i][j]){
visited[i][j] = true;
if(mineField[i][j]){
if(currentCollection == null){
currentCollection = new ArrayList<Point>();
}
checkMineField(mineField, visited, results, i-1, j-1, currentCollection);
checkMineField(mineField, visited, results, i-1, j, currentCollection);
checkMineField(mineField, visited, results, i-1, j+1, currentCollection);
checkMineField(mineField, visited, results, i, j-1, currentCollection);
checkMineField(mineField, visited, results, i, j+1, currentCollection);
checkMineField(mineField, visited, results, i+1, j-1, currentCollection);
checkMineField(mineField, visited, results, i+1, j, currentCollection);
checkMineField(mineField, visited, results, i+1, j+1, currentCollection);
}
}
}``````

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.