Circular pumps

Given a circular trace with pumps and a car running on a trace. Each pump has a well known distance from the origin, and the amount of kilometers you can run if you stop and refuel your car. Find a suitable starting point so that the car will not run out of fuel and the number of stops are minimal.

Special sort

Given an array of numbers, arrange them in a way that generate the largest value. For instance, if the given numbers are {34, 345, 348, 50}, the arrangement 5034834534 gives the largest value. 

Visit a BST in level order

Visit a BST in level order.
Visit a BST in reverse level order

Implement T9 dictionary

Given a BST find a triplet with sum 0

Find a pair in a BST with sum 0

Given a BST of integers find a pair with sum 0.

Class of problems with Facebook Graph search

Several classes of problems with Facebook graph search have been reported. Here there is a list:

• Non Sensical suggestions
• Low quality suggestions
• Embarassing suggestions

Plus, they frequently give no search results for suggested queries

Given a set of time intervals in any order, merge all overlapping intervals into one and output the result which should have only mutually exclusive intervals

Facebook naive graph search and the need of proper query understanding algos

Search engines use multiple data sources to help users in their query formulation. Among those sources three are very important:

• The web graph, which includes all the web pages published on the net. Mining the content of those pages and their connections can be very useful for detecting topics/entities and for understanding the correlation among those topics/entities;
• The query graph, which includes all the queries submitted to a search engine in the past. Mining this graph can be useful for detecting what are the needs expressed by past users and how those needs change over the time;
• The blog and news graph, which are useful for detecting fresh content;

Facebook is very interesting for search because they have access to other sources of data including:

•  The friend graph, which keeps track of all the friendship relations for each user;
•  The content graph, which includes all the postings and the content produced by your friends.

However, it seems like Facebook lacks quality access to the first three types of information. Here there are some examples:

Freshness
Today, the most important financial news is Dell's acquisition and every single newspaper or financial web site report the news. Bing (and Google) both have this information in their suggestion, while Facebook is completely missing it. It seems like they are not analyzing the news graph (3rd source in the above list)

In the below example, the last two suggestions are provided by Bing. Facebook just tries to complete the prefix {microsoft and} with stuff such as {London} and {Pisa}, which are popular in my social graph but have NO correlation with Microsoft and with today's news.

Query understanding
So, If you spend sometime analyzing Facebook suggestion it's clear that they create synthetic suggestions trying to complete every query prefix with stuffs popular in my social graph. This approach is naive because they DON'T seem to understand the meaning of what the user is looking for. Here there are some more examples:

Again, "Happy Diwali", "Spotify", "Microsoft" and "London" are popular in my social graph but they have NO correlation with Tom Cruise. Still, Facebook is naively generating those suggestions.

A proper search engine understands the right correlation by analyzing the Web graph, the query graph and the news graph something that Facebook is missing at the moment.

There are many web sites out there which clearly say that tom cruise is correlated with {scientology}, {katie holmes} (his wife),  {suri} (his daughter), and {cameron diaz} (since they performed in many films together), and {nicole kidman} (his past wife). However, Facebook does not capture the intent of user query and does not understand the correlation among those entities. Let's see another example:

Last suggestion is from Bing, while Facebook keeps suggesting the same {Happy Diwali} stuff which is popular in my social graph. Again, they are missing a quality access to the 2nd and 3rd sources of information in my above list.

Bing (and Google) analyse the Web graph, the query graph, the news graph and many other sources and therefore they detect the right correlations among entities (strangely enough Google misses the correlation between {Obama} and {Michelle}).

Please note that if you try the above examples you may get different suggestions from Facebook because those are personalized with stuff popular in your social graph. However, it's easy to reproduce similar naive suggestions when you understand the pattern.

Can you search a list with length n in less than O(n)?

Facebook Graph Search and problems with synthetic suggestions

I spent sometime playing with the suggestions mined by Facebook for their recent Graph Search. It seems to me that many of them are synthetic e.g. they are generated by mining the friends's graph and not the queries past queries submitted by users.

This approach seems to create many nonsensical suggestions. In this example, I was searching {hotels in new york city close} and the top suggestions are "hotels in new york city close to London", which is clearly a no sense. It seems to me that they are using some kind of frequent itemset algorithm and they notice that I have many friends in London, hence the  synthetically generated nonsensical suggestion. As you see, Bing suggestions are not suffering this problem and correct locations are shown.

Another example: I am an Italian guy and for me Milan is in Italy (btw, this Milan is way more popular on the Web that the one in Tennessee). Plus, none of those Milan cities are near to London. Web suggestions are nailing the correct location "il duomo" is central area in Milan, Italy.

Here there is another example of nonsensical suggestion. I assume that there are no Google employees who work for Microsoft at the same time. However, both the companies are quite popular in my social network hence the synthetic suggestion.

Now, let's consider another class of defects. There are queries which are not directly answered and the proposed suggestions are quite unrelated. In this example, I was searching for {actors who won the oscar} and Facebook graph search suggestions are clearly unrelated since I am not interested in "actors who like Oscar wilde"

Here there is another example of unrelated suggestion. I am searching {visit the taja} and this is not related to   "People named 'taja' who work at Visit Holland". In this case the semantic of the query is quite not understood.

If you try to replicate my examples, please note that you could get a different set of suggestions because those are generated by using your personal friend graph. However, it would be easy to generate similar situations once you understand the pattern.

See also my past postings:

http://codingplayground.blogspot.co.uk/2013/01/spelling-spelling-spelling-facebook.html

http://codingplayground.blogspot.co.uk/2013/01/facebook-graph-search-with-bing-web.html

Spelling, Spelling, Spelling. Facebook Graph Search and Bing Web Search

Continuing with my personal analysis on the Facebook Graph Search and Bing Web Search's integration,  here is another example of why you can get the best of two worlds. In this case, I will discuss misspelled words, a common problem for English (see for instance this funny article: "Why misspelled names are so common and what journalists are doing to prevent them").

Let's suppose that users start to type the word {swarzin}: their intent is to get information about the actor, but they are unsure of the correct spelling. As you see in the below image, Bing’s Speller processes tens of millions of data points mined from searches, web pages, clicks and user actions to help you find the right “Schwarzenegger".

Another example is {terramis} a delicious Italina cake of which the correct spelling is {tiramisu} - technically, {terramis} is a mispelled query prefix  for the full query{tiramisu}. Other mispelled prefixes are {bufet warr} and one of the myriad variants of {britnay s}. In all of these cases, Bing nails the correct suggestions and  are integrated into Facebook typeahead search.

Bing has a significant investment in building a state-of-art speller and those technologies are also leveraged by our team in London in securing the right suggestions. In this context, the additional problem is dealing with the mispelled fragments represented by the query prefix, correct the errors and, at the same time, predict which the more relevant suggestions are, and we need to do this every time new characters are typed in real time!

Can you imagine how fast the predictions and corrections need to be?

Facebook Graph Search, with Bing Web Search

Many people asked what are the benefits of merging Facebook internal search (aka Facebook Graph Search), with Bing Web Search results. This is my poster query {Conrad Bain} just died, and Facebook knows many people with that name from their internal data, while Bing nails the name of the actor performing 'Different Strokes' series. 

Try your own queries and give us feedback

The meaning of life

Someone in my team pointed out that now I have an answer to the meaning of the life http://www.bing.com/search?q=42

Facebook Graph Search and Bing Web Search suggestions

You have probably seen the new Facebook Graph Search for searching Facebook internal data. Anytime you search something from the public Web, then you will use the suggestions coming from Bing Web Search. This is a feature run by my team. Congratulation to all of them for driving the amazing team who shipped the core web suggestions feature from London

Calculate the span on a stock

You are given the value of a stock during different days. For each day d, we want to know how many preceding and consecutive day the stock had a value less or equal to the one observed on d.

finding the longest substring with at least k occurrence

Find all the permutations of an array A

Find the lowest common ancestor

For a binary tree for a binary search tree

Serialize and deserialize a generic tree

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

Given an array randomize it

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;
}

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)?

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

Given an array of integers, populate another array with the product of the elements of the first array except for the current index element.

Identify all the pythagorian triplets in the given array.

2 , 4 -> 4 + 16 = 20
1, 3 -> 1 + 9 = 10

In efficient way

BST, kth

 Find the Kth largest integer in a Binary Search Tree. 

Find non-unique characters in a given string

Optimal complexity in time and space

Generic graph with weights

Here the code based on boost::unordered_map

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

Creating a generic graph

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

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

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

Construct BST from given preorder traversal

Construct BST from given preorder traversal (recursive solution)

Linked list

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

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.

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.

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)

Merge sort a linked list

Matrix of 0/1

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

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

Given an array of integers compute the subsequence of max sum

Here the code.

Compute the longest path in a binary tree

Given a binary tree, compute the longest length path

Here the code

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

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

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 ;

Back to basic: all the nodes in a level

Given a binary tree create create a list of nodes which are at the same level.

here the code

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

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 ;)

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

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

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

Given a matrix nxn

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

Maintain the median in a stream of integers

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);
 }
}

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

 How would you implement it in a social graph?

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

Shuffle an arrary A[0... n-1]

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

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

This is a bit hard

Given two arrays that represent preorder and postorder traversals of a full binary tree, construct the binary tree.

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?

Generate all the permutations of 1.. N integer numbers

Find all the anagrams in a collection of strings

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.

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?

Sorted matrix

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

Implement a smart pointer class

with assignment, constructor and destructor

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

Exit a labyrinth

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

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 )

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

Reverse a single linked list

Given a tree, return an array A

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

Check if a string has balanced parenthesis

Convert a BST into a double linked list

preserving the order

K-Means: describe the intuition behind the algo

and write some code for it

SVM

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

Describe the intuition behind the esamble of classifiers

Describe the intuition behind boosting and bagging

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.

BST, visit preserving the order

In an array of integers take the k largest elements

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

Compare time and space

Implement a readline in C and suppose you have read available

Unsorted array

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

Sort a large set of std::vector

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

Array rotation

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

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?

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

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

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]

Max sum in an array

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

Given a stream compute the running average and the running median

Search engines and monetization

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

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?

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?

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.

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

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?