Thursday, June 30, 2011

My circled view

Maybe it's just me but I consider Facebook my public persona and my email my private one. Not sure that I need a semi-public version. What I really need is a way to filter what I receive non just what I send. Indeed, I banned some of my friends (ops can I say that?) who are sending certain types of updates (e.g. one farmville or horoscope and you are out and rules like that). Also, I am using temporal order for my news updates and I know from friends inside facebook that I belong to a very small number of users who have this behaviour. I asked whether I can ban someone but still receive periodic updates now and then just for exploring but this is a low prio feature.

Do you want to have in-circle? or out-circles? how about triangles?

Wednesday, June 29, 2011

How would you store a symmetric matrix?

Old question just to start with: give me an estimate of the space used.

Tuesday, June 28, 2011

Bing overtakes Google News in UK

"Interestingly Bing's news aggregation service has zoomed past Google's, at least in the UK, according to the survey of 50,000. It's had a growth spurt of 141 percent since May last year, while Google News' readership has fallen by 56 percent."

Very proud of my team's achievement and my thanks to our colleagues in Beijing for this wonderful result!

Bing overtakes Google News in UK

Monday, June 27, 2011

Sequence of numbers. What is next?

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211 . What is the next in sequence? write the code to generate the sequence.

Sunday, June 26, 2011

Encode the move of a knight on a chessboard and check for all the cases

What data structure are you going to use?

Saturday, June 25, 2011

Renting a car

I own my car and I want to rent it. I receive all the orders in advance, where an order is made up of a triplet (starting time, ending time, offer in money). I want to maximize the revenues.

Friday, June 24, 2011

diagonals and interior points for rectangles

You are given a R rectangle  a x b of integer size. Each rectangle contains unit blocks, consider the diagonal and count how many blocks c are touched by the diagonal. Given a value K how many rectangles have exactly K block touching the diagonal?  here an example

I found this problem online but was not able to solve it so far

Thursday, June 23, 2011

Find the minimum window of text containing all the words in a query string

Given a query Q = w1, ... wt made up of t words in AND and an Index of text I, rank the documents contained all the words in I by minimum length of window matching the words.

Wednesday, June 22, 2011

Nick is going to parties

Nick loves to go to partieeees, but he has budget constrains. It has a list of parties, and for each party he knows the cost and the expected fun. How to maximize the fun and keep the cost under a prefixed budget C?

Tuesday, June 21, 2011

Serialize binary tree

We have a tree  where leaves are represented with ‘L’ and non-leaf with ‘N’. Each node has either 0 or 2 children. If given preorder traversal of this tree, construct the tree.

Can you use this as basis for serializing a generic tree?

Monday, June 20, 2011

Find the sum of all the nodes in a level

Given a tree T where each node contains a positive integer, find all the sum of the nodes at the same level and print it.

Sunday, June 19, 2011

Serialize a binary tree

compare different solutions both from space and time point of view.

Saturday, June 18, 2011

maximum in an array

You are given an array of integer A[1..n] and a maximum sliding window of size w. you need to output an array B where B[i] is the maximum in A[i, i+w-1]. Optimal complexity?

Friday, June 17, 2011

Find duplicate profiles in Facebook (part of the problem is to define what a duplicate is).

Thursday, June 16, 2011

Google News shifts away from clustering and toward personalization. ([1] [2]), Thanks to Greg

Tuesday, June 14, 2011

Prefetching pages

Google is integrating pre-fetching of search results. This was a feature already available in many browsers. Personally, I had concerns about this feature: how can you guarantee to save bandwidth? how can you have a consistent analytic on the target sites and avoid to artificially inflate stats? how can you guarantee that ads shown on the target pages are real and not just coming from artificiallly pre-fetched pages that no one is really looking at?

Sunday, June 12, 2011

Stream and running median

You have a stream of random numbers that are inserted into an expanding array. How can you maintain the current median and what is the complexity.

PS: solved it with two heaps, but not sure whether this is the best approach

Thursday, June 9, 2011

And the party version

Completely useless and waste of time ;-)

Wednesday, June 8, 2011

Back in a future, Google or Backrub in 1996

When everything started. I found this link and I believe it is fascinating. They were already working on clustering.

Tuesday, June 7, 2011

Equal values of 0s and 1s

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. In linear time! tricky but funny

Monday, June 6, 2011

Find all the permutation

Given a telephone number, find all the permutations of the letters assuming 1=abc, 2=def, etc.

Sunday, June 5, 2011

Playing with tries and errors

We just launched this new "spell as you type" product for Bing in Int'l markets. Question: how would you implement the below data structure and what would be your search strategy?

Saturday, June 4, 2011

Algo is nothing without Data

sometime data can follow interesting paths, and data can be automatically generated

Friday, June 3, 2011

Mapping Facebook Faces to Bing Maps

I made it just for fun and for playing with different APIs. Check how to map facebook faces on bing maps

Thursday, June 2, 2011

From list of lists to list

Given a linked list structure where every node represents a linked list and contains two pointers of its type:
(i) pointer to next node in the main list.