0/1 matrix

Given a 0/1 matrix A of size n x n, find the row with the maximum number of 0s

Find top log(n) or top sqt(n) values in an array of integers

Find top log(n) or top sqt(n) values in an array of integers in less than linear time.

Lucky numbers

Lucky numbers are numbers whose prime factors are just 2, 3, 5. Find the first k lucky numbers.

Interesting talk @ facebook for creating Places and entitites

I believe that the problem of extracting entities from social data would be an hot research problem. Here they use naive social mining for building basic information which is than combined with machine learning techniques.
Extending the graph tech talk [HQ]

Longest run of 0s and 1s

Really like the linear solution of this problem. You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal.

Example

pos = 0  1  2  3  4  5  6  7  8

          0  1  0  0  1  1  1  1  0

One interval is (0, 1) because there the number of 0 and 1 are equal. There are many other intervals, find all of them in linear time.

Beauty of xor-lists

XOR-lists are beautiful because your can store a double chained list by using a single pointer for cell. For instance   in the list A, B, C, D, E  you store A (B), B (B xor C), C (C xor D), D ( D xor E), E . So coming from B you can perform a B xor (B xor C) obtaining C and viceversa coming from D, you  have C = ( C xor D) xor D. In modern computers you have enough ram for not paying attention to those xor-lists, but they are still useful in many circumstances.

Do you know when?

Fascinating problems for the maximum subsequence problems

The linear solution for the maximum contiguous subsequence problem is one of most fascinating solution for a problem that is cubic at first glance. Sometime this problem is also known as Maximum subarray problem, and the idea is that you have an array of positive and negative integers and you need to find a "slice" whose sum is maximum (e.g.−2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6). The linear solution is one the pearls in Bentley's book

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    /* invariant: maxendinghere and maxsofar are accurate
       are accurate for x[0..i-1] */
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)

The key observation is to maintain the maximum found so far, putting a zero as minimum because that's the empty sequence. Then we have another variable for computing the global maximum among all the local maximum.

Now given this pearl, can you solve the following problem: "Given an array of 0s and 1s, Find the maximum contiguous subsequence so the number of 0's and 1's in that subsequence are equal"

Amazon service disruption -- an example of open post-mortem

Amazon suffered a large service disruption during past weeks. Summary of the Amazon EC2 and Amazon RDS Service Disruption in the US East Region is a very professional and open post-mortem analysis that I really enjoyed for his transparent form of communication style and very rich informative details.

Sort an array of 0, 1, 2, 3 symbols

with no additional memory and in linear time

Fresh Autosuggest

Clustering news and Bin Laden in International markets

Great collaboration among Asia, Europe and U.S. for shipping the new clustering infrastructure in multiple international countries

Open source and Facebook

Facebook is becoming more and more the champion of large scale open source adoption. Traditionally, this was a Yahoo! prerogative but now Facebook is using a good combination of Hadoop, Hbase, and Lucene for their

Facebook Messages' Application Server

Generate all the bit string of length n

easy one: PMs keep asking for meetings

Identify conflicting ones and just decline them.

PS: dedicated to the other side of the moon

Broke a circle which become a cage

what was the complexity

Bing or Google?

http://www.stateofsearch.com/osama-bin-laden-killed-how-did-google-and-bing-respond/

“So in this battle, who won? And then I am off course speaking of the battle between Bing and Google. In my personal opinion I get a much better feeling from Bing compared to Google. Even though Bing has nothing Social in it.

The look and feel is much better, with the big image on top. You immediately feel you are “into the news”. Even though Google has relevant information on it, they fail to actually make it really useful for the user.

But the main no-go for Google in this case for me is the lack of videos. I can not understand why there are not more videos there. If you put up a live channel, make sure it shows up in the SERPS.

For me this one goes to Bing. How about for you?”

Launched News in 4 countries

Given an huge web graph identity the top k pages with largest number of incoming links

discuss the problem and find solutions

Balance a single linked list of integers

In other words transform the list into a balanced Binary Search Tree

120 G cables

Typical G. question. here is a bunch of 120 electrical cables laid under the ground. The cables are 10 KM in length and both ends of each wire are out in open.

We need to identify and label the cables 1-120. As you might have guessed, the only way to gain information in this setup is to connect some set of wires at one end, walk up to the other end, and test for conductivity. The process may have to be repeated many times before a complete labeling can be constructed. And since each such step involves walking across 10 KM, we wish to solve the problem with the least number of trips.

How would you identify each cable in minimum number of trips?

Launched Deep Links in 8 countries

STC-E London launched DL in 8 international countries

Ask outsourced

IAC Asks For More Google, Please

Cyclic strings

how do understand whether a string is the cyclic string of another (e.g. 12345, 23451)

4 numbers and 4 operations

You have 4 numbers, and 4 operations (+, -, -, /) can you combine the 4 numbers with the 4 operations and check whether the final result is equal to the number X.

Two array

You have two arrays of characters, find whether they overlaps.

Numbers on the phone

You have a traditional phone with numbers 0-9, *, #. how many different words can you compose selecting 10 digits?

Select the less expensive flight going and return

Given two locations A, B there are K flights going A -> B and H flights A <- B each one with a cost. Select the less expensive combination assuming that the flights can be fully booked.

Roses

Mary comes and buys half of my roses, plus I give her one rose as gift. Then, Sally comes and buys half of my remaining roses and i give her 2 roses as a gift. Then Molly comes and she buys all the remaining roses. How many roses did I have at the beginning?

check a tree

Write a function that returns true if given binary tree the value of each node is equal to sum of the nodes present in its left subtree and right subtree.

Inversion pairs

Given an array of n integers find all the inversion pairs in O(n).

A nice video by the way of Google

This made my day

Check the validity of an arithmetic expression with parenthesis

Having the standard operators +, -, x, /, and three different types of parenthesis

Maximum number of trains in the station

You are given a collection of trains C. each train t_i  will enter the station at time t_i_0 and will leave the station at time t_i_1. How many trains do you have in the train station at a given moment in time t? What is the maximum number of trains you have during a day?

How do you invoke a callback using a predefined method but passing parameters?

function callback(a){

}

function b( ...., callback(data))
{

} 

what is the problem with the above code snippet?

Array problem

Given an array A of n integers, find two indexes i, j such that  j > i and maximize (j - i) with A[j] - A[i] > 0

Google’s Page Begins Major Reorg: Engineers, Not Managers, In Charge

Google’s Page Begins Major Reorg: Engineers, Not Managers, In Charge

Do you believe is a good idea?

A feature suggestion for Facebook: increasing Facebook monetization for mobile payments

In my posting "A feature suggestion for Skype: turning skype in a cash-cow machine for mobile payments I suggested a new model of payments for Skype. The same one can be adopted by Facebook mobile on a larger scale and adopting the same principle. Wouldn't mind if they finance the idea.

Classical yahoo question

You are on a strict medical regimen that requires you to take two types of pills each day. You must take exactly one A pill and exactly one B pill at the same time. The pills are very expensive, and you don't want to waste any. So you open the bottle of A pills, and tap
one out into your hand. Then you open the bottle of B pills and do the same thing -- but you make a mistake, and two B pills come out into your hand with the A pill. But the pills are all exactly identical. There is no way to tell A pills apart from B pills. How can you satisfy your regimen and take exactly one of each pill at the same time, without wasting any pills?

A feature suggestion for Skype: turning skype in a cash-cow machine for mobile payments

Mobile payments is an hot area, with startup like Square. This company is based on the very simple idea of plugging a low cost little device to a normal mobile phone for reading traditional credit cards. So your mobile will turn into a credit card reader. Not all the platforms are supported (just Iphone & Android), but the company got around 1M users in a short amount of time, $37M in funding and an evaluation of about $200M. Sequoia is one of the investor. Their business model is to take around 2-3% for each transaction. What I don't like about Square is that it is still not working with all the mobile platforms, and that you need to have an external little device for reading the cards.

I was considering how to use Skype to make mobile payments with no external accessories. A couple of considerations. First, Skype is installed on several mobile phones because users likes to make (video) calls at very low fare rates. Second, Skype has already a working billing system for each Skype account. The billing system is currently used for paying calls from skype to traditional phone numbers.   So, why don't they use this credit for making mobile payments?

This can work in a very easy way. Suppose that a Skype account A decides to accept Skype payments. A should register some identity/billing information (name, company, address, and so on and so forth). When a customer B wants to make a payment to A  for a given amount of money, the only thing that B should know is the login name for A. Skype will present to B all the already registered information for A, so that B can verify the identity of A and authorize the money transfer.

For example, say that Ely wants to transfer $10 to Lucy. Ely will start a request to Skype which will answer with all the registered information for Lucy (her address, her age, her town and so and so forth). Ely recognizes Lucy and authorizes the money transfer. Similarly, if Lucy wants to pay the company ACME.COM, skype will provide all the registered data for ACME and will transfer the money if Lucy recognizes ACME billing information.

Simply enough and already working. No external accessories, no need of having a new distribution platform, no need of creating a new billing system. The idea is already there and can be easily implemented by the way of Skype.

I would not mind if they will fund me with $37M for the idea itself ;-)

15 top Google & Microsoft acquisitions

Google's 15 Biggest Acquisitions And What Happened To Them

Microsoft's Biggest Acquisitions And What Happened To Them

It's official, I am now working for Crop

It's official! I am now working for Crop a new Social Search Startup, as Director of our cool search project codename "Circle". Currently, we are in private beta. IM me if you want an invitation. Oak and U-Combinator are the investors and we are currently hiring.

Crop (Beta), Create your Personal Social Circle

A feature I like in Google Search (for power users)

Search "Swine Flu" with temporal information turned on. You clearly see that they tagged offline temporal entities, since those are highlighted in the snippets

A comment on google coming from an ex-employee

What Larry Page really needs to do to return Google to its startup roots.

(it could be applied to other companies as well)

Specialize swap

in C++ how do you specialize swap for your own Class? and what about a template?

A feature suggestion for Wikipedia or Facebook: Social Wikipedia, or wikipedia with Subjects

This is not a new idea. Three years ago, I was considering to leave my CTO position in Ask.com for creating a new start up around a new idea of social content creation. This posting will describe a revision of those original intuitions.

I am a big fan of Wikipedia, which is, in my opinion, the natural complement of Web search. In Wikipedia, hundreds of thousands of editors contribute to create content organized in millions of different encyclopaedic voices which are available in multiple languages. The key strength of Wikipedia is that anyone can start creating content but this content will be continuously revised by other editors. As a consequence, this never ending process guarantees very high quality. Indeed, On 14 December 2005, the scientific journal Nature reported that, within 42 randomly selected general science articles, there were 162 mistakes in Wikipedia versus 123 in Britannica.

My idea was to give a clear identity to the editors, associate an explicit profile and an explicit network of relations, so that it would have been possible to identify experts around different topics in a clear and direct way.

Adopting a more recent jargon introduced in my recent posting "from objects to subjects", I can describe the idea in a more synthetic way.  Encyclopaedic voices in Wikipedia are a particular type of objects and the editors are the subjects who are creating, editing and discussing those objects. It should be possible to rank those subjects, match on the fly different subjects according to the objects they annotate, identify expertise in subjects and so on and so forth.

You may wonder what was the reason why I decided to not create a new startup. Well, while I was considering the idea Google announced Knol, which is probably one of the less successful initiative started by Google because Wikipedia was already very strong and there was no idea of Social graph at that time.

Anyway, three years ago was probably too early but now it could be the right time to have a Social Wikipedia == Social Graph + Wikipedia.

What do you think?

A nice intro for HTML5

HTML+CSS+JS

(this is my posting number 888)

A puzzle with switches

There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too

Give an algorithm which, given a starting configuration, will tell you whether the lock can be unlocked by a sequence of switch toggles

A question of classes

One frequent element of discussion during my interviews is about the different types of classes you can define in C++. In this sense, C++ Coding Standard provides a valuable summary:

1. Value classes have a public constructor and a public destructor and a copy constructor with value semantics. Also, they have no virtual function, no virtual destructor and so you cannot inherit from them. The idea is that you use value classes for holding other objects and the typical example are STL containers;
2. Base classes are used as base of a hierarchy. Therefore you can have a virtual public destructor, or in very rare cases a protected non virtual destructor (if you don't want to use polymorphism as in std::unary_function;
3. Trait classes are template classes with information about types, where you define a certain numbers of typedefs and you never instantiate explicitly the class with a constructor;
4. Policy classes represents pluggable behaviour and it is usually instantiated as a base or a member;
5. Exception classes mix a value and reference semantics since they throw the exception by value and capture it by reference. Quite frequently they have virtual functions.

Two nice initiatives from Google and Microsoft

Google Ventures Launches $10,000 Startup Referral Program For Employees

Microsoft incentivizes employees to develop Windows Phone Apps after hours

A feature suggestion for Facebook: one login, multiple social graphs stored in a central place

I really like the idea of having one single login for multiple sites and Facebook connect is a real killer application which rapidly became a de-facto standard over Internet because it simplifies our life. In short, I believe that having one single login is cool because I am myself regardless of the place where I am.

Anyway, having a single global social graph is not exactly the same thing because the friends I have for my hobbies (acquaria, ham radio, and programming) are different from my professional friends, who are in turn different from my gym friends, who are in turn different from my Italian friends, who are in turn different from my U.K. friends and so on and so forth. Also, I use other community sites powered by vbulletin and other similar software tools which encourage users to build local social graphs (see the friend list feature) for each different community site.

In this case, having multiple social graphs hosted in one central place but with different access rights for being shared would be probably much better than having one single social graph hosted in one central place.So facebook, how about being the place in internet where everyone can store his own set of social graphs and decide how, if and when they are connected?

A classical one: how many different optimizations you know about quicksort?

Smart pointers

Smart pointers must be part of the background of every programmer. Surprisingly enough this is not the case in several situations and many candidates who are not aware of them.

The intuition is very simple: when you assign an area of memory to a (naked) pointer, you must remember to deallocate that memory when you are no longer using it. This is the typical situation which can create leaks because it is easy to forget to deallocate an area of memory in a complex program.Smart pointers deallocates the area of memory when they are no longer used, in the destructor. Since an area can be referred by many smart pointers we should have a shared counter where we store the number of active references. Here you have the code. For a more professional use, please refer boost.

Find single element

You are given an array A that contains integers. Every integer occurs 3 times in A leaving one integer that appears only once. Fastest way to find that single integer

A rant against CSS

So I should be considered a backend guy. The problem is that I don't know what is the different from backend and frontend and the two things are actualy the same one.

Anyway, this is a rant. Who was that crazy guy that suggested to abandon the HTML table and adopt divs? Cmon it's embarrassingly hard to create a table with autofit and div!!!

Virtual constructor

In c++ we don't have such a thing as a virtual constructor. Anyway, given a derived class B : public C would you call a virtual function in the constructor of B?

QT clustering

QT clustering is a very simple clustering algorithm, where you don't need to provide the desired number of clusters (like in K-Means). Instead, you give a maximum distance allowed. In one variant, you consider the diameter of the clusters already formed. In another variant you consider a single linkage distance. Here you have the code

A feature suggestion for Facebook: associate objects to subjects, Web page owners can annotate their pages with their Facebook profile

In my post From objects to subjects: Next possible scenarios for Social search, i claimed that social search is a complete paradigm shit, where you no longer interacts with just objects (pages, images, news and so on and so forth), but you start to interact with subjects that are making concrete actions on objects (create, comments, likes, annotations, shares, and so on and so forth).

Now, one technical problem is how to associate in a reliable way the owner of an object with the subject that created it. I started to think about the problem early this morning while running in Pisa under a light rain. The run was amazing good, and I felt very good after 7 kms.

My first thought was that I can simplify the problem if I just focus on Web pages (a type of object), because almost all the other objects (images, videos, audios) are generally embedded in web pages.

My second though was that all the Web pages belongs to a domain. Therefore, I can check whether the subject claiming the ownership has email access to that domain by sending an email and asking for an explicit acknowledgement. After all, Facebook adopts a similar solution for checking the rights when you want to declare your (work) affiliation. This solution may work but has the problem of discriminating the ownership for multiple users belonging to the same domain. It works for affiliation, it does not work for ownership.

My third thought was that the owner of a page has, by definition, edit rights on it. Any owner can edit her own pages. Therefore, she can embed a special tag with an unique id generated for checking the ownership. Whoever wants to check the ownership can, therefore, check the presence of this tag and verify the ownership.

Now, if you think about it you can ask yourself if you have seen this elsewhere. In a sense, Facebook is already adopting a similar principle for their Like buttom which must be generated ad-hoc for each specific page. Therefore, Facebook can check the ownership of a page once the like button is embedded in the page, because only the owner can edit the page.

Apparently, Facebook is not exposing this feature because the Like button is "only" used by other people for express their preference on a page (an object), instead of checking the ownership of the object itself.

Anyway, this could be a good feature: Giving the opportunity to all the Web page owners to annotate their pages with their facebook profile. In my lingo associate any object with the subject that create it.

PS: here it is the like button generated for this particular URL. I certify the ownership of the page by embedding the button

The beaty of lazy workers -- doing more with less

I usually sleep 4-5 hours per night, and the less I sleep the more I do. Don't be surprised. It is all about the quality of your activities and the respect you have for your body and your mind.

I am a big fan of lazy working which means do more with less but make sure you conclude your activities just when needed and not before. In computer science, we have this beautiful concept of Lazy evaluation, also known as "call by need" which delays the evaluation of an expression until its value is actually required. The intuition is very simple you start an activity very very early, but you don't conclude it immediately. No, you defer it until you are forced to conclude it by a real need.

Let me make a toy example to clarify. Suppose you need to compute 2+3, you write the sum but you don't carry out the summation. Instead, you defer it. And you keep deferring until you need to consume that result for another operation. And so on and so forth. It's a very simple principle but it is powerful. Because it allows to do more with less. Why? because you can start multiple activities, and you keep deferring them until you really need to consume their results as input to new activities.

The magical aspect is that you can carry out many activities in parallel. If you are good in managing your time, you will start to observe a mutual boosting effect where you reduce the time needed to conclude one single activity because you have all the other pending and waiting on-hold.

In a sense, this is similar to a runner who is not just running. No, she trains her body taking care of different muscles of her body in parallel starting to improve each muscle, then stopping that particular activity and starting a new one, deferring the conclusion until there is a real need.

So next time someone will ask you: "Are you focused? Are you carrying out your assigned activity?" you may answer: "No, I am a lazy worker. I do more with less"

From objects to subjects: Next possible scenarios for Social search

We are living an age of amazing transformation for Web search, which was very hard to forecast until two or three years ago. In a sense, search is a teenager and it is about to become an adult. A teenager plays with objects, an adult interacts with other subjects.

Search was born in 1995 circa with Lycos, an open source project from CMU. Do you remember "pursuit"? It was a mix of perl script and c code which offered (almost) everything a modern engine is offering including crawling, index, search, dynamic caption generation, and textual ranking. Well, the Web was kind of small at that time -- say a less than 10 millions of pages. So, when the Web became larger we saw the raise of Altavista, which added the ability to scale to an index of hundred of millions of pages. Anyway, the quality of search was still poor because the ranking was purely a textual match. Everything changed in 1999 when Google started to consider the Web as a graph with connections among pages. Pagerank was an idea already used in the academic world, where a paper is important if it is frequently cited by other (important) papers, but the wonderful intuition of Google was to apply the same principle to the Web. In doing so, they created a new type of science. Also, Google had the superb merit of understanding how to make money out of search, when everyone else was considering it as a commodity with no real business opportunities. They introduced an auction system and created an ecosystem with users, publishers & advertisers, and a new science (of making money). In a glimpse Google became a verb, a monopoly, and an incentive to reduce our attitude to learn and reason ("People don't think, they Google!", said my friend Alessio Signorini). Nowadays, Bing and Yahoo! have the merit of fighting the monopoly and using massive machine learning for systematically improving the quality of results, which are in addition more and more visual.

So in 1995 we had almost everything, with the only exception of scale (altavista), a good ranking (google), money (google), machine learning & visual ux (bing). If you think about it in 16 years we saw many changes but no one was dramatic (maybe the only one was to start making money, meaning that the search kiddie understood how to walk on her own legs). More or less, no change was dramatic. Why? Well the Web was still the same. It was a collection of objects (pages, images, videos, news and so on and so forth). Surely, we moved from from say a couple of millions of objects to hundreds of billions of objects (or trillions? ;-) and therefore the data mining problems to solve are fascinating and ever changing but still we are talking about objects.

Now, two years ago something changed. The web is no longer a collection of objects, but we are starting to see people, subjects, organized in a social network. Facebook counts more than 600 millions of subjects, connected in fascinating structure and very active in making instantaneous comments about the world, sharing objects, and liking or disliking actives carried out by other subjects. Twitter offers similar perspective.

Think about it: this is a complete change of search paradigm! You no longer search just objects, you can know start to interact with subjects.


Phase I

If you look carefully, this change is already starting to happen. Today, if you search Web pages (a type of object) in Bing the results are enriched with information coming from Facebook about the subject that produced an action related to that page (or that object). This action can be either sharing that particular link or liking that particular page. In this case, Bing offers a picture of the person -- the subject -- who carried out that particular action. Let's call this phase one.

Phase II

What can happen in the future? The limit is just in our imagination. If you think in terms of objects and subjects, you understand that, in phase I, search is annotating objects with subjects making actions on objects. But it is still a search about objects. Now what is the next step? How about a search directly mixing objects and subjects? In other words, can i submit a query and get as result the best subject, the best expert about that query? My friend Tony is my expert for handcrafted lights, and my friend Max doesn't know this. Can Max get Tony as a result of a query for {handcrafted lights}, in addition to the most relevant sites out of there? Think about it, this could easily be a new type of science where we learn the expertise of subjects by observing what types of objects they produce and what types of object they annotate? Once we have learned this information can we propagate it to the graph of interconnection among subjects. Sometime, we can learn expertise about friends that we were not aware of (my friend Ian is an expert in cycling and I was not aware of it). Sometime we can introduce friends that don't know each others once we discover their expertize. Sometime we can produce a set of subjects (e.g. persons) as result of a query.

Also, we clearly need a robust and consistent model for ranking subjects. We probably have many persona, including producers, early adopters, influential, and the mass. For each topic, we can follow the temporal evolution of likes and create an evolving ranking.

So, phase II would be about moving from a Web of Objects to a Web of Objects and Subjects.

Is this the evolution of the adolescent search into a more mature subject?

Phase III

Now let's assume that we have a Web of Subjects and Objects. How can this impact the art of making money? Can we sell the expertise of subjects and transform the ads space?

In my idea, once you discover expertise by observing public behaviors you can match different subjects and allow them to compete in selling their expertise with an auction based mechanism similar to the one adopted for ads.

Sometime, two matching subjects agree to exchange expertise just for free because they are friends or because they enjoy helping each others. Sometime, when the expertise is more professional and become a Service offered by Subjects, then several experts can compete for offering their expertise at the best price. In this case, the matchmaker takes a little margin for the cost of this transaction. As an example, my friend Ralf is an expert of non-bayesan prediction, and my friend Bret may be not aware of it. So Bret my want to talk with Ralf about his expertise.

So, phase III would be about moving from a Web of Objects to a Web of Objects, Subjects, and Services

Conclusions

Web is evolving from a collection of objects (pages, news, images, videos, and so on and so forth) into a collection of objects and subjects interacting each others and eventually offering services. In my view, Social search is all about this shift in paradigm.

Now, let's step back for a little while and let's ask to ourselves is this a generalization of a model seen elsewhere? I just said: "Pagerank was an idea already used in the academic world, where a paper is important if it is frequently cited by other (important) papers, but the wonderful intuition of Google was to apply the same principle to the Web".

Think about it: in academic world a paper, an object, is important if it is frequently cited by other (important) papers or by other (important) authors, the subjects. This is the natural evolution of PageRank. In addition, an author, a subject, is important if other authors are frequently citing her. More about this point. We can learn the expertise of an author by observing the papers she publishes, We can match authors even if they don't know each others once we learn about their expertise, We can learn about new expertise of authors we already know, and so on and so forth.

In short, the paradigm shift exists elsewhere and we just need to apply it to Social Search. Google focused on the objects (the papers, the pages), Social search is about objects and subjects (the authors and their expertise).

Disclaimer

The views and opinions expressed in this article are those of the authors and do not necessarily reflect the official policy or position of Bing, Microsoft. Examples of analysis performed within this article are only examples. Assumptions made within the analysis are not reflective of the position of Bing, Microsoft.

I wrote this article during 1.5 hour flight while listening Greatest, Duran Duran

Special queue

Implement a queue in which push_rear(), pop_front() and get_min() are all O(1) operations.

Japan earthquake (Bing UK and FR)

My thoughts and prayers with all our Japanese friends, colleagues and citizens today.

When those events happen our role is to report relevant information as fast as we can so that users can be informed and, hopefully, reduce that sense of fear and uncertainty generated by lack of first hand communications.

During last months we worked hard to improve the freshness and quality of our search algorithms by leveraging new clustering algorithms which work in multiple countries and multiple language. This is a visual comparison of our results in two countries and two different languages. Thanks to all the teams (Beijing, Bellevue, and London) who made this possible working together for a global market and a better service offered to world wide users.

France









United Kingdom

News is the ultimate frontier for personalization

My friend Greg was the pioneer in this area with Findory. Then, I really felt in love with paper.li, now Linked.In is entering the arena. They have the people sharing news, and they know the professional category to which that particular user is belonging to. So this is a little and nice innovation.

News answers in Fr and UK

When freshness is important (again ...)

Sort 10 Tbs of data

Assume you have 100 tbs of data made up of fixed length records. How would you sort it?

Build a caption for a document and accept to match not all the keywords

What approach would you use?

Would you keep you index in internal memory or external memory

Consider this a classical question for IR and the source of infinite discussions for the community. What is the most reasonable answer?

Prime numbers that are pairs

A couple of pairs prime numbers is made up of two prime numbers that have distance 2 (e.g. (2,5), (5, 7), (11, 13)). How would you generate all the couples of pair prime numbers?

In how many ways can 2 sorted arrays of combined size N be merged?

meaning n+m = N

Build a caption for a document

Given a query Q made up of p keywords Q = k1, k2... kp and a text T find the portion of text which mimize the distance among words. What is the complexity?

Note that this algo is used by search engines to build the snippet provided as an answer to Q and for highlighting word.

News Clustering is live in US and FR

News ClusteringV2 is live in U.S.. This is a result of a wonderful collaboration among Beijing, Bellevue and London. London provided the core clustering algorithm, which is language agnostic and scales to multiple markets.

What happens when there is no collaboration: no good recipes

A couple of days ago, Google launched a nice recipe search engine where you can search for specific ingredients and get a selection of recipes. This product is very similar to the recipe engine developed by Ask.com three years ago as a result of a collaboration of three offices Pisa, in Europe, Piscataway in New Jersey and Oakland in California.

Unfortunately the first recipe engine suffered a lot of internal fights among different groups aiming at getting the ownership of the product. As a consequence, the quality of the product suffered because the original team was fed up about the political implications of those fights. That was a good lesson learned for the future and something I wanted to share with the readers of this blog.

Competition is outside and it is huge. So tell me: why there are inside fights? Don't get me wrong, competition is always good provided that the rules are fair and that the judges are not part of the competition. Otherwise it becomes just destructive.

Similar images

Given an index I of images and an M image, devise techniques for matching similar images in the index.

A good book to read if you are in DM: "Ensemble Methods in Data Mining: Improving Accuracy Through Combining Prediction"

Ensemble Methods in Data Mining: Improving Accuracy Through Combining Prediction is a book that I definitively recommends if are interested in latest data mining trends.

A couple of years ago, I got fascinated by the simplicity of Adaboost algorithm and the amazing performance it offers for mining quite different sets of data. Adaboost is based on a very simple intuition: you start with a very simple and naive classifiers and then you improve the performance with boosting techniques. After that, I started to read papers about RandomForest, Bagging, Mart and many other boosting methodologies but I felt the lack of an unifying approach and description of all those techniques.

Ensemble Methods in Data Mining: Improving Accuracy Through Combining Prediction offers this view by giving a description of the ISLE framework in a very synthetic yet detailed exposition. Great work!

Given a stream of items, select the k more frequent.

This is a nice problem to solve and a quite fascinating solution thanks to Vitter.

Interval with same sum

Given with two arrays A and B, each of size N where the elements of array contains either 1 or 0 we have to find such an interval (p,q)(inclusive) such that the sum of all the elements of A in this interval and sum of all elements of B in this interval is equal.

Given points in 2d space separate in two regions with approximately same amount of points

In other words, how to extend the median idea from a segment to a 2d space with n points within?

Serialize a generic tree

Area for historgrams

You are given an array representing heights of bars for an histogram. Find a rectangle in this histogram that has the maximum area.

Three lists

Given three lists: A, B and C of size N. Write a function which returns true if any 3 three numbers (1 from each list), sum up to K. False otherwise

Autosuggest is live in Italy, spain, and France Canada

We finally are live in 8 markets and 5 languages with geo-located aggregation, ranking, and filtering. This is really an amazing result achieved by my team

Spell check problem

Given a dictionary find out if given word can be made by two words in dictionary. For example "spellchecker" is composed by "spell" and "checker". How can you detect it in efficient space and time?

Sets intersection, union, membership

Given a set S1 and set S2 how can you estimate the intersection, the union, and the existence of at least one element in common. Assume that S1 is very large AND/OR S2 is also very large that they cannot fit in memory and you accept to have an approximate solution.

boxes: store them in minimal space

You have a set of n boxes, each one has dimensions (x, y, z) and you want to store them in minimal space. How do you proceed?

Product at least k

How will you find the subarray whose product is at least k in an array of negative and positive numbers

Element that appears p% of times

You are given an array A of non unique elements and size M. Find an element that appears p% of times.

A feature suggestion to Spotify and Facebook (and youtube)

Spotify is probably one of the most useful social application so far. Here social means Facebook, even if there is a limited number of activities you can make on Twitter too. The number of social features available is amazing: I can share my music with my friends, create collaborative playlists, listen to what they listen, publish my playlist to my social Friends, and so on and so forth.

But.. wait a second. Could this be a new way of expanding my social network? I'd like to be friend with someone who shares my musical interest. Facebook is suggesting new friendships because You and the potential new friend(s) are both both having one or more friends in common.

So what about suggesting new friendships because You and the potential new friend(s) are both having similar musical interests? This would be an interesting new signal for making new friendships.

I wonder if this principle can be applied in other contexts as well...

Hey Youtube, I have one idea for you...

Processes and Processors

A process P_i has a e_i execution time, and must start at time t_i. The process can start just if a processor is available. There are PR processors in your systems and N processes P_i. Give an algorithm to test whether an execution is possible.

Facebook usage of HBase and Haystack

This interesting video explains how Facebook uses Hbase for storing messages, email, etc. Hbase is a very good general purpose storage supporting fault-tolerance, replica and self balance. HBase is a public domain solution similar to google Hbase. So in a sense, Facebook is leveraging Google old ideas. Also, they are using an internal solution Haystack for storing attachments. Haystack is also used for the image product.

Secret references, A feature suggestion to my Friends in Linked

LinkedIn is a wonderful social community for building your professional network, finding talents, and being contacted by tons of recruiters. One feature that is generally considered useful is "Recommendations" where your business partners, your colleagues or your manager can send a public recomendation about your experience, skills, and professional results based on their direct past work relations established with you.

This feature is useful but it's main problem is that all the references are public and people tends to coalize and quite soon they start sending multual bragging and very often exagerating their own capabilities. Therefore, it is sometime very hard to make a distinction between a good and a bad (or exagerrated) reference. How to solve this problem?

If you think about how "References" work in real life, you soon understand that we have a different mechanism in place. When I want to hire someone, I ask the candidate to provide the name of three anonymous refereers. Then, I contact the referees directly and their authoritativeness together with the secreteness of the communication will allow me to judge the quality of the candidate with no risk of listening to exaggerated bragging.

So LinkedIn, how about having a similar feature? I would pay for it. Give me a way to ask for secret refeerees and a way to communicate with them in a private manner.

Thanks

Instant Twitter: can I follow who is around me?

I like the idea of followers in Twitter. I can follow my friends, celebrities and influencial people and other people can also follow me.

Not sure whether there is already a similar social service out of there, but I woul like to have a way to instantaneously communicate with the people around my geo-location that are willing to listen.

I believe that this would be an interesting feature for establishing new friendships around a place (e.g. a pub, a bistro, a disco, and so on and forth), or for getting help when I am in new area. Probably, there should also be a way to tag annoying people and for switching this feature on and off.

Doe anyone know whether there is already such social service?

A feature suggestion to Facebook: Let my friends tag their messages, we have multiple interests.

I am a voracious user of Facebook News feed, where I receive messages from selected friends and updates from groups and pages that I like. Anyway, I believe that this service is currently working like old black and white colour TV. I can either decide to receive messages from a given friend (white colour), or decide to not receive them (black colour). Surely, Facebook is adopting quite sophisticate ranking algorithms for deciding whether messages coming from a specific friend that I like a lot should have a better position than the messages from a friend that I like a bit less. Nevertheless, there is no explicit way to differentiate among different types of message produced by a specific friend. This world is not having multiple colours, but just two.

In reality, people have multiple interests (or multiple colours). I could be very much interested in following all the messages coming from my friend Alice about latest cool technological gadgets, but not very interested in getting all her messages about recipes. Anyway, Mandy can have a lot of interest in recipes and zero interest in all the Alice's postings about gadgets. Alice has multiple interests and they should be expressed by the way of multiple colours. How to solve this problem?

How about to adopt a social solution? Let anyone posting a message annotate it with one more more tag ("recipes", "gadgets", and so on and so forth). Let anyone receiving a message express a like for that specific tag. This combination can be used by Facebook ranking algorithms as a powerful signal for expressing my willness to receive more and more messages about a specific topic (and less messages about a topic that I never liked).

How to create new topics? Well again a social solution. First, suggest a list of popular topics "as a I type", because I am lazy and I want to reuse meaningful tags already produced by my social graph. Second, simply allow the creation of new tags when no satisfying match is found. Each tag is a new colour and this world can therefore become a full HD colour TV.

How to select the topics that I like? Well again a social solution. I should be simply be allowed to "Like" that tag and this is an explicit signal to Facebook.

So Facebook can I have this feature?

Thanks

Longest subarray with sum less than K

Given an array of integers find the longest subarray with sum less than k

find the longest palindromic substring.

Given a string, find the longest palindromic substring.

The node in the middle

There is a binary tree in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path between x and z.

Skip lists

Given an array of integers, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array.

PS: In IR these are the skip lists, can you devise an quadratic algo? how about a linear one?

Find a good sample of a query log

You have a stream of queries (infinite, meaning no way to hold all of it in memory). The stream follows a power law. Find a good strategy to sample the stream giving "a good" representativeness to both the tail and the head of the power law.

Find the top K elements in an hash

You have an hash (key, value). Find the top-K keys with largest value.

Google, Bing, and web browsing data

Not fair to talk , but decided to mention this interesting posting by the way of Greg. It is also quotede below. Thanks Greg was my pleasure to quote you.

"

I suppose I should comment, as everyone else on the planet has, on Google's claim that Bing is copying their results.

My reaction is mostly one of surprise. I am surprised that Google wants this issue discussed in the press. I am surprised that Google wants this aired in the court of public opinion.

Google is trying to draw a line on what use of behavior data is acceptable. Google clearly thinks they are on the right side of that line, and I do too, but I'm not sure the average searcher would agree. And that is why Google is playing a dangerous game here, one that could backfire on them badly.

Let's take a look at what Google Fellow Amit Singhal said:

This experiment confirms our suspicion that Bing is using some combination of:

• Internet Explorer 8, which can send data to Microsoft via its Suggested Sites feature
• the Bing Toolbar, which can send data via Microsoft’s Customer Experience Improvement Program

or possibly some other means to send data to Bing on what people search for on Google and the Google search results they click.

Of course, what Amit does not mention here is that the widely installed Google Toolbar and the fairly popular Google Chrome web browser send very similar data back to Google, data about every page someone visits and every click they make. Moreover, Google tracks almost every web search and every click after a web search made by web users around the world, since almost every web search is done on Google.

By raising this issue, Google very publicly is trying to draw a particular line on how toolbar and web browsing data should be used, and that may be a dangerous thing for Google to do. The average searcher, for example, may want that line drawn somewhere other than where Google might expect it to be drawn -- they may want it drawn at not using any toolbar/Chrome data for any purposes, or even not using any kind of behavior data at all -- and, if that line is drawn somewhere other than where Google wants it, Google could be hurt badly. That is why I am surprised that Google is coming out so strong here.

As for the particular issue of whether this is copying or not, I don't have much to say on that, but I think the most thought-provoking piece I have seen related to that question is John Langford's post, "User preferences for search engines". John argues that searchers own their browsing behavior and can reveal what they do across the web to whoever they want to. Whether you agree or not with that, it is worth reading John's thoughts on it and considering what you think might be the alternative.

Posted by Greg Linden at 10:50 AM"

Given a function producing random numbers in the interval [0, X]

Given a function F1 producing random numbers in the interval [0, X] with uniform probability, build a function F2 producing random numbers in the interval [0, Y] with uniform probability. How many different solutions can you find to the problem?

Give a test of symmetry for a generic tree

Write a C code for understanding whether a tree is symmetric. This is a classical interview question, where the attention is to the programming details AND the ability to make induction reasoning.