StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POinterviewstreet median challenge
text
Body
copied!<p><strong>Problem</strong> The median of M numbers is defined as the 1) if M is odd middle number after sorting them in order 2) if M is even the average number of the middle 2 numbers (again after sorting) You have an empty number list at first. Then you can add or remove some number from the list. For each add or remove operation, output the median of numbers in the list.</p> <p>Example : For a set of m = 5 numbers, { 9, 2, 8, 4, 1 } the median is the third number in sorted set { 1, 2, 4, 8, 9 } which is 4. Similarly for set of m = 4, { 5, 2, 10, 4 }, the median is the average of second and the third element in the sorted set { 2, 4, 5, 10 } which is (4+5)/2 = 4.5 </p> <p><strong>My approach</strong> I think the problem can be solved in this way.. Idea is to use previous median value and pointer to find new median value instead of recalculating at every add or remove operation.</p> <p>1) Use multisets which always keep elements in order and allow duplicates. In other words maintain sorted list somehow.</p> <p>2) If the operation is add</p> <pre><code>2.1) Insert this element into set and then calculate the median 2.2) if the size of set is 1 then first element will be the median 2.3) if the size of set is even, then if new element is larger then prev median, new median will be avg of prev median and the next element in set. else new median will be avg of prev median and previous of prev element in the set. 2.4) if the size is odd, then if new element is larger then prev median if also less then 2nd element of prev median ( 2nd element used to calculate avg of prev median) then this new element to be added will be new median else median will be 2nd element use to calculate the avg during last iteration prev median. else new median will be previous of prev median element in the set </code></pre> <p>3) If the operation is remove</p> <pre><code>3.1) First calculate the new median 3.2) If the size of set is 0 can't remove 3.3) If the size is 1 if the first element is the element to be removed, remove it else can't remove. 3.4) If the size of set is even, then if the element to be deleted is greater than or equal to 2nd element of prev median, then 1st element of prev median will be new median else 2nd element of prev median will be the new median 3.5) If the size of set is odd, then if the element to be deleted is the prev median then find the avg of its prev and next element. else if the element to be deleted is greater then prev median, new median will be avg of prev median and previous to prev median else median will be avg of prev median and next element to prev median. 3.6) Remove the element. </code></pre> <p>Here is the working code ...<a href="http://justprogrammng.blogspot.com/2012/06/interviewstreet-median-challenge.html" rel="nofollow">http://justprogrammng.blogspot.com/2012/06/interviewstreet-median-challenge.html</a>. What are your views on this approach?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload