Author |
Topic: Median (Read 1615 times) |
|
sulfur
Newbie
Posts: 18
|
You are given 5 arrays.
Each array contains 5 nos.
Find Median of these 25 nos.
You can load only 1 array at a time.
|
|
 IP Logged |
|
|
|
kaka
Newbie
Gender: 
Posts: 24
|
 |
Re: Median
« Reply #1 on: Mar 29th, 2010, 4:19am » |
 Quote  Modify
|
First sort them individually. Than get the min's of 5 into memory. Keep removing the minimum among them, adding the next minimum from the same array. Repeat till we get 13th min.
I am sure better algorithms exists out there. Can someone please start discussing ideas?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Median
« Reply #2 on: Mar 29th, 2010, 10:24am » |
Quote Modify
|
I'd start with finding the median of each array, then find the median among those 5 medians. That leaves you with a number that is greater than 8 of the numbers, and lower than 8 of the numbers, leaving 8 more that you'd have to find out about.
Not sure what might be a good way to proceed from there.
|
| « Last Edit: Mar 29th, 2010, 10:25am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
vamshi143
Newbie
Posts: 3
|
|
Re: Median
« Reply #3 on: Mar 30th, 2010, 5:37am » |
Quote Modify
|
we can just sort each array and merge them..
|
|
IP Logged |
|
|
|
diptendubhowmick
Newbie
Posts: 11
|
|
Re: Median
« Reply #4 on: Mar 31st, 2010, 3:48am » |
Quote Modify
|
How will you merge ? The problem is only one array can be loaded in the mem at max.
|
|
IP Logged |
|
|
|
sk
Newbie
Posts: 45
|
|
Re: Median
« Reply #5 on: Mar 26th, 2011, 8:10pm » |
Quote Modify
|
We can extend on towrs idea.
1. Sort the individual arrays.
2. Find the median of all of them.
3. take the median of the median.
4. Now you end up with a matrix, with 1st quadrant (top left) < median of medians and 3rd quadrant (bottom right) > median of medians.
5. Check if the median of medians is the median.
6. IF not swap quadrant 2 and 3.
7. You end up with half the matrix to search. This reduces to binary search.
8. Repeat steps 2 to 7.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Median
« Reply #6 on: Mar 28th, 2011, 10:02am » |
Quote Modify
|
The problem is a bit ill-defined. It doesn't say how many extra variables you can use.
If you can use 13 extra variables, you can process one row at a time, keep the 13 smallest values and then return the largest value among these.
Of course, if you can store 13 values, you can load 2 rows, so it is probably not allowed.
Is it allowed to load a column and sort it? Like when we compute the median of medians?
Is it allowed to examine individual values in a row? That way we could sort the arrays by thinking of them as an array of 25 values and sort them by loading only 2 values at a time.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print