经典题目

int fib(int n)
{
    int a = 0;
    int b = 1;
    while (n-- > 1) {
        int t = a;
        a = b;
        b += t;
    }
    return b;
}





Write a function that takes a positive integer n and returns n-squared. You may use addition and subtraction but not multiplication or exponentiation.
multiply two number :
int Multiply(int n1, int n2) {
    int res = 0;
    for (; n2 > 0; n2 >>= 1, n1 <<= 1) {
        if ((n2 & 1) == 1)
            res += n1;
    }
    return res;
}

Multiply two large integers represented in char array.
void multipy(char* a, char* b, char* res)
{
    int lenA = strlen(a);
    int lenB = strlen(b);

    int i, j;


    int* c = new int[lenA + lenB];
    memset(c, 0, sizeof(int) * (strlen(a) + strlen(b)));

    for (i = lenA - 1; i >= 0; i--)
        for (j = lenB - 1; j >= 0; j--)                   
            c[i + j + 1] += (b[j] - '0') * (a[i] - '0');

    for (i = lenA + lenB - 1; i >= 0; i--)
    {
        if (c[i] >= 10)
        {
            c[i - 1] += c[i] / 10;
            c[i] %= 10;
        }
    }
       
    i = 0;
    while (c[i] == 0)
        i++;

    j = 0;
    while (i < lenA + lenB)
    {
        res[j] = c[i] + '0';
        i++; j++;
    }

    res[j] = 0;
    delete[] c;
};

int main()
{
    char* a = "999";
    char* b = "9999";
    char* res = new char[strlen(a) + strlen(b)];

    multipy(a, b, res);
    return 0;
}

Google on-site最后一面的一道题目
写一个shuffle数组的算法
给一个数组A[]，里面的数是无序的，比如 A[]={1,2,3,7,3,2,5}
shuffle完之后，使之满足A[0]<=A[1]>=A[2]<=A[3]..
比如一种可能的结果是 A[]={1,7,3,5,2,2,1}

void shuffle(int A[], int n)
{
}
写出算法，并且证明其正确性。


用调整算法.

从第一个数开始往右扫描， 我们要做的是当扫描到第i个数的时候， 前i个数必须满足 a[0] <=a[1] >= a[2] .... a， 当i为n就结束了

当i为0, 2, 4...，前i - 1个元素已经满足了。 如果a[ i ] > a[i + 1] 交换a[ i ] 和 a[i + 1]， 这样使得前i个都满足, 因为a[i + 1] 必然小于a[ i - 1]。
当i为1,3,5... 同理， 如果a[ i ] < a[i + 1], 交换使得前i个满足， 因为a[i + 1] 必然大于a[i - 1]。其余的情况不用理会

我们每一步都能保证当前和之前的元素都满足这个规律， 所以必然有解。
void shuffle(int A[], int n)
{
    for(int i=0;i<n-1;i++)
    {
        if(i%2==0)
        {
            if(a[i]>a[i+1])
                swap(a[i],a[i+1]);
        }
        else{
            if(a[i]<a[i+1])
                swap(a[i],a[i+1]);
        }
    }
}