masicの自留地

   

一共三次电话面试，分别是Apr 10, Apr 16, May 11. 原文发在求实BBS的ITfocus版，我又汇总了一下。

总体感觉是难度不大，经典题挺多。算法不难，但思维要灵活，比如random_shuffle这个题我就是第一次见到，很有意思。

================ 电话一面 （Apr 10, 2010）=================

facebook总部，电话面试

职位：基础开发工程师 Software Engineering, Infrastructure Engineering

职位要求：C/C++ on Linux， 要求有工作经验

首先谢谢ITfocus版上的祝福哈~~我在新加坡，原定今天凌晨1:00am电话面试（加州时间10:00am），结果00:30的时候NTU全校断网，郁闷，改到了今天8:00am，他们是5:00pm，整个过程大约持续了50分钟。

也没什么准备，提前半小时写了个merge_sort练练手，然后就开始了。我的背景是TJU 08年本毕业，百度基础平台部工作一年。目前PHD刚读了一年，想试试自己的水平，所以投了一下简历。

用http://collabedit.com/ 这个网站面试，可以在上面写代码，对方能实时得看到。

上来先是自我介绍，说是讲什么都行，我投的是Infrastructure，所以从头到尾都是讲自己以前工作的项目。然后让我讲了自认为最重要的项目及其关键点。blabla的讲了20-30分钟吧。面试的GG英语很地道，看名字是个中国人，一直讲得比较慢，也没有什么难的词汇，所以我这么烂的英语从头到尾都只说了一次excuse me，而且那次确实是没听清而已……

然后是问我问题，一个是写strcmp。手生，写土了，几行代码，足足憋了五六分钟：

int strcmp( char * str1, char * str2) {    do{        if(*str1 != * str2){            return *str1 < *str2 ? -1 : 1;        }        if(*str1 == 0 || *str2 == 0)break;        ++str1;        ++str2;    }while(1);    return 0;}

这个题其实关键就是考验abc和ab的比较。他说我代码不对，abc和ab比较时会不对，我告诉他对的。然后他发现是自己没看明白，然后说我代码difficult to read，我说了sorry……

这里告诉大家，以后面试，一定要把strcmp, strncmp, strcpy, strncpy这几个函数写得滚瓜烂熟！几乎每家公司都考……

然后下一个比较有意思，让实现random_shuffle。把一个数组随机打乱顺序，概率上要保证均匀。

这个想了大约2-3分钟，然后写出来了，自认为实现得不错~：

//need srand() before calling itvoid shuffle(int * array, int length) {    int unshuffled = length;    while(unshuffled > 0){        int rnd = rand() % unshuffled;        swap(array[rnd], array[unshuffled - 1]);    }}

（我现在才发现这个代码swap之后忘了–unshuffled了，不过这个一运行就能找出来。）

这个题基本没怎么问，说我实现的不错。主要是让我证明为什么是概率均匀的。我给了个直观的解释。他说了下这个解释太直观，不过觉得我理解了算法，就不再要求我继续证明了。

接下来是经典题，就是在一个长度为n的数组中挑出最大的k个元素~ 太经典了，类似于快排的算法。我说就是跟快排差不多，然后让我讲了和快排的异同，还有具体细节，问题都不大。然后问best complexity, average complexity, worst complexity，除了best想了一下是O(n)，其它的不难，知道这个算法的都知道是O(n)和O(n^2)。

然后问我如何选取那个pivot（就是快排中用于把数组分成两半用的那个中间值），我对这个没有深入的了解，只说这个没法找一个完美的中间值，只能用一些简单的方法，比如选头尾，再从中间选3个，然后求5个数的middle number。快排这个研究的人很多，也许有更多的好方法吧，欢迎补充。

然后就是一些闲聊~~呃~~

第一个是代码功底，第二个考思维，第三个是算法经典题~整个过程比想象中的容易得多~~

================ 电话二面 （Apr 16, 2010）=================

新加坡时间（也是北京时间）上周六8am第一面，周二凌晨收到二面通知。周二回邮件确认二面时间。

二面为今天上午8am。昨晚在实验室赶course report赶到5点，睡了一个小时，在奇困无比的状态下接受二面。

整个过程持续1个小时，面试官是个美国人，先闲聊了一会儿，然后就是做题。一个小时下来就做了两个题：

第一，写一个函数：

void divide (int num, int den, int & quo, int & rem)

其中num和den为传入，后两者传出。求 num/den = quo 余数为rem

要求：函数内不可以使用除法和取模。

看似容易，细节一堆，没任何提示。我自己一边写一边想，折腾了近30分钟才折腾清楚。同样是又考算法又考功底的题。

只能说，我老了……当初做ACM的时候这种代码3分钟就该拍出来的

第二，写一个函数look_and_say，输出下列字符串的第n个串：

第1个串：1

第2个串：11 （表示上一个串里有1个1）

第3个串：21 （上一个串里有2个1）

第4个串：1211 （上一个串是1个2和1个1）

第5个：111221

第6个：312211

如果有12个1就写121

这个我倒是也得很顺。

大家可以试试手。我的代码见沙发。困死了，回家睡觉。

注：关于除法这个题，JYW师兄在求实BBS上给出了一个非常完善的实现，地址是：http://bbs.tju.edu.cn/TJUBBS/con?B=ITfocus&F=M.1271756050.A

下面是我的代码。当时想到了移位，但是细节太多，面试中不敢尝试，直接说了二分，然后还是写了半天。

void divide (int num, int den, int & quo, int & rem) {    // try k = 0 .... num like binary search    // test if k * den > num    // find the largest k that k * den < num    // quo = k    // rem = num - den * k;    // O(log2(num))     //if(den == 0)  it's error    int low, high;    if(num > 0){        low = -num;        high = num;    }    else{        low = num;        high = -num;    }    int mid;    int result = low;    while(high >= low){        mid = (high + low) >> 1;         if(mid * den > num){            high = mid - 1;        }        else {            result >?= mid;            low = mid + 1;        }    }    quo = result;    rem = num - result * den; }

第二题，在文本编辑器上写的，没编译，可能有小错。

/** "look" "say"* 1: 1* 2: 11* 3: 21* 4: 1211* 5: 111221* 6: 312211   111111111111   121*/void look(char * prev, char * cur); void look_and_say(int iteration) {    const int N = 1024;    char buf1[N] = "1", buf2[N];    char * cur = buf2, * prev = buf1;    if(iteration == 1){        printf("%s", buf1);    }    for( int i = 2; i <= iteration; ++i){        look(prev, cur);        swap(prev, cur);    }    printf("%s\n", prev); // the result of the iteration} void look(char * prev, char * cur){    int pos = 0, int cnt = 0;    char buf[32];    cur[0] = 0; // delete cur     for(int i = 0; ; ++i){        if(prev[i] == prev[pos]){            ++cnt;        }        else{            sprintf(buf, "%d%c", cnt, prev[pos]);            strcat(cur, buf); //add it            pos = i;            cnt = 0;            if(prev[i] == 0){                break; // the end            }        }    }}

================ 电话三面 （May 11, 2010）=================

放了我两次鸽子，终于等来了第三次面试。

整个过程就两个问题：

1)求最长上升子序列

2)一共有多少个最长上升子序列 (1,1,2)认为有2个

第一问O(N*logN)，经典题了。DP是O(N^2)，用Lower_bound就5行代码

第二问O(N^2)，外加O(N)额外的空间，不知道有没有更优的解

a sequence of numbers:

1, 3, 2, 3, 4, 5

write a function to find the longest increasing subsequence

actually increasing

answer = 1, 2, 3, 4, 5

———————————————–

// famous DP problem /* a :input   n :size of a  res:result   Time complexity :　  O(N * logN)  */ 1, 3, 2, 4, 3, 4, 5 //11, 3  -> 21, 21, 2, 4 -> 31, 2, 31, 2, 3, 4, 5 #include <algorithm>int LIS(int a[], int n, int res[]){    int ans = 0;    for(int i = 0; i < n; ++i){        if(ans == 0 || res[ans-1] < a[i]){ //directly add it            res[ans++] = a[i];        }        else{ // lower_bound is a STL algorithm.            // lower_bound(iterator begin, iterator end, T value)            // [begin, end) must be sorted            // will return the first value inside the [begin, end) that >= value            * std::lower_bound(res, res+ans, a[i]) = a[i];        }    }    return ans; // the length of the answer}

(注：这个算法只能输出正确的LIS长度，但是返回的res不是LIS序列。当时面试官也没意识到，我也没想起来。)

//———————-

total number of longest increasing sequence.

1 (1, 2, 3, 4, 5).

seq: 5 4 3

3: (5, or 4, or 3).

seq: 1, 1, 2

2: (1 (1st), 2, or 1 (2nd), 2)

struct Record{    int max_length;    int number; // how many largest sequence}rec[N]; // 1, 3, 2, 5, 4// max = 31 -> {1, 1}1, 3, -> {2, 1}1, 3, 2 -> rec = {2, 1}1, 3, 2, 5 -> {2, 1}// put 1 before 5           -> {3, 1} // put seq1,3 before 5           -> {3, 2} // add seq 1,2 before 51, 3, 2, 5, 4 -> {3, 2} result = {3, 4}total_max = 3total_number = 4 //init rec to {1, 1}int total_max = 0;int total_number = 0;for(int i = 0; i < n; ++i){    for(int j = 0; j < i; ++j){        if(a[i] > a[j]) { // a[j] can put before a[i]            if(rec[j].max_length + 1 > rec[i].max_length){                rec[i].max_length = rec[j].max_length + 1;                rec[i].number = rec[j].number;            }            else if(rec[j].max_length + 1 == rec[i].max_length){                rec[i].number += rec[j].number;            }         }     }     if(rec[i].max_length > total_max){         total_number = rec[i].number;         total_max = rec[i].max_length;     }     else if(rec[i].max_length == total_max){         total_number += rec[i].number;     }}// then total_number is our result.

=========================================

两天后收到email，电话面试结束，接下来就是办签证，然后去美国onsite interview