Saturday, October 29, 2011

Flood Fill

//http://www.mitbbs.com/article_t1/JobHunting/31909771_0_5.html
//白话文应该是: 下坡时把数进堆栈 (这样堆栈中最上元素是最小的,保存一个下坡序
//列),上坡时:如果
//有底的话(堆栈中至少有两个元素),找出底,flood(累加,顶减底乘长度)。
//知道过完为止。
int water(int * a, int n){
  stack > mystack;
  int water = 0;
  for(int i = 0; i    while(!mystack.empty() && mystack.top().second <= a[i]){ //上坡
      int bottom = mystack.top().second; //底
      mystack.pop();
      if( mystack.empty())  //堆栈中只有一个元素,不能形成底。
        break;
      int top = mystack.top().second < a[i]?  mystack.top().second:  a[i];  //找到顶(次大数)

      int length = i - mystack.top().first - 1;  //长度
      water = water + (top-bottom)* length;  //填充
    }  //当前上坡处理完。
    mystack.push(make_pair(i, a[i]));  //下坡,进堆栈。

    //上坡无底的话,是什么都不做的,因为上次进堆栈的元素直接出堆栈了,只是查了一下底(至少两元素在堆栈)。
  }
  return water;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int value[10] = {5,5,1,7,1,1,5,2,7,6};


    int result=0;

    cout << result;

    result = water(value, 10);
    cout << result;

    return 0;
}

lambda function in C++0x

Lambda function in C++0x

1. Simplify code. good for simple predicate (i.e. a condition check);
[](//input parameters){ //lambda function body}

2. Anonymous call, function to be defined at the point it is needed.

3. Lambda function can only use global variable and passed parameters, just as a math function, i.e.
sin, cos, pow etc.

4. No local variable in the containing scope, special capture operation has to be defined, if you want to
use the local variables, i.e. [=] by value, [&] by reference.









Friday, October 28, 2011

C++ const: why and how-- a really messy feature

I was even asked during a job interview, const keyword can be put in 5 places, make it 5 meanings, pls refer to: http://duramecho.com/ComputerInformation/WhyHowCppConst.html

Friday, September 23, 2011

A nice data mining course handout

recommendation system, pagerank, mapreduce etc: http://i.stanford.edu/~ullman/mining/2009/index.html

Tuesday, September 20, 2011

Who is the greatest inventor ever since?

Someone asked me: who is the greatest scientist?
A name comes to my mind: Thomas Edison.
What's his contribution? I am asking myself. Light Bulb?
He has 1093 granted patents around the world (he applied much more than that).
Finally I see, his biggest invention is to massively produce patents/inventions.

Forming industrial lab to massively produce patents/inventions just
as his friend Henry Ford did to form a streamline to massively produce
cars.

Sunday, September 4, 2011

C++ 11 (C++0x ) concurrency

the most important addition to C++11 is concurrency, here is an introduction
video:

http://www.corensic.com/Learn/Resources/ConcurrencyTutorialPartOne.aspx

an early book: C++ concurrency in Action.

The Biggest Changes in C++11 (and Why You Should Care):
http://www.codeproject.com/News/16244/The-Biggest-Changes-in-Cplusplus11-and-Why-You-Sho.aspx


C++11 - the recently approved new ISO C++ standard

http://www2.research.att.com/~bs/C++0xFAQ.html#lambda

Friday, September 2, 2011

Trie


Trie has wide application in "words": suggestion system,
phone book, spell check etc.

http://www.technicalypto.com/2010/04/trie-in-java.html


A lot of people was asked about Trie during interviews:
http://www.mitbbs.com/article_t/JobHunting/31926643.html