临时抱佛脚

将要迎来到美国之后的第一个onsite interview了，来自一个半导体芯片公司Qualcomm，大公司，很不错。希望不要浪掷机会。

赶紧上mitbbs的JobHunting版去找以前有关Qualcomm的面试题，还真看见一个有用的：
－－－
发信人: Zhuimeng1314 ( 追梦一生), 信区: JobHunting
标 题: Qualcomm 电面面经
发信站: BBS 未名空间站 (Fri Mar 11 21:31:21 2011, 美东)

问简历
如何测试一个DVD player

第二题
int x=20; int y=35;
x=y+++x++;
y=++y+++x;
问之后x 和y 是多少

第三题
怎样交换两个数而不用temp （XOR）

哎。。简历被问得SB了。。

 
 
发信人: luckyseeker (lucky), 信区: JobHunting
标 题: Re: Qualcomm 电面面经
发信站: BBS 未名空间站 (Fri Mar 11 23:33:28 2011, 美东)

我靠，第一题我用C和java分别run了一下，居然结果不一样。

java的结果（run in eclipse 3.6.1）
x=55, y=36 //第一步
x=56, y=93 //第二步

C的结果（cygwin + gcc）
x=56, y=36 //第一步
x=57, y=94 //第二步

顺便说一下，y=++y+++x;两个都报错，至少要空一格写成：y=++y+ ++x;
觉得java下面，第一步算出来x=20+55 = 55，后面的x++不运行。
但是C下面，x=55之后，x++还要先加再用一次，就变成了56。
跟内存模式有关么？是不是java下面的left side构造了一个新地址for x?



发信人: Zhuimeng1314 ( 追梦一生), 信区: JobHunting
标 题: Re: Qualcomm 电面面经
发信站: BBS 未名空间站 (Sat Mar 12 01:09:42 2011, 美东)

我问用来播放什么，用来干什么。。他不说。。。
不过我倒是没想到遥控器什么的
还有什么是bt测试？我完全不知道。。
盗版盘用英文怎么说？

【 在 HanSolo7 (隼) 的大作中提到: 】
: 如何测试一个DVD player:
: 先询问对方：　用来做什么？播放什么？谁使用？接什么电视？在哪个国家？
: 测试项目：　DVD机器本身，遥控器，连接线
: 然后测试各种功能：普通测试，极限测试，bt测试（比如同时操作遥控器和DVD机
: 器上的按钮，盗版盘测试）。。。。



发信人: done (折埋), 信区: JobHunting
标 题: Re: Qualcomm 电面面经
发信站: BBS 未名空间站 (Sat Mar 12 01:10:49 2011, 美东)

以前版上有无数人说过，这++的题不同编译器的结果是不一样的



发信人: done (折埋), 信区: JobHunting
标 题: Re: Qualcomm 电面面经
发信站: BBS 未名空间站 (Sat Mar 12 01:15:42 2011, 美东)

我认为凭自己的理解知道i++和++i的区别去计算结果就好了。
或者如牛人说的，直接答"如果谁敢写这种code就马上炒了他/她"

【 在 Zhuimeng1314 ( 追梦一生) 的大作中提到: 】
: 哦~~那他拿来折磨我。。。
－－－
对这个帖子，我所关心的是第三个题：如何交换两个数而不用临时变量。

正如楼主说用，用xor可以做到。参见Bit Twidding Hacks上面的文章：http://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesXOR

Swapping values with XOR

#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

This is an old trick to exchange the values of the variables a and b without using extra space for a temporary variable.

On January 20, 2005, Iain A. Fleming pointed out that the macro above doesn't work when you swap with the same memory location, such as SWAP(a[i], a[j]) with i == j. So if that may occur, consider defining the macro as (((a) == (b))

(((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))). On July 14, 2009, Hallvard Furuseth suggested that on some machines, (((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b))) might be faster, since the (a) ^ (b) expression is reused.

还有一种方法是用加减法：http://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesSubAdd

Swapping values with subtraction and addition

#define SWAP(a, b) ((&(a) == &(b)) \
                                 (((a) -= (b)), ((b) += (a)), ((a) = (b) - (a))))

This swaps the values of a and b without using a temporary variable. The initial check for a and b being the same location in memory may be omitted when you know this can't happen. (The compiler may omit it anyway as an optimization.) If you enable overflows exceptions, then pass unsigned values so an exception isn't thrown. The XOR method that follows may be slightly faster on some machines. Don't use this with floating-point numbers (unless you operate on their raw integer representations).

Sanjeev Sivasankaran suggested I add this on June 12, 2007. Vincent Lefèvre pointed out the potential for overflow exceptions on July 9, 2008

这种方法更易于理解，不过有overflow的危险，且不能用于浮点数的交换。话说回来，异或算法也不是没有缺点。比如当两个要交换的值相同的时候，用这种方法会使之成为零（因为A^A == 0）。

对于这两种算法的证明和分析，可以参考wikipedia上面的链接：http://en.wikipedia.org/wiki/XOR_swap_algorithm

核心在于异或几条类似于加法的性质。

The binary operation XOR over bit strings of length N exhibits the following properties (where denotes XOR):

L1. Commutativity: A ^ B = B ^ A （中文名称：交换律）
L2. Associativity: (A ^ B) ^ C = A ^ (B ^ C) （中文名称：结合律）
L3. Identity exists: there is a bit string, 0, (of length N) such that for any A ^ 0 = A （这个性质中文该怎么讲？）
L4. Each element is its own inverse: for each A, A ^ A = 0. （这个性质和加法就有些区别了）

值得注意的是，加减swap可以看作是异或swap的一个扩展。

Find both the duplicated number and the missing number

How to find the duplicate and missing number in an array of unsorted set of continuous numbers (1 to N)?

Solution from http://anuviswan.blogspot.com/2007/08/missing-and-duplicate-number-algorithm.html:

1. Find RealSum = ( sum of all numbers in array )
2. Find RealProduct = ( product of all numbers in array )
3. Find ExpectedSum = n*(n+1) / 2 where n is number of integers
4. Find ExpectedProduct = n!

Equation 1 : X - Y = (RealSum - ExpectedSum)
Equation 2 : X/Y = (RealProduct / ExpectedProduct)

Solve this equation.

X is the duplicated number
Y is the missing number

这种算法易于理解，且实现很简单，但有overflow的危险。能否用异或的方法解决呢？其实也是可以的。

把这个给定的set里面所有的数都xor一遍，可以看出，duplicate的两个数字必定相互抵消。换句话说，相当于duplicate的数字missing了。

从而我们可以得出结论：如果set里面有duplicate，那么finding duplicate的问题可以等价为finding missing element的问题。如果set里面有一个数字duplicate，那么可以转化为求一个missing number的问题。如果set里面有一个duplicate和一个missing，那么找出它们和找出两个missing numbers是等价的。

Find duplicates

从MITBBS上面看来的brainteaser题目：
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
发信人: hytt (荷叶田田), 信区: JobHunting

标 题: 两道algorithm电面题(update 答案）
发信站: BBS 未名空间站 (Wed Mar 16 13:31:32 2011, 美东)

两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b， 把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。

——————————————————————————

应该算很简单的，我实在是比较水，学艺不精：

1) A big array with a thousand and one elements storing integers from 1 to 1000, not sorted. One number is duplicated. How do you find the duplicated number most efficiently?

2) An array with 1000-1 elements storing integers from 1 to 1000, not sorted. One number is missing in the array. How do you find that missing number in the most efficient way.
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
荷叶田田的第二个题在NetApp的电面中已经碰到过，就不再赘述了。最简单的方法就是用加减法：先把1到1000连续加起来，再把给定的数组中每个元素的值全部相加，两个结果相减，就得到missing的那个数了。当然如果有两个数missing的话，就要用异或的方法了。

正如荷叶田田所提到的，第一个题也可以用上述的加减法来判断duplicate的数字。不过，如果两个或两个以上的数字出现重复，这个方法就不太好使了。他/她的面试官提到的方法本质上就是利用了一个associative container，比如map或者hash table。

以下的程序可供参考：
#include <iostream>
#include <map>

#define NELEMS(array) (sizeof(array)/sizeof(array[0]))

using namespace std;

int main()
{
    int arr[8] = {3, 2, 7, 4, 4, 6, 1, 5};
    map counters;

    for (int i = 0; i < NELEMS(arr); ++i)
        ++counters[arr[i]];

    for (map::const_iterator it = counters.begin();
          it != counters.end(); ++it)
    {
        cout << it->first << "\t" << it->second << endl;
    }

    return 0;
}
这段代码是将《Accelerated C++》里面Section 7.2里面的例子稍作修改而来。

更全面的总结可以看这里：http://geeksforgeeks.org/?p=7953，其中的Method 2、3、4比较有意思。

Method 2 (Use Count array)

Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, print it as duplicate.

This method uses the range given in the question to restrict the size of count[], but doesn’t use the data that there are only two repeating elements.

#include <stdio.h>
#include <stdlib.h>

void printRepeating(int arr[], int size)
{
    int *count = (int *)calloc(sizeof(int), (size - 2));
    int i;

    printf("Repeating elements are ");

    for (i = 0; i < size; i++)
    {
        if (count[arr[i]] == 1)
            printf(" %d ", arr[i]);
        else
            count[arr[i]]++;
    }

    free(count);
    return;
}

int main()
{
    int arr[] = {4, 2, 4, 5, 2, 3, 1};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    printRepeating(arr, arr_size);

    getchar();
    return 0;
}

Time Complexity: O(n)
Auxiliary Space: O(n)

Method 3 (Make two equations)

We have to find two numbers, so two unknowns. We know the sum of n numbers is n(n+1)/2 and product is n!. Make two equations using these sum and product formulas, and get values of two unknowns using the two equations.

Let summation of all numbers in array be S and product be P.
Let the numbers which are being repeated are X and Y.

X + Y = S – n(n+1)/2
XY = P/n!

Using above two equations, we can find out X and Y. For array = 4 2 4 5 2 3 1, we get S = 21 and P as 960.

X + Y = 21 – 15 = 6
XY = 960/5! = 8

X – Y = sqrt((X+Y)^2 – 4*XY) = sqrt(4) = 2

Using below two equations, we easily get X = (6 + 2)/2 and Y = (6-2)/2

X + Y = 6
X – Y = 2

Thanks to geek4u for suggesting this method. As pointed by Beginer , there can be addition and multiplication overflow problem with this approach.

#include <stdio.h>
#include <stdlib.h>>
#include <math.h>

/* function to get factorial of n */
int fact(int n);

void printRepeating(int arr[], int size)

{

    int S = 0; /* S is for sum of elements in arr[] */

    int P = 1; /* P is for product of elements in arr[] */

    int x, y; /* x and y are two repeating elements */

    int D; /* D is for difference of x and y, i.e., x-y */

    int n = size - 2, i;

    /* Calculate Sum and Product of all elements in arr[] */

    for (i = 0; i < size; i++)

    {

        S = S + arr[i];

        P = P*arr[i];

    }

    S = S - n*(n+1)/2; /* S is x + y now */

    P = P/fact(n); /* P is x*y now */

    D = sqrt(S*S - 4*P); /* D is x - y now */

    x = (D + S)/2;

    y = (S - D)/2;

    printf("The two Repeating elements are %d & %d", x, y);

    return;

}

int fact(int n)

{

    return (n == 0)? 1 : n*fact(n-1);

}

int main()

{

    int arr[] = {4, 2, 4, 5, 2, 3, 1};

    int arr_size = sizeof(arr)/sizeof(arr[0]);

    printRepeating(arr, arr_size);

    getchar();

    return 0;

}

Time Complexity: O(n)
Auxiliary Space: O(1)

Method 4 (Use XOR)

Thanks to neophyte for suggesting this method.

The approach used here is similar to method 2 of this post.

Let the repeating numbers be X and Y, if we xor all the elements in the array and all integers from 1 to n, then the result is X xor Y.

The 1’s in binary representation of X xor Y is corresponding to the different bits between X and Y. Suppose that the kth bit of X xor Y is 1, we can xor all the elements in the array and all integers from 1 to n, whose kth bits are 1. The result will be one of X and Y.

void printRepeating(int arr[], int size)
{
    int xor = arr[0]; /* Will hold xor of all elements */
    int set_bit_no; /* Will have only single set bit of xor */
    int i;
    int n = size - 2;
    int x = 0, y = 0;

    /* Get the xor of all elements in arr[] and {1, 2 .. n} */
    for (i = 0; i < size; i++)
        xor ^= arr[i];
    for (i = 1; i <= n; i++)
        xor ^= i;

    /* Get the rightmost set bit in set_bit_no */
    set_bit_no = xor & ~(xor-1);

    /* Now divide elements in two sets by comparing rightmost set
        bit of xor with bit at same position in each element. */
    for (i = 0; i < size; i++)
    {
        if (arr[i] & set_bit_no)
            x = x ^ arr[i]; /* XOR of first set in arr[] */
        else
            y = y ^ arr[i]; /* XOR of second set in arr[] */
    }
    for (i = 1; i <= n; i++)
    {
        if (i & set_bit_no)
            x = x ^ i; /* XOR of first set in arr[] and {1, 2, ...n } */
        else
            y = y ^ i; /* XOR of second set in arr[] and {1, 2, ...n } */
    }

    printf("\n The two repeating elements are %d & %d ", x, y);
    return;
}

int main()
{
    int arr[] = {4, 2, 4, 5, 2, 3, 1};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    printRepeating(arr, arr_size);

    getchar();
    return 0;
}

NetApp的Phone Interview惨败（五）

9. 一个很大的整型数组（length possibly reaches millions），里面有duplicate，用怎样的方法可以快速地去除这些duplicate？

我感觉应该先把这个数组sort一下，但是之后该怎么办呢？完全没有思路。当时只提到了用quicksort排序先，没想到面试官接着又问quicksort的工作原理。

亏了我前晚在看1337coder的blog关于recursion的文章的时候顺带查了一下The C Programming Language, 2nd Edition, by K&R，大概是第87页上谈到了quicksort()的实现。The Practice of Programming by K&R的第32~34页上也谈到了其实现，还给出了算法的量级。

我就和他大致讲了一下quicksort的实现思路。不料他又继续追问这个算法的量级，这个TCPL没有提到，TPOP提到了，但我没有仔细看。结果随口报了个O(logN)的量级，他没做声。后来我翻书一查，才发现是O(NLogN)的量级。操，又挨了一刀。

OK，转入正题。究竟该怎样做才可以remove duplicates呢？下面是我在mitbbs上的求助和高手的应助：
－－－
一个很大的整型数组，里面有duplicate，用怎样的方法可以快速地去除这些duplicate？我感觉应该先把这个数组sort一下，但是之后该怎么办呢？完全没有思路。

by johny

bitmap比较好，当然sort也可以做。这个有个问题就是，可能in-place remove 所用的两个指针所指的位置不能同时装入内存，这个问题还没想好如何解决。

by Chevy

bitmap不是图形格式吗？能把数组变成一个bitmap？不太懂啊。能不能给段代码的例子？

by johny

bitmap你可以看看programming pearls的第一章

by Chevy

还有其他的方法吗？

by johny

我知道的就这些了。如果本来已经排序好了的话，可以用binary search，在O(logN)时间内找到一个。

by Chevy

binary search倒是可以用，但找到以后，还要把duplicate从这个大数组里面剔除，我所能想到的只有remove之后，再依次把后面的element向前挪一位依次填坑，但似乎这样太影performance。

当时面试官给的提示是再新建一个数组，似乎他的意思是把没有duplicate的element往新数组里面扔。而且他还提到的hashtable，这个地方该怎样应用hashtable呢？

by johny

你每次遇到一个数，先判断已经在不在hashtable中，在的话说明重复；不在的话，插入hashtable。

by Chevy

Remove duplicates 的 Sort 的方法如下：

/* Remove the duplicates in place, and returns
   the new size of the array. Assumes the array
   is already sorted. */
int removeDuplicates(int A[], int n) {
    int j = 0;

    for (int i = 0; i < n; i++) {
        if (A[i] != A[j])
            A[++j] = A[i];
    }

    return j+1;
}

by ihasleetcode

已经验证过了，确实可以实现in place remove duplicates. 顺便问一下，这段code在你的blog里面出现过吗？这是个有名的算法吗？

当时面试官给的提示是再新建一个数组，似乎他的意思是把没有duplicate的element往新数组里面扔。他还提到要用hashtable的方法，这个地方该怎样应用hashtable呢？据他说用hashtable的话，就用不着先对数组进行排序了。

我对hashtable没什么概念，只知道是个key-value pair的table。似乎还要定义一个hash function来建立从key到value之间的mapping关系。

如果用面试官所说的方法，该怎么解呢？可否给个example code？

by johny
－－－
还没有完全解开，但已经有了大致的思路。其一是参照Programming Pearl第一章去用所谓的“bitmap”；其二是“每次遇到一个数，先判断已经在不在hashtable中，在的话说明重复；不在的话，插入hashtable”，但关于hash的知识还得补；其三为in-place removal as 1337 exampled（当然要先quicksort一把）。


后续的帖子：
－－－
不要sorting的remove duplicate：

const int REMOVE = -1000;

int removeduplicate(int a[], int n) {
    unordered_map hash;

    for(int i = 0; i < n; i++) {
        if(hash.find(a[i]) != hash.end()) {
            a[i] = REMOVE;
        } else {
            hash[a[i]] = 1;
        }
    }

    int j=0;
    int i=0;

    while (i < n) {
        while (a[i] == REMOVE) {
            i++;
        }
        a[j] = a[i];
        i++;
        j++;
    }

    return j;
}

by icn9

谢谢啊。这两天我也在学习hashtable的方法，刚好看到C++里面有个map可以用。调试了一下你的程序，稍作调整后的code如下：

#include <iostream>
//#include <unordered_map>
#include <map>

using namespace std;

const int REMOVE = -1000;

int remove_duplicate(int a[], int n) {
    int i = 0, j = 0;
    //unordered_map hash;
    map hash;

    for (i = 0; i < n; ++i) {
        if (hash.find(a[i]) != hash.end()) {
            a[i] = REMOVE;
        } else {
            hash[a[i]] = 1;
        }
    }

    j = 0;
    i = 0;

    while (i < n) {
        while (a[i] == REMOVE) {
            i++;
        }
        a[j] = a[i];
        i++;
        j++;
    }

    return j;
}

int main()
{
    int arr[8] = {3, 2, 7, 4, 4, 6, 1, 5};
    int len = 0, i = 0;

    len = remove_duplicate(arr, sizeof(arr));
    cout << "The new size of arr[] is " << len << endl;

    for (i = 0; i < len; ++i)
        cout << arr[i] << "\t";
    cout << endl;

    getchar();
    return 0;
}

我在windows xp下的用的是Dev-C++，似乎比较老，因此而不支持，因此我把它改成map了。但编译通过后，跑出来的结果很奇怪，见附图。能帮我看一下是什么导致的吗？

by johny

You passed a wrong size of the array and accessed memory out of boundary:

    int arr[8] = {3, 2, 7, 4, 4, 6, 1, 5};
    ...
    len = remove_duplicate(arr, sizeof(arr));

When sizeof is applied to an array, the result is the size in bytes of the array in memory. Thus, it should be changed to:

    len = remove_duplicate(arr, sizeof(arr)/sizeof(int));

by recursive

多谢，确实是这个问题。我的疏忽。改成remove_duplicate(arr, sizeof(arr)/sizeof(arr[0]))了，编译通过，运行正常。多谢指出这个错误。

不过，Dev-C++似乎不支持unordered_map。这个模板类不在C++的标准库里面吗？但是我用了1337coder的coding panel，也是有通不过这个模板类的编译。

为什么呢？

by johny

你的问题不在于map和unordered_map的区别。
不过如果你要用到unordered_map，可以这样写：

    #include <tr1/unordered_map>
    ...
    tr1::unordered_map hash;

同时这两个东西是有区别的，你应该要能理解他们的不同。

by recursive

: 你的问题不在于map和unordered_map的区别。

那倒是。用unordered_map的想法是不想用map对数组重新排序。节省一点CPU开销，出于performance的考虑。不过对这个测试程序来说，也许用不着。

: 不过如果你要用到unordered_map，可以这样写：
:     #include <tr1/unordered_map>
:     ...
:     tr1::unordered_map hash;
: 同时这两个东西是有区别的，你应该要能理解他们的不同。

谢谢提醒啊。加上你提示的改变之后，1337的coding panel可以通过，并顺利跑起来了。但是Dev-C++的编译还是报错。看来应该是编译器有点老了（2005年最后一个release）。

你的意思是unordered_map与tr1::unordered_map有区别吗？

by johny
－－－
这个问题到这里基本告一段落，特别感谢Chevy、1337、icn9与recursive同学。

NetApp的Phone Interview惨败（四）

8. 给我9999个数字，数值连续从1到10000，但缺了一个。要求用一种非常简洁的方法得出缺了哪个数字？

完全不会，面试官的答案是从1连续加到10000，得到A；再把给定的9999个数字加起来，得到B；然后A - B即可。

他后来又说，如果是9998个数字，数值从1到10000，缺两个。这种情况该怎么处理？

以下是我在mitbbs上求助和高手的应助：
－－－
给我9999个数字，数值连续从1到10000，但缺了一个。要求用一种非常简洁的方法得出缺了哪个数字？

by johny

方法很多：
a. 全部加起来，看缺多少，就是哪个数
b. 1xor2xor...10000，然后继续xor给的9999个数字

by Chevy

这第一个方法就是面试官后来跟我说的。不过他后来又说，如果是9998个数字，数值从1到10000，缺两个，加法就貌似不行了。这种情况下，该用什么方法呢？

by johny

两个的话，可以解方程：
x+y+其他9998个数 = 1+...+10000
x^2+y^2+...=1^2+...+10000^2

by Chevy

两个仍然用xor
不然很可能溢出

by fzblg

不明白这个xor解法的原理是什么，可以简单讲一下或给个参考文献吗？

by johny

xor有个性质就是，对于一个数a，a xor a = 0
所以用这个性质其他9999个数都消掉了。

by Chevy

没找到，我试着讲一下：仍然按照Chevy的方法做。

如果是一个数：最后的结果就是M。
如果是两个数：结果就是M1 xor M2。

从这个结果中挑一个bit为1的，就可以把原数组划分为两组。missing numbers分别在这两个组中。

然后，按照1个数的方法再分别做一遍。据说这个思路可以扩展到3个，4个数去。

有个类似的http://geeksforgeeks.org/?p=2457

by fzblg
－－－
从这些帖子，我可以理解一个数的解法。但对于两个数的解法，还是有些迷惑。



去到fzblg提供的链接，仔细读了一番，终于基本搞明白了。

Given an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way.

Method 1(Use Sorting)
First sort all the elements. In the sorted array, by comparing adjacent elements we can easily get the non-repeating elements. Time complexity of this method is O(nLogn).

Method 2(Use XOR)
Let x and y be the non-repeating elements we are looking for and arr[] be the input array. First calculate the XOR of all the array elements.

        xor = arr[0]^arr[1]^arr[2].....arr[n-1]

All the bits that are set in xor will be set in one non-repeating element (x or y) and not in other. So if we take any set bit of xor and divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, we will get x in one set and y in another set. Now if we do XOR of all the elements in first set, we will get first non-repeating element, and by doing same in other set we will get the second non-repeating element.

Let us see an example.
        arr[] = {2, 4, 7, 9, 2, 4}
1) Get the XOR of all the elements.
        xor = 2^4^7^9^2^4 = 14 (1110)
2) Get a number which has only one set bit of the xor.
    Since we can easily get the rightmost set bit, let us use it.
        set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010
    Now set_bit_no will have only set as rightmost set bit of xor.
3) Now divide the elements in two sets and do xor of
    elements in each set, and we get the non-repeating
    elements 7 and 9. Please see implementation for this
    step.

Implementation:

#include <stdio.h>
#include <stdlib.h>

/* This function sets the values of *x and

   *y to non-repeating elements in an array
   arr[] of size n */
void get2NonRepeatingNos(int arr[], int n, int *x, int *y)

{

  int xor = arr[0]; /* Will hold xor of all elements */

  int set_bit_no;  /* Will have only single set bit of xor */
  int i;

  *x = 0;

  *y = 0;  

    /* Get the xor of all elements */

  for(i = 1; i < n; i++)
    xor ^= arr[i];

  /* Get the rightmost set bit in set_bit_no */

  set_bit_no = xor & ~(xor-1);

    /* Now divide elements in two sets by comparing
     rightmost set bit of xor with bit at same
     position in each element. */

  for (i=0; i < n; i++)

  {

    if(arr[i] & set_bit_no)

      *x = *x ^ arr[i]; /* XOR of 1st set */

    else

      *y = *y ^ arr[i]; /* XOR of 2nd set */

  }

} 

/* Driver program to test above function */

int main()
{ 
  int arr[] = {2, 3, 7, 9, 11, 2, 3, 11};

//johny.0
  /* if we declare "int x" and "int y" here, and
     call "get2NonRepeatingNos(..., &x, &y)", we
     would not need to free them later */
//johny.1
  int *x = (int *)malloc(sizeof(int));

  int *y = (int *)malloc(sizeof(int));

  get2NonRepeatingNos(arr, 8, x, y); 

  printf("The non-repeating elements are %d and %d",

         *x, *y); 

  getchar();

//johny.0

  free(x);

  free(y);

  return 0; 

//johny.1

}

Time Complexity: O(n)
Auxiliary Space: O(1)


Can some1 explain me the logical part of how it works? I find it difficult to analyse it.

by nn

XOR of two same numbers results in 0(000..00).

XOR of two different numbers x and y results in a number which contains set bits at the places where x and y differ. So if x and y are 10...0100 and 11...1001, then result would be 01...1101.

So the idea is to XOR all the elements in set. In the result xor, all repeating elements would nullify each other. The result would contain the set bits where two non-repeating elements differ.

Now, if we take any set bit of the result xor and again do XOR of the subset where that particular bit is set, we get the one non-repeating element. And for other non-repeating element we can take the subset where that particular bit is not set.

We have chosen the rightmost set bit of the xor as it is easy to find out.

by Sandeep

这个帖子和里面的code基本把要点都讲到了，非常好。其实，昨天面试官出的题目本质上就是这个题。设想9998个数的数值是1到10000，缺了两个。然后我再补上连续的1到10000，原来找漏的问题不就是变成找出两个non-repeated numbers了吗？


对于缺两个数的情形，程锦后来提出一个巧妙的算法：在1~10000中，大致找到一个中点，比如5000这个数，分别计算1+...+5000 = A；5001+...+10000 = B。接着再把给定的9998个数分成两堆，一堆是1到5000，另一堆是5001到10000，分别求两堆的和，设为C和D。然后A-B，再C-D，如果两个差俱不为0，那么说明漏掉的数一边一个，得出的两个差值就是漏掉的两个数。如果任何一个差为0，就说明两个漏掉的数在另一堆里面。假设是在5001到10000这一堆里面，则下一步为在这一堆里面找一个中点，再重复上面的步骤。这样，总有一个时刻，会有两个差都不为0的时候。

这是个类似binary search的解法。虽然程锦没有CS的背景，可她有一颗比我聪明得多的脑袋，呵呵。

NetApp的Phone Interview惨败（三）

6. CIFS SMB protocol里面，当要read big chunks of data的时候，client端send出去的message type是什么？

这个我也不会。以前在工作中都是用Wireshark检查SMB的network trace，而且主要是关注authentication这块（所用的msg type似乎是SESSION SETUP ANDX REQUEST ），很少bug是发生在data transfer中的，所以也未曾关注过其msg type。不过，只要手上有一个SMB的trace，用Wireshark应该很容易看得出来的。

依稀记得这个msg type是“User Data”？不确切，网络上也找不到这方面的准确资料。留待以后手上有trace再说吧。Not a critical problem, after all.


7. 一个storage server的运行过程中，突然出现stop responding的现象。如果不看code，不看GDB的trace和应用程序的log，该怎样快速诊断出可能的原因？

当时面试官和我说的是这种问题，第一个想法应该是不是disk IO出问题了？也有可能是database的操作出了问题，因为database的操作和读写硬盘紧密相关。不过我想，不看log，不看trace，怎么能断定是disk IO的问题？莫非去看硬盘指示灯？

因为电面表现太差，也没好意思去详细问这个问题的思路。

NetApp的Phone Interview惨败（二）

4. Perl里面，$_的含义是什么？

说实话，我的Perl都是自学的，工作中基本用不到。不过既然写进简历里面（号称精通Perl），就免不了要被问到。而且一问就问倒了。

以下是从Perl in A Nutshell的Section 4.4.1里面抄来的：

The most common special variable is $_, which contains the default input and pattern-searching string. For example:

foreach ('hickory','dickory','doc') {
        print;
}

The first time the loop is executed, "hickory" is printed. The second time around, "dickory" is printed, and the third time, "doc" is printed. That's because in each iteration of the loop, the current string is placed in $_ and is used by default by print. Here are the places where Perl will assume $_, even if you don't specify it:

• Various unary functions, including functions such as ord and int, as well as the all file tests (-f, -d), except for -t, which defaults to STDIN.
• Various list functions such as print and unlink.
• The pattern-matching operations m//, s///, and tr/// when used without an =~ operator.
• The default iterator variable in a foreach loop if no other variable is supplied.
• The implicit iterator variable in the grep and map functions.  
• The default place to put an input record when a line-input operation's result is tested by itself as the sole criterion of a while test (i.e., ). Note that outside of a while test, this does not happen.

说实话，还是看不太明白，毕竟没有真正在工作中应用过，印象不深。Interviewer看我这个粗浅的问题都答不上来，就没再往下问Perl的东西了。


5. C++里面，virtual class的作用是什么？

操，我只听说过virtual function，可从来没听说过virtual class，这下抓瞎了。听他的意思好象是用在inheritance里面，防止出现多个instance？我记不太清楚他说的答案了。

万能的Google又一次找到了答案：http://publib.boulder.ibm.com/infocenter/comphelp/v8v101/topic/com.ibm.xlcpp8a.doc/language/ref/cplr135.htm

其实就是多重继承时，若中间层的class共有同一个祖先，则定义中间层级的class时，将他们声明为继承virtual祖先class就可以防止底层class（从多个中间层的class继承下来）拥有多个祖先class的copy。其实，Bjarne Stroustrup大神的C++ Bible之Section 15.2.4里面也谈到了这个问题。

NetApp的Phone Interview惨败（一）

1. What is the difference between a mutex and a spinlock?

当头第一棒，一下子就把我捶晕了。mutex我当然明白了，就是个binary semaphore。但是spinlock我从没接触过。

在网上搜索一番，总算找到了答案：
http://www.alexonlinux.com/pthread-spinlocks
http://www.alexonlinux.com/pthread-mutex-vs-pthread-spinlock

According to the author, spinlock is more effective (than mutex) in term of CPU consumption and speed.

Things to note:

(1) Spinlocks perform better than mutexes in this particular setup, on multi-processor computer.
(2) Spinlocks are totally useless on uni-processor computers. This is due to a nature of spinlocks.


2. GDB调试程序的时候，attach之后，怎样显示thread information？

这个我也傻眼了。以前用GDB的时候最多就是用backtrace（bt）命令检查一下coredump里面的信息，还真没用过attach，更不要说显示线程信息了。

还是Google帮忙：
http://sourceware.org/gdb/onlinedocs/gdb/Threads.html
http://developer.apple.com/library/mac/#documentation/DeveloperTools/gdb/gdb/gdb_5.html
http://stackoverflow.com/questions/47701/is-there-a-way-to-attach-a-debugger-to-a-multi-threaded-python-process

The most basic command is "info threads".


3. In network socket programming, what are the basic APIs?

我提到先用socket()做initialization，再分配address，whether it is IPv4 or IPv6。接着在server端是listen() and accept()，在client端，开始也是initialization，接着应该是某个send request的function，但是具体我记不清了，以前在Richard Stevens的Unix Network Programming, 2nd Edition, Volume 1里面见过。

Interviewer后来说client端send出request的function是connect()，server端还缺少一个bind()。

考这个题我稍微有点意见，何必问这种书上一查就有的东西呢？当然，如果说从这个问题察看我网络编程的熟练程度，我也无话可说。

还是查一下Stevens的书吧，先看server的例子：

1 #include "unp.h"

2 int
3 main(int argc, char **argv)
4 {
5     int listenfd, connfd;
6     pid_t childpid;
7     socklen_t clilen;
8     struct sockaddr_in cliaddr, servaddr;

9     listenfd = Socket (AF_INET, SOCK_STREAM, 0);

10   bzero(&servaddr, sizeof(servaddr));
11   servaddr.sin_family = AF_INET;
12   servaddr.sin_addr.s_addr = htonl (INADDR_ANY);
13   servaddr.sin_port = htons (SERV_PORT);

14   Bind(listenfd, (SA *) &servaddr, sizeof(servaddr));

15   Listen(listenfd, LISTENQ);

16   for ( ; ; ) {
17       clilen = sizeof(cliaddr);
18       connfd = Accept(listenfd, (SA *) &cliaddr, &clilen);

19       if ( (childpid = Fork()) == 0) { /* child process */
20           Close(listenfd); /* close listening socket */
21           str_echo(connfd); /* process the request */
22           exit (0);
23       }
24       Close(connfd); /* parent closes connected socket */
25   }
26 }

1 #include "unp.h"

2 void
3 str_echo(int sockfd)
4 {
5     ssize_t n;
6     char buf[MAXLINE];

7   again:
8     while ( (n = read(sockfd, buf, MAXLINE)) > 0)
9         Writen(sockfd, buf, n);

10   if (n < 0 && errno == EINTR)
11       goto again;
12   else if (n < 0)
13       err_sys("str_echo: read error");
14 }

摘自Section 5.2 and 5.3，code都是self explanatory的，不用多说什么。

再来看看client端的code：

1 #include "unp.h"

2 int
3 main(int argc, char **argv)
4 {
5     int sockfd;
6     struct sockaddr_in servaddr;

7     if (argc != 2)
8         err_quit("usage: tcpcli ");

9     sockfd = Socket(AF_INET, SOCK_STREAM, 0);

10   bzero(&servaddr, sizeof(servaddr));
11   servaddr.sin_family = AF_INET;
12   servaddr.sin_port = htons(SERV_PORT);
13   Inet_pton(AF_INET, argv[1], &servaddr.sin_addr);

14   Connect(sockfd, (SA *) &servaddr, sizeof(servaddr));

15   str_cli(stdin, sockfd); /* do it all */

16   exit(0);
17 }

1 #include "unp.h"

2 void
3 str_cli(FILE *fp, int sockfd)
4 {
5     char sendline[MAXLINE], recvline[MAXLINE];

6     while (Fgets(sendline, MAXLINE, fp) != NULL) {
7         Writen(sockfd, sendline, strlen (sendline));

8         if (Readline(sockfd, recvline, MAXLINE) == 0)
9             err_quit("str_cli: server terminated prematurely");

10       Fputs(recvline, stdout);
11   }
12 }

摘自Section 5.4 and 5.5，也不用多作解释。没啥办法，手不熟，难怪会被问倒。

Wikipedia上面有个简洁的介绍：http://en.wikipedia.org/wiki/Berkeley_sockets，可供快速参考。

后来interviewer又问我，如果server有两个port可以accept connection from client，应该用怎样的function？我提到select()，他认可了，没有追究怎样实现的细节。问了我也不会。

这篇文章（http://stackoverflow.com/questions/3655053/python-listen-on-two-ports）谈到一些，不过细节还不是很深入。UNP第1卷第6章I/O Multiplexing也可以参考。

Basically, the idea is to create two sockets with each port, and listen on these two sockets. Then select() will let you know which socket is ready and when, so you can accept() appropriately.

这个Unix Socket FAQ论坛（http://developerweb.net/viewtopic.php?pid=23096）里面的mlampkin也简明扼要地列出了以下的要点：

The select function is designed to handle multiple sockets so the only changes you would need to make are:

* Create 3 more server sockets ( bound / listening ) with the new addresses - port pairs.
* Change the select nfds parameter from 1 to 4, add the new server sockets to the readfds group and potentially the errorfds group.
* When you call select and it returns, just iterate thru the readfds group with FD_ISSET to determine which socket actually is accepting a new connection.

While you could add a lot more complexity, in simplest terms that really should be about it...

by Michael

关于多线程死锁

从CSDN上面看来的讨论，很有启发性：
－－－
A_lock()
B_lock()
do_something()
A_unlock()
B_unlock()

是否能产生死锁，
死锁的条件是什么？

#1 by zhangjingyuhua

这样看不出来。
但是考虑下面这种情况：

void f1()
{
    A_lock();
    do_something(); #P1
    A_unlock();
}

void f2()
{
    B_lock();
    f1(); #P2
    B_unlock();
}

void do_something()
{
    B_lock();
    B_unlock();
}

例如两个线程，线程A调用f1,线程B调用f2。如果线程A执行到P1位置，线程B执行到P2位置。那么就死锁了。

A进入do_something且A获得了A_lock，里面有B_lock()，但是线程B已经获得了B_lock，而线程B这时却在等待f1中的A_lock。
这样就死锁了。
 
#2 by Jinhao
 
别跑题，是在一个函数中。

func()
{
    lock(A)
    lock(b)
    do something()
    unlock(b)
    unlock(A)
}

加锁顺序是：A->b
解锁顺序是：b->A

把题看清再说话。
 
#3 by zhangjingyuhua
 
麻烦你看清楚。已经说了，看不出来。
我写那段代码是回答你“死锁的条件是什么”这个问题。这与是不是在一个函数中无关。明白不？

如果你懂了，那你还跑到这里来问什么？

func()
{
    lock(A)
    lock(b)
    do something()
    unlock(b)
    unlock(A)
}

你觉得这个没问题？光看这个有什么用？

如果存在另一个函数：

func2()
{
    lock(B)
    lock(A)
    do something()
    unlock(A)
    unlock(B)
}

那你认为你的func有没有问题？
 
#4 by Jinhao
 
我在用别人的时，别人不应该在等我。
满足这一条就不会死了。

A_lock()
B_lock()
do_something()
A_unlock()
B_unlock()

除非do_something有对A_lock操作。
 
#5 by lin_style
 
单纯地这么看，不会有死锁。
其次，如果do_something里面会调用A_lock，则要看A_lock的实现。
最后，要保证正确操作锁的顺序，后入的锁要先出。

A_lock()
B_lock()
do_something()
B_unlock()
A_unlock() 

#6 by Jinhao
－－－
来源：http://topic.csdn.net/u/20090429/19/fffd3f89-6cea-4859-a57b-bd84c04ead96.html。我觉得最有用的是以下这么两句。

一、我在用别人的时，别人不应该在等我。满足这一条就不会死了。
二、要保证正确操作锁的顺序，后入的锁要先出。

mutex deadlock

Problems with Mutexes

An important problem associated with mutexes is the possibility of deadlock. A program can deadlock if two (or more) threads have stopped execution or are spinning permanently. The simplest deadlock situation: thread 1 locks lock A, thread 2 locks lock B, thread 1 wants lock B and thread 2 wants lock A. Instant deadlock. You can prevent this from happening by making sure threads acquire locks in an agreed order (lock ordering). Deadlock can also happen if threads do not unlock mutexes properly.

Race conditions occur when multiple threads share data and at least one of the threads accesses the data without going through a defined synchronization mechanism (Nichols 203). This could result in erroneous results even in an inconsistent manner which makes race conditions particularly difficult to debug. Library calls outside of your program's control are common culprits. Make sure you take steps within your program to enforce serial access to shared file descriptors and other external resources. On most Solaris man pages, you can find out if your library call is safe to use in reentrant code. Towards the bottom of the man page, you will see Categories of MT Library Calls. MT Safe means that the function can be called concurrently from different threads. MT Hot are "fast" MT Safe functions (usually not found on man pages). MT Unsafe means that the function cannot be called concurrently. Alternative means that there are MT Safe equivalents (e.g. gethostbyname() and gethostbyname_r()).

Another problem with mutexes is that contention for a mutex can lead to priority inversion. A higher priority thread can wait behind a lower priority thread if the lower priority thread holds a lock for which the higher priority thread is waiting. This can be eliminated/reduced by limiting the number of shared mutexes between different priority threads.

from http://randu.org/tutorials/threads/

言简意赅的一段，不错。

回来后又接到一个电话

是Bloomberg的电话面试，问一些C++的问题。不是很难，在《Accelerated C++》里面都有谈到过。但毕竟我是看书学习，没有什么hands-on exercise的经验，所以答得磕磕绊绊。最后那个面试者就说你不用过来面试了，因为Bloomberg expects quick and correct answers.

:-(

一天fail掉两个面试，看来还得加强基本功。没事要少看看围棋网站了。


主要跌跤的地方：

1. When is the copy constructor necessary?
我回答的是initialization的时候需要（这个对），还有就是convert的时候需要（这是错的，convert需要一个constructor，但不是copy constructor）。正确答案是：
－－－
11.3.6 The rule of three

Classes that manage resources such as memory require close attention to copy control. In general, the default operations will not suffice for such classes. Failure to control every copy can confuse users of the class and often will lead to run-time errors.

Consider our Vec class, but pretend that we did not define the copy constructor, assignment operator, or destructor. As we saw in §11.3.1/195, at best we will surprise our users. Users of Vec will almost surely expect that once they've copied one Vec into another, the two objects will be distinct. They will expect that operations on one Vec will not have any effect on the data held by the other.

Even worse, though, is that if we do not define a destructor, then the default destructor will be used. That destructor will destroy the pointer, but destroying a pointer does not free the space to which it points. The result will be a memory leak: The space consumed by Vecs will never be reclaimed.

If we fix the leak by providing a destructor, but we do not also add the copy constructor and assignment operator, then we set things up so that a crash is likely. In such a flawed implementation, it would be possible for two Vecs to share the same underlying storage, as we illustrated in the first diagram in §11.3.1/196. When one of those objects is destroyed, the destructor will destroy that shared storage. Any subsequent reference through the undestroyed copy will lead to disaster.

Classes that allocate resources in their constructors require that every copy deal correctly with those resources. Such classes almost surely need a destructor to free the resources. If the class needs a destructor, it almost surely needs a copy constructor, as well as an assignment operator. Copying or assigning objects of classes that allocate resources usually allocates those resources in the same way that creating an object from scratch does. To control every copy of objects of class T, you need

    T::T(); one or more constructors, perhaps with arguments
    T::~T() the destructor
    T::T(const T&) the copy constructor
    T::operator=(const T&) the assignment operator

Once we have defined these operations, the compiler will invoke them whenever an object of our type is created, copied, assigned, or destroyed. Remember that objects may be created, copied, or destroyed implicitly. Whether implicitly or explicitly, the compiler will invoke the appropriate operation.

Because the copy constructor, destructor, and assignment operator are so tightly coupled, the relationship among them has become known as the rule of three: If your class needs a destructor, it probably needs a copy constructor and an assignment operator too.
－－－
From Andrew Koenig's 《Accelerated C++》

2. Can a copy constructor be virtual?
正确答案：No. （原因尚不确切）Only destructors can be virtual.

3. When do we need a virtual destructor?
正确答案是：
－－－
Dynamic binding refers to the ability to select at run time which function to run based on the actual type of the object on which the function is called. Dynamic binding is in effect for calls to virtual functions made through a pointer or a reference. The fact that a function is virtual is inherited, and need not be repeated in the derived classes.

Derived classes are not required to redefine their virtual functions. If a class does not redefine a virtual, then it inherits the nearest definition for that function. However, any virtual functions that the class does contain must be defined. It is often a source of mysterious error messages from compilers to declare but not define a virtual function.

Overriding: A derived-class member function overrides a function with the same name in the base class if the two functions have the same number and types of parameters and both (or neither) are const. In that case, the return types must also match, except that as in §13.4.2/246, if the base-class function returns a pointer (or reference) to a class, the derived-class function can return a pointer (or reference) to a derived class. If the argument lists don't match, the base- and derived-class functions are effectively unrelated.

virtual destructors: If a pointer to the base class is used to delete an object that might actually be a derived-class object, then the base class needs a virtual destructor. If the class has no other need for a destructor, then the virtual destructor still must be defined and should be empty:

    class base {
    public:
        virtual ~base(){ }
    };

As with any other function, the virtual nature of the destructor is inherited by the derived classes, and there is no need to redefine the destructor in the derived classes.
－－－
Also from 《Accelerated C++》. 其实这第三个问题我知道什么时候需要一个destructor，就是总是无法精确地表达这层意思，关键还是没做过实际的C++项目，印象不深刻。

今天有个Qualcomm的面试

是第一轮，直接和hiring manager谈的。别的都还好，有两个问题。
1. White-board coding of factor function.
---
int factor(int n)
{
    int result;

    if (n == 1)
        return 1;
    else if (n > 0)
        result = factor(n - 1); /* should be result = n * factor (n - 1); */
    else
    {
        printf("input must be positive");
        return -1;
    }

    return result;
}
---
惭愧的是，这么个简单的白板写code都没有答对，非要等到manager说“Where is the multiplication?”我才想起来。

2. What is a thread deadlock?
这是我的死穴，以前工作中没有遇到过，也没有什么这方面的知识。一定要补一下。看来以后空闲的时候不能光看围棋，水木的C/C++版面也得经常去学习一下。要不碰到面试还真的没辙。

估计这次面试后，进入第二轮的希望不大。

static member in a class?

想起来Scott那天还问道static member in a class和non-static member有什么不同。前几天一直在看《Accelerated C++》，对这个有印象，就回答static member is not associated with any instance/object of the class（Section 13.4, Page 244~245）。

但是Scott又继续追问：“这个性质有什么作用？”我立刻就有些傻眼，当时书上好象是谈到这样做的话，外面的程序call这个static member func的时候，前面要加一个classi qualifier，比如这样：sort(students.begin(), students.end(), Student_info::compare)。好处是For our purposes, static member functions have one significant advantage: Their names are within the scope of their class. So, when we say that compare is a static member we are defining a function named Student_info::compare. Because the function has a qualified name, it does not overload the compare that we used to compare Core objects. Thus, our users will be able to call sort, passing Student_info::compare, and the compiler can know which function they want.



更详细的描述可以见于Section 15.2.3, Page 282~283：
－－－
15.2.3 Padding the output

We can now think about our padding function. Because we want to access this function from each of the derived classes, we'll define the pad operation as a function member of Pic_base that is both static and protected:

class Pic_base {
    // as before
protected:
    static void pad(std::ostream& os, wd_sz beg, wd_sz end) {
        while (beg != end) {
            os << " ";
            ++beg;
        }
    }
};

This function takes an ostream on which to write blanks, and two values that control how many blanks to write. When a display function needs to call pad, it will pass the current column number and one past the last column number that needs to be filled in by the current display operation. The pad function will fill this range with blanks.

Note the use of the static keyword on the declaration of pad. As we saw in §13.4/244, this use of static indicates that pad is a static member function. Such functions differ from an ordinary member function in that they are not associated with an object of the class type.

It may also be surprising that we can define a member function for an abstract base class. After all, if there can be no objects of the base class, why should there be member functions? However, remember that each derived object contains a base-class part. Each derived class also inherits any member functions defined in the base. Thus, a base-class function will execute on the base-class portion of a derived object. In this particular case, the function that we are defining is a static member, so the question of access to members of the base is moot. But it is important to realize that abstract classes may define data members, and (ordinary) member functions, as well as static ones. These functions will access the base-class objects that are part of derived objects.

Static members (both functions and static data members, which we can also define) are useful in that they let us minimize the names that are defined globally. Our pad function is a good example. We can imagine many abstractions that have the notion of padding. In this book we talked about padding in the context of writing a formatted report of student grades, as well as in the context of writing Pictures. If the Picture class were to define pad as a global function, then we would not also be able to define a pad function for Student_info, or vice versa. By making pad a static member, we allow for the fact that other abstractions in our program might have the notion of padding. As long as each class defines what pad means only in the context of the class, these mutually independent notions of padding can coexist within our program.
－－－
简言之，static member的好处就是可以minimize the names that are defined globally。但是当时没能明确地说出这一点，还是概念模糊所导致的。

想起来昨天有几个问题没有答好

1. 在C里面，string的data structure是什么？

我想来想去，C的string不就是用char *来表示的吗？比如以下的code：
－－－
char * pStr ＝ malloc(SOME_LEN + 1); /* + 1 for the ending 0x00 byte */
strcpy(pStr, ...);
－－－
不就是一块continuous memory area吗？

Scott似乎对这个答案不满意，但我实在也没想起来是什么。后来他告诉我C里面string是通过character array实现的。嗯，从数据结构的角度讲是这样的，不知为什么我总是没想起来。不过后来他问我这个array到什么时候终止我倒是答上来了，terminated with null character (0x00)，这个简单。



2. 同样是在C语言里面，除了strcat()以外，有没有其他concatenate string的方法？

我当时只能想出strcat()的方法，比如下面的帖子：
－－－
In C, strings are just char arrays. So you can't add to them directly.

Here is an example from cplusplus.com:

char str[80];
strcpy (str,"these ");
strcat (str,"strings ");
strcat (str,"are ");
strcat (str,"concatenated.");

So in your example, you would want:

char *foo = "foo";
char *bar = "bar";
char str[80];
strcpy (str, "TEXT ");
strcat (str, foo);
strcat (str, bar);

The return value of strcat can just be ignored, it returns the same pointer as was passed in for the first argument. You don't need this value. The return value is simply for convenience, so it allows you to chain the calls into one line of code.

For the first parameter, you need to have the destination buffer itself. The destination buffer must be a char array buffer. Example char buffer[1024];

Be very careful that the first parameter has enough space for what you're trying to copy in. If available to you, it is safer to use functions like: strcpy_s and strcat_s which explicitly specify the size of the destination buffer.

You can never use a string literal as a buffer, you must always use your own buffer.

by Brian R. Bondy in http://stackoverflow.com/questions/308695/c-string-concatenation
－－－
对我提的strcat()的答案，Scott应该是不满意的，但他当时也没有说成还有什么别的方法。


今天早上去跑步的时候，想到这个问题还是应该再琢磨一下，就去网上搜索了一下，看到下面的帖子：
－－－
Avoid using strcat. The cleanest and, most importantly, the safest way is to use snprintf:

char buf[256];
snprintf(buf, sizeof(buf), "%s%s%s%s", str1, str2, str3, str4);
 
by Alex B in http://stackoverflow.com/questions/308695/c-string-concatenation
 
sizeof() only works here for char buf[...]. NOT for char * buf = malloc(...). There aren't many differences between arrays and pointers, but this is one of them!
 
by Mr.Ree in http://stackoverflow.com/questions/308695/c-string-concatenation
 
Here's my problem: I have an array, which contains a command a[1], followed by several command args a[2], a[3], ...

What I need to do is the following

    •Create a string, consisting of the cmd and a combination of args e.g.: cmd arg1 arg2 arg3
    •Execute that command-string

Here's how I woud do it (pseudo-code):

    1.Precompute the length of each arg and store it in an array
    2.Get a combination (using GNU Scientific Library)
    3.Compute the size in bytes needed to allocate the string (length of cmd + 1 + lengthof arg1 + 1 + argn-1 + 1) (the +1 generally for the for the blank and at the end for the \0)
    4.Build the string by using strcat
    5.Execute the command-string

Well, it works but I wonder if using strcat that deliberately is actually efficient/the right way to do it. Any suggestions?

by Alok in http://stackoverflow.com/questions/2272418/efficient-string-concatenation-in-c

No, using strcat() is not efficient since it has to step through the string to find the end each time you call it.

Much better to either do it all at once using snprintf() if you have it (and can squeeze your arguments in there), or do it yourself using direct pointer manipulation.

Of course, for this to matter in practice you need to be running this command very often indeed.

by unwind in http://stackoverflow.com/questions/2272418/efficient-string-concatenation-in-c

strcat(), as well as all string manipulation functions from the standard library, is inefficient. this is due to way strings are stored in C, namely zero-terminated, thus each function has to find the end of the string by iterating over each character.

anyway, you are doing a premature optimization: the multiple strcat() calls here will execute really fast compared to the command execution, so you should not worry about the efficiency of your way of concatenating.

before optimizing part of a code, you have to show that it is a bottleneck and that optimizing will really improve execution time. in most cases, there is no need to optimize: it is simply not worth the time spent.

by Adrien Plisson in http://stackoverflow.com/questions/2272418/efficient-string-concatenation-in-c
－－－
哈，看到这些帖子我才想起来，以前我在写code的时候，确实在strcat()以外，还用过snprintf()来concatenate strings，昨天电话面试的时候，没想起来的原因可能是因为有一段时间没写code了，多少有些生疏所致。

跟Scott谈完之后，发现还有一个missed call

来自Oasis的Jon Mckee（http://www.oasiscorporation.com/contactus.html），不过他没有问太多，好象主要是探询一下我的visa status，知道我需要sponsorship之后，说这是个小公司，可能不赞助H1-B，不过无论如何，他会去check一下。

我提了持新加坡护照，以及可以做volunteer的事情，不过估计希望不大。

即使这样，一天能有两个电话，以前是没有过的，看来就业市场真地回暖了？

今天有个Phone Screen

没想到大名鼎鼎的SlickEdit，业界和UltraEdit齐名的编辑器公司，也在Morrisville的范围内。

Scott Westfall，这个公司的技术主管（Vice President）跟我打的电话，谈了有一个多钟头。C的问题基本还行，没有答出来的是关于queue这个数据结构的常用操作比如insert、remove这些。C++的问题，拜Andrew Koenig的《Accelerated C++》所赐，基本也答出来了，主要的问题是static member in a class的用处、virtual function、pure virtual function、dynamic binding、polymorphism、virtual destructor的价值、还有如果class里面含有指针，那么在这个class被pass去一个function的时候，两个class instances里面的指针会指向同一块memory area，这种情况需要在copy constructor和assignment operator中重新分配内存，再把内存值copy过来。

对了，还有一个问题没有答上来。他让我说出三个sorting algorithm，我想来想去，只想到两个，一个是binary sort，另一个是quicksort。第三个怎么也没有想出来。其实第一个就不对了，只有binary search，没有binary sort。详细的参考，在Wiki上有：http://en.wikipedia.org/wiki/Sorting_algorithm

Scott说这整个礼拜都会忙着phone screen，下个礼拜早些时候，可能礼拜二会给我答复。

虽然也答错了几个题，但到目前为止，这个phone interview是感觉最好的一次。尤其是当我答出缺少virtual destructor会导致memory leak的时候，Scott很满意，说他问的人少过5%能说出virtual destructor的用处及价值。

希望能有好运。

马克思和恩格斯

整个一月份，我基本都是在录入棋谱，完成了《棋经众妙》（林元美编著）与《围棋死活辞典》（上册，赵治勋编著）的SGF格式棋谱。

感觉非常充实，比整天海投简历却没有回音那种落寞要强多了。虽然录入棋谱的时候没有工作，但感觉却像是当年写作《资本论》的马克思，被恩格斯养着完成一项伟大的工作。

笑谈，呵呵。

昨天又一个电话面试失败了

到现在为止，第二个电话面试，也失败了。

原因估计是他们需要low level的embedded developer，似乎还要和kernel有些关联。当然，我以前在施乐的工作和kernel是没什么关系的。雇主也就兴趣缺缺了。过程中，雇主还提到他们做的是微型仪器，硬件限制很大，比如ram，和flash memory方面的限制似乎cap在640KB。他还问到我国内的专业对应于美国的什么专业，我跟他说对应于美国的Mechanical Engineering，他还问我有没有CS方面的学位？我说没有，全都是learn on the job and learn by myself and by google，似乎他不是很满意。

也无所谓了。

今天路考通过，拿到驾照。

考完后，我还忐忑不安地坐在桌前，看她是不是准备再抽出一张Evaluation Report，然后数落我的缺点，没想到她敲了一会儿计算机之后，就对我说“Eight Dollars”，也就说我过了，她这是问我要办驾照的钱。

欣喜若狂。

坚韧和努力才是通向成功的唯一道路。

Virtual functions in C++

昨天读到《Accelerated C++》的第13章Using inheritance and dynamic binding，才对virtual function有了正确的认识。

原文如下：
－－－
13.2 Polymorphism and virtual functions


We have not yet completely reimplemented the original Student_info abstraction. That abstraction relied on a nonmember function to support part of its interface: It used the compare function to compare two student records. This function is used by sort to arrange records in alphabetical order.

Our new comparison function is identical to the one we wrote in §9.3.1/162 except for the change in type name:

bool compare(const Core& c1, const Core& c2)
{
    return c1.name() < c2.name();
}

We compare two student records by comparing their names. We delegate the real work to the string library < operator. What is interesting about this code is that we can use it to compare both Core records and Grad records, or even to compare a Core record with a Grad record:

Grad g(cin); // read a Grad record
Grad g2(cin); // read a Grad record
Core c(cin); // read a Core record
Core c2(cin); // read a Core record

compare(g, g2); // compare two Grad records
compare(c, c2); // compare two Core records
compare(g, c); // compare Grad record with a Core record

In each of these calls to compare, the name member of class Core will be run to determine the value to return from compare. Obviously, this is the right member to call for class Core, but what about for Grad? When we defined class Grad, we said that it is inherited from Core, and we did not redefine the name function. Thus, when we invoke g.name() for a Grad object g, we are invoking the name member that it inherited from Core. That function operates the same way on a Grad as it does on a Core: It fetches the underlying n field from the Core part of the object.

The reason that we can pass a Grad object to a function expecting a Core& is that we said that Grad is inherited from Core, so every Grad object has a Core part:

Because every Grad object has a Core part, we can bind compare's reference parameters to the Core portions of Grad objects, exactly as we can bind them to plain Core objects. Similarly, we could have defined compare to operate on pointers to Core or on objects of type Core (as opposed to a reference to Core). In either case, we could still call the function on behalf of a Grad object. If the function took pointers, we could pass a pointer to Grad. The compiler would convert the Grad* to a Core*, and would bind the pointer to the Core part of the Grad object. If the function took a Core object, then what would be passed is just the Core portion of the object. There can be striking differences in behavior, depending on whether we pass an object itself, or a reference or pointer to the object—as we shall now see.

13.2.1 Obtaining a value without knowing the object's type

Our compare function does the right thing when we call it with a Grad object as an argument because the name function is shared by both Grad and Core objects. What if we wanted to compare students, not on the basis of their names, but on the basis of their final grades? For example, instead of producing a listing of final grades sorted by name, we might need to produce a listing sorted by final grade.

As a first cut at solving this problem, we'd write a function that is similar to compare:

bool compare_grades(const Core& c1, const Core& c2)
{
    return c1.grade() < c2.grade();
}

The only difference is that here we're invoking the grade function rather than the name function. This difference turns out to be significant!

The difference is that Grad redefines the meaning of the grade function, and we have done nothing to distinguish between these two versions of grade. When we execute the compare_grades function, it will execute the Core::grade member, just as compare executes Core::name. In this case, if we are operating on a Grad object, then the version from Core gives the wrong answer, because the grade functions in Core and Grad behave differently from each other. For Grad objects, we must run Grad::grade in order to account for the thesis.

What we need is a way for compare_grades to invoke the right grade function, depending on the actual type of object that we pass: If c1 or c2 refers to a Grad object, then we want the Grad version of grade; if the object is of type Core, then we want the one from Core. We want to make that decision at run time. That is, we want the system to run the right function based on the actual type of the objects passed to the function, which is known only at run time.

To support this kind of run-time selection, C++ provides virtual functions:

class Core {
public:
    virtual double grade() const; // virtual added
    // ...
};

We now say that grade is a virtual function. When we call compare_grades, the implementation will determine the version of grade to execute by looking at the actual types of the objects to which the references c1 and c2 are bound. That is, it will determine which function to run by inspecting each object that we passed as an argument to compare_grades. If the argument is a Grad object, it will run the Grad::grade function; if the argument is a Core object, it will run the Core::grade function.

The virtual keyword may be used only inside the class definition. If the functions are defined separately from their declarations, we do not repeat virtual in the definitions. Thus, the definition of Core::grade() need not change. Similarly, the fact that a function is virtual is inherited, so we need not repeat the virtual designation on the declaration of grade within the Grad class. We do have to recompile our code with the new Core class definition. Once we have done so, then because the base-class version is virtual, we get the behavior that we need.

13.2.2 Dynamic binding

This run-time selection of the virtual function to execute is relevant only when the function is called through a reference or a pointer. If we call a virtual function on behalf of an object (as opposed to through a reference or pointer), then we know the exact type of the object at compile time. The type of an object is fixed: It is what it is, and does not vary at run time. In contrast, a reference or pointer to a base-class object may refer or point to a base-class object, or to an object of a type derived from the base class, meaning that the type of the reference or pointer and the type of the object to which a reference or pointer is bound may differ at run time. It is in this case that the virtual mechanism makes a difference.

For example, assume we rewrote compare_grades as follows:

// incorrect implementation!
bool compare_grades(Core c1, Core c2)
{
    return c1.grade() < c2.grade();
}

In this version, we say that our parameters are objects, not references to objects. In this case, we always know the type of objects represented by c1 and c2: They are Core objects. We can still call this function on behalf of a Grad object, but the fact that the argument had type Grad is immaterial. In this case, what happens is that what we pass is the base part of the object. The Grad object will be cut down to its Core part, and a copy of that portion of the Grad object will be passed to the compare_grades function. Because we said that the parameters are Core objects, the calls to grade are statically bound—they are bound at compile time—to Core::grade.

This distinction between dynamic binding and static binding is essential to understanding how C++ supports OOP. The phrase dynamic binding captures the notion that functions may be bound at run time, as opposed to static bindings that happen at compile time. If we call a virtual function on behalf of an object, the call is statically bound— that is, it is bound at compile time—because there is no possibility that the object will have a different type during execution than it does during compilation. In contrast, if we call a virtual function through a pointer or a reference, then the function is dynamically bound—that is, bound at run time. At run time, the version of the virtual function to use will depend on the type of the object to which the reference or pointer is bound:


Core c;
Grad g;
Core* p;
Core& r = g;

c.grade(); // statically bound to Core::grade()
g.grade(); // statically bound to Grad::grade()
p->grade(); // dynamically bound, depending on the type of the object to which p points
r.grade(); // dynamically bound, depending on the type of the object to which r refers

The first two calls can be statically bound: We know that c is a Core object, and that at run time, c will still be a Core object. Therefore, the compiler can statically resolve this call, even though grade is a virtual function. In the third and fourth calls, however, we can't know the type of the object to which p or r refers until run time: They might be Core or Grad objects. Hence, the decision as to which function to run in these cases must be delayed until run time. The implementation makes that decision based on the type of the object to which p points or to which r refers.

The fact that we can use a derived type where a pointer or reference to the base is expected is an example of a key concept in OOP called polymorphism. This word, from the Greek polymorphos, meaning "of many forms," was already in use in English in the mid-nineteenth century. In a programming context, it refers to the ability of one type to stand in for many types. C++ supports polymorphism through the dynamic-binding properties of virtual functions. When we call a virtual through a pointer or reference, we make a polymorphic call. The type of the reference (or pointer) is fixed, but the type of the object to which it refers (or points) can be the type of the reference (or pointer) or any type derived from it. Thus, we can potentially call one of many functions through a single type.

One final note about virtual functions: These functions must be defined, regardless of whether the program calls them. Nonvirtual functions may be declared but not defined, as long as the program does not call them. Many compilers generate mysterious error messages for classes that fail to define one or more virtual functions. If your program evokes a message from the compiler that you do not understand, and that message says that something is undefined, you should verify that you have defined all of your virtual functions. You are likely to find that the error goes away when you do so.

13.2.3 Recap

Before we continue, it is probably worth summarizing where we are, and making one slight additional change: We'll make the read function virtual as well. We'd like to be able to have the choice of which read function to run depend on the type of the object on which it is invoked. With that final change, let's look at our classes:

class Core {
public:
    Core(): midterm(O), final (0) { }
    Core(std::istream& is) { read(is); }
    std::string name() const;


    // as defined in §13.1.2/230
    virtual std::istream& read(std::istream&);
    virtual double grade() const;

protected:
    // accessible to derived classes
    std::istream& read_common(std::istream&);
    double midterm, final;
    std::vector homework;

private:
    // accessible only to Core
    std::string n;
};

class Grad: public Core {
public:
    Grad(): thesis(0) { }
    Grad(std::istream& is) { read(is); }

    // as defined in §13.1.2/230; Note: grade and read are virtual by inheritance
    double grade() const;
    std::istream& read(std::istream&);

private:
    double thesis;
};

bool compare(const Core&, const Core&);

We have defined two classes to encapsulate our two kinds of students. The first class, Core, represents students meeting the core requirements for the course. Our second class inherits from Core, adding the requirements for completing a thesis. We can create Core or Grad objects in two ways. The default constructor creates a properly initialized, empty object; the other constructor takes an istream& and reads initial values from the specified stream. The operations let us read into an object, resetting its values, and let us fetch the student's name or final grade. Note that in this version, we have made both the grade and read functions virtual. Finally, our interface includes a global, nonmember compare function that compares two objects by comparing students' names.
－－－
也就是说，virtual functions的作用是为了dynamic binding/polymorphism之用的。


对比之下，overload则是另外一种概念。
－－－
Functions: A function must be declared in every source file that uses it, and defined only once. The declarations and definitions have similar forms:


ret-typefunction-name (parm-decls) // function declaration
[inline] ret-typefunction-name (parm-decls) { // function definition
    // function body goes here
}

Here, ret-type is the type that the function returns, parm-decls is a comma-separated list of the types for the parameters of the function. Functions must be declared before they are called. Each argument's type must be compatible with the corresponding parameter. A different syntax is necessary to declare or define functions with sufficiently complicated return types; see §A.1.2/297 for the full story.

Function names may be overloaded: The same function-name may define multiple functions so long as the functions differ in the number or types of the parameters. The implementation can distinguish between a reference and a const reference to the same type.

We can optionally qualify a function definition with inline, which asks the compiler to expand calls to the function inline when appropriate—that is, to avoid function-call overhead by replacing each call to the function by a copy of the function body, modified as necessary. To do so, the compiler needs to be able to see the function definition, so inlines are usually defined in header files, rather than in source files.
－－－
简言之，overload是一种根据不同的形参调用不同函数的编译机制。

从广义的概念上讲，可能dynamic binding也可以算作某种overload。但严格来说，二者的应用范围还是不太一样的。前者和C++的核心－Class－紧密相关，而后者与Class是没有关系的。

由此可以想见，那次电话面试的第一题我也没有答对。

又查了一下书，dynamic binding对应的还是不能算overload，连广义的都不能算：
－－－
Dynamic binding refers to the ability to select at run time which function to run based on the actual type of the object on which the function is called. Dynamic binding is in effect for calls to virtual functions made through a pointer or a reference. The fact that a function is virtual is inherited, and need not be repeated in the derived classes.


Derived classes are not required to redefine their virtual functions. If a class does not redefine a virtual, then it inherits the nearest definition for that function. However, any virtual functions that the class does contain must be defined. It is often a source of mysterious error messages from compilers to declare but not define a virtual function.

Overriding: A derived-class member function overrides a function with the same name in the base class if the two functions have the same number and types of parameters and both (or neither) are const. In that case, the return types must also match, except that as in §13.4.2/246, if the base-class function returns a pointer (or reference) to a class, the derived-class function can return a pointer (or reference) to a derived class. If the argument lists don't match, the base- and derived-class functions are effectively unrelated.
－－－
由此可见，dynamic binding对应的是override，而不是overload。