字符串匹配问题

为了准备面试，开始啃《编程之美》这本书，卡在“最短摘要生成“这一题已经很多天了，决心自己把代码实现，今天终于初步调试通过，在这里做一个小结。
思路书上写的很清楚，可以概括为：
1.先将页面分词，得到分词后的数组W，假设关键词数组为K。
2.对数组W进行扫描，第一次得到包含所有关键词的数组段，其起点和终点分别为beg和end，记下此时数组段的长度length。将beg指向数组段中下一个关键词，end向后移，继续扫描数组W，直到包含所有的关键词，将此时数组段的长度与length进行比较，若比其短，则记录下数组段的起始和终止位置，继续重复上述过程，直到数组W的末尾。
设数组W长为N，关键词数组长为M，此方法的时间复杂度为O( N*M )。
代码：
#include <iostream>
#include <string>
#include <map>
using namespace std;

void shortest_abstract(const string arrW[], const string arrK[], int * aBeg, int * aEnd, int lenW, int lenK);

int main()
{
    int lenW, lenK;
    int aBeg = -1;
    int aEnd = -1;
    cout << "Please enter the length of words and keys: " << endl;
    cin >> lenW >> lenK;

    string * arrW = new string[lenW];
    string * arrK = new string[lenK];

    cout << "Please enter words: " << endl;
    for(int i = 0; i < lenW; i++)
        cin >> arrW[i];

    cout << "Plearse enter keys: " << endl;
    for(int i = 0; i < lenK; i++)
        cin >> arrK[i];


    shortest_abstract(arrW, arrK, &aBeg, &aEnd, lenW, lenK);

    if(aBeg == aEnd)
    {
        cout << "Can't contain all words." << endl;
    }
    else
    {
        cout << "The shortest abstract is: " << endl;
        for(int i = aBeg; i <= aEnd; i++)
        {
            cout << arrW[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

void shortest_abstract(const string arrW[], const string arrK[], int * aBeg, int * aEnd, int lenW, int lenK)
{
    int i,j;
    map<int, int> pos_key;//store the key's index and its corresponding poistion
    int * pos = new int[lenK];
    int count = 0; // the number of keys have been found
    int beg = 0;
    int end = 0;
    int length;   // the length contains all key words
    int aLength = lenW; // the length of abstract

    cout << "lenW = " << lenW << " lenK = " << lenK << endl;
    //initial position
    for(i = 0; i < lenK; i++)
        pos[i] = -1;

    // begin finding the shortest abstract
    for(i = 0; i < lenW; i++)
    {
        for(j = 0; j < lenK; j++)
        {
            if(arrW[i] == arrK[j])
            {
                if(pos[j] == -1)
                {
                    if(count == 0)
                        beg = i;
                    count++;
                    cout << "count = " << count << endl;
                    // This is the first time that find this key
                    pos[j] = i; // record key's position in words array
                    pos_key.insert( pair<int,int>(i,j) );
                    if(count == lenK)
                    {
                        end = i;
                        length = end - beg;
                        if(aLength > length)
                        {
                            cout << "------" << endl;
                            *aBeg = beg;
                            *aEnd = end;
                            aLength = length;
                        }
                        map<int, int>::iterator it;
                        it = pos_key.begin();
                        beg = (*it).first;
                        pos[(*it).second] = -1;
                        it++; // move beg to next word
                        beg = (*it).first;
                        it--;
                        pos_key.erase(it);
                        count--;
                    }
                }
                else
                {
                    map<int, int>::iterator it;
                    it = pos_key.find(pos[j]);
                    // if this key word is the same as the begin word of abstract, then move beg to next word
                    if(beg == (*it).first)
                    {
                        it++;
                        beg = (*it).first;
                        it--;
                    }
                    pos_key.erase(it);
                    pos_key.insert( pair<int, int>(i,j) );
                    pos[j] = i; //update position to make it as the newest position   
                }
                break;
            }
        }
    }
    cout << "aBeg = " << *aBeg << " aEnd = " << *aEnd << endl;
}

numpy及scipy安装

最近在看online lda的文章，同时也将文章里的算法的实现代码下载了下来一并学习。这次看的文章的算法是用python实现的，同时还用到python的两个数值计算库numpy和scipy。那么，要让代码跑起来，先要安装这两个库。期间几费周折，忘了ubuntu下可以直接apt-get，因为源里的资源都很全了。最后，直接用apt-get从源里安装，才算搞定。
sudo apt-get install build-dev python-numpy
sudo apt-get install python-numpy
sudo apt-get install build-dev python-scipy
sudo apt-get install python-scipy

要测试numpy是否安装成功，还要安装nose
sudo apt-get install python-nose

好吧，不能不说，ubuntu还是非常方便的。

处女面

今天，进行了我进入预备找工作阶段的第一次面试。之前如火如荼的实习生招聘，我都强忍住了好奇，安份的奔波于实验室和图书馆之间，老实的看着论文、读着天书，感叹着自己的未来。
NI 是第一个来学校进行正式招聘的，这次主要是计算机专场招聘会。本以为是下午开宣讲，于是悠哉的跑去上自习，结果被真真的短信叫了回来，匆忙打印了简历，到了宣讲会会场，听了半头的宣讲。NI 主要是做嵌入式的，和我这两年来研究的内容关系不大，本来也是抱着去体验一下的心态，犹豫了要不要投简历，最终还是投了一份。
很幸运，在中午的时候收到了面试通知。下午将简历上所有的内容都复习了一篇，以备面试官问到相关的内容。在晚上面试前，给好友打了个电话，询问了一下，她下午去面试的，具体就是按照简历上的内容，问了一下相关的项目。心里稍微有了一些底，比较平静的开始了面试。
我的经历比较特殊，本科学的不是CS，面试官按照简历，从这个方面开始了交流。我一五一十的交代了跨专业考研的前因后果，面试馆这才罢休，开始了简历中技术性内容的提问。我的研究生阶段偏重于研究，所以简历的很大篇幅都在讲我的研究经历，面试官对此倒没有什么异议，我也给他讲了其中的一个模型，应该感觉还不错。但是，他对的我实践能力表示怀疑，因为我大多数时间都是在看论文，可能很少写程序，而且我本科还不是学计算机的。事实确实如此，时间和精力有限，大部分用来看论文了，花在写代码上的时间必然会减少。不过我确实写过一些程序，论文里的算法是需要实现的。“你在写程序的时候，遇到过怎样的不可预见的错误？”，“段错误“，”能具体举个例子吗？“”如数组越界、文件读取的时候遇到过“，”能更具体一些吗？”“我试试。。。。”于是，一段沉默，我已经忘了那次文件读取的错误在哪里了。很窘。“我给你出一个简单的算法题吧，就是链表反转，写个小函数“，”。。。。。“， 勉强写出来了，拿给面试官，面试官说可能还有问题，又细心的指出。好吧，此时我的已没有了仔细听的心情，被鄙视了。最后一个问题，是我向他提问，这个问题我在面试的时候已经问过了，就是关于机器人方面的研发，可惜他不是那个组的，具体情况不了解。这个面试过程就这样结束了。
经过了这次面试，有如下感悟：
1.自己的理论知识在外行人面前可以忽悠一下，但是内行人面前还远远不够，所以理论还要继续补充，不能懈怠。
2.自己对实践的重视不够，平时还是应该多写代码，多编程，将看新闻、发呆的时间都拿来写代码，抓紧最后的两个月。
3.要对自己有信心，尤其是在面试遇到编程问题的时候，要自信满满的，以肯定的语气回答。
4.自己对编程的基础，如数据结构的重视还是不够，需要再次的复习巩固。
最后，尽力去做，不要让自己后悔就好的。