Microsoft Interview Question for Software Engineer in Tests


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
4
of 8 vote

I hope this will be helpful. It has time complexity O(k.num_rows) and space complexity O(num_cols)

Basically I find the minimum element k times. And for finding minimum element we just need to check the first (unscanned) element of each row. And then increment it accordingly.
min stores the minimum element.
minOfRows[i] stores the index (i.e column) of row i which is the first unscanned or rather minimum element of that row.
For eg: a[3][4]={{2,5,6,10},{4,8,9,12},{7,15,20,22}};
minOfRows = 0 for all rows.
For 1st iteration:
min = 2 (1st element of the matrix is minimum and last element (bottom right) is the maximum)
minOfRows[0] is incremented by 1;
For 2nd iteration:
We check minimum from among minOfRows[j] column element for each row j. and update min and minOfRows accordingly.

int min = a[0][0];
int minOfRows[rows];
for(i = 0;i < rows;i++)
	minOfRows[i] = 0;
minOfRows[0] = 1;	
for(i = 1;i < k;i++){
	min = INT_MAX;
	for(j = 0;j < rows; j++){
		if(minOfRows[j] < cols){
			if(a[j][minOfRows[j]] < min){
				min = a[j][minOfRows[j]];
				r = j;
			}	
		}		
	}
	minOfRows[r]++;	
}

- artemis October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Okay..here is another one..in O(k.x) time and O(k+x) space.
where x = k in worst case, but in average case , x will be of order O(1).

The idea is to traverse the matrix in such a way that we encounter kth element directly.

a.) Maintain two sets Set A and Set B.
Initially, set A = { NULL }, Set B = {NULL}
Set A == elements which we have seen till now.
Set B == neighbours of the elements of Set A,in sorted order using insertion sort.

b.) Set A = {a[0][0]} , Set B = { Neighbours of a[0][0], i.e a[0][1] , a[1][0] } ;

c.) if sizeof(set A) == k ), return kth element from Set A.

d.) else move minimum(Set B) to set A .

e.) Insert neighbours ( neighbours(a[x][y]) = {a[x][y+1] ,a[x+1][y],a[x-1][y],a[x][y-1]) of minimum(Set B) to Set B[use insertion sort]. As Set B will be of small size, you can assume that insertion sort will be fast and will do the ordering in O(1) time.

In the above example:
Set A Set B
{NULL } {NULL}
{2} {4,5}
{2,4} {5,6,7}
{2,4,5} {6,7,8}
{2,4,5,6} {7,8,15}
{2,4,5,6,7} {8,15}
Here...k == 5 , so stop and return 5th element of Set A i.e, '7'

- Dharam November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how to do this arrays if three arrays are given?

- abhishek.92k January 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

find min at 0,0 then adjust the matrix by moving all the row elements or columns then repeat the same for k times.

- deepak October 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void getkthMin(int kth)
{
	int a[3][4] = {{2,5,8,10}, {4,7,9,12}, {6,15,20,22}};

	// The smallest item is located at a[0][0]
	// For given a a[x][y], the succeding item will be in one of the following numbers:
	// a[x-1][y+1] if (a[x-1][y+1] < a[x][y]) then increase the column until a bigger number is reached.
	// a[x][y+1]
	// a[x+1][y]
	// a[x+1][y-1] if (a[x+1][y-1] < a[x][y]) then increase the row until a bigger number is reached.

	if (kth == 1)
	{
		std::cout<<"The "<<kth<<"th smallest number is "<<a[0][0];
	}
	else
	{
		int counter = 1;
		int x = 0;
		int y = 0;

		while (counter < kth)
		{
			int a1 = INT_MAX;
			int a2 = INT_MAX;
			int a3 = INT_MAX;
			int a4 = INT_MAX;

			int x1 = x;
			int y1 = y;
			int x2 = x;
			int y2 = y;
			int x3 = x;
			int y3 = y;
			int x4 = x;
			int y4 = y;


			if (x - 1 >= 0)
			{
				while (a[x1-1][y1+1] < a[x][y])
				{
					y1++;
				}
				x1 = x1 - 1;
				y1 = y1 + 1;
				a1 = a[x1][y1];
			}

			if (y2 + 1 < 4)
			{
				y2 = y2+1;
				a2 = a[x2][y2];
			}

			if (x3 + 1 < 3)
			{
				x3 = x3 + 1;
				a3 = a[x3][y3];
			}

			if (y - 1 >= 0)
			{
				while (a[x4+1][y4-1] < a[x][y])
				{
					x4++;
				}
				x4 = x4 + 1;
				y4 = y4 - 1;
				a4 = a[x4][y4];
			}

			if (a1 < a2 && a1 < a3 && a1 < a4)
			{
				// a1 is the succeding item
				x = x1;
				y = y1;
			}
			else if (a2 < a1 && a2 < a3 && a2 < a4)
			{
				x = x2;
				y = y2;
			}
			else if (a3 < a1 && a3 < a2 && a3 < a4)
			{
				x = x3;
				y = y3;
			}
			else
			{
				x = x4;
				y = y4;
			}

			std::cout<<"The "<<counter + 1<<"th smallest item is "<<a[x][y]<<std::endl;

			counter++;
		}

		std::cout<<"The "<<kth<<"th smallest item is "<<a[x][y];
	}
}

- roger.li October 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will this work for a(mXn) matrices since it seems by your pointer initialization, that it is assumed only for 3X4 matrices!

- Anon October 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Anon you are right. This problem is more difficult than what I thought. I will post another solution for it which will print the matrix in order.

- roger.li October 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

r1=0;c1=0;r2=0,c2=1;
int element;
while(ctr<k)
{
if(a[r1][c1]<a[r2][c2]){element =a[r1][c1]; r1++; }
else {element =a[r2][c2];r2++;}
if(r1==arr.length){r1=0;c1=c2+1;}
if(r2==arr.length){r2=0;c2=c1+1;}
ctr++
}

- biro October 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will not work for following matrix:-
int [][] a =
1, 2, 3, 4
5, 7, 9, 10
6, 15, 20, 22

Find 3rd minimum i.e. 3 here..
Your algo will output 6.

- Anonymous October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This method will print the matrix in order and it's easy to modify so it can print the nth element

struct Point
{
	Point(int row = 0, int column = 0):
		x(row),
		y(column)
	{}

	int x;
	int y;
};

void printInOrder(void)
{
	int a[4][4] = {{2,5,8,10}, {4,7,9,12}, {6,15,20,22}, {11,16,21,23}};
	bool visitedNode[4][4] = {false};

	std::cout<<a[0][0]<<"(0,0) ";;

	typedef std::list<Point> BoundaryList;
	BoundaryList boundaryList;

	int minX = 0;
	int minY = 0;
	Point aPoint(minX,minY);
	visitedNode[minX][minY] = true;
	boundaryList.push_back(aPoint);

	while (minX < 4 && minY < 4)
	{
		int succeedingNum = INT_MAX;

		BoundaryList::iterator it = boundaryList.begin();
		while (!boundaryList.empty() && it != boundaryList.end())
		{
			aPoint = *it;

			// The left and down side items have been visited already so this is
			// not the bondary point anymore. Remove it from the list
			//
			if ((aPoint.x == 4 || visitedNode[aPoint.x + 1][aPoint.y] == true) &&
				(aPoint.y == 4 || visitedNode[aPoint.x][aPoint.y + 1] == true))
			{
				it = boundaryList.erase(it);
			}
			else
			{
				int x = aPoint.x;
				int y = aPoint.y;

				// For each bonuary point, check the left and down side item and the smallest
				// one will be the succeeding item
				//
				if (x + 1 < 4 && visitedNode[x+1][y] != true && a[x+1][y] < succeedingNum)
				{
					succeedingNum = a[x+1][y];
					minX = x+1;
					minY = y;
				}

				if (y + 1 < 4 && visitedNode[x][y+1] != true && a[x][y+1] < succeedingNum)
				{
					succeedingNum = a[x][y+1];
					minX = x;
					minY = y+1;
				}

				it++;
			}
		}

		Point boundaryPoint(minX, minY);
		visitedNode[minX][minY] = true;
		std::cout<<succeedingNum<<"("<<minX<<","<<minY<<") ";
		boundaryList.push_back(boundaryPoint);

		if (minX == 3 && minY == 3)
		{
			break;
		}
	}
	
}

- roger.li October 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

The following sorts the matrix. To find 'kth' element, the add a check to stop the while loop at ctr==k.

private static int[] sortMatrix(int a[][],int rows,int cols){
		int elem[]=new int[rows*cols];
		
		int r1=0,c1=0,r2=0,c2=1,count=0;
		while(c1<cols && c2<cols){
			if(a[r1][c1]<a[r2][c2]){
				elem[count]=a[r1][c1];
				r1++;
			}
			else{
				elem[count]=a[r2][c2];
				r2++;
			}
			if(r1==rows){
				r1=0;
				c1=c2+1;
			}
			if(r2==rows){
				r2=0;
				c2=c1+1;
			}
			count++;
		}
		elem[count]=a[rows-1][cols-1];
		return elem;
	}

- cijo.thomas October 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Something similar to 25 horses . Minimum number of steps to find to 3

- Srikant Aggarwal October 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First I sort the matrix merging each row. Then element at (k-1) of the sorted array is the answer. For this solution, it is enough that the matrix is sorted row wised. Or I couldn't make the use of column and row sorted matrix :(

void mergeSortedArray(int *a1, int *a2, int &sizeR)
{
	int size1 = sizeR;
	int size2 = 4;
	sizeR = size1 + size2;
	int arrayR[sizeR];

	int index1 = 0;
	int index2 = 0;
	int indexR = 0;
	while ((index1 < size1) && (index2 < size2))
	{
		if (a1[index1] < a2[index2])
		{
			arrayR[indexR] = a1[index1];
			index1++;
		}
		else
		{
			arrayR[indexR] = a2[index2];
			index2++;
		}
		indexR++;
	}
	for (int i=index1; i<size1; i++)
	{
		arrayR[indexR] = a1[i];
		indexR++;
	}
	for (int i=index2; i<size2; i++)
	{
		arrayR[indexR] = a2[i];
		indexR++;
	}

	for (int i=0; i<sizeR; i++)
	{
		a1[i] = arrayR[i];
		std::cout << "element in arraymerged " << arrayR[i] << std::endl;
	}
}

void findKthSmallestInColumnRowSortedMatrix(int k)
{
	int array[3][4] = {{2,5,8,10}, {4,7,9,12}, {6,15,20,22}};

	int numberofRows = 3;
	int numberofColumns = 4;

	int sizeResult = numberofColumns * numberofRows;
	int arrayResult[sizeResult];
	int indexResult = 0;
	for (int i=0; i<numberofRows; i++)
	{
		mergeSortedArray(arrayResult, array[i], indexResult);
	}

	std::cout << k << " smallest element is " << arrayResult[k - 1] << std::endl;
}

- bambam November 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is called Young's Tableau.
Perform k remove from this and maintain the state of Tableau. Remember to use INFINITY as a large number for elements which are no longer valid.
Complexity O( max(M,N)+K)

int RemoveMin(PYNGTBL tbl, int x, int y)
{
	if( Empty(tbl, x, y))
		return INF;
	int min = tbl->a[x][y];
	if(Min(tbl,x,y+1) > Min(tbl, x+1, y))
	{
		tbl->a[x][y]= RemoveMin(tbl,x+1, y);
	}
	else
	{
		tbl->a[x][y]= RemoveMin(tbl,x, y+1);
	}
	return min;
}

- Sandy November 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Corrected :Complexity is O((m + n)*k)

- Sandy November 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void find(int nth) {
		if (nth >= M * N) {
			return;
		}
		int[] rows = new int[M];
		for (int i = 0; i < M; i++) {
			rows[i] = 0;
		}
		int ptr = 0;
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < nth; i++) {
			min = Integer.MAX_VALUE;
			int r = 0;
			for (int k = 0; k <= ptr; k++) {
				if (matrix[k][rows[k]] < min) {
					min = matrix[k][rows[k]];
					r =k;
				}
			}
			if(rows[r] == 0){
				ptr++;
				if(ptr == M){
					ptr--;
				}
			}
			rows[r]++;
		}
		System.out.println(min);
	}

- Kevin March 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A O(K log K) algorithm
Logic: after ary[p][q], the next smallest element is either ary[p+1][q] or ary[p][q+1]

If K==1 return ary[0][0];
if k==m*n return ary[m][n];
if k<(m*n)/2 {
  //create a minHeap H
  //push triplet (ary[0][0],0,0) into minHeap
  for (int i=0; i<k; i++) {
    //extract root of heap, say (val, p, q)
    min=val
    //push ary[p+1][q], and ary[p][q+1]
    //pop the top element
  }
else {
//do the same as if block, except you start from bottom and use maxHeap and execute it m*n-k times
}

return min

- IntwPrep.MS December 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

This comment has been deleted.

- Administrator October 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Using a Tableau algorithm doesn't need a min-heap data structure.
The code is as follows:

int getKthMin(int matrix[][],int m,int n,int k){
      int min;
      for(int i=0;i<k;i++){
             extractMin(matrix[][],m, n,min);
      }
      return min;
}
bool extractMin(int &matrix[][],int m,int n,int& min){
       if(matrix[0][0]=INT_MAX){  //the matrix is empty
               return false;
       }
       min=matrix[0][0];
      int i=0,j=0,ii,jj;
      while(true){
         if(i+1<m){
               if( j+1<n ){
                   if(matrix[i+1][j]<matrix[i][j+1]){
                           ii=i+1;
                           jj=j;
                   }else{
                          ii=i;
                          j=j+1
                   }
              }else{
                  ii=i+1;
                  jj=j;
              }
         }else{
             if(1+j<n){
                   ii=i;
                   jj=j+1;
              } else{
                 return true;
              }
        }
        int temp=matrix[ii][jj];
        matrix[ii][jj]=matrix[i][j];
        matrix[i][i]=temp;
        i=ii;
        j=jj;
    }
}

- Shan October 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Can we do better with this way?

public int findKth (int[][] mat, int m, int n, int k) {
	if (k > m*n)
                return -1;    // Just an error code
        int[] count = new int[m];
	int total = 0;
        // when there are still elements in the matrix
	while (true) {
		int min = Integer.MAX_VALUE;
		int idx;
                // Find the min one
		for (int i = 0; i < m; i++) {
			if (count[i] < n) {
				if (mat[i][count[i]] < min) {
					min = mat[i][count[i]];
					idx = i;
				}
			}
		}
		
		total++;
		count[idx]++;
		if (total == k) {
			return min;
		}
	}
}

In this way, the running time should be O(k*m), and we should always choose min(m, n) to use here. If I am wrong, please correct me. Thanks!

- shou3301 October 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't have a solution for this question.
However, there is an algorithm to find Kth elements in an array, which runs O(N)

- Vincent October 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In your case, if K is median, then the run time will be O(m*(m*n/2))

- Vincent October 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static int findSmallest(int arr[][], int k) {
		int row = 0;
		int column = 0;
		int m = arr.length;
		int n = arr[0].length;
		 
		
		//k is out of range	
		if(k > m * n)
				return -1;
		
		//k is the max element
		if(k == m * n)
			return arr[m - 1][n -1];
		
		if(k <=  m) 
			column = 0;
		else 
			column = k / m;
		
		
		row = ((k - (column * m)) - 1);
		
		return arr[row][column];
		
	}

- steveholt October 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For this input
int a[3][4] = {{2,5,8,10}, {4,7,9,12}, {6,15,20,22}};

This will give the wrong result for k=3.
your code will return 6, correct answer should be 5.

- Prateek November 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

check out my solution above..It works.

- artemis November 02, 2012 | Flag


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