Microsoft Interview Question Software Engineer / Developers
Team: ICE
Country: India
Interview Type: In-Person
Excellent comments.
Just a minor issue on Step 2 and 3. I guess Step 2 is to find the distances from each pond to the rest, therefore the data on Step 3 will have the "star-like" connection.
I believe that this is not correct way because the result of this will not be the global optimal. When consider the distance of i-th pond to the rest of (N-i), the flip of "1" to "0" that we've done on the previous (i-1) ponds have already changed the map of water and island, and the number of ponds from N to (N-i+1). The previous work has to be considered.
Step 2 and Step 3 are to find shortest edges btw each pair. Those steps aren't problematic - not all of those edges will be part of the final solution.
The step 4 - that's where we have a problem.
I think I miscalculated the complexity. I realized that the problem is isomorphic to Rectilinear Steiner Tree. problem. Latter is NP-complete
For the first part of finding number of ponds:
public class Pond {
public static final int WATER = 0;
public static final int LAND = 1;
public int[][] matrix;
public Pond(int [][] matrix){
this.matrix = matrix;
}
public int getNoOfPonds(){
boolean [][]visitedPond = new boolean[this.matrix.length][this.matrix[0].length];
//initialize visitedPond
for(int row=0; row<visitedPond.length; row++)
for(int col=0; col<visitedPond[0].length; col++)
visitedPond[row][col] = false;
int noOfPonds = 0;
for(int row=0; row<matrix.length; row++){
for(int col=0; col<matrix[0].length; col++){
if(matrix[row][col] == WATER && visitedPond[row][col] == false){
noOfPonds++;
traversePond(visitedPond, row, col);
}
}
}
return 0;
}
private void traversePond(boolean [][]visited, int row, int col){
//If already visited
if(visited[row][col] == true)
return;
//Check out of bounds
if(row < 0 || row+1 > this.matrix.length || col < 0 || col+1 > this.matrix[0].length)
return;
//Check if we are on land
if(this.matrix[row][col] == LAND)
return;
visited[row][col] = true;
//left
traversePond(visited, row, col-1);
//right
traversePond(visited, row, col+1);
//bottom
traversePond(visited, row+1, col);
//up
traversePond(visited, row-1, col);
}
}
hello manish,
Consider this the matrix as a graph,Now you know 0 is pond and it is not connected in graph.So first find no of ponds using BFS/DFS,then for two separate pond u have to connect it some how because ur goal is to make a single pond so u have to connect all the ponds .So starting from any pond try DFS and capture the number of element u have remove to connect pond.U have to do this for all possible pond ,and have to maintain a min count for comparison. Once you have encountered all the ponds ,u have the answer for minimum no of replacement.
Good Luck.
For any further query get back
warm Regards
go4gold
Unfortunately, the 2nd part of your solution gives minimum connections between individual pair of ponds but doesn't give you the global minimum (as requested).
First of all you don't have to connect each pair of ponds (minimal spanning tree is enough), and second there could be a configuration of k (k>2) ponds which can be more efficiently connected using star-like (or cross-like) connection, instead of connecting individual pairs.
Consider following example. It shows that globally-optimal solution doesn't always consist of shortest distances between pairs of ponds.
.........
....0000.
00..0..0.
0...0....
0........
000...000
........0
....0...0
.0..0..00
.0000....
For the first part:
bool checkLocation(int x, int y, vector<vector<int> >& matrix){
if(x<0 || x>=matrix.size() || y<0 ||y>=matrix[0].size() || matrix[x][y] != 1) return false;
return true;
}
void bfs(int x, int y, vector<vector<int> >& matrix, int& sum){
if(!checkLocation(x, y, matrix)) return;
int width = matrix[0].size();
deque<int> queue;
queue.push_back(x*width+y);
while(!queue.empty()){
int cur = queue.front();
queue.pop_front();
int idx_x = cur / width;
int idx_y = cur % width;
matrix[idx_x][idx_y] = 2;
if(checkLocation(idx_x-1, idx_y, matrix)){
queue.push_back( (idx_x-1) * width + idx_y );
}
if(checkLocation(idx_x+1, idx_y, matrix)){
queue.push_back( (idx_x+1) * width + idx_y);
}
if(checkLocation(idx_x, idx_y+1, matrix)){
queue.push_back( idx_x * width + idx_y + 1 );
}
if(checkLocation(idx_x, idx_y-1, matrix)){
queue.push_back( idx_x * width + idx_y - 1);
}
}
sum++;
}
int findIslandNum(const vector<vector<int> >& matrix){
vector<vector<int> > cache = matrix;
int sum = 0;
for(int i=0; i< matrix.size(); i++){
for(int j=0; j<matrix[0].size();j++){
bfs(i, j, cache, sum);
}
}
return sum;
}
void islandWaterTest(){
vector<vector<int> > matrix {{1,0,0,1,0},{1,0,0,0,0},{1,1,1,1,0},{0,0,1,1,1}};
cout << findIslandNum(matrix) <<endl;
}
Solution in Javascript using disjoint set linked lists, can be upgraded to disjoint set forests for faster Find operations. This one optimizes merge operations.
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'
//Read Input, preformatting
var reformat = input.split(/\n/);
var N = reformat[0];
var adjMatrix = [];
for (var i = 1; i < reformat.length; i++) {
adjMatrix.push(reformat[i]);
}
//for (each person x from 1 to N) CREATE-SET(x)
var sets = [];
for (var i = 0; i < N; i++) {
var s = new LinkedList();
s.add(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++){
if (isFriend(adjMatrix,potentialFriends[i]) === 'Y'){
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][0];
var y = friends[i][1];
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;
}
function LinkedList(){
this.head = null;
this.tail = null;
this.size = 0;
// Add node to the end
this.add = function(data){
var node = new Node();
node.data = data;
if (this.head == null){
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
};
this.contains = function(data) {
if (this.head.data === data)
return this;
var next = this.head.next;
while (next !== null) {
if (next.data === data) {
return this;
}
next = next.next;
}
return null;
};
this.traverse = function() {
var current = this.head;
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 current = this.head;
var next = current.next;
while (next !== null) {
current = next;
next = next.next;
}
current.next = list.head;
this.size += list.size;
return this;
};
this.reverse = function() {
if (this.head == null)
return;
if (this.head.next == null)
return;
var currentNode = this.head;
var nextNode = this.head.next;
var prevNode = this.head;
this.head.next = null;
while (nextNode != null) {
currentNode = nextNode;
nextNode = currentNode.next;
currentNode.next = prevNode;
prevNode = currentNode;
}
this.head = 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) {
var listC = new LinkedList();
listA.merge(listB);
listC = listA;
return listC;
}
//access matrix by i,j -> returns 'Y' or 'N'
function isFriend(matrix, pair){
return matrix[pair[0]].charAt(pair[1]);
}
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++) {
head = set.slice(i, i+1);
tailcombs = k_combinations(set.slice(i + 1), k - 1);
for (j = 0; j < tailcombs.length; j++) {
combs.push(head.concat(tailcombs[j]));
}
}
return combs;
}
Use DFS here
A[N,M] is the input matrix
C[N,M] is color matrix, whose C[i,j] = -1 for all at the begining.
MaxPondSize = 0;
MaxPondColor = -1
PondStartingColor = 0;
TotalPondSize = 0
For i = 1 to N
For j = 1 to M
IF A[i,j] = 1 and C[i,j] < 0
Start DFS with this node as Starting Node with Final Color as PondStartingColor instead of Black, return FinishTime/2 as pondSize
PondStartingColor = PondStartingColor + 1;
if MaxPondSize < pondSize
MaxPondSize = pondSize
TotalPondSize = TotalPondSize + pondSize
end
end
end
PondStartingColor is the count of number of ponds on the given area.
MaxPondSize is the size of maximum pond and MaxPondColor is the color of that pond,
we can print its location as well.
Number of changes need to have one pond : TotalPondSize-MaxPondSize.
Tomake one pond, we just change the numbers to 0 for all the places whose color is not MaxPondColor
Complexity :
Time : O(N*M)
Space : O(N*M)
First one:
Check for Zero in the matrix and whether it is surrounded by 1's.
M[i][j] ==0 && M[i+1][j] == 1 && M[i-1][j] == 1 && M[i-1]j-1] == 1 && M[i+1][j+1] == 0 && M[i][j-1] == 0 && M[i][j+1] ==0. // Ofcourse take care of corner cases such as edges etc
Second one: As per my understanding, if it takes one change from 1 to zero, then changes required to make 1 pond: (#no of ponds -1 ) provided #noOfPonds > 1
I noticed, that the only allowed change is to change 1 into 0 which makes the remaining part of the problem simpler (e.g. we can only connect ponds).
- 0xF4 December 17, 2014Here's the sketch of an algorithm:
1)
Finding ponds in NxN matrix is trivial - O(N^2) time with BFS traversal for finding connected components.
2)
Next step is to add all points which belong to the edges of all ponds to the queue [we can do this as a part of step 1] and continue running BFS extending all ponds until we fill all the matrix. We'll end up with regions similar to what we see on voronoi diagram with manhattan distance metric. This will require O(N^2) time.
3)
What's nice about the resulting data - the boundaries of computed areas give us all possible shortest connections between each pair of ponds including "star-like" connections between N ponds.
Based on that we can compute the graph where nodes are ponds and edges are connections between ponds. Graph might contain fake nodes for star-like connections. The weight of the edge - is number of changes (manhattan distance metric).
4)
Then we run a minimal spanning tree algorithm on the computed graph which will give us the minimal connections. The spanning tree search should be slightly modified to exclude fake nodes from tracking, so they aren't constrained to be part of the resulting tree.
----
Time complexity O(N^2 + P^2) where P is number of ponds.
Any other ideas? I personally don't like my solution - sounds too complicated as for interview problem. Please criticize and suggest alternatives.