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

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

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

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

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.

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

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

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?

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