Antonio Gulli's coding playground

A certain program makes use of malloc and free several times. Anyway, you forgot to free one block of memory allocated with one malloc. What strategy do you use to check the place where the unpaired malloc is located?

You are given an unsorted list of n-1 distinct integers from the range 1 to n. Write a linear-time algorithm to find the missing integer. Please pay attention to potential overflow

Find all the patterns which are present in the character array C. A pattern is a sub-array containing 2 or more chars and is having a frequency of more than one.

It's done.

MySpace and Google just announced that starting today, status updates from MySpace users will appear in Google's real-time search.

"Then there's advertising, which relies on data collection. Google wouldn't probably be as succe$sful if they didn't know that web users aren't very web savvy. Plus, when web users get a hint of data collection, they tend to swing to the other side of the pendulum and overstate the issue, ignoring things like anonymized data.

Perhaps Google got a little too comfortable with Internet ignorance. They certainly struck a nerve with the autofollowing and autosharing of Buzz. Still, it's doubtful this will do any serious damage to Google. The psychological relief of getting what you want from a company (in this case, greater perceived privacy) is easier than changing your email and search habits."

source: searchenginewatch

Two trains are running one against the other at 50 km/h each. They are 100Km far away. Soon they will collide. One fly is flying from one train to another, first it moves in one direction and as soon as it touches one train it flyies back in the other direction. The fly has a 30Km/h speed. How much space will the fly cover?

"Carl Icahn has substantially cut his stake in Yahoo, according to regulatory filings made public Friday.

The billionaire investor had just under 12 million shares of Yahoo at the end of 2009, according to the new filing with the Securities and Exchange Commission. That compares with more 60 million shares he held last summer"

"I said: “many in this audience want Yahoo to be competitive and succeed but remain skeptical that you can.” Larry Cornett responded that he was at Apple during the “dark time” before the return of Steve Jobs, when critics were calling for the company to shut down. He likened the media perceptions of Yahoo Search now to that period in Apple’s history and promised that Yahoo Search would “be back.” He added that many of Yahoo’s innovations were being freely copied by its competitors but in more superficial ways."

Aardvark, a company that lets you use IM, Twitter and e-mail to ask full-text questions and then get answers from people in or close to your social network, confirmed it signed a deal with Google.

Will the next step be a merge? I bet so.

"New York-based IAC (NASDAQ: IACI) wrote down 991ドル.9 million from the goodwill on IAC Search & Media, the part of its business that contains Ask.com and also the much smaller Dictionary.com. Goodwill is a company’s guess about the future earning power of an asset or company it has bought. It’s the difference between the price paid for the asset and its book value on the balance sheet. Ask.com started life in Berkeley in 1996 as Ask Jeeves -- it was an early dot-com darling. Later, the business moved to a tower in downtown Oakland and was bought by IAC in 2005 in a deal that valued it at 1ドル.85 billion."

Microsoft sites grew January core search volume by 49.6% Y/Y, Google search volume growth of 16.7% Y/Y, Ask grew January core search volume by 15.5% Y/Y, Yahoo! January core search volume decreased by 8.9% Y/Y
source: business insider

Academia and search R&D labs are publishing more and more papers about recenty ranking. I am pretty excited about that since I spent the last 3 years on this topic both in Ask.com and in Bing.com.

Towards Recency Ranking in Web Search is an high quality paper from Yahoo! about relevancy ranking. The main contribution of the paper is twofold: it presents a query classifier for recency and a ranking model for recent results.

The query classifier builds two models representing the Content and the Query data at time t, respectively. The two models are then compared on different instants of time and a query is considered recent if it increases his probability of being generated in two different istants. This approach is interesting. Nevertheless there are queries that would fresh results, even if they are constantly observed (such as "Obama", "Britney Spears", "stock quotation", etc).

The ranking model aims at learning a ranking function based on four categories of recency-related features: timestamp features, linktime features, webbuzz features and page classification
features. The learning algorithm is GBrank. To solve the recency data insufficiency problem, the authors explored several modeling approaches by utilizing regular ranking data. In compositional model the normal ranking output is used as a training feature, while in over-weighting model the normal ranking output is used with recency features and an emphirical optimal weight is derived. In adaptation model, training data from normal ranking is used for learning a regression tree model, which is then fine-tuned with recency ranking data.

The evaluation set is made up of 70,131 query-url pairs collected during a period of four months (Feb.∼May, 2009) judged by humans and is based on NDGC metrics. One final result is worth mentioning. In the paper, linktime features are the most important recency features among all recency features. Quoting the authors: "Thus, recency is competing with popularity, which is usually indicated by link-based features and click-based features. This leads to the interesting topic on how to appropriately deal with the relationship between recency and popularity"

Write the C++ code for an optimal algorithm -- both in time and space.

Given a stream of symbols, with a finite alphabet, compute all the items which appears more than 50% of time

[フレーム]

Thanks to Greg for pointing out them. Interesting work@LinkedIn based on Lucene's customizations.

[埋込みオブジェクト:http://vimeo.com/moogaloop.swf?clip_id=9225227&server=vimeo.com&show_title=1&show_byline=1&show_portrait=0&color=00ADEF&fullscreen=1]

Twitter Code Swarm from Ben Sandofsky on Vimeo.

Second, we are extending our cooperation outside the US, bringing the Bing-Facebook search integration to the more than 400 million people using Facebook around the world.

Aardvark Q&A engine going to WWW10

• Users can ask questions in natural language, not keywords
• Content is generated “on-demand”, tapping the huge amount of information in peoples’ heads
• The system is fueled by the goodwill of its users

• 87.7% of questions sent to Aardvark got answered (very high answer rate!)
• 75.0% of users who asked Aardvark a question also answered a question for someone else (very high participation rate!)
• 70.4% of answer feedback had a rating of ‘good’ as opposed to ‘ok’ or ‘bad’ (high quality!)

So Bing is will probably power Yahoo, and Google will power AOL.
Who is out of this list?

1. http://geeksforgeeks.org/
2. http://stackoverflow.com
3. http://www.topcoder.com/tc
4. http://www.spoj.pl
5. http://www.projecteuler.net
6. http://codechef.com
7. http://uva.onlinejudge.org/

Anything missing from the list?

Great initiative from Russia

Introduction to Machine Learning it's a quite practical book that I do like to suggest for reading