Google杯具电面面经

重在参与，不知道该怎么优化

// assume no such cases as: 9999
public static void recursiveAddOne(int[] num, int length) {               
                if (num[length - 1] == 9) {
                        num[length - 1] = 0;
                        addOne(num, length - 1);
                } else {
                        num[length - 1] = num[length - 1] + 1;
                }
}


public static void nonRecursiveAddOne(int[] num, int length) {
                while (--length >= 0 && num[length] == 9) {
                        num[length] = 0;
                }
                if (length >= 0) {
                        num[length]++;
                }
}

优化可以用lazy carry，只在最后输出结果时进位

You mean optimize the space ? BTW, thanks for your sharing!

%效率低，因为只进一位所以直接>9则-10

再接再厉~

试着写了一下，求优化
int add1(int *a, int n)
{
        if(a == NULL || n < 1)
                return 1<<31;
        int i = 0, count = 0;
        for(i=0; i<n; ++i)
        {
                if(a[i] > 9 || a[i] < 0)
                        return 1<<31;
                if(a[i] == 9)
                        ++count;
        }
        if(count == n)
                return 1<<31;
        if(a[n-1] < 9)
                a[n-1] += 1;
        else
        {
                for(i=n-1; i>=0; --i)
                {
                        if(a[i] < 9)
                        {
                                a[i] += 1;
                                break;
                        }
                        else
                                a[i] = 0;
                }
        }
        return 1;
}

void bigIntAddN(int *&nums, int &N, int add)
{
        int inc = 0;
        for(int i=0; i<N; i++)
        {
                int cur_num = nums[i];
                if( i==0 )
                        cur_num += add;
                cur_num = cur_num+inc;
                inc = 0;
                if( cur_num>=10 )
                {
                        cur_num -= 10;
                        inc = 1;
                }
                nums[i] = cur_num;
                if( !inc )
                        break;
        }
        if( inc>0 )
        {
                int *new_nums = (int *)calloc( N+1, sizeof(int) );
                memcpy( new_nums, nums, N*sizeof(int) );
                new_nums[N] = inc;
                N++;
                free(nums);
                nums = new_nums;
        }
}

补充内容 (2013-11-25 22:15):
拓展了下，该题应该是大整数的加法，所以拓展了两点，一个是可以进位，超过N后calloc，另一个是可以加N，而不是仅加1，优化点我想可能没那么复杂，就是没有进位直接break吧，这样速度应该足够快了

你好，工作找好了吗？我看到了你年初发的这个帖子，google的面经.
你现在怎么样了？留在美利坚了没？

没优化过的
思路是从最后一位往前找第一个不是9的，那位进位后面都变成0
void addOne(int []num, int N){
        int k;
        for (k = N-1; k >= 0 & num[k] != 9 ; k--);
        num[k]++；
        for (k=k+1; k<N ; k++) num[k] = 0;               
}
时间上优化可能就是想办法预测下一个数的进位会在哪里吧，跟union-find差不多的想法。空间上要多申请一个一样大的array。
void addOneInc(int []num, int N, int[]last_nine){
        //initially last_nine = {0, 1, 2, ..., N-1}
        int k;
        for (k=N-1; k>0 & last_nine[k]!=k; k=last_nine[k]);
        num[k]++;
        if (k>0 & num[k]==9) last_nine[k] = last_nine[k-1];
        for (k=k+1; k<N; k++) {
                num[k]=0;
                last_nine[k] = k;
        }
}
因为说全是9的不处理，我就简单处理成如果全是9第一位的值变成10了。