Morgan Stanley Interview Question
Software AnalystsTeam: Sooftware
Country: India
{{for(int i = 0; i<row;i++){
for(int j =0 ;j<col;j++){
int rowdiff = Math.abs(zeroRow - i);
int coldiff = Math.abs(zeroCol - j);
int total = rowdiff + coldiff;
orgArray[i][j] = total;
System.out.print(total+"\t");;
}
System.out.println("\n");
}
}}
where zeroRow and zeroCol are row and column for element with value 0 and orgArray is any array which will hold the distance value from [zeroRow][zeroColumn]
The thought is bfs with visited flags. Following is code in Java:
package morganStanley;
import java.util.LinkedList;
import java.util.Queue;
class Position{
public int row, col, dis;
public Position(int r, int c, int d){
row = r;
col = c;
dis = d;
}
}
public class DistanceInMatrix {
public static void main(String[] args){
int[][] matrix = {
{-1, 0, -1},
{-1, -1, -1},
{-1, -1, -1}
};
int[][] dis = findMinimumDistanceToNearestZero(matrix);
for(int[] arr : dis){
for(int d : arr) System.out.print(d + " ");
System.out.println();
}
}
public static int[][] findMinimumDistanceToNearestZero(int[][] matrix){
//step 1: initialize
int totalRow = matrix.length, totalCol = matrix[0].length;
int[][] dis = new int[totalRow][totalCol];
boolean[][] vis = new boolean[totalRow][totalCol];
Queue<Position> queue = new LinkedList<Position>();
for(int i = 0; i < totalRow; ++i){
for(int j = 0; j < totalCol; ++j){
if(matrix[i][j] == 0){
dis[i][j] = 0;
vis[i][j] = true;
queue.add(new Position(i, j, 0));
}
}
}
//step 2: BFS
while(!queue.isEmpty()){
Position pos = queue.poll();
for(int i = 0; i < 4; ++i){
int nr = pos.row + MOVE[i][0], nc = pos.col + MOVE[i][1];
if(nr < 0 || nr >= totalRow || nc < 0 || nc >= totalCol) continue;
if(vis[nr][nc]) continue;
dis[nr][nc] = pos.dis + 1;
vis[nr][nc] = true;
queue.add(new Position(nr, nc, dis[nr][nc]));
}
}
return dis;
}
private static int[][] MOVE = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
}
time complexity O(m*n), space complexity O(m*n)
#include<iostream>
#include<stdlib.h>
using namespace std;
int main()
{
int m,n;cin>>m>>n;
int **A=new int*[m];
for(int j=0;j<n;j++)
{
A[j]=new int[n];
}
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>A[i][j];
int *zeroi=new int[m*n];
int *zeroj=new int[m*n];
int k=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
if(A[i][j]==0)
{
zeroi[k]=i;
zeroj[k]=j;
k++;
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
int min=m+n;
for(int z=0;z<k;z++)
{
int dist=( abs(i-zeroi[z])+abs(j-zeroj[z]) );
if(min>dist)
min=dist;
}
A[i][j]=min;
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
cout<<A[i][j]<<" ";
cout<<"\n";
}
}
#include<iostream>
#include<stdlib.h>
using namespace std;
int main()
{
int m,n;cin>>m>>n;
int **A=new int*[m];
for(int j=0;j<n;j++)
{
A[j]=new int[n];
}
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>A[i][j];
int *zeroi=new int[m*n];
int *zeroj=new int[m*n];
int k=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
if(A[i][j]==0)
{
zeroi[k]=i;
zeroj[k]=j;
k++;
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
int min=m+n;
for(int z=0;z<k;z++)
{
int dist=( abs(i-zeroi[z])+abs(j-zeroj[z]) );
if(min>dist)
min=dist;
}
A[i][j]=min;
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
cout<<A[i][j]<<" ";
cout<<"\n";
}
}
check the condition, if we have find the minimum distance as 0 for any node, we don't need to travel the loop any more.
if (min == 0)
break;
#include<iostream>
#include<stdlib.h>
using namespace std;
int main()
{
int m,n;cin>>m>>n;
int **A=new int*[m];
for(int j=0;j<n;j++)
{
A[j]=new int[n];
}
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>A[i][j];
int *zeroi=new int[m*n];
int *zeroj=new int[m*n];
int k=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
if(A[i][j]==0)
{
zeroi[k]=i;
zeroj[k]=j;
k++;
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
int min=m+n;
for(int z=0;z<k;z++)
{
int dist=( abs(i-zeroi[z])+abs(j-zeroj[z]) );
if(min>dist)
min=dist;
if (min == 0)
break;
}
A[i][j]=min;
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
cout<<A[i][j]<<" ";
cout<<"\n";
}
}
O(n^2) solution:
void MatrixDistance(vector<vector<long>>& data, size_t x, size_t y)
{
if (x < data.size() && y < data[0].size()) {
for (size_t i = 0; i < data.size(); i++) {
for (size_t j = 0; j < data[0].size(); j++) {
if (x != i && y != j)
data[i][j] = abs((int)(x - i)) + abs((int)(y - j));
else if (x == i && y != j)
data[i][j] = abs((int)(y - j));
else if (x != i && y == j)
data[i][j] = abs((int)(x - i));
}
}
}
}
#include<stdio.h>
int k ,d[2][100];
int mindis(a,m,n)
{ int i ,fd ,min1 ,min2,min;
if (a==0)
return 0;
else
if(d[0][0]> m) min1=d[0][0]- m;
else min1=m - d[0][0] ;
if(d[1][0]> n) min2=d[1][0]- n;
else min2=n - d[1][0] ;
min = min1+ min2;
for(i=1;i<k; i++)
{ //printf("%d -- %d \n",d[0][0],d[1][0]);
if(d[0][i]> m) min1=d[0][i]- m;
else min1=m - d[0][i] ;
if(d[1][i]> n) min2=d[1][i]- n;
else min2=n - d[1][i] ;
fd = min1+ min2;
if(fd<min)
min=fd;
}
return min;
}
int main()
{ int a[10][10],i,j,m,n;
k=0;
scanf("%d%d",&m,&n);
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
{ scanf("%d",&a[i][j]);
if(a[i][j]==0)
{ d[0][k]=i;
d[1][k]=j;
++k;
}
}
}
////////////////////////
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
//////////////////////
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
{
printf("%d ",mindis(a[i][j],i,j));
}
printf("\n");
}
return 0;
}
#include<stdio.h>
int k ,d[2][100];
int mindis(a,m,n)
{ int i ,fd ,min1 ,min2,min;
if (a==0)
return 0;
else
if(d[0][0]> m) min1=d[0][0]- m;
else min1=m - d[0][0] ;
if(d[1][0]> n) min2=d[1][0]- n;
else min2=n - d[1][0] ;
min = min1+ min2;
for(i=1;i<k; i++)
{ //printf("%d -- %d \n",d[0][0],d[1][0]);
if(d[0][i]> m) min1=d[0][i]- m;
else min1=m - d[0][i] ;
if(d[1][i]> n) min2=d[1][i]- n;
else min2=n - d[1][i] ;
fd = min1+ min2;
if(fd<min)
min=fd;
}
return min;
}
int main()
{ int a[10][10],i,j,m,n;
k=0;
scanf("%d%d",&m,&n);
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
{ scanf("%d",&a[i][j]);
if(a[i][j]==0)
{ d[0][k]=i;
d[1][k]=j;
++k;
}
}
}
////////////////////////
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
//////////////////////
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
{
printf("%d ",mindis(a[i][j],i,j));
}
printf("\n");
}
return 0;
}
1. Get the coordinates of all zeros in the input matrix.
- enzeart August 09, 20142. Populate an output matrix of the same dimensions with all cells initialized with infinity.
3. For each set of zero-coordinates recorded in step 1, iterate through the output matrix and calculate the distance with the following formula:
distance = abs(x_coordinate_of_zero - x) + abs(y_coordinate_of_zero - y)
4. If the calculated distance is less than the recorded minimum, replace the recorded minimum with the calculated distance.
Time complexity:
Where 'n' is the total number of elements in the input matrix, and 'm' is the number of zeros in the input matrix.
1. n
2. n
3. n * m
n + n + (n * m)
Runtime = O(n*m)