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