What is the best way to keep track of the median?

Posted by Steven Mou on Programmers See other posts from Programmers or by Steven Mou
Published on 2011-06-28T15:37:40Z Indexed on 2011/06/28 16:30 UTC
Read the original article Hit count: 274

Filed under:

interview-questions

|

algorithms

|

Performance

I read a question in one book: Numbers are randomly generated and stored into an (expanding) array, How would you keep track of the median?

There are two data structures can solve the problem. One is the balanced binary tree, the other is two heaps which keep trace of the biggest half and the smallest half of the elements. I think these two solutions has the same running time as O(n lg n), but I am not sure of my judgement.

In your opinions, What is the best way to keep track of the median?

© Programmers or respective owner

Related posts about interview-questions

SQL SERVER – Interview Questions & Answers Needs Your Help

as seen on SQL Authority - Search for 'SQL Authority'
About an year ago, I had posted SQL Server related Interview Questions and Answers. It was very well received in community. I have received many comments, suggestions and emails on this subject. I am planning to upgrade the Interview Questions and Answers and take it to next level. Here, I need your… >>> More
SQL SERVER – Interview Questions and Answers – Frequently Asked Questions – Introduction – Day 1 of 31

as seen on SQL Authority - Search for 'SQL Authority'
List of all the Interview Questions and Answers Series blogs Posts covering interview questions and answers always make for interesting reading. Some people like the subject for their helpful hints and thought provoking subject, and others dislike these posts because they feel it is nothing more… >>> More
C# Multithreading Interview questions for a senior developer/designer position.

as seen on Programmers - Search for 'Programmers'
I know there have been a great deal of interview questions posted on SO and specifically i like the post "Good C# interview questions for a Senior developer position" But i really wondered what sort of interview questions were asked to a senior developer or technical consultant on multithreading… >>> More
SharePoint interview questions

as seen on Stack Overflow - Search for 'Stack Overflow'
Let's have a list of some good interview questions for SharePoint developers. Please provide one question per entry, and if possible, the answers. Also, please feel free to suggest corrections if the provided answers are wrong. I will go first: Q: How does SharePoint store pages? A: How-to-locate-sharepoint-document-library-source-page-on-the-server… >>> More
MySQL Interview Questions

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I've been asked to screen some candidates for a MySQL DBA / Developer position for a role that requires an enterprise level skill set. I myself am a SQL Server person so I know what I would be looking for from that point of view with regards to scalability / design etc but is there anything… >>> More

Related posts about algorithms

Finding a problem in some task [closed]

as seen on Programmers - Search for 'Programmers'
Recently I competed in nation wide programming contest finals. Not unexpectedly all problems were algorithmic. I lost (40 points out of 600. Winner got ~300). I know why I lost very well - I don't know how to find actual problem in those obfuscated tasks which are life-blood of every competition.… >>> More
Genetic algorithms

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to implement a genetic algorithm that will calculate the minimum of the Rastrigin functon and I'm having some issues. I need to represent the chromosome as a binary string and as the Rastrigin's function takes a list of numbers as a parameter, how can decode the chromosome to a list of… >>> More
understanding evaluation function

as seen on Programmers - Search for 'Programmers'
I am developing a chess program. And have made use of an alpha beta algorithm and a static evaluation function. I have successfully implemented both but I want to improve the evaluation function by automatically tuning the weights assigned to its features. At this point am totally confused about the… >>> More
How to know whether to create a general system or to hack a solution

as seen on Programmers - Search for 'Programmers'
I'm new to coding , learning it since last year actually. One of my worst habits is the following: Often I'm trying to create a solution that is too big , too complex and doesn't achieve what needs to be achieved, when a hacky kludge can make the fit. One last example was the following (see paste… >>> More
How to implement a genetic algorithm with distance, time, and cost

as seen on Programmers - Search for 'Programmers'
I want to make a solution to find the optimum route of school visit. For example, I want to visit 5 schools (A, B, C, D, E) in my city. Then I must find out what school I should visit first, then the second, then the third etc. with distance, time, and cost criteria. The problem is, I am confused… >>> More