Microsoft Interview Question for Software Engineer in Tests


Country: United States
Interview Type: In-Person




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

/* Consider you have a grid of size m x n. There are stones placed randomly in some of the squares of this grid.
Design a way to find out minimum rectangular area which covers all the stones in this grid. */

/*            WORKING CODE
Input
5 4
0 0 0 0
0 1 0 0
0 0 0 1
1 0 0 0
0 0 0 0

Output:   (1,0), (1,3), (3,0), (3,3)
*/

#include<stdio.h>
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
int main()
{
    int m,n,A[10][10],i,j,i1=10,i2=0,j1=10,j2=0;
    printf("enter m & n (m*n) :");
    scanf("%d %d",&m,&n);
    printf("entet array (place 1 as rock other wise 0 :\n");
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            scanf("%d",&A[i][j]);
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            if(A[i][j]==1)
            {
                i1=MIN(i1,i);
                i2=MAX(i2,i);
                j1=MIN(j1,j);
                j2=MAX(j2,j);
            }
    printf("\n(%d,%d), (%d,%d), (%d,%d), (%d,%d)\n",i1,j1,i1,j2,i2,j1,i2,j2);
return 0;
}

- niraj.nijju July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think this is a right solution. My only proposal for improvement not to do straight forward iterating but go by perimeter: top,left to top,right; top,right to bottom,right; bottom,right to bottom,left and, finally, bottom,left to the top,left. Then just decrease each grid dimension by one and continue iterating.
Improvement here is that we stop exactly at the moment we have processed each side of the target minimum rectangular.

- Aleksey.M May 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

is there any solution better than O(n^2).

- Animesh Sinha July 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think we can improve the run time by not traversing row wise, but on the borders of the grid. Keep min-i, max-i, min-j, max -j as the four variables (as in 1st comment to this problem) and also maintain flags for them. as soon as all the four variables are modified we are done. Once the exterior most border is traversed move on to one level below and so on. The worst case for this will still be O(n^2).

- prawal July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for a m*n matrix, find Min n and Max n also Min m and Max m where the stones are kept.
now get the difference of Max n & Min m , let say l, also difference of Max m and Min m, let say b. so area will be l*b

- Niket July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ public class question1 { public static void main(String[] args) { int[][] arr= new int[10][5]; int minx=-1; int miny=-1; int manx=-1; int many=-1; for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[i].length; j++) { arr[i][j]=0 ; int rad =(int) (12*Math.random()); if(rad==4){ arr[i][j]=1 ; } System.out.print(arr[i][j]+ " "); } System.out.println(" "); } for (int xi = 0; xi < arr.length; xi++) { for (int xj = 0; xj < arr[xi].length; xj++) { if(arr[xi][xj]>0){ System.out.println("i*j "+ xi + "*"+ xj+ " arr[i][j] "+arr[xi][xj]); if (xi<minx || minx==-1) { minx=xi ; System.out.println("mix"+minx); } if (xi>manx || manx==-1) {manx=xi ; System.out.println("manx"+manx); } if (xj<miny || miny==-1) miny=xj ; if (xj>many || many==-1) many=xj ; } } } System.out.println("valueof the system minx + manx+miny+many"+ minx +" "+ manx + " "+ miny+ " "+many); }// ending funcfions } - Ankur Bansal . July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take the min of all x-coordinates, the max of all x-coordinates, the min of all y-coordinates, and the max of all y-coordinates. These values correspond to the edges of the rectangle, ie. if min-x coordinate is -5, then there is a vertical line x=-5.

- pws July 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One more approach:

Lets Find the diagonal co-ordinates of the rectangle. That should be enough to define a rectangle covering all stones.

ALGO: Array M*N
1) Start from (0,0) and move along matrix diagonal.
2) For the first (i,j) if row i or col j contains stone, then (i,j) becomes the first coordinate of the rectangle's diagonal. Stop Here.
3) if row i or col j doesn't contains stone, then set i=i+1 , j=j+1 , GOTO 2)

4) To Find Second coordinate of the rectangle, start from (M-1,N-1), and similar to above, just in this case set i=i-1, j=j-1.

Time Complexity = O(mn)

- Shakes July 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Store the matrix as a sparse matrix. Then O(m+n) solution exists.

- Relic April 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for (row=0; row < n; row++)
      for (col =0 ;  col < n;   col++)
                if a[row][col] == 1  break; // top-row found .. similary do for the bottom-row, left-coloumn and right column (O(M*N)) ;

- Anonymous July 28, 2013 | 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