## Microsoft Interview Question for Software Engineer / Developers

• 1
of 1 vote

Team: ICE
Country: India
Interview Type: In-Person

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

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).

Here'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.

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

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.

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

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

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

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.length];
//initialize visitedPond
for(int row=0; row<visitedPond.length; row++)
for(int col=0; col<visitedPond.length; col++)
visitedPond[row][col] = false;

int noOfPonds = 0;
for(int row=0; row<matrix.length; row++){
for(int col=0; col<matrix.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(visited[row][col] == true)
return;

//Check out of bounds
if(row < 0 || row+1 > this.matrix.length || col < 0 || col+1 > this.matrix.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);
}

}``````

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

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

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

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....``````

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

For the first part:

``````bool checkLocation(int x, int y, vector<vector<int> >& matrix){

if(x<0 || x>=matrix.size() || y<0 ||y>=matrix.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.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.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;

}``````

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

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'

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

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)

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

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

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

These reasonings are based on incorrect understanding of the problem. We need to count all "connected" zeros as one pond

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

ABCD

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.