wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> Max-Min in a matrix
        
(Message started by: ThePriest on Feb 24^th, 2008, 6:06am)

Title: Max-Min in a matrix
Post by ThePriest on Feb 24^th, 2008, 6:06am

This question was given recently(2 months back in an MS interview) to one of my friends.

We have an M * N matrix, filled with random numbers, and we have to select a number (from this matrix) that's maximum among all M rows and it's also minimum among all N columns. (to be honest i too am a bit confused on whether such a number could exist or not), the interviewer did say that it does.

Any solutions?

Title: Re: Max-Min in a matrix
Post by towr on Feb 24^th, 2008, 10:24am

It doesn't quite seem to make sense as it is. If it's the maximum among M rows, than it's simply the maximum in the matrix; so it can't also be the minimum among N columns (which also spans the entire matrix).

Perhaps what's meant is to find an element that's the maximum of the row it's in and the minimum of the column it's in. (Or vice versa; not like that matters qualitatively.)

Title: Re: Max-Min in a matrix
Post by Icarus on Feb 24^th, 2008, 11:30am

Maybe they want the intersection of the max row (by sum) and the min column?

Title: Re: Max-Min in a matrix
Post by tiber13 on Feb 24^th, 2008, 6:20pm

i would pull out the average, think about it.

but 1+I deosnt allways make II

Title: Re: Max-Min in a matrix
Post by ThePriest on Feb 25^th, 2008, 12:35am

I think, for this particular situation, what towr is saying is closest to the problem. Going by his line of reasoning, can we say for sure that there would be only one such number in the entire matrix, as proposed by the interviewer? Can any one site an example

Title: Re: Max-Min in a matrix
Post by towr on Feb 25^th, 2008, 2:14am

on 02/25/08 at 00:35:47, ThePriest wrote:

If you have for example
1 3
4 2
then the minimum of the column is the minimum (rather than maximum) of the row as well. So we have no number fitting the criteria. So perhaps something else was meant after all.

Title: Re: Max-Min in a matrix
Post by ThePriest on Feb 25^th, 2008, 11:58am

@towr

Your example clearly shows that the criteria of maximum in a row and being minimum for that column fails

what about this matrix?

1 2 3 4
13 14 15 16
5 6 7 8
9 10 11 12

In the above matrix, 4 is a number that follows this definition, is it possible that we could have a 3 * 3 or a 4 * 4 (or higher) matrix where the condition fails? Or if it does pass, is it the unique number in that matrix (given there are no repetitions of the numbers)?

Title: Re: Max-Min in a matrix
Post by towr on Feb 25^th, 2008, 12:24pm

If you put the minimum elements along the diagonal, every square matrix fails. (And in quite a few other cases as well)

Title: Re: Max-Min in a matrix
Post by ThePriest on Feb 25^th, 2008, 1:03pm

thanks towr, that clears all doubts.