Amazon Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
The mines' positions are given in the grid. 1s indicate where mines are present.
But yes, the question is not perfectly worded.
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.
Start with a counter
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.
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);
}
}
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>> linkPoint;
set<pair<int, int>> minePoints;
public:
int maxRow();
int maxCol();
bool addPoint(pair<int, int> p);
void mergeWithCluser(Cluster &c);
void print() {
for (auto p : minePoints) {
cout << " (" << p.first << "," << p.second << ") ";
}
}
Cluster(pair<int, int> p) {
linkPoint.insert(p);
addPoint(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;
}
bool Cluster::addPoint(pair<int, int> p) {
auto it = linkPoint.find(p);
if (it != linkPoint.end()) {
linkPoint.erase(it);
linkPoint.insert({p.first + 1, p.second});
linkPoint.insert({p.first, p.second + 1});
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 ) {
linkPoint.insert(p);
}
}
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;
}
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>();
results.add(currentCollection);
}
currentCollection.add(new Point(i, j));
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);
}
}
}
Model it as a graph, where each coordinate in the grid has a respective node. You can disconsider the coordinates containing no mine (= 0).
- Victor November 18, 2014Add 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.