Tuesday, November 30, 2010

A classical one: find the element which appears 5/8 of times

Given an Array A, with very large size N find the element which appears 5/8 of times.

(this is a classical must solve// know problem)

Monday, November 29, 2010

Out of Band but interestingç "Microsoft Gives the Cloud to Scientists"

http://bits.blogs.nytimes.com/2010/11/17/microsoft-gives-the-cloud-to-scientists/?src=tptw

"Microsoft has hit on a direct path to university researchers’ hearts and minds: give them free tools and easy access to huge data sets.

The software maker has started grafting popular scientific databases and analysis tools onto its Windows Azure cloud computing service. This basically means that researchers in various fields can get access to a fast supercomputer of their very own and pose queries to enormous data sets that Microsoft keeps up to date. For the time being, Microsoft will allow some research groups to perform their work free, while others will have to rent calculation time on Azure via a credit card."

Disclaimer: I work for Microsoft

Sunday, November 28, 2010

A classical one: a triangle and a point

Given a triangle ABC and a point P, device an algorithm for understanding whether P is inside or outside the triangle.

PS: sometime you forgot old geometry, but this problem is simply a generalization of a point P and a segment S. Is the point above or below S?

Thursday, November 25, 2010

Friendship and Polymorphism

I was using this for my interviews. Now no more: Can you explain the use of friendship and polymorphism?

Monday, November 22, 2010

Exchange coins

A classical DP problem: you have a set of coins in your currency. If one coin has a value of n, i will exchange it with coins in my currency of value n/2, n/3, n/4. What is the best exchange strategy for you?

Sunday, November 21, 2010

Serialization and deserialization

Google has a nice alternative to boost::serialize. Those ProtocolBuffers are a good way of marshalling data structures over the wire.

Saturday, November 20, 2010

Friday, November 19, 2010

Everyone is allied to someone

Yahoo made an alliance with Bing, Ask.com apparently made an alliance with Google, and now Myspace made an alliance with Facebook. Also, Bing is allied with Facebook. Isn't that what they call market consolidation?

Wednesday, November 17, 2010

Arrays comparison. don't always sort them.

Two arrays are given A[n] and B[n+1]. Array A contains n integers and B contains n+1 integers of which n are same as in array B but in different order and one extra element x. Find x.

Tuesday, November 16, 2010

Facebook is opening read-only the Message service

The OpenGraph API for google is becoming richer. They just launched the new Message service and decided to open read only the Message inbox via an API. So what products do you believe we need to develop over this API?



Interestingly enough, Message works on the top of HBase

Monday, November 15, 2010

Looking for a new ads major paradigm shift (part I, where we are)

Search ads is the business of selling paid links, together with a short description of the destination sites. The price of the ads is decided by means of an auction where advertisers bid for position and pay just enough to beat their runner-up. When the user submits a query, a set of related paid ads are served together with the search results, and the bidder pays a cost if the ads are clicked (pay per click). For Google, this business has a value of about 5.8billions per quarter. Bing has a proportional business value. Probably, you are thinking.. I already know all this stuff, what is new? Nothing is new, I just want to analyze the above scenario under a different perspective.

We have hundreds of millions of users producing zillions of web pages, blogs, real time updates, and so on and so forth. Then, search engines index this content and serve search results, when users submit relevant queries. In addition, search engines serve commercial ads together with the indexed content. Now, why the content producers receive no money for their content? After all, if there no content then there will be no index, no search results and no commercial ads.

You may say ... well your analysis is partial since commercial ads are not the only way to monetize the content. Another element to consider is the traffic sent to the content producer by the search. Fair enough. This observation is certainly pertinent. However, receiving traffic is very much important for commercial sites, but is not necessarily the same of getting direct money.

For instance, say that I love the music of the 80s. This is my hobby, and so I write about it. I would be interested in receiving some traffic for content produced for this hobby. Anyway, I would be more happy to get some direct money anytime that my content is accessed by using a search engine. After all, the search engine has probably served some commercial ads together with the index built on the top of my content (and on the top of the content written by other similar content producers).

Nowadays, A similar mechanism is missing .. and I am not sure why? Would you consider it a new ads major paradigm shift? And could it be a pair with a new search major paradigm ?

Sunday, November 14, 2010

Friday, November 12, 2010

Personalized Facebook Autosuggest. I like it.

Facebook is quietly doing an amazing work with Autosuggest. Until a couple of days ago, Autosuggest was a method to find People. Now it’s a true personalized search tool where Facebook is injecting articles posted by your friends (see below on the left), Wikipedia pages (see 2nd result below on the right), question and answers (see 3rd result), Facebook pages (4th result). I believe that the experience with Facebook is potentially more exciting that the one exposed in Google Instant. Apparently, they are trying to move away from the SERP paradigm.



Update: they also have Web pages where users expressed a "Like it". So they are effectively crawling them (or at least leveraging the "Like" anchor). Is Facebook starting to become a true search engine?

Thursday, November 11, 2010

Bing, if you want to play a role in algorithmic search

TO: my ex-colleagues in Ask.com and my friends in Yahoo!. Bing is hiring.

There are just two players with algoritmic search out of there. Search follows fractal geometries. You can take advantage of your experiences and, by learning and generalizing, you can anticipate and recognize problems with similarities :)

Wednesday, November 10, 2010

Stock had a 40% increase last year, IAC's Barry Diller Surrenders to Google, Ends Ask.com's Search Effort

IAC's Barry Diller Surrenders to Google, Ends Ask.com's Search Effort. A first glance, this is strange for a company where "Search represented nearly half of revenues ($205 million). The search business grew 20 percent, goosed primarily by a 55 percent increase in active toolbars to 97 million. IAC’s toolbar business is its secret distribution weapon, but those searches tend to generate lower revenue per query than those on Ask.com, which itself is still growing and is now ranked as the sixth largest website in the U.S”

Tuesday, November 9, 2010

Repeating numbers

All numbers in an array repeat twice except two numbers which repeat only once. All the numbers are placed randomly. Find out efficiently the two numbers that have not repeated with O(1) extra memory.

Monday, November 8, 2010

Find the min difference among two numbers in an Array

Given an array of n integers A, find the minimum difference between two numbers in A. It's easy to make it in O(n log n). Can you make it in O(n)?

Sunday, November 7, 2010

Store the file and save space

A file contains a number of repeated but not consecutive zeros. Can you read and store the file such that you save space, but you still can reconstruct the original file? Please C++ code.

(PS: this was an old interview coding question, which I am not going to use anymore)

Saturday, November 6, 2010

Database of queries and similarity

You are given a database of queries Q, with 100 millions of queries. Given a query q return all the queries that have a similarity of 50%. Make your own assumptions and write some C++ code for that.

Friday, November 5, 2010

sharing lists.

Given 2 linked lists find intersection point(s) in the form of X (so the lists share only one element), or Y (so the lists share more than one element). How many other shapes can you have?

Thursday, November 4, 2010

Find two numbers in an unsorted array

Given an unsorted array A find two numbers a, b in A such that a - b = x. In linear time!

Wednesday, November 3, 2010

Alice and Bob play with an array

Alice and Bob play with an array of integers. In turn, each one can pop a number from one of the two ends of the array. What strategy can be used to maximize the sum of popped integers for Alice?

Tuesday, November 2, 2010

News Personalization

Greg, do you mind to comment on this one?
I am really interested in your opinion
http://www.projectemporia.com/