x***j
发帖数: 75 | 1 老印，三个题。电话晚打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 fileId, int machID){
//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){
}
大牛说说这题怎么写？ |
W*********y
发帖数: 481 | 2 第一题可以看做是longest increasing sequence 的特例，一旦找到increasing
sequence 长度为2的就return true
这样可以有1 pass的线性算法，constant space。
【在 x***j 的大作中提到】
: 老印，三个题。电话晚打1个半小时，中间掉线6次，还把我挂了。投诉HR，再安排一次
: 电面, 希望下次不要碰到这么傻逼的人。
: 1.
: 给一个数组
: 有没有三个下标 i < j < k, 满足A[i] < A[j] < A[k]。
: 我用2个数组，dp做的。好像不太满意，有没有比较好的解法？
: 2.
: 有一个函数
: long compute(int i) {
: return …;
|
e********2
发帖数: 495 | 3 第二题分成n/k段，每段k个，重复t次。然后优化
[[1-(1-p)^k}^t]^(n/k) < p
先对k做最大化，然后求t。
第三题Binary sum，Machine之间应该能通信吧！
【在 x***j 的大作中提到】
: 老印，三个题。电话晚打1个半小时，中间掉线6次，还把我挂了。投诉HR，再安排一次
: 电面, 希望下次不要碰到这么傻逼的人。
: 1.
: 给一个数组
: 有没有三个下标 i < j < k, 满足A[i] < A[j] < A[k]。
: 我用2个数组，dp做的。好像不太满意，有没有比较好的解法？
: 2.
: 有一个函数
: long compute(int i) {
: return …;
|
j**********3
发帖数: 3211 | |
r****7
发帖数: 2282 | 5 G果然是bar高啊。。。除了第一题别的都不会。。。
第一题应该是扫一遍，更新min 和 mid，遇到大于mid的就返回
【在 x***j 的大作中提到】
: 老印，三个题。电话晚打1个半小时，中间掉线6次，还把我挂了。投诉HR，再安排一次
: 电面, 希望下次不要碰到这么傻逼的人。
: 1.
: 给一个数组
: 有没有三个下标 i < j < k, 满足A[i] < A[j] < A[k]。
: 我用2个数组，dp做的。好像不太满意，有没有比较好的解法？
: 2.
: 有一个函数
: long compute(int i) {
: return …;
|
l*****a
发帖数: 14598 | 6 关于第二题
function call一次的出错概率是p
call n次的话就是np?
【在 x***j 的大作中提到】
: 老印，三个题。电话晚打1个半小时，中间掉线6次，还把我挂了。投诉HR，再安排一次
: 电面, 希望下次不要碰到这么傻逼的人。
: 1.
: 给一个数组
: 有没有三个下标 i < j < k, 满足A[i] < A[j] < A[k]。
: 我用2个数组，dp做的。好像不太满意，有没有比较好的解法？
: 2.
: 有一个函数
: long compute(int i) {
: return …;
|
x***j
发帖数: 75 | 7 没有，new grad
【在 j**********3 的大作中提到】
: lz简历上有多线程背景么？
|
a*****a
发帖数: 46 | 8 不出错的概率是(1-p)
n次里面都不出错的概率是(1-p)^n 因为p很小，约等于1-np,
然后出错的概率是1-(1-np) = np.
【在 l*****a 的大作中提到】
: 关于第二题
: function call一次的出错概率是p
: call n次的话就是np?
|
k*******a
发帖数: 433 | 9 是多少？
P的n 次方？？？
【在 l*****a 的大作中提到】
: 关于第二题
: function call一次的出错概率是p
: call n次的话就是np?
|
k*******a
发帖数: 433 | 10 第三题如果用锁的话，怎么做？
是什么atomic？
【在 x***j 的大作中提到】
: 老印，三个题。电话晚打1个半小时，中间掉线6次，还把我挂了。投诉HR，再安排一次
: 电面, 希望下次不要碰到这么傻逼的人。
: 1.
: 给一个数组
: 有没有三个下标 i < j < k, 满足A[i] < A[j] < A[k]。
: 我用2个数组，dp做的。好像不太满意，有没有比较好的解法？
: 2.
: 有一个函数
: long compute(int i) {
: return …;
|
|
|
r****7
发帖数: 2282 | 11 关键是没有一个对与错的标准，call多少次也无助于找到对的结果啊
【在 l*****a 的大作中提到】
: 关于第二题
: function call一次的出错概率是p
: call n次的话就是np?
|
m*********p
发帖数: 112 | 12 zan
【在 x***j 的大作中提到】
: 老印，三个题。电话晚打1个半小时，中间掉线6次，还把我挂了。投诉HR，再安排一次
: 电面, 希望下次不要碰到这么傻逼的人。
: 1.
: 给一个数组
: 有没有三个下标 i < j < k, 满足A[i] < A[j] < A[k]。
: 我用2个数组，dp做的。好像不太满意，有没有比较好的解法？
: 2.
: 有一个函数
: long compute(int i) {
: return …;
|
j**********3
发帖数: 3211 | 13 一般不会多线程，简历没写，人家不会问的
【在 x***j 的大作中提到】
: 没有，new grad
|
x***j
发帖数: 75 | 14 那是一般。
【在 j**********3 的大作中提到】
: 一般不会多线程，简历没写，人家不会问的
|
m*********p
发帖数: 112 | 15 约等于np吧 1-(1-p)^n，因为p<<1
【在 l*****a 的大作中提到】
: 关于第二题
: function call一次的出错概率是p
: call n次的话就是np?
|
m*********p
发帖数: 112 | 16 LIS的DP难道不需要一个O(n)的status vector吗？
【在 W*********y 的大作中提到】
: 第一题可以看做是longest increasing sequence 的特例，一旦找到increasing
: sequence 长度为2的就return true
: 这样可以有1 pass的线性算法，constant space。
|
m*********p
发帖数: 112 | 17 第二个能不能
call每个函数3次，然后take majority vote呢，这样单次出错的概率大概是3p^2 << p
【在 x***j 的大作中提到】
: 老印，三个题。电话晚打1个半小时，中间掉线6次，还把我挂了。投诉HR，再安排一次
: 电面, 希望下次不要碰到这么傻逼的人。
: 1.
: 给一个数组
: 有没有三个下标 i < j < k, 满足A[i] < A[j] < A[k]。
: 我用2个数组，dp做的。好像不太满意，有没有比较好的解法？
: 2.
: 有一个函数
: long compute(int i) {
: return …;
|
T*****u
发帖数: 7103 | 18 就是这个思路吧。关键看需要多少次才能满足出错概率，3次可能太多也可能太少。
p
【在 m*********p 的大作中提到】
: 第二个能不能
: call每个函数3次，然后take majority vote呢，这样单次出错的概率大概是3p^2 << p
|
g**4
发帖数: 863 | 19 第一题我也只会用2个数组来做，类似G家的买卖股票那题
有没有人能提供个更好的解法？ |
w****a
发帖数: 710 | 20 这个解法能不能用？
vector three_nums(const vector& nums) {
if(nums.empty()) return {};
int first = 0, mid = 0;
int second = -1;
for(int i = 1; i < nums.size(); ++i) {
if(second == -1) {
if(nums[first] < nums[i]) {
second = i;
} else if (nums[first] > nums[i]) {
first = i;
}
} else if (nums[i] > nums[second]) {
return {nums[first], nums[second], nums[i]};
} else if (nums[i] > nums[first]) {
first = mid;
second = i;
}
}
return {};
}
【在 g**4 的大作中提到】
: 第一题我也只会用2个数组来做，类似G家的买卖股票那题
: 有没有人能提供个更好的解法？
|
|
|
c*****w
发帖数: 50 | 21 第一题O1 space 解
设ai是原数组
xi=min{aj|j
yi=min{aj|exist ak
For every i
If ai>y[i-1], done
Elif ai
Else
yi = ai
One pass while updating xi yi
[发表自未名空间手机版 - m.mitbbs.com] |
W*********y
发帖数: 481 | 22 不是的，其实是需要一个size 为 k+1的vector，其中k为最大increasing subarray 的
长度。
对本题只需找到k为3的解是否存在，因此空间constant，时间O(n)
bool kLIS(vector &data, int k){
vector stack(k+1);
int top = 0;
stack[0] = -1;
for(int i=0;i
if(data[i]>stack[top]){
stack[++top] = data[i];
}
else{
auto low = lower_bound(stack.begin(), top+stack.begin(), data[i]);
*low = data[i];
}
if(top==k)
return true;
}
return false;
}
【在 m*********p 的大作中提到】
: LIS的DP难道不需要一个O(n)的status vector吗？
|
j*******p
发帖数: 73 | 23 我看第一题也是想到用stack一次扫描即可，保存到当前位置最大值最小的上升序列，
跟楼上一样。但stack长度只需要k-1就够了吧，一旦溢出就可以返回结果了。
第二题只需要循环内部做一个majority vote即可
第三题我会用map reduce的思路去解
【在 W*********y 的大作中提到】
: 不是的，其实是需要一个size 为 k+1的vector，其中k为最大increasing subarray 的
: 长度。
: 对本题只需找到k为3的解是否存在，因此空间constant，时间O(n)
: bool kLIS(vector &data, int k){
: vector stack(k+1);
: int top = 0;
: stack[0] = -1;
: for(int i=0;i: if(data[i]>stack[top]){
: stack[++top] = data[i];
|
l****h
发帖数: 274 | 24 若凭南辕吏
为问乘槎人
包含通远迩
子夏正离群
故人别二年
万里忽争先
事与云水白
皆欲肆轥轹
可夭札迷冥
抛官归旧谿 |
l********s
发帖数: 358 | 25 1. O(n)
从左到右update minValue, 对于A[i]比minValue大，说明A[i]有小的在左边, 记录在
一个boolean array里面
从右到左update maxValue, 对于A[i]比minValue小，说明A[i]有大的在右边
2.
s += compute(i)
在这里call computer(i)两次
1）如果两次值一样，出错的几率是p*p
2）如果两次值不一样，就任意取一个p*p + p*0.5 （可能两个值都错，也有可能一个
对一个错）
3.
同一个machine多线程的话，blockingQueue里面放fileId，sum设为static的
atomicInteger
多个machine的话，就是IPC，一个machine做coordinator，往message queue里面放
fileID。其他machine从message queue里面拿fileID，统计完把结果放到另外一个
message queue里面，coordinator取出结果然后sumAll.
其实就是mapper + reducer
【在 x***j 的大作中提到】
: 老印，三个题。电话晚打1个半小时，中间掉线6次，还把我挂了。投诉HR，再安排一次
: 电面, 希望下次不要碰到这么傻逼的人。
: 1.
: 给一个数组
: 有没有三个下标 i < j < k, 满足A[i] < A[j] < A[k]。
: 我用2个数组，dp做的。好像不太满意，有没有比较好的解法？
: 2.
: 有一个函数
: long compute(int i) {
: return …;
|
e******n
发帖数: 3435 | 26 多长时间那，要做3题？
【在 x***j 的大作中提到】
: 老印，三个题。电话晚打1个半小时，中间掉线6次，还把我挂了。投诉HR，再安排一次
: 电面, 希望下次不要碰到这么傻逼的人。
: 1.
: 给一个数组
: 有没有三个下标 i < j < k, 满足A[i] < A[j] < A[k]。
: 我用2个数组，dp做的。好像不太满意，有没有比较好的解法？
: 2.
: 有一个函数
: long compute(int i) {
: return …;
|
P****i
发帖数: 1362 | 27 只返回T/F constant space就可以，不然得linear space
不过感觉还有更快的O(log n)的方法
【在 c*****w 的大作中提到】
: 第一题O1 space 解
: 设ai是原数组
: xi=min{aj|j: yi=min{aj|exist ak: For every i
: If ai>y[i-1], done
: Elif ai: Else
: yi = ai
: One pass while updating xi yi
|
e*******0
发帖数: 3 | 28 反例 2,3,1,4
【在 c*****w 的大作中提到】
: 第一题O1 space 解
: 设ai是原数组
: xi=min{aj|j: yi=min{aj|exist ak: For every i
: If ai>y[i-1], done
: Elif ai: Else
: yi = ai
: One pass while updating xi yi
|
c*****w
发帖数: 50 | 29 2 3 1 4
x 2 2 1 1
y na 3 3 3(4>3done)
[发表自未名空间手机版 - m.mitbbs.com]
【在 e*******0 的大作中提到】
: 反例 2,3,1,4
|
c*****w
发帖数: 50 | 30 变量名没用好，这里的x y不对应原题的x y
[发表自未名空间手机版 - m.mitbbs.com]
【在 c*****w 的大作中提到】
: 2 3 1 4
: x 2 2 1 1
: y na 3 3 3(4>3done)
:
: [发表自未名空间手机版 - m.mitbbs.com]
|
|
|
Q**F
发帖数: 995 | 31 第二题，可不可以用这个思路。
假设每个compute（i）算两次，比较两次的结果，如果相等就算完成，要不然就重新计
算，这步出错的概率为p^2,
那么这个出错的概率问n*(p^2).
如果这个要小于 p
n<1/p 就可以了
如果计算3次，比较3次的结果，这本出错的概率为p^3.
只要n<1/(p^2)就可以了。 |
w****k
发帖数: 755 | 32 bool incr(vector& v)
{
int min = INT_MAX;
int mid = INT_MAX;
for(int i : v)
{
if(i <= min)
min = i;
else if(i <= mid)
mid = i;
else
return true;
}
return false;
} |
k***7
发帖数: 6 | 33 5, 6, 1, 2, 3
【在 w****a 的大作中提到】
: 这个解法能不能用？
: vector three_nums(const vector& nums) {
: if(nums.empty()) return {};
:
: int first = 0, mid = 0;
: int second = -1;
:
: for(int i = 1; i < nums.size(); ++i) {
: if(second == -1) {
: if(nums[first] < nums[i]) {
|
i*******t
发帖数: 79 | 34 第一题你考虑太复杂了，先考虑如果只是i,j怎么做，只是找个比当前最小的值大的就
结束了。扩展到k，就是找个比当前A[j]大的就结束了，当然A[j]可能会变小的。
第二题，如果compute(i)是p，那么连续两次都出错的概率就是p^2 （连续调用直到连
续两次得到的结果相同），根据n的大小，连续调用compute(i)多次，使得最终的概率
小于p
第三题，没觉得是多线程，都有machineid了，怎么是多线程？分布式吧。map reduce
【在 x***j 的大作中提到】
: 那是一般。
|
