Author |
Topic: Max-Min in a matrix (Read 1992 times) |
|
ThePriest
Newbie
Gender: 
Posts: 16
|
 |
Max-Min in a matrix
« on: Feb 24th, 2008, 6:06am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Max-Min in a matrix
« Reply #1 on: Feb 24th, 2008, 10:24am » |
Quote Modify
|
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.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Max-Min in a matrix
« Reply #2 on: Feb 24th, 2008, 11:30am » |
Quote Modify
|
Maybe they want the intersection of the max row (by sum) and the min column?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Random Lack of Squiggily Lines
Senior Riddler
Everything before 7/1/2008 is now irrelevant.
Gender:
Posts: 460
|
|
Re: Max-Min in a matrix
« Reply #3 on: Feb 24th, 2008, 6:20pm » |
Quote Modify
|
i would pull out the average, think about it.
but 1+I deosnt allways make II
|
|
IP Logged |
You can only believe i what you can prove, and since you have nothing proven to cmpare to, you can believe in nothing.
I have ~50 posts to hack a "R" into a "D". Which one?
|
|
|
ThePriest
Newbie
Gender:
Posts: 16
|
|
Re: Max-Min in a matrix
« Reply #4 on: Feb 25th, 2008, 12:35am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Max-Min in a matrix
« Reply #5 on: Feb 25th, 2008, 2:14am » |
Quote Modify
|
on Feb 25th, 2008, 12:35am, ThePriest wrote:| 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 |
|
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.
|
| « Last Edit: Feb 25th, 2008, 2:15am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThePriest
Newbie
Gender:
Posts: 16
|
|
Re: Max-Min in a matrix
« Reply #6 on: Feb 25th, 2008, 11:58am » |
Quote Modify
|
@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)?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Max-Min in a matrix
« Reply #7 on: Feb 25th, 2008, 12:24pm » |
Quote Modify
|
If you put the minimum elements along the diagonal, every square matrix fails. (And in quite a few other cases as well)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThePriest
Newbie
Gender:
Posts: 16
|
|
Re: Max-Min in a matrix
« Reply #8 on: Feb 25th, 2008, 1:03pm » |
Quote Modify
|
thanks towr, that clears all doubts.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print