电面

发信人: xxzbj (xxue), 信区: JobHunting
标  题: G电面面经
发信站: BBS 未名空间站 (Sun Dec 14 11:15:55 2014, 美东)

老印，三个题。电话晚打1个半小时，中间掉线6次，还把我挂了。投诉HR，再安排一次
电面,  希望下次不要碰到这么傻逼的人。

1.
给一个数组
有没有三个下标  i < j < k, 满足A[i] < A[j] < A[k]。

我用2个数组，dp做的。好像不太满意，有没有比较好的解法？

2.

有一个函数
long compute(int i) {
 return …;
}
返回值有可能出错概率是 p=1/10000。

还有一个函数
long total(int n) {
 long s = 0;
 for (int i =0; i < n; i++) {
   s += compute(i);
 }
 return s;
}
这样出错概率就是 np;

问： 如何改第二个函数，让他的出错概率小于p?
我的思路是，for 循环里,再加个循环，写了代码。 最后老印说work, 大多人都这么做
，好像他不满意。这个题怎么做？

3. 考多线程。
给个函数
long sum(int file_ID, int machine_ID){
    //return the sum of the numbers in this file using this machine.
}

实现另一个函数，
input: N(N files from 1 to N)， enough machine for using
output; the total sum of these files.

long getAllSum(int N){

}




review:
1.第一题应该是扫一遍，更新min 和 mid，遇到大于mid的就返回
pseudo-code:
设ai是原数组
xi=min{aj|j<i}
yi=min{aj|exist ak<aj k<j<i}

For every i
If ai>y[i-1], done
Elif ai<x[i-1], xi = ai
Else
yi = ai
One pass while updating xi yi

runnable code: xi is the current min value, yi is the current middle value, left is the final min value.
    int xi=aVec[0];
    int yi=INT_MAX;
    int left=xi;
    for (int i=1;i<aVec.size();i++)
    {
        if(aVec[i]>yi){
            cout<<left<<"  "<<yi<<"  "<<aVec[i]<<endl;
            break;
        }
        else if(aVec[i]<=xi)
        {xi=aVec[i];}
        else
        {yi=aVec[i];left=xi;}
    }

注意上面aVec[i]<=xi必须要有“=”，否则会出错。因为没有等号的话，可能会进入最后一个else，这样yi和left就相等了。可以运行这个例子：
{82,14,72,14,19,14,78,36,6,23};

another idea for 1
O(n) space, O(n) time
从左到右update minValue, 对于A[i]比minValue大，说明A[i]有小的在左边, 记录在
一个boolean array里面
从右到左update maxValue, 对于A[i]比minValue小，说明A[i]有大的在右边