Wednesday, June 30, 2010

Post office

The post-office location problem is defined as follows. We are given n points p1, p2, ..., pn with associated weights w1, w2, ..., wn. We wish to find a point p (not necessarily one of the input points) that minimizes the sum , where d(a, b) is the distance between points a and b. Any strategy?

Tuesday, June 29, 2010

Airline passengers

A line of 100 airline passengers is waiting to board a plane. They each hold a ticket to one of the 100 seats on that flight. (For convenience, let's say that the nth passenger in line has a ticket for the seat number n.). Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. All of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. If it is occupied, they will then find a free seat to sit in, at random. What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?

Monday, June 28, 2010

Quicksort is O(n log n) in average. How about worst case?

Surprisingly enough, there are still people who are not aware that Quicksort is O(n log n ) in average. How can we make it O(n log n) in the worst case?

Sunday, June 27, 2010

Saturday, June 26, 2010

Fit a set of (x,y) data points to a rectangular display

You are given a set of datapoints (x, y) with 0<x<N, 0<y<M. Try to map them in a rectangular display of size [0, S] x [0, T] with S<N and T<M. Make your own assumptions.

Friday, June 25, 2010

Facebook going search mode

Web Search is all about crawling, indexing and ranking external pages. Facebook is bringing the pages inside the site. Is this a new search dimension? yes it is.

Thursday, June 24, 2010

Wednesday, June 23, 2010

Sum to X

Given a large file, having N (N is very large) positive integers, how will you find a pair of numbers that add up to x.

Tuesday, June 22, 2010

Bing Products in Europe

One here and all the brothers here. Some of the works carried out by our group in London in the past 10 months. This in collaboration with Bellevue, Beijing, Hyderabab, and Munich

Monday, June 21, 2010

Sum to 0

Given three lists: A, B and C of length n each. Write a function which returns true if any 3 three numbers (1 from each list), sum up to zero. Else return false, if there is no such combination.

Sunday, June 20, 2010

Part III: getting the name of your location via geonames.org

Geonames.org provides an API for accessing geolocal information. For instance, given a latitude and longitude you can access the name of the closest geographical location. One problem I faced is the need of accessing geonames with a javascript code downloaded from my own server. This is traditionally prevented by XMLHttpRequest which is constrained by the Same Origin Policy. Therefore, I reverted to JsonRequest that supports safe cross-site communication. Luckly, Geonames supports JSON web service requests.

Here is the code
function processLocation1(jData){
if (jData == null) {
// There was a problem parsing search results
alert("Error parsing geoname data");
return;
}
locationData = 'just arrived close to ' + jData.geonames[0].name + ' in ' + jData.geonames[0].adminName1 + ', ' + jData.geonames[0].countryName;
}

function geonameRequest(request){
// Create a new script object
aObj = new JSONscriptRequest(request);
// Build the script tag
aObj.buildScriptTag();
// Execute (add) the script tag
aObj.addScriptTag();
}

function reverseGeonameLookup(){
var request1 = 'http://ws.geonames.org/findNearbyPlaceNameJSON?lat=' + lat + '&lng=' + lng + '&callback=processLocation1';
geonameRequest(request1);
}

Thursday, June 17, 2010

Wednesday, June 16, 2010

Part II: Getting your geo location and pointing the correct Bing Map

This is the easiest part, since modern HTML5 supports Geocoding identification in a native way. The javascript code is as easy as it follows:

function showMap(position) {
lat = position.coords.latitude;
lng = position.coords.longitude;

}

function getLocation() {
if (navigator.geolocation) {
navigator.geolocation.getCurrentPosition(showMap);
} else {
error('not supported');
}
}
The showMap(position) is a callback function used as soon as the browser identifies your location. Please note that this approach is currently known to work in Chrome, Firefox and Safari for mobile (e.g. Ipad and Iphone). It seems that other browsers will support geolocalization in the near future.

Once you have the location in terms of latitude and longitude you can find that point on Bing Maps using the Javascript Bing Map SDK. Let's see how to make it:

<script type="text/javascript" src="http://ecn.dev.virtualearth.net/mapcontrol/mapcontrol.ashx?v=6.2">
<script type="text/javascript">
var map = null; // the map object
var lat = null; // latitude
var lng = null; // longitude
var locationData = null; // string msg

function showMap(position) {
lat = position.coords.latitude;
lng = position.coords.longitude;
// load map
map = new VEMap('myMap');
map.LoadMap(new VELatLong(lat, lng, 0, VEAltitudeMode.RelativeToGround), 16,
VEMapStyle.Birdseye, false, VEMapMode.Mode2D, true, 1);
}
This will show yourself in a BingMap, in this particular case I used the pretty cool Birdseye style.

Tuesday, June 15, 2010

Monday, June 14, 2010

Phase 1: bulding a Facebook app

Facebook has a rich documentation site for building Apps. The only problem I had is that there are different layers of API which actually carry out the same operation, and so it is difficult to understand the one you want to use. First step is to register your future app and to edit it. Then, I used the Social plugin for Login, which is a trivial way for remote login and authentication in Facebook. The code is simply

<!-- login in facebook with extended perms -->
<fb:login-button autologoutlink="true" perms="email,user_birthday,status_update,publish_stream" faces="true"></fb:login-button>

This will use FB extensions to HTML, which must be activated before with an asynchronous initialization of Facebook javascript library (noticed the appId:, and xfbml:true down below
<script type="text/javascript">
window.fbAsyncInit = function() {
FB.init({appId: '117083285001944', status: true, cookie: true,
xfbml: true});
};
(function() {
var e = document.createElement('script');
e.type = 'text/javascript';
e.src = document.location.protocol +
'//connect.facebook.net/en_US/all.js';
e.async = true;
document.getElementById('fb-root').appendChild(e);
}());

This function uses the FB.UI Api call to publish on your facebook account
function streamPublish(name, description, caption, hrefTitle, hrefLink, userPrompt, thumb, urlThumb){
FB.ui(
{
method: 'stream.publish',
message: '',
attachment: {
name: name,
caption: (caption),
description: (description),
href: hrefLink,
media: [{ type: 'image', src: (thumb), href: (urlThumb)}]
},
action_links: [
{ text: hrefTitle, href: hrefLink }
],
user_prompt_message: userPrompt
},
function(response) {

});
}
</script>

Sunday, June 13, 2010

Facebook infrastructure and data


Very interesting presentation about Facebook by Aditya Agarwal, Director of Engineering
  • 8 billion minutes spent every day, 5 billion of contents shared per week, 3 billion photos per month
  • 80,000 applications use Facebook connect
  • 500,000 million user
Stack is made up of several components. The front-end is a PHP optimized with mem-cache and asynchronous communication, which has been replaced by a HipHop code transformer in C++. The service components is written in different languages and communicating by using Thrift, Scribe and some in-house components. Memcache is used to store in memory hash table and for caching mysql data or application generated data. Mysql is used to store data (key, value) and with almost no relational model (clearly no local relational join, since "tables" are distributed ;-). All the software they have contributed to the community is here

Saturday, June 12, 2010

Efficient dictionary

Given a dictionary of words D, find out the longest chain of 'ancestors' in it. Ancestors are defined in the following way: A word is said to be the parent of another word if (1) It is a valid word in D, (2) It can be obtained by deleting one character of the word and permuting the remaining characters.

What if we allow to delete k characters?

Friday, June 11, 2010

Where is the point?

Given a polygon and a point give an algorithm to understand where is the point with respect to the polygon

Wednesday, June 9, 2010

Vertices of a polygon

how to find two vertices of a polygon which are farthest from each other in linear time

Monday, June 7, 2010

Apple going OS?

IOS is the historical name of Cisco Routers OS, now Apple licenced it

Sunday, June 6, 2010

HTML5 is damn hot

HTML5 is not just a video player, is an amazing collection of API

HackaTon: 1 week, 1 hour, 1 social experiment with Html5, Bing Maps, Facebook, Geonames.org

Last week I had one week of vacation. So i started a social experiment. Every day, I coded for 1 hour. Time is the key for programming and I believe that 7 hours are a very long release cycle. Those are the rules:
  1. I want to make something social. And I when I say social, I mean sharing on Facebook. Social is a so catchy and meaningless word, these days;
  2. I want to make something with geolocatization. I heard that HTML5 made a great progress on that side and I know that Bing Maps are pretty cool;
  3. KISS mode must be on;
  4. Everything must stay on the client, keep it small keep it fast. Code is public, since is just javascript;
  5. I am starting an Mashup HackAthon, send me your contribution and I will post it.
So the result of my little hackton is an application. It geocalizes you with your HTML5 browser. Then, it accesses geonames.org for getting the name of the place where you are. Then, it gets your position on a 3D Bing Map. Then, it posts your position, your map, your comment on your Facebook profile.

During the next days I will comment the code here. If you want to test it, this is the result after 7 hours of coding. Crisscrossy.com (you must use a browser with geolocalization support)

Saturday, June 5, 2010

Mysql vs Cassandra: or SQL vs NoSQL

A very interesting article here:

A new generation of low-cost, high-performance database software is rapidly emerging to challenge SQL's dominance in distributed processing and Big Data applications. Some companies have already traded SQL's rich functionality for these new options that let them create, work with, and manage large data sets.

A big reason for this movement, dubbed NoSQL, is that different implementations of Web, enterprise, and cloud computing applications have different requirements of their databases. Not every app requires rigid data consistency, for example.

Friday, June 4, 2010

Why I like the Ipad, and why i don't like the App model

So I bought an Ipad. I must confess that I like it. Disclaimer: I don't have any apple stock right now. You know "sell in May...". Disclaimer: I don't have an iphone, at the moment. I bought it, the model 1 in new york city, two days after the first launch -- and I bought also some stocks at that timet. I played a bit with the SDK, and was all but easy to program with a lot of features disabled by choice (e.g. no multi-thread, no video, erghhh!). I never felt in love with the Iphone, but I predicted his amazing success -- at least 20 people can confirm it. I made my money for that prediction and I built some apps just for fun.

Now I tell you, I love the IPad and I predict an amazing success. First at all, the battery lasts for 9-10 hours. Second, there is a pull mode that download content offline. Third, display is amazing: you can read your newspapers, watch your movies, browse the net, email, a keyboard that is working with my big fingers. Still video is not there. And is quite expensive. Anyway, this will be a blast. Apple will release new versions with little additional features just to sell more devices.

Anyone is about Apps right now. Like anyone was about corba, 15 years ago. Like Web 2.0, 5 years ago or The cloud, just yesterday.

Can I say? I don't like the app model. I know you can make a lot of money out of it. And a lot of devs are happy because they can participate to this new golden age. The claim is: "There is an app for that", anything you need to do.

Well my question: "how can i find that app?". You need to find an app for finding things. There is an additional level of indirection to go in a cage.

And it is not easy to find that app. Should we have a search engine for that?

Thursday, June 3, 2010

Unique elements

Take an array and return same array with only unique elements in it in o(n) .

Wednesday, June 2, 2010

Top 1000 Sites on Web

Facebook is 1st with an impressive 540M unique users, then Yahoo, Live (for email), Wikipedia, Microsoft. Google omitted themself from its own list

Tuesday, June 1, 2010

Array Increment Problem

Given an array A consisting of 'n' elements. Do the following both operations in O(log n) time using a data structure.

Increment (A,i,j,x) : This should increment elements from A to A[j] by value x .
Report(A,j) : This should report A[j]

Trivially in an array Increment takes O(j-i) time and report takes O(1) . Now we need to store in a data structure (can be augmented) such that both operations takes O (log n) time.

(Interesting data structure for this one http://en.wikipedia.org/wiki/Segment_tree)

Google goes Ad Mobile

Several days after the Federal Trade Commission closed its investigation into Google's acquisition of AdMob, Google said Thursday that it has also closed its acquisition and is the proud new owner of a mobile ad network.