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!
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 Search
3.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.
Here my approach:
ReplyDeleteKeep 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!
ReplyDeletepost it correctly, I delete this one
ReplyDeleteDone, thanks.
ReplyDeleteThis 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?
ReplyDelete1) 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 Search
3.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.