## Friday, November 30, 2012

### Find all the permutations of an array A

## Thursday, November 29, 2012

### Find the lowest common ancestor

For a binary tree
for a binary search tree

## Wednesday, November 28, 2012

### Serialize and deserialize a generic tree

File * serialize (node * n);
node * deserialize (File * f);

## Tuesday, November 27, 2012

## Monday, November 26, 2012

### Isomorphic trees

Two trees can be called isomorphic if they have similar structure and the only difference amongst them can be is, that their child nodes may or may not be swaped. Write a function to detect whether two trees are isomorphic

int isIsomorphic(Node root1,Node root2) { if(root1==null && root2==null) return 1; if((root1 == null && root2 != null) || (root1 !=null && root2 == null )) return 0; if(root1.val == root2.val){ if(isIsomorphic(root1.left, root2.left) == 1){ return (isIsomorphic(root1.right, root2.right)); } else if(isIsomorphic(root1.left, root2.right) == 1){ return (isIsomorphic(root1.right, root2.left)); } } return 0; }

## Sunday, November 25, 2012

### Pascal’s triangle is a triangular array of the binomial coefficients

Method 1 -

Each line n is the binomial coefficient C(n, k) where k is the row. This has complexity n^3. because in this case k has the same order of n

Method 2

Complexity n^2, with space n^2

Method 3

complexity n^2, with space O(1) -- this is more difficult because you need to move in the triangle storing just a constant number of locations. Can you express C(n, k) as function of C(n, k-1)?

Each line n is the binomial coefficient C(n, k) where k is the row. This has complexity n^3. because in this case k has the same order of n

Method 2

Complexity n^2, with space n^2

Method 3

complexity n^2, with space O(1) -- this is more difficult because you need to move in the triangle storing just a constant number of locations. Can you express C(n, k) as function of C(n, k-1)?

## Saturday, November 24, 2012

### Compute the binomial coefficient in efficient way

C(n, k) = n ! / (n-k) ! k! = n (n-1) ... (n-k+1) / 1. 2. ... (k-1)k

C(n,k) = C(n, n-k) = n! / (n-n +k)! (n-k)! so we can change r to r-p is r > p-r and keep the operation smaller

for (i = 0; i < k; i++)

{

res *= (n - i);

res /= (i+1);

}

O(k) time and (1) space

## Friday, November 23, 2012

## Thursday, November 22, 2012

### Identify all the pythagorian triplets in the given array.

2 , 4 -> 4 + 16 = 20

1, 3 -> 1 + 9 = 10

In efficient way

1, 3 -> 1 + 9 = 10

In efficient way

## Wednesday, November 21, 2012

### BST, kth

Find the Kth largest integer in a Binary Search Tree.

## Tuesday, November 20, 2012

### Find non-unique characters in a given string

Optimal complexity in time and space

## Monday, November 19, 2012

## Sunday, November 18, 2012

### Gas stations

You have a certain number of gas stations in a circle and a car running on the circle. The car has a certain amount of gas available at the beginning. Find the right station to start for not running out of gas

This is a version of max subarray

This is a version of max subarray

## Saturday, November 17, 2012

### Creating a generic graph

Here the code based on C++, template, and boost::unordered_map and boost::unordered_multimap

## Friday, November 16, 2012

### Huge file of parenthesis ( .. ) . Find if they are balanced

The file is huge and you don't want to run out of memory.

## Thursday, November 15, 2012

### Construct BST from given preorder traversal

Construct BST from given preorder traversal
(recursive solution)

## Wednesday, November 14, 2012

### Linked list

Given an unidirectional linked list, return the last but k element. No recursion

## Tuesday, November 13, 2012

### Deep copy

A random link list is a linked list where every node contains 2 links, one like a normal node which points to the next node. The other link points to a random node in the list, even itself. You are to write a function to perform a deep copy of this random link list.

## Monday, November 12, 2012

### Transormations

Given a number n and another number m, which is a permutation of n find the number of moves needed to transform m into n.

## Sunday, November 11, 2012

### Shortest path

Given a binary square matrix of size n*n. 1 means there is a path, 0 means no path.
Find the shortest path and print it from (0,0) to (n-1, n-1)

## Saturday, November 10, 2012

## Friday, November 9, 2012

### Matrix of 0/1

Find all the islands and return them. An island is a sub-matrix of contiguous 1s.

## Thursday, November 8, 2012

### Select a number from a stream with uniform probability

Here the code. the tricky part is the uniform probablity and the stream, which should be ideally processsed with O(1) memory

## Wednesday, November 7, 2012

### Given an array of integers compute the subsequence of max sum

Here the code.

## Tuesday, November 6, 2012

### Compute the longest path in a binary tree

## Monday, November 5, 2012

### Data structures in Boost

I like boost for the rich collection of data structures, which are very handful now and then.

- Tuples, for tuples in mathematical sense
- Any, when you have a collection of objects with different types
- Variant, when you have a collection of objects with different types, a modern version of union
- Dynamic bitset, when you need to create a bitset whose dimension is unknown at compile time

## Sunday, November 4, 2012

### how many unique symbols in a file

Given a file of 1 petabyte containing unicode strings, compute the number of unique symbols contained in the file. Suppose that you have no more than 100Mb of available RAM.

Write some C++ code

Write some C++ code

## Friday, November 2, 2012

### Template typedef

In C++ you can have the first definition of a template class. However you cannot have a template typedef. In C++0x this will be supported but for now the only thing that you can do is to have a typedef within a template struct, which will add a bit of un-necessary redundancy to the code

```
template <typename T>;
class C {...};
```

```
template <typename T>;
typedef T ;
```

## Thursday, November 1, 2012

### Back to basic: all the nodes in a level

## Monday, October 29, 2012

### Back to basics: given a generic list and a pointer

Delete that element. The list is single linked and the element to be deleted is not the tail of the list.

Here the code

Here the code

## Sunday, October 28, 2012

### Back to basics: write a matrix of generic types

Imagine to build a matrix [MxN] of generic type. Implement the classic [x, y] operator for accessing the element [x, y]. How would you implement it in C++?

here the code, where size can be either allocated at compile time or at run-time.

do you have any alternative solution? yes, boost::matrix is a valid one ;)

here the code, where size can be either allocated at compile time or at run-time.

do you have any alternative solution? yes, boost::matrix is a valid one ;)

## Saturday, October 27, 2012

### Back to basics: a question, a code snippet

During past years, I used this blog to publish code snippets just for personal fun. Some of those snippets became relatively popular (see: A collection of algos and data structures published here).

I am now returning to basics and will restart the series. Everyday will publish a question and a solution with relative code snippet. Again, just for fun and just to keep myself in good shape.

First question: write a C++ generic binary tree and an interative inorder visit (e.g. stack no recursion, and templates)

here the code

I am now returning to basics and will restart the series. Everyday will publish a question and a solution with relative code snippet. Again, just for fun and just to keep myself in good shape.

First question: write a C++ generic binary tree and an interative inorder visit (e.g. stack no recursion, and templates)

here the code

## Thursday, October 18, 2012

### BigData @ Twitter

Some good information about BigData in Twitter, including Cassandra, Hadoop, Pig and others.

http://www.slideshare.net/kevinweil/nosql-at-twitter-nosql-eu-2010

http://www.slideshare.net/kevinweil/nosql-at-twitter-nosql-eu-2010

### Good talk about topic modelling

Very nice talk http://videolectures.net/mlss09uk_blei_tm/

### Given a tv screen mxn

Implement a pan-fill algorithm (i.e. given a new color n and an original color o, and a position (x, y) change (x, y) and all the surrounding points until you meet the color 0).

## Tuesday, October 16, 2012

### Given a matrix nxn

Zero all the columns and rows which contains at least one zero.

## Monday, October 15, 2012

### Maintain the median in a stream of integers

## Sunday, October 14, 2012

### Decode a phone number

Phones have keyboard with letters, decode a phone number

const char* code[]={{"0"}, {"1"}, {"abc"}, {"def"}, {"ghi"}, {"jkl"}, {"mno"}, {"pqrs"}, {"tuv"}, {"wxyz"}}; void decode(std::string & inputString, std::string result, int i, int n) { std::string value; if (n == 0){ std::cout << std::endl; for(std::string::const_iterator it = result.begin(); it != result.end(); ++it) { std::cout << *it ;} std::cout << std::endl; } else { char c = inputString.at(i); int v = atoi(&c); for (const char *p = code[v]; *p != '\0'; ++p) decode (inputString, result + *p, i+1 , n-1); } }

## Saturday, October 13, 2012

### Facebook has a feature which allows to discover the friends in common among two users.

How would you implement it in a social graph?

## Friday, October 12, 2012

### Estimate the cost of building a typeahead system

Are you familiar with Bing Autosuggest? Now let's say that we store 20M of suggestions what would be the cost in $$ to implement this infrastructure? And what would be the cost if we have 20Billions of suggestions

## Thursday, October 11, 2012

## Wednesday, October 10, 2012

### Given a string permute it generating the permutation in lexicographical sorted order

## Tuesday, October 9, 2012

### Given a string, find its rank among all its permutations sorted lexicographically.

This is a bit hard

## Monday, October 8, 2012

## Sunday, October 7, 2012

### Realize a youtube service

Suppose you need to store 10 billions of videos and to address a growth of 10 millions of videos daily, how many space do you need for storing the videos and what would be the cost in $? Also, suppose that you want to have some replica for fault tolerance how this would increase the cost?
Also, suppose that each single server can retrieve videos with a QPS=1000 provided that the index is not larger that 10 millions videos so that it can be fit in memory, how many servers do you need for serving 100 millions of queries daily? Is the QPS=1000 reasonable?

## Saturday, October 6, 2012

### Generate all the permutations of 1.. N integer numbers

## Friday, October 5, 2012

### Find all the anagrams in a collection of strings

## Thursday, October 4, 2012

### Machine learning on Twitter data

A nice talk about ML on Twitter big data. Keep the model simple and leverage the amount of data and the connections.

## Wednesday, October 3, 2012

### Biased coin into a unbiased coin

A coin returns head with p=0.6 and tail with p=0.4. How to use this coin to simulate an unbiased one?

## Tuesday, October 2, 2012

### Sorted matrix

Given a boolean 2D array, where each row is sorted. Find the row with
the maximum number of 1s.

## Monday, October 1, 2012

### Implement a smart pointer class

with assignment, constructor and destructor

## Sunday, September 30, 2012

### A great machine learning book

Many times people are asking what is the best book to start studying machine learning. Among other books, I'd like to suggest: Machine Learning, An algorithmic Perspective, which has a good mix of topics covered and where every algorithm is implemented in python

## Saturday, September 29, 2012

### Exit a labyrinth

given a matrix of 0/1, where the 1s represent the walls of a labyrinth, find the exit

## Friday, September 28, 2012

### My view on Facebook Gift

Gift could be a changing moment for Facebook. In my view, this is a service with a great user experience and it also has opportunities for increasing FB's revenues. In my view, Facebook can become a cash-cow but they need to add services for allowing money transfer or gift transfers ( see my posting on this topic of about 1 year ago "http://codingplayground.blogspot.co.uk/2011/09/facebook-social-wallet.html )

## Thursday, September 27, 2012

### Given a BST find the k-th element in an efficient way

## Wednesday, September 26, 2012

## Tuesday, September 25, 2012

### Given a tree, return an array A

where A[i] is the head of a linked list containing all the elements at level i.

## Monday, September 24, 2012

### Check if a string has balanced parenthesis

## Sunday, September 23, 2012

### Convert a BST into a double linked list

preserving the order

## Saturday, September 22, 2012

### K-Means: describe the intuition behind the algo

and write some code for it

## Friday, September 21, 2012

### SVM

Explain the intuition behind SVM and optionally try to figure out the math

## Thursday, September 20, 2012

### Describe the intuition behind the esamble of classifiers

## Wednesday, September 19, 2012

### Describe the intuition behind boosting and bagging

## Tuesday, September 18, 2012

### Select friends from your social network

You need to select the maximum number of friends in your network and invite them to a party. The requirement is that each friend knows a minimum of 5 friends and she does not know at least 5 other friends.

## Monday, September 17, 2012

## Sunday, September 16, 2012

### In an array of integers take the k largest elements

## Saturday, September 15, 2012

### Given an array of integers A, compute efficiently the max in any interval [i, j]

Compare time and space

## Friday, September 14, 2012

### Implement a readline in C and suppose you have read available

## Thursday, September 13, 2012

### Unsorted array

Given an unsorted array, how to divide them into two equal arrays whose difference of sum is minimum

## Wednesday, September 12, 2012

###
Sort a large set of std::vector

Sort a large set of std::vector, larger than the size of RAM

## Tuesday, September 11, 2012

### Array rotation

Given an array, rotate the elements of an array within O(n) time and with 0(1) space

## Monday, September 10, 2012

### A frog jumping

A frog can jump a river of n meters and at each step she can jump either x-1 or x or x+1 meter if she jumped x meter at the previous step. She can jump just if the starting place and the ending place has a stone. The available stones are maintained in an array S[i] given as input. The first just is just 1 meter. Can you compute whether or not the frog will arrive at the destination?

## Sunday, September 9, 2012

### implement a first fit strategy

You have a m set of boxes of different sizes and a set of n envelopes. Find a strategy to fit the box in the envelopes

## Thursday, September 6, 2012

### an url can contain words

an url can contain words. For instance akillernewappforwork.com. Device an algorithm for extracting all the words from an url

## Wednesday, September 5, 2012

### Longest subsequence

Given an array A of integers such that #A = n, find the longest sequence such that i_j < i_{j+1} and A[i_j] <= A[i_{j+1}] for any j \in [1, k-1]

## Tuesday, September 4, 2012

### Max sum in an array

Given an array of integers A find a, b such that \sum_{i=a}^b A[i] is maximized

## Monday, September 3, 2012

### Given a stream compute the running average and the running median

## Sunday, September 2, 2012

### Search engines and monetization

Search engines are making money selling ads. Can you envision any different strategy?

## Saturday, September 1, 2012

### inverted lists

Given a very large set of document, you can define the following relation
d_i ->; w_a, w_b, w_c, ......
meaning that the document d_i contains the word w_a, w_b, w_c, and so on and so forth

Suppose you want to invert the relation and build lists such as

w_a -> d_i, d_j, d_k ...

meaning that the word w_a is contained in documents d_i, d_j, d_k ...

how would you proceeed?

Suppose you want to invert the relation and build lists such as

w_a -> d_i, d_j, d_k ...

meaning that the word w_a is contained in documents d_i, d_j, d_k ...

how would you proceeed?

## Friday, August 31, 2012

### unique records

you are given 1 billion of records taking 1 petabyte of spaces. Some entries are reperated. How to find the unique records if you have just 8Gb of memory? How much space do you need for processing, what is the complexity?

## Thursday, August 30, 2012

### View from the top

You are given a million of segments in a 3d space. segments can have different colours. draw the segments you will see on the plane where z-axes is zero.

## Wednesday, August 29, 2012

### arrays

Given an array A and an integer m, find all the i, j such that A[i]+A[j] = m. Find all the i, j, k such that A[i]+A[j]+A[k] = m

## Tuesday, August 28, 2012

### find elements that appears [n/k] times in the stream

Given a stream of lenght n, and an integer k find all the elements appearing more than (n/k) times. what is the memory you need? how many times you need to process the stream? what about complexity?

## Monday, August 27, 2012

### cluster users by attributes

A massive social network decided to assign an unsigned int as unique id for each user. Also, each user has a set of attributes represented as string and integers. Define a suitable cluster strategy for users based on the common attributes.

## Sunday, August 26, 2012

### Intersect two sorted arrays

Given two arrays A and B, where #A = m and #B = n, how would you intersect A and B? Please discuss complexity and real optimization

## Saturday, August 25, 2012

### Sum maximum

Given an array of n positive integers. Write a program to find the sum of maximum sum subsequence of the given array such that the intgers in the subsequence are sorted in increasing order.

## Friday, August 24, 2012

## Thursday, August 23, 2012

### Sequences in sorted order

Given two integers k and n, write a function that prints all the
sequences of length k composed of numbers 1,2..n. You need to print
these sequences in sorted orde

## Wednesday, August 22, 2012

### Find the minimum distance

Given an unsorted array arr[] and two numbers x and y, find the minimum
distance between x and y in arr[]. The
array might also contain duplicates. You may assume that both x and y
are different and present in arr[]

## Tuesday, August 21, 2012

### A collection of algos and data structures published here

Design Patterns

Design Patterns : C++ full collection of Gamma's p...

Data Structures

KD-Tree: A C++ and Boost implementation

A commodity vector space class

Generic B-Tree

Splay Trees in C++

Decision Trees (part I)

Genetic Programming

Linear Suffix Array

Generic Tree

Hashing, Shingling and HashTrees

Generic Skip list (skiplist)

Generic Graph

Generic heap

Generic list and list iterators

Generic Hash_Map

Chained hash and hash function

Generic list and mergesort

Algorithms

DBSCAN clustering algorithm

Multidimension Scaling

Range minimum queries and LCA

Fuzzy Clustering

Adaboost : improve your weak performance

K-means in C++

Viterbi Algorithm in Boost and C++

Longest common substring, subsequences, increasing...

Maximum sub-array sum

Finding the the more frequent symbol in a stream o...

Shingling and Text Clustering (Broder's shingles)

Maximum sub-array product

Finding a loop in a list

Useful stuff

Memory Mapped files in Boost and C++

Boost::serialization for storing generic class

Boost::asio, Keep-alive, Boost::serialization

Design Patterns : C++ full collection of Gamma's p...

Data Structures

KD-Tree: A C++ and Boost implementation

A commodity vector space class

Generic B-Tree

Splay Trees in C++

Decision Trees (part I)

Genetic Programming

Linear Suffix Array

Generic Tree

Hashing, Shingling and HashTrees

Generic Skip list (skiplist)

Generic Graph

Generic heap

Generic list and list iterators

Generic Hash_Map

Chained hash and hash function

Generic list and mergesort

Algorithms

DBSCAN clustering algorithm

Multidimension Scaling

Range minimum queries and LCA

Fuzzy Clustering

Adaboost : improve your weak performance

K-means in C++

Viterbi Algorithm in Boost and C++

Longest common substring, subsequences, increasing...

Maximum sub-array sum

Finding the the more frequent symbol in a stream o...

Shingling and Text Clustering (Broder's shingles)

Maximum sub-array product

Finding a loop in a list

Useful stuff

Memory Mapped files in Boost and C++

Boost::serialization for storing generic class

Boost::asio, Keep-alive, Boost::serialization

## Monday, August 20, 2012

### A collection of feature suggestions published here

Skype

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

Mobile Social payments, Facebook, Skype and Google

Linkedin

Why people are not using LinkedIn for Search? my opinion their ranking is broken

Secret references, A feature suggestion to

Facebook

Monetizing free login

A feature request for Facebook

Sharing revenues with skilled friends

Skilled friends can gain money after they share

Skills cannot be faked

An idea for Facebook: from friends to skilled friends

A feature suggestion for facebook: multiple langua..

Facebook Social Wallet

A feature suggestion for facebook: Social calendar..

Shipping that feature one day before of Facebook

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

Mobile Social payments, Facebook, Skype and Google

Why people are not using LinkedIn for Search? my opinion their ranking is broken

Monetizing free login

A feature request for Facebook

Sharing revenues with skilled friends

Skilled friends can gain money after they share

Skills cannot be faked

An idea for Facebook: from friends to skilled friends

A feature suggestion for facebook: multiple langua..

Facebook Social Wallet

A feature suggestion for facebook: Social calendar..

Shipping that feature one day before of Facebook

## Sunday, August 19, 2012

### Bing and Windows 8

Apparently, I am in the video (someone told me ;))

## Saturday, August 18, 2012

### Autosuggest and Bing

My team is shipping this Autosuggest Backend

*"“As you type results, Bing will offer suggestions and if we do say so, the auto-completion feels pretty quick.”"**http://www.engadget.com/2012/08/15/windows-8-rtm-whats-new/*

## Friday, August 17, 2012

### Related Searches and Bing

My team is shipping this Related Searches ;) ;)

http://news.cnet.com/8301-10805_3-57495215-75/bing-windows-8-app-brings-tiled-goodness-to-your-search-results/

http://news.cnet.com/8301-10805_3-57495215-75/bing-windows-8-app-brings-tiled-goodness-to-your-search-results/

## Thursday, August 16, 2012

### Subset sum

Find subset of elements that are selected from a given set whose sum adds up to a given number K. The set contains non-negative values.

## Wednesday, August 15, 2012

### Special Stack

Design a Data Structure SpecialStack that supports all the stack
operations like push(), pop(), isEmpty(), isFull() and an additional
operation getMin() which should return minimum element from the
SpecialStack

## Tuesday, August 14, 2012

### Count in an array

Write a function to count number of smaller elements on right of each
element in an array.

## Monday, August 13, 2012

### Celebrity problem

In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions

## Sunday, August 12, 2012

### Find the two numbers with odd occurrences in an unsorted array

## Saturday, August 11, 2012

### Longest Bitonic distance

Given an array arr[0 ... n-1] containing n positive integers, a subsequence of arr[] is called Bitonic if it is first increasing, then decreasing.

## Friday, August 10, 2012

### Find the smallest positive number missing from an unsorted array

## Thursday, August 9, 2012

### Find a triplet that sum to a given value

Given an array of integers

## Wednesday, August 8, 2012

## Tuesday, August 7, 2012

### Given a sequence, find the length of the longest palindromic subsequence in it.

## Monday, August 6, 2012

### Check whether two strings are anagram of each other

## Sunday, August 5, 2012

### ind the maximum sum leaf to root path in a Binary Tree

## Saturday, August 4, 2012

### Intersection and Union

Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Discuss complexity and make your assumptions.

## Friday, August 3, 2012

### Add two numbers without using arithmetic operators

Hint: use bit operators

## Thursday, August 2, 2012

### Bing and Facebook

“Facebook is a partner with Google’s biggest
rival, Bing, to handle web searches.”

“Readers: Are you seeing the “search the Web”
link in your typeahead search results?”

“Facebook
had previously allowed users to filter their Facebook searches by web results
after clicking over to a main results page, but it hadn’t offered the option
from the typeahead, which only included Facebook objects. Making it more
efficient to search the web from Facebook’s search bar will give users an
incentive to use Facebook search rather than going to a separate search engine
like Google. “

## Wednesday, August 1, 2012

http://academic.research.microsoft.com/Author/77558/antonio-gulli?query=antonio+gull

## Tuesday, July 31, 2012

### Sharing revenues with skilled friends

In my previous postings I discussed about the opportunity of explicitly share your skills on facebook showing that the authenticity of those skills would be self-regulated by the social network. Also, I claimed that the current web search ads system is not necessarily the only monetization model available. In web search, when a query is submitted some relevant content is retrieved and ads are sold together with the results. The engine takes the money and the web content producers take no money. Web content producers take benefits from the traffic received by the search engine, but they directly take no money -- which is strange to me.

Now the question is what incentive could we give the users who are sharing their own skills?

First answer would be to send them traffic in analogy to what happen in web search. Anyway, I am not sure that this would be valuable for my friend Giuseppe who claimed that he is an expert in Photography. Why sending traffic to his Facebook page should have any additional value to him?

Now the question is what incentive could we give the users who are sharing their own skills?

First answer would be to send them traffic in analogy to what happen in web search. Anyway, I am not sure that this would be valuable for my friend Giuseppe who claimed that he is an expert in Photography. Why sending traffic to his Facebook page should have any additional value to him?

The second answer is to share revenue between my skilled friend Giuseppe and Facebook whenever Facebook shows Giuseppe among the friends skilled in Photography. The more likes Giuseppe gets the higher would be the chances to be retrieved for a search about Photography. Whenever ads shown for that topic are clicked Giuseppe will get a little amount of the revenues generated. He produced the content, he has the skill so he takes some direct money for it. In my view, this model would give a natural incentive to share skills and to get likes for those skills.

The third answer is still to about sharing revenues, but would be based on inserting ads into skilled pages. What is a skilled page? pretty simple. If Giuseppe declares a skill in Photography he can create a special page on his profile very similar to the traditional timeline but focused just on Photography. All the ads shown in that page are about the Photograpy topic and again there should be some form of revenue sharing as form of incentive to produce high quality, curated skilled pages. After all, Giuseppe is the expert so he has to tell something about his expertise.

## Monday, July 30, 2012

### Skilled friends can gain money after they share their skills for free

An anonymous reader told me: "people need an incentive/experience to provide this information for free. They will assume that their friends know - so why should they tell Facebook this information?"

In my previous posting, I showed that skills cannot be faked because they are judged by the rest of the friends. This is nothing but just applying the power of social ties which self-regulates authenticity.

Now, let's go to the next step. I believe that current web ads system is fundamentally flawed. A lot of people produce web content which is then indexed by search engines. When a query about a topic is submitted by a user some relevant content is retrieved and ads are sold together with the results. The engine takes the money and the content producers take no money.

Why that?

Yes, content producers will receive more traffic and this has certainly an economic value. Anyway, who said that this is the only model we can think of?

Do you have any alternative?

In my previous posting, I showed that skills cannot be faked because they are judged by the rest of the friends. This is nothing but just applying the power of social ties which self-regulates authenticity.

Now, let's go to the next step. I believe that current web ads system is fundamentally flawed. A lot of people produce web content which is then indexed by search engines. When a query about a topic is submitted by a user some relevant content is retrieved and ads are sold together with the results. The engine takes the money and the content producers take no money.

Why that?

Yes, content producers will receive more traffic and this has certainly an economic value. Anyway, who said that this is the only model we can think of?

Do you have any alternative?

## Sunday, July 29, 2012

### Skills cannot be faked

One more thought about my idea of skilled friends on Facebook. I don't believe the a friend can mystify her skills by declaring a talent which is not there. Her social network will understand this and she will look bad in front of her friends.

So, skills cannot be faked. Plus, when you declare a skill there is always the opportunity to like it and this will be an important signal to rank friends by skills.

So, skills cannot be faked. Plus, when you declare a skill there is always the opportunity to like it and this will be an important signal to rank friends by skills.

## Saturday, July 28, 2012

### An idea for Facebook: from friends to skilled friends (or how to make money)

Facebook has 900 millions of users, and everyone is connected to a number of friends. Sometime you don't know what are your friends' skills. In my network there are people expert in photography, people expert in art, people experts in skiing, people expert in surfing, and people expert in solar power, and people expert in philosophy, and people with an immense musical background, and many geeks, and people with tremendous interest for electrical cars, and people with a passion for astronomy and celestial stuffs, and ....

So many people, so much talent to discover.

So Facebook, let everyone declare their own skills and talents to their social network. Let my friends be skilled friends. Let me also tag the skills of my friends as I tag my friends' faces in pictures.

Then, let me discover this talent when I search: if I search for photography give the name of my friend Giuseppe who has a skill in this subject, and If I search surfing give me the name of Luca who is the expert here. If no friend is an expert in that topic, please find a skilled expert among the friends of my friend.

Transform generic search in search for skilled friends.

And when I search a skill, here you have the magic opportunity to sell ads about that topic.

So If i search for surfing give me the name of Luca, but also ads related to the topic. Give me the name of that online market where I can buy great surf tables or show me where to find swimsuits. Likewise, if I search for camera give me the name of Giuseppe but also ads for the latest Nikon D7000. And...

Transform generic search in a search for skilled friends, and make money out of a great user experience.

## Friday, July 27, 2012

### Implement an hash table with chains in case of collision

## Thursday, July 26, 2012

### Bing search meets Facebook: exciting typeahead progress

Very happy about the integration of typeahead/autosuggestion technologies between Bing and Facebook. Now you can Bing directly from Facebook search box. Congratulation to the teams that made this happening by establishing a collaboration with several locations in the world (California, Washington, and London). My team in London provided core backend technologies for Bing Autosuggestion.

Enjoy!

Enjoy!

## Wednesday, July 25, 2012

### A phone has two sides. An idea for phone manifactures

Yesterday, I was listening this conversation: "I have always to carry at least two phones. My iphone is great for browsing and the apps, and my blackberry is great for browsing emails". How many of you have a similar experience: either you have a phone with a large touch display which is great for browsing, or you have a phone with smaller display but with a decent keyboard. So you go out of there and buy your favourite Android, Windows Phone, Iphone AND you possibly buy a traditional Blackberry or the like.

Now I wonder why two devices? Why don't have just one with two sides? On one side you have the large touch display, and on the other side you have the smaller display but a good traditional keyboard.

I should probably patent this idea and sell it to companies out of there, but there is a war so I prefer to publish here and give it for free.. as in freedom

Now I wonder why two devices? Why don't have just one with two sides? On one side you have the large touch display, and on the other side you have the smaller display but a good traditional keyboard.

I should probably patent this idea and sell it to companies out of there, but there is a war so I prefer to publish here and give it for free.. as in freedom

## Tuesday, July 24, 2012

### Implement a tree inorder visit with no recursion

## Monday, July 23, 2012

### What colour would you pain an airplane

motivate your answer

## Sunday, July 22, 2012

### LRU

How to implement LRU caching scheme? What data structures should be used

## Saturday, July 21, 2012

### Implement set and traditional set operation

Please discuss trade-offs in your choice.

## Friday, July 20, 2012

### Given a stream of integers always maintain the median

This is a bit difficult, try with heaps

## Thursday, July 19, 2012

### Bitonic arrays

iven an array A[0 ... n-1] containing n positive integers, a subarray A[i ... j] is bitonic if there is a k with i <= k <= j such that A[i] <= A[i + 1] ... <= A[k] >= A[k + 1] >= .. A[j - 1] > = A[j]. Write a function that takes an array as argument and returns the length of the maximum length bitonic subarray.

## Wednesday, July 18, 2012

### Array and positions

Given an array of n distinct integers sorted in ascending order, write a function that returns true is there is an index i such that arr[i] is equal to i

## Tuesday, July 17, 2012

### Strange struct.

`struct`

`str`

`{`

` `

`int`

`i: 1;`

` `

`int`

`j: 2;`

` `

`int`

`k: 3;`

` `

`int`

`l: 4;`

`};`

`what is this? is it a good and portable code?`

## Monday, July 16, 2012

### Two arrays

Given two sorted arrays of any length, find out the median of them if they are sorted into single array

## Sunday, July 15, 2012

### Find the maximum element in an array which is first increasing and then decreasing

Go with binary search (well, pretty much)

## Saturday, July 14, 2012

### Maze

Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array).

ex: 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1If there is a block it’s represented by 0.

If there is a path it’s represented by 1.

## Friday, July 13, 2012

### Beautification

Write a program for beautificaion of a program file in an IDE

## Thursday, July 12, 2012

### Linked list

Write a program to print the n-nodes from tail of the linked list.

## Wednesday, July 11, 2012

### IPv4

Write a program to Validate an IPv4 Address

## Tuesday, July 10, 2012

### Distributed sort

Given N machines. Each machine contains some numbers in sorted form. The amount of numbers for each machine is not fixed. Output the numbers from all the machine in sorted non-decreasing form.

## Monday, July 9, 2012

### Unique words

Design a system to calculate the number of unique words in a file..
1) What if the file is huge ?
2) Assuming that you have more than one computers available, how can you distribute the problem ?

## Sunday, July 8, 2012

### Array of 0 and 1

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.
linear

## Saturday, July 7, 2012

### Check Number is perfect Square or Not

## Friday, July 6, 2012

### Implement a data structure for storing and retrieving non overlapping intervals of integer

## Thursday, July 5, 2012

### Given an array of size n, find all the possible sub set of the array of size k

typical recursive problem

## Wednesday, July 4, 2012

### Sum 3 numbers

given an array and a target value. Find a,b,c such that a+b+c=target

## Tuesday, July 3, 2012

### fiven n points find m points closer to origin

in a r-space

## Monday, July 2, 2012

### Solve the coin change problem

def count( n, m ):
if n == 0:
return 1
if n < 0:
return 0
if m <= 0 and n >= 1: #m < 0 for zero indexed programming languages
return 0
return count( n, m - 1 ) + count( n - S[m], m )

## Sunday, July 1, 2012

### Regexp match

Write a function checkRegex() which takes two strings as input, one string represents a regex expression and other is an input string to match with the regex expression. Return true if it matches, else false. Regex may contain characters ‘a-z’, ‘.’ and ‘*’ where ‘.’ matches any character and ‘*’ means 0 or more occurrences of the previous character preceding it.

## Saturday, June 30, 2012

### Min and Max

Find the min and max in an array. Now do it in less than 2n comparisons

## Friday, June 29, 2012

### Event store

Question: Design a component that implements the following functionality..
1) Record an Event (For the sake of simplicity, treat the Event as an integer code)
2) Return the number of Events recorded in the last one minute.
3) Return the number of Events recorded in the last one hour.
i.e implement the following interface

## Thursday, June 28, 2012

### Points closer to a point

You are given a list of points in the plane, write a program that outputs each point along with the three other points that are closest to it. These three points ordered by distance.

## Wednesday, June 27, 2012

### Last 60secs

Create a data structure which is supposed to log number of user requests per second. At any point of time your boss can ask you the number of hits for the last 60 seconds.

## Tuesday, June 26, 2012

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

## Monday, June 25, 2012

### Reverse words

Given a file with billions of records data. The file is too large to in main memory, and you need to reverse each word in that file and then save the reversed words to another file.

## Sunday, June 24, 2012

### Creative d80 -- Bluetooth wireless music box

I recently bought a Creative d80 -- Bluetooth wireless music box and my impression is WOW!! It is very cheap just less than $40 and the quality of music is impressive. I can stream over Bluetooth from my iphone, ipad, android, winphone, and windows 7. I don't have a Mac but it seems as easy as the remaining ones. If you have win7 make sure that your Bluetooth device has a stack supporting a2dp or enhanced data rate.

Geek is about founding creative and inexpensive cool technologies.

Geek is about founding creative and inexpensive cool technologies.

## Saturday, June 23, 2012

https://webspace.princeton.edu/users/jedwards/Turing%20Centennial%202012/Mudd%20Archive%20files/12285_AC100_Turing_1938.pdf

## Friday, June 22, 2012

### Given preorder traversal of a binary search tree, construct the BST.

## Thursday, June 21, 2012

### Find the k most frequent words from a file

## Tuesday, June 19, 2012

### Given a singly linked list, rotate the linked list counter-clockwise by k nodes

## Monday, June 18, 2012

### maximal subsets

Given a set S, find all the maximal subsets whose sum <= k. For example, if S = {1, 2, 3, 4, 5} and k = 7
Output is: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}

## Sunday, June 17, 2012

### Lucky numbers are numbers whose prime factors are just 2, 3, 5.

Find the first k lucky numbers.

## Saturday, June 16, 2012

### Value of A and B

Given two sorted positive integer rrays A(n) and B(n). We define a set S = {(a,b) such that a in A and b in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. The tricky part is that we need an O(n)
algorithm.

## Friday, June 15, 2012

### true and false

Given a function bool Zoo(int x) and its called for y times , how you will generate the true with probability x/y times .

## Thursday, June 14, 2012

## Wednesday, June 13, 2012

### Eggdrops

Solve the classical Google's interview problem.

Dynamic programming

Dynamic programming

k: Number of floors

n: Number of Eggs

eggDrop(n, k): Minimum number of trails needed to find the critical floor in worst case.

1) If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs

2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.

eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)): x in {1, 2, ..., k}}

## Tuesday, June 12, 2012

### you have a fleet of trucks and each truck has an autonomy of 1000KMs

How many kms in total you can cover if all the trucks start from the same place?

### You have 25 horses and you can make races of 5 of them in parallell

How many races to get the top 3 horses?

## Monday, June 11, 2012

### A feature request for Facebook

Sometime I just want to pin a thread and follow it without expressing an explicit like. Would it be possible to just follow a thread?

## Sunday, June 10, 2012

### Monetizing free login

Several different providers are offering universal login schema, including Microsoft, Linkedin and Facebook. Apparently, none is monetizing this phase while there are plenty of opportunities to be leveraged.

Let's analyse a simple scenario where Alice, a Spotify user, decides to login using her Facebook account. Facebook knows Alice's geo-location, Alice's profile, Alice's past postings and likes. So Facebook has a lot of information to be mined for serving ads while Spotify does not have the same information. In other words, Facebook can sell ads to Spotify's users. So this could be the "Adsense" program for Facebook.

So my question is why Facebook is not opening this ads platform?

Let's analyse a simple scenario where Alice, a Spotify user, decides to login using her Facebook account. Facebook knows Alice's geo-location, Alice's profile, Alice's past postings and likes. So Facebook has a lot of information to be mined for serving ads while Spotify does not have the same information. In other words, Facebook can sell ads to Spotify's users. So this could be the "Adsense" program for Facebook.

So my question is why Facebook is not opening this ads platform?

## Saturday, June 9, 2012

### Stars

Find the closest stars in the sky

## Friday, June 8, 2012

## Thursday, June 7, 2012

### Phonebook

Data structure TO use to design a phonebook. What is time complexity for retrieving, adding, and deleting entries

## Wednesday, June 6, 2012

### Write a function that finds the square root of a decimal number

## Tuesday, June 5, 2012

### Implement a division without division

## Monday, June 4, 2012

### Write a function that takes 2 arguments: a binary tree and an integer n, it should return the n-th element in the inorder traversal of the binary tree

int findNthElementByInorder(Node *node, int &n) { if (node == null) return -1; findNthElementByInorder(node->left, n); if (n == 0) return node-> value; else n--; findNthElementByInorder(node->right, n); }

### N-th

Write a function that takes 2 arguments: a binary tree and an integer n, it should return the n-th element in the inorder traversal of the binary tree.

int findNthElementByInorder(Node *node, int &n) { if (node == null) return -1; findNthElementByInorder(node->left, n); if (n == 0) return node-> value; else n--; findNthElementByInorder(node->right, n); }

## Sunday, June 3, 2012

### Reverse a linked list

Node* reverseLL(Node* n) { Node* curr = n; Node* prev = null; while(curr !=null) { Node* temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; }

## Saturday, June 2, 2012

### Duch national problem

void threeWayPartition(int data[], int size, int low, int high) { int p = -1; int q = size; for (int i = 0; i < q;) { if (data[i] < low) { swap(data[i], data[++p]); ++i; } else if (data[i] >= high) { swap(data[i], data[--q]); } else { ++i; } }

## Friday, June 1, 2012

### Given array find 3 elements that sum up to 0

For each i = 1..length do left = 0, right = length While left < i and right > i do if values[left] + values[i] + values[right] == 0 # Got solution here if values[left] + values[i] + values[right] > 0 # means that right border should be moved right-- else # moving left border left++

## Thursday, May 31, 2012

### Sort an array of objects

There are just three sizes large, small, medium. what is the optimal complexity? Can you make this in-place?

## Wednesday, May 30, 2012

### Given 2 very large numbers, each of which is so large it can only be represented as an array of integers, write a function to multiply them

const unsigned MULTIPLY_BASE = 10; void multiplyLittleEndian(const vector < unsigned > &a, const vector < unsigned > &b, vector < unsigned > &r) { r.assign(a.size()+b.size(), 0); unsigned ri=0; for(unsigned ai=0; ai < a.size(); ++ai) { unsigned cri = ri++, carry = 0, am = a[ai], cr; for(unsigned bi=0; bi < b.size(); ++bi, ++cri) { cr = carry + am*b[bi] + r[cri]; r[cri] = cr % MULTIPLY_BASE; carry = cr / MULTIPLY_BASE; } while(carry) { cr = carry + r[cri]; r[cri++] = cr % MULTIPLY_BASE; carry = cr / MULTIPLY_BASE; } } while((!r.empty()) && r.back() == 0) r.pop_back(); // trim result }

## Tuesday, May 29, 2012

### Write a function to check if polygon is simple based on given list of points

## Sunday, May 27, 2012

### add two numbers represented by strings

First need to reverse both strings, then add char by character and reverse final String again.

## Saturday, May 26, 2012

## Friday, May 25, 2012

### Interweave a linked list

Interweave a linked list. Do it in Linear time and constant space. Input: A->B->C->D->E Output: A->E->B->D->C

## Thursday, May 24, 2012

## Wednesday, May 23, 2012

### Implement a function to compute cubic root what is the time complexity?

pay attention to negative values, but it's a binary search

## Tuesday, May 22, 2012

### Roman strings

Get numeric number out of a roman string, linear time Given: mapping I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000 Input/Output: II = 2, III = 3, IV = 4 VI, VII, VIII IX = 9 XL = 40, XLIX = 49

mapping = { 'I' : 1, 'V' : 5, 'X' : 10, 'L' : 50, 'C' : 100, 'D' : 500, 'M' : 1000, } def roman(string): prev = 0 totalsum = 0 for c in string: if mapping[c] <= prev: totalsum = totalsum + mapping[c] else: totalsum = totalsum - prev totalsum = totalsum + mapping[c] - prev prev = mapping[c] print(totalsum) roman("XCIX")

## Monday, May 21, 2012

## Thursday, April 19, 2012

### About the openness

Google is complaining about the direction where Internet is going. Apparently, they say that there is less openness these days and it seems that the bad guy is Facebook, which is collecting user generated content which is not shared in an open way. I am puzzled.

If this is a genuine rant why are they building Google+ which is just a copycat of Facebook? Also, why they collect search data since 1998 about everyone's behaviour but they don't share this data with the rest of the world?

Long time ago, I dreamt about a different world with open standards for exchanging facebook-like news feeds but hosted by different providers (remember RSS and ATOM? something similar but social) so that data is public. Then, the aggregation is centralized and you access aggregated information in a similar way to what is happening nowadays with search engines. In that ideal world, login would be no longer centralized but it would be based on openID. The social graph would be shared across different servers and remote nodes would be just special form of href, so that someone can index public data.

(this is my personal idea and it's not representing any opinion expressed by my company)

If this is a genuine rant why are they building Google+ which is just a copycat of Facebook? Also, why they collect search data since 1998 about everyone's behaviour but they don't share this data with the rest of the world?

Long time ago, I dreamt about a different world with open standards for exchanging facebook-like news feeds but hosted by different providers (remember RSS and ATOM? something similar but social) so that data is public. Then, the aggregation is centralized and you access aggregated information in a similar way to what is happening nowadays with search engines. In that ideal world, login would be no longer centralized but it would be based on openID. The social graph would be shared across different servers and remote nodes would be just special form of href, so that someone can index public data.

(this is my personal idea and it's not representing any opinion expressed by my company)

## Tuesday, April 17, 2012

### Birthday

you are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?

## Sunday, April 15, 2012

### Better a game where you can win in 1 shot or better one where you can win 2 out of 3 shots?

## Saturday, April 14, 2012

### An interesting project for parallel machine learning:

Interesting collection of data parallel machine learning algorithms

"MADlib is an open-source library for scalable in-database analytics. It provides data-parallel implementations of mathematical, statistical and machine-learning methods for structured and unstructured data.

"MADlib is an open-source library for scalable in-database analytics. It provides data-parallel implementations of mathematical, statistical and machine-learning methods for structured and unstructured data.

The MADlib mission: to foster widespread development of scalable analytic skills, by harnessing efforts from commercial practice, academic research, and open-source development."

## Friday, April 13, 2012

### How many zeros at the end of 100!

This is tricky but funny

## Thursday, April 12, 2012

### how many different ways there are to paint a cube with 3 colours?

## Wednesday, April 11, 2012

### how many different ways there are to paint a cube with 6 colours?

## Tuesday, April 10, 2012

### Compute 2^128 -- no computer and possibly no paper

can you just compute it in your mind?

## Monday, April 9, 2012

### Can you estimate the cost of Facebook data center?

## Sunday, April 8, 2012

### Search ads is a well consolidate business: how large it is ? and how can you innovate?

## Saturday, April 7, 2012

### How many servers do you need to index the web?

## Friday, April 6, 2012

### How many numbers with a 7 in the first 10000 integers?

## Thursday, April 5, 2012

### DBScan

Hi Antonio,

First of all apologies if this query is out of scope- I appreciate you may have moved on to other things, or may be just too busy at the moment.

I was looking for a simple implementation of DBSCAN to use as a starting point for some work and I found your implemention here (http://codingplayground.blogspot.com/2009/11/dbscan-clustering-algorithm.html). I found it worked quite well for small enough data sets, but for large ones it was allocating excessive amounts of memory, and I eventually looked at the code to see where the problem could be. It seems to me there may be an issue with the cluster expansion part of your algorithm- this issue may not affect the results (I think it may still produce the correct clusters), but it uses much more memory than it needs and this problem is more severe for larger input datasets.

The problem is with these lines of code

specifically the line "ne.push_back(n1)". At this point in the algorithm you have found a cluster and are looking for density connected neighbours. You are adding all the new neighbours to the list to be considered, when you only need to add the ones that have not been considered yet. So rather than extending the original list with the full contents of the new list, you need to extend it with the difference of the two lists. This small change stabilises the memory usage and makes it run much faster.

kind regards

aonghus

First of all apologies if this query is out of scope- I appreciate you may have moved on to other things, or may be just too busy at the moment.

I was looking for a simple implementation of DBSCAN to use as a starting point for some work and I found your implemention here (http://codingplayground.blogspot.com/2009/11/dbscan-clustering-algorithm.html). I found it worked quite well for small enough data sets, but for large ones it was allocating excessive amounts of memory, and I eventually looked at the code to see where the problem could be. It seems to me there may be an issue with the cluster expansion part of your algorithm- this issue may not affect the results (I think it may still produce the correct clusters), but it uses much more memory than it needs and this problem is more severe for larger input datasets.

The problem is with these lines of code

Neighbors ne1 = findNeighbors(nPid, _eps);

// enough support

if (ne1.size() >= _minPts)

{

debug_cerr << "\t Expanding to pid=" << nPid << std::endl;

// join

BOOST_FOREACH(Neighbors::value_type n1, ne1)

{

// join neighbord

ne.push_back(n1);

//debug_cerr << "\tPushback pid=" << n1 << std::endl;

}

//debug_cerr << std::endl;

//debug_cerr << " ne: " << ne << endl;

debug_cerr << " ne size " << ne.size() << " " << ne1.size() << endl;

}

// enough support

if (ne1.size() >= _minPts)

{

debug_cerr << "\t Expanding to pid=" << nPid << std::endl;

// join

BOOST_FOREACH(Neighbors::value_type n1, ne1)

{

// join neighbord

ne.push_back(n1);

//debug_cerr << "\tPushback pid=" << n1 << std::endl;

}

//debug_cerr << std::endl;

//debug_cerr << " ne: " << ne << endl;

debug_cerr << " ne size " << ne.size() << " " << ne1.size() << endl;

}

specifically the line "ne.push_back(n1)". At this point in the algorithm you have found a cluster and are looking for density connected neighbours. You are adding all the new neighbours to the list to be considered, when you only need to add the ones that have not been considered yet. So rather than extending the original list with the full contents of the new list, you need to extend it with the difference of the two lists. This small change stabilises the memory usage and makes it run much faster.

kind regards

aonghus

## Wednesday, April 4, 2012

### Check if Alice has my phone number, and don't tell Eve

Alice is a friend of mine, Bob is my assistant but I don't want him to know my super-private phone number. Also, I want to check whether Alice has my super-private phone number but I don't want to communicate the number to Bob. What can I do to preserve my number?

## Tuesday, April 3, 2012

### An airplane is going from city A to city B

what would be the impact of the wind for a round-trip travel A to B?

## Monday, April 2, 2012

### Helium balloon in a car

What direction will the balloon go when you accelerate?

## Sunday, April 1, 2012

### One biased coin

You have a biased coin and the result can be H or T but biased towards T. How can you make sure whatever is the toss the result will be fair?

## Saturday, March 31, 2012

### magic square

You have a 3x3 square, fill with integers such that the sum for each row, for each column and in diagonal is 15. All the numbers must be different.

Hint: brute force is difficult (how many?), what would be number you put in the middle?

Hint: brute force is difficult (how many?), what would be number you put in the middle?