Random commentary about C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Here my approach:Keep reading from the stream and store the values until you collect N values (N is decided by the user) into a temp array A. For each element "a" from the stream do:1.1) Keep calculating the AVG of the read values so far by summing and dividing by the current number of elements read from the stream.1.2) Maintain a MAX-heap and a min-heap and a variable k where top(MAX-heap) < k < top(min-heap). Once you read the next element "a" from the stream you compare it against k and if it is lesser than k you put "a" into MAX-heap else into min-heap. If the size of the two heaps differs by more than 1, then you pop the top elements of the heaps (let's call them M and m), and push M, m and k into the smaller heap. Then you pop from it the top element and assign k to that element. Now, the two heaps have the same size and k is the median.As you read the N+k (k>0) value do:2.1) print AVG and k as the current running average and median.2.2) Maintain the AVG current by subtracting A[i]/N and adding a/N. Then a[i] = a and i = (i + 1) % N (i starts from 0).2.3) maintain k as the current median applying the strategy described in 1.2.
Oh no! Just realized I posted the answer for "Given a stream compute the running average and the running median" as comment here :( Could you move it? Thanks!
post it correctly, I delete this one
This is an hard question actually. Selling ads it's a strong and kind of unbeatable business model as advertisers want to spend (a lot of) money and users don't complying too much in clicking on a sponsored link (if related to the search of course). So, what else?1) A SE has a lot of infos that can be sold to Marketing specialists for their market research. This can bring some money in, but your users will start crying for more privacy.2) A SE can try to sells it's search technology to the companies in need of a better information management system. Not a multi billionaire business though.3) On the web you can make money in two ways: selling products a-la Amazon or by some advertising strategy a-la Bing (to not mention Google). Basing on this declaration, in my opinion a SE can either:3.1) starts to sell product (sort of Amazon+Bing). The SE needs to invest on an hyper efficient supply chain system to integrate with the Search3.2) finding different way to advertise instead of just selling keywords. To menton few:- Retargeting- Behavioral using social data + past queries- Gamification, i.e. engaging the user in something (a game) and rewarding him with a real product sponsored by...So it doesn't seem to me that a SE is really in a position to find any other strong business model to make big money (pretty sure that the future will prove me wrong of course). I find a Social Network in a much better position to find a new and more lucrative model. Let's see if FB will confirm this my hypothesis.