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.

- Victor November 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

The example given is not clear.

- ninhnnsoc November 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

But yes, the question is not perfectly worded.

- Victor November 18, 2014 | Flag
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.

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.

- Markymark November 20, 2014 | Flag
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);
		}
	}

- Anonymous November 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I like this solution, dfs to seach mine cluster.

- suwei19870312 November 18, 2014 | Flag
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>> 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;
}

- Mhret November 18, 2014 | Flag Reply
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>();
				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);
		}
	}
}

- zortlord November 19, 2014 | 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