London Software Development Engineer Job

http://www.microsoft-careers.com/job/London-Software-Development-Engineer-Job/1468397/

London Software Development Engineer Job

www.microsoft-careers.com

London Software Development Engineer Job

Given a set of integers select the minimum set with sum greater than k

Complexity? here is the code

A request for facebook: Let me use my timeline and change the timings

Other quick suggestion: it would be useful to allow a fine tune for 'created_time' for each post. This would be particularly useful for pictures. I may want to upload pictures from my past memories in my timeline so that their creation time should be back in the past. just my 2c

Microsoft Research

Microsoft Research is an immense asset for Microsoft. Really like that several Research guys are a driving force for Bing (including Harry Shum, Paul Viola, Susan Dumais and many others)

http://research.microsoft.com/en-us/um/redmond/about/timeline/#/1991/

A request for facebook: open the location API

Facebook recently allowed to tag postings (e.g. status, pictures, and so on and so forth) with locations. Anyway, this information is not available via the OpenGraph API, as discussed here and here. Can we have it?

Discover anagrams in a collection of strings

here the old style c-only version code . Ok that's was a wild journey back in the past, here the more modern version of stl code

A great tool for developing with Facebook

This is useful for exploring the OpenGraph and this is useful for building apps.

Max sum of a subarray of integers

This is the classical kadane's algorithm and it's always a pearl to study.  A couple of key observations: (1) the empty subarray has sum 0, and this is the minimum. (2) We can maintain a running sum and when we go negative we start again with the empty subarray

So

max_so_far = max_ending_here  = 0;
for (i  = 0; i < A.size(); i++)
{
   max_so_far = max (0, max_so_far+A[i]);  /// if we get negative, consider the empty string
   max_ending_here = max (max_so_far, max_ending_here);
}

Tranform a BST into a double linked list, no recursion

Here is the code

Shipping that feature one day before of Facebook

I had the impression that the feature was useful and so we worked on Picplacer.com (see my posting
Places where you and your friends have been: Geo-tagging your Social Pictures) and i was not aware that Facebook was working on something similar.

So we shipped one day before the f8 and that day Facebook shipped something similar as you can see from my timeline here below. This is apparently based on my pictures and the tag you have in your mobile phone. It seems that you cannot see the pictures from your friends around a place.

Woahhhhhh, nailed it. One day before

Mantaining intervals and looking for a number

You are given a number a and a sequence of numeric intervals  ( .., ..) . What data structure would you use for searching the number in the intervals? What if they are overlapping?

Places where you and your friends have been: Geo-tagging your Social Pictures

Sharing your pictures with your friends is an important part of your social activities, and a killer application for Facebook. Anyway, I thought that something was missing for that feature. During a recent journey to Ibiza, I said to myself: "Hey it would be cool to see the pictures of my friends who have been in this place before?" So I went to Facebook and was looking for a way to search the places where me and my friends have been.

Surprisingly enough, that feature was not there. I said "uh! let's change that". So I work for Microsoft, but I also like to play with other players' API during some off-work long night programming sessions. I said: "maybe I can create a mash up using Bing Maps and Facebook API. Let's start with something simple and map the face of my friends over a Bing Map". That worked and was fast to implement.

So I involved my old-friend Mario Veri and exposed the idea: "Why don't we let the user tag their own images and show them on a map?", which he liked. I said to him: "we will just spend couple of hours per night but let's make it and let's change what is missing in Facebook". So, we worked for a week or so late at night with the target of having the first PROTOTYPE (a beta!) before the F8 conference. A lot of strawberries (for me),  coffees (for mario) and code written we are now happy to introduce to picplacer.com

An image is worth a thousand words, and an image with the correct geographical context is probably worth more! What can you do with picplacer? Let's see:

You can load your facebook albums, select a specific picture, and associate this picture with a geographical place. Picplacer.com runs on the top of giants' shoulders and will search the appropriate information from Facebook and Bing on your behalf.

You can drag and drop the picture so that you will fine tune the position of the image in the map. You can even zoom in and out according to your needs.

You can see what you have shared on facebook and tagged in Picplacer for the whole world or for a specific geographical area

And we are actively working for adding the possibility to show the public pictures that your Social friends have shared for a specific place. But this will probably require another week of work late at night with strawberries and coffees (we already have that information and we know how to use it).

Send more coffees, strawberries and suggestions if you want to see more or if you have an opinion. We are going to add that missing search feature in Facebook and allow you and your friends to search and see the places where you have been.

Antonio & Mario

DISCLAIMER: Antonio works for Bing Microsoft in London and Mario is an ex-student of mine. Picplacer is a mashup that me and Mario have developed just for fun and is not rappresenting any official Microsoft or Facebook initiative. It's something we made just for fun and for our own pleasure to experiment with fast prototyping and making an impact. That's it.

NOTE: you probably have seen something similar with Footprint for Android,  Photos for Iphone, and Panoramio or Flicker on the web. Anyway, those are apps or web sites for mapping pictures on a map but there is no Social aspect there (where are your Social friends?) and they are not running on Facebook the place where you already are sharing your own images. We just wanted to connect the dots...

Mobile Social payments, Facebook, Skype and Google Wallet

I already posted about using Social Graphs (either Facebook or Skype) for making mobile payments and transactions. See my postings "A feature suggestion for Skype: turning skype in a cash-cow machine for mobile payments"  and Facebook Social Wallet. The idea is to use Facebook Login (or Skype Login) and transfer Facebook/Skype credits from one account to another in a secure way (see the postings for the details).

Today. Google announced their Wallet based on a chip in your phone where they store the credit card.  Technically, I don't quite understand why you need a brand new phone with a special custom chip on it.

Why this should not work with already available mobile phones (e.g. Android, Iphone, Windows mobile, RIM)?

Why do I need to buy a new phone for accessing the Wallet? As described in the postings, I propose to just use either Skype or Facebook. Both of them are already running on all the mobiles  available on the markets.

single linked list, reverse print it in linear time and constant space

Smart Lists and subscriptions are the gateway for Enterprise Search

compute the k-th smallest element in a BST

what is the optimal complexity in time and space?

here the code

implement a deque using stacks

This  is a kind of "two snakes" game

1234

snake1      snake2

1 push

2 push
1

3 push
2
1

               3 push
     
               2 push
               3

               1 push       -> ready to pop
               2
               3


so push in 2nd stack if empty.

The beauty of SQRT(N) -- part II

Another good SQRT(N) trick can be applied to Lowest Common Ancestor (LCA) problem.

LCA
This problem consists in identifying the lowest common ancestor given two nodes in a tree. One way is to split the tree vertically in SQRT(H) parts, where H is height of the tree. So for each part, we should store the ancestor situated in the part immediately above. That is easy because the ancestor for each border section is the father of the section (e.g. the node at the frontier).

So assume that the node i, has father F[i], we can pre-compute an array P [1..N] as it follows

if (i is at first level) P[i] = 1   // first level
else if (i is at the border of one of the SQRT(H) partitions than P[i] = F[i]) // border
else (P[i] = P [ F[ i] ])  // any other node

So we have SQRT(H) partitions and the pre computation is linear. We use P for reducing the cost of LCA to SQRT(H) as it follows

 while (P[x] != P[y])          // different section
          if (L[x] > L[y])     // up with the longest
             x = P[x];         // up one section    
          else
             y = P[y];       // up one section
           
      while (x != y)           // same section 
          if (L[x] > L[y])     // up with the longest
             x = F[x];         // take the father
          else
             y = F[y];
      return x;

The beauty of SQRT(N)

Many quadratic algorithms can be "changed" into a linear version pre-processing sqrt(N) "points" so that the algorithm will be a linear one on the subset of selected "points". This is a typical trick adopted in clustering and in many other situations. Let's review some examples.

RMQ

Range minumum queries is the problem of finding the minimum value into an interval. A trivial solution is quadratic and can be computed with dynamic programming, by observing that the minimum for an interval with 1 number is the same number and that we can get the minimum for the interval [i, j] if we know where is the index corresponding to the minimum for the interval [i, j-1].

We can use the above trick and divide the interval in SQRT(N) intervals and for each of them precompute the minimum in O(N), then we can answer the query in SQRT(N) just by checking the overlapping intervals with the query -- those are no more than SQRT(N). So we will have

Machine learning from Stanford

Back in the late 90ies the first ML course @ stanford had less than 20 students. Next fall they will open the course for online students and more than 50K students (including me) have signed up so far. Consider the opportunity of adding yourself to the list.

http://www.ml-class.com/

Passing a parameter to a jasonp callback

jsonp is a quite popular paradigm for mashup and crosssite scripting. Sometime is useful to pass a parameter to a  jsonp callback. My solution is to encode the parameter in the name of the callback or to dynamically push functions with the parameter embedded in the code. The name of the callback will be a random string.

Do you have other solutions?

Interesting POVs on Yahoo

A Former Senior Yahoo Exec Emailed Us This Wish List For The Board Of Directors

Inside The Yahoo Mess: Meet The Winners And Losers

balance strings

Implement a function string which given a string s consisting of some parenthesis returns a string s1 balanced and the differences between s and s1 are minimum

here the code

Facebook Social Wallet

Facebook login became the universal login system. Plus they have a system for buying credits which they use for making transactions such as buying games and other items.

It would be interesting to expand this mechanism into a 'Social Wallet' for Social Payments. If a merchant has a facebook login than it can be recognized it in a trusted way. In addition, it would be possible to generate a unique number for each transaction in a way similar to what Paypal is doing today. In this scenario, there will be a set of merchants selling items in real life and using facebook as a payment system. The payment is nothing more but a facebook credit transfer (again similar to Paypal). Likewise, they can use Facebook to transfer social gifts,  game points, and other types of virtual objects.

The real power of this is that the system will be available for 700millions of users and it would work perfectly for micro-payments. Plus facebook is available on many different devices so it would possible to pay on phones, tablets, and PCs.

rotate

given a vector of ints rotate it by an integer k

here the code

implement strstr

int strstr (char * needle, char * haystack);

Google is shutting down several products and betas

Google is going to shut down many betas. Most notably, Aadwark was a very interesting semantical type of search and Google desktop was a very good piece of software.

Aardvark

Desktop

Fast Flip

Google Maps API for Flash

Google Pack

Google Web Security

Image Labeler

Notebook

Sidewiki

Google and Facebook growth

Compute the LCA for a BST

I really like this problem because it's an interesting application of recursion and it shows your attitude to code paying attention to the details.

A BST is a binary tree where the value stored in the left child is less than the value of the current node, which in turn is less than the value of the right child. This would allow to search for the LCA (lowest common anchestor) by leveraging the structure of the tree.

You visit the current node, if it's value v_current is within the range [v1, v2] and you are looking for v=LCA[n1, n2] then you return the value v  otherwise you move recursively left ( right ) down in the tree according if v_current < n1 < n2 (n1 < n2 < v_current, respectively)

here the code

visit a BST with no recursion

implement a getline

This is a typical situation when you deal with the TCP/IP stack. One underlying layer defines a blocking read which reads into a buffer. You need to use this read for implementing a getLine() which reads until \n. You can have multiple calls of getLine()

here is the code