v***a
发帖数: 365 | 1 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
FB的新题：
X）Initial Onsite，
题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
于是把公式写出来，顺便程序也写出来，
然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
deploy 到所有机器里，大概百万台，
怎么设计一个系统。
这个新题，正好想到了Gossip，
于是扯了一通 Gossip 算法，给出复杂度O(LogN) 就可以发送完，
随后发现由于带宽限制，网络拓扑结构已知，所以Gossip 不好，
抄袭 mapReduce 的框架，设计了一个有 Master 节点的 Gossip 算法
X) 顺利拿到Onsite, 一个印度 Manager 听我面的很好，对algorithm 和 backend很熟
悉，
于是 onsite 时特地来面我，题目都是behavior，你为啥有激情，为啥想来FB等等，
当然在问之前花了半小时介绍他的工作， 说他们走backend的多牛，多重要，
同时强烈推荐我去他的组，说有多激情，可以改变世界，我边听边在心里说:
我艹烙印
X）Onsite，给你一个函数 bool Prob() ，有50%的概率返回 True，50%的概率返回
False
请你用写一个新的函数：bool Prob2(double p)
要求 p 的概率返回 True， 1 - p 的概率返回 False
当然，肯定使用 Prob 了
这题我用的2分法，花了不少时间，，
然后问了fibonacci的 O(1) Space 或者 O(N) time 的解法，
刚好剩下5分钟问他问题，
结果大跌眼镜，内部推荐的朋友告诉我，这个人给了我个 Negative！！
HR 也没告诉我为啥，莫须有的罪名。
面试是看RP的，RP不好，总能碰到看你不顺眼的
X）Onsite 老题新酒，直方图，天上下雨，求能存多少水
E.G:
3,1,5 => 2
3,1,0,5 => 5
很假单的O(N)扫描就行
扩展是改成Online的算法，就是说：
有些地方高度随时会变，
E.G.
3,1,5 => 3,0,5 => 3
3,1,0,5 => 3,3,0,5 => 3
设计一个算法，最快的返回改变高度之后的结果
----
我的方法：
做题
------------------------------------------------------
非常感谢提供面经的人，没有这些面经，绝对没把握当场作出来！ |
b*****n
发帖数: 453 | 2 gxgx!
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
b***u
发帖数: 12010 | 3 prob()怎么搞？
我能想到是你能构造1/2^k。以及或事件造p1+p2-p1p2。怎么逼近p呢？
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
m******s
发帖数: 165 | 4 比如p=0.3
call prob->
>0.5：返回失败
<0.5：call prob->
<0.5：返回成功
>0.5（0.25-0.5）：call prob。。。
期望大概是扔3次
【在 b***u 的大作中提到】
: prob()怎么搞？
: 我能想到是你能构造1/2^k。以及或事件造p1+p2-p1p2。怎么逼近p呢？
|
b***u
发帖数: 12010 | 5 没看懂。怎么generalize?
【在 m******s 的大作中提到】
: 比如p=0.3
: call prob->
: >0.5：返回失败
: <0.5：call prob->
: <0.5：返回成功
: >0.5（0.25-0.5）：call prob。。。
: 期望大概是扔3次
|
h*********n
发帖数: 11319 | 6 so strong! mark
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
r*******n
发帖数: 266 | 7 cong!
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
z******w
发帖数: 36 | |
B******5
发帖数: 4676 | |
i******r
发帖数: 793 | 10 我现在对烙印真的有心理阴影
我面F的时候也是个烙印
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
|
|
n***a
发帖数: 34 | |
w********n
发帖数: 58 | |
w********n
发帖数: 58 | |
k***t
发帖数: 276 | 14 为啥选G不选F？按说你这样的编程竞赛大拿该选动态、
高速发展的平台，而不是一个相对established环境。
G跳F的比F跳G的要多吧？如果试因为pkg差别，应该可以谈。
尽管F以后如何还不一定，但向上空间同样不可限量。
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
P*****f
发帖数: 2272 | 15 谁给钱多去谁。
G跳Twitter/Zynga的更多，Facebook也算比较大公司了，IPO搞头不大。要去动态的，
观察下从这些公司跳出来的去哪就可以了
【在 k***t 的大作中提到】
: 为啥选G不选F？按说你这样的编程竞赛大拿该选动态、
: 高速发展的平台，而不是一个相对established环境。
: G跳F的比F跳G的要多吧？如果试因为pkg差别，应该可以谈。
: 尽管F以后如何还不一定，但向上空间同样不可限量。
|
P*****f
发帖数: 2272 | 16 welcome to G
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
k***t
发帖数: 276 | 17 同意向钱看和向前看:) 说说从这些公司跳出来的都去哪？
【在 P*****f 的大作中提到】
: 谁给钱多去谁。
: G跳Twitter/Zynga的更多，Facebook也算比较大公司了，IPO搞头不大。要去动态的，
: 观察下从这些公司跳出来的去哪就可以了
|
m*****a
发帖数: 636 | 18 Congrats!
啥叫带宽限制，toplogic已知 -> master 节点 Gossip
积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
FB的新题：
X）Initial Onsite，
题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
于是把公式写出来，顺便程序也写出来，
然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
deploy 到所有机器里，大概百万台，
怎么设计一个系统。
这个新题，正好想到了Gossip，
于是扯了一通 Gossip 算法，给出复杂度O(LogN) 就可以发送完，
随后发现由于带宽限制，网络拓扑结构已知，所以Gossip 不好，
抄袭 mapReduce 的框架，设计了一个有 Master 节点的 Gossip 算法
X) 顺利拿到Onsite, 一个印度 Manager 听我面的很好，对algorithm 和 backend很熟
悉，
于是 onsite 时特地来面我，题目都是behavior，你为啥有激情，为啥想来FB等等，
当然在问之前花了半小时介绍他的工作， 说他们走backend的多牛，多重要，
同时强烈推荐我去他的组，说有多激情，可以改变世界，我边听边在心里说:
我艹烙印
X）Onsite，给你一个函数 bool Prob() ，有50%的概率返回 True，50%的概率返回
False
请你用写一个新的函数：bool Prob2(double p)
要求 p 的概率返回 True， 1 - p 的概率返回 False
当然，肯定使用 Prob 了
这题我用的2分法，花了不少时间，，
然后问了fibonacci的 O(1) Space 或者 O(N) time 的解法，
刚好剩下5分钟问他问题，
结果大跌眼镜，内部推荐的朋友告诉我，这个人给了我个 Negative！！
HR 也没告诉我为啥，莫须有的罪名。
面试是看RP的，RP不好，总能碰到看你不顺眼的
X）Onsite 老题新酒，直方图，天上下雨，求能存多少水
E.G:
3,1,5 => 2
3,1,0,5 => 5
很假单的O(N)扫描就行
扩展是改成Online的算法，就是说：
有些地方高度随时会变，
E.G.
3,1,5 => 3,0,5 => 3
3,1,0,5 => 3,3,0,5 => 3
设计一个算法，最快的返回改变高度之后的结果
----
我的方法：
做题
------------------------------------------------------
非常感谢提供面经的人，没有这些面经，绝对没把握当场作出来！
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
r*****k
发帖数: 1281 | 19 假设double p 二进制表示是：100011
call prob 6次
如果结果小于100011 返回p
大于返回 1-p
等于再call prob 6次
zz from Google
【在 b***u 的大作中提到】
: prob()怎么搞？
: 我能想到是你能构造1/2^k。以及或事件造p1+p2-p1p2。怎么逼近p呢？
|
z*****n
发帖数: 447 | |
|
|
k*********5
发帖数: 1417 | |
p*****2
发帖数: 21240 | 22 恭喜大牛。刚看了一下题目。还没看回复。这道概率题我是这样考虑的
static boolean Prob2(double p, boolean expected)
{
if(p<0.5)
{
expected=!expected;
p=1-p;
}
if(Prob()==expected)
return expected;
else
{
return Prob2((p-0.5)/0.5, expected);
}
} |
p*****2
发帖数: 21240 | |
P**********c
发帖数: 3417 | 24 F现在很多时候给的股票跟G的差不多，大家当然都选G. G的股票基本没有风险。F按
照100B的valuation给，风险很大，涨的potential不大，不怎么划算。
以前从G跳到F的人家拿多少股，你得看去年还有多少人跳过去。不如在G待一段时间再去
一个感觉有前途还很小的startup. F的revenue还只能看作G的一个部门吧，
不觉得从career的角度就有多大差别。比如说G的search组也就跟F差不多大吧, career
角度我觉得是差不多的。不拿出点实际的motivation来，就谈career就是bullshit.
【在 k***t 的大作中提到】
: 为啥选G不选F？按说你这样的编程竞赛大拿该选动态、
: 高速发展的平台，而不是一个相对established环境。
: G跳F的比F跳G的要多吧？如果试因为pkg差别，应该可以谈。
: 尽管F以后如何还不一定，但向上空间同样不可限量。
|
p*****2
发帖数: 21240 | 25
再去
upside
G有一个不好就是拿到offer的时候不知道去哪个组。如果被分到一个不喜欢的组也没意
思吧？好像换组也得等18个月吧？那看来现在从待遇来说G已经Top了。要不怎么
Fortune 100 G今年排了第一。不过不知道收购moto之后会有不会有什么变化。moto人
可不少。
【在 P**********c 的大作中提到】
: F现在很多时候给的股票跟G的差不多，大家当然都选G. G的股票基本没有风险。F按
: 照100B的valuation给，风险很大，涨的potential不大，不怎么划算。
: 以前从G跳到F的人家拿多少股，你得看去年还有多少人跳过去。不如在G待一段时间再去
: 一个感觉有前途还很小的startup. F的revenue还只能看作G的一个部门吧，
: 不觉得从career的角度就有多大差别。比如说G的search组也就跟F差不多大吧, career
: 角度我觉得是差不多的。不拿出点实际的motivation来，就谈career就是bullshit.
|
r*****k
发帖数: 1281 | 26 moto应该和原来的g分开运营把。招人和发工资都分开。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****2 的大作中提到】
:
: 再去
: upside
: G有一个不好就是拿到offer的时候不知道去哪个组。如果被分到一个不喜欢的组也没意
: 思吧？好像换组也得等18个月吧？那看来现在从待遇来说G已经Top了。要不怎么
: Fortune 100 G今年排了第一。不过不知道收购moto之后会有不会有什么变化。moto人
: 可不少。
|
p*****2
发帖数: 21240 | 27
那简历上能写Google吗？
【在 r*****k 的大作中提到】
: moto应该和原来的g分开运营把。招人和发工资都分开。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
v***a
发帖数: 365 | 28 只是因为大学开始的时候，G就是dream company了
【在 k***t 的大作中提到】
: 为啥选G不选F？按说你这样的编程竞赛大拿该选动态、
: 高速发展的平台，而不是一个相对established环境。
: G跳F的比F跳G的要多吧？如果试因为pkg差别，应该可以谈。
: 尽管F以后如何还不一定，但向上空间同样不可限量。
|
r*****k
发帖数: 1281 | 29 google moto啊。
就像现在intel mcafee。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****2 的大作中提到】
:
: 那简历上能写Google吗？
|
p*****2
发帖数: 21240 | 30
大牛再贴几道F的题吧，应该还有其他吧？
【在 v***a 的大作中提到】
: 只是因为大学开始的时候，G就是dream company了
|
|
|
p*****2
发帖数: 21240 | 31
那也有点用。起码有Google这个keyword了。如果老员工已经离开公司的能不能也用
Google Moto呢？
【在 r*****k 的大作中提到】
: google moto啊。
: 就像现在intel mcafee。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
r*****k
发帖数: 1281 | 32 北京也要面了 ？
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****2 的大作中提到】
:
: 那也有点用。起码有Google这个keyword了。如果老员工已经离开公司的能不能也用
: Google Moto呢？
|
p*****2
发帖数: 21240 | 33
过了一面，现在想是不是拖两个月。因为复习的还不够，很多老题我还没做过。而且也
还没做到600道题。
【在 r*****k 的大作中提到】
: 北京也要面了 ？
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
r*****k
发帖数: 1281 | 34 我还没做到60题 好多都不会。。。
【在 p*****2 的大作中提到】
:
: 过了一面，现在想是不是拖两个月。因为复习的还不够，很多老题我还没做过。而且也
: 还没做到600道题。
|
y*****z
发帖数: 9 | 35 这个是概率题。。
先生成 4个bit的 二进制 true代表1，false代表0
这样我们能生成0-15的 等概率的 distribution
然后 [0,15] 当中 选[0,10] -->[0,2](true), [3,9](false)
public class Solution {
/**
* @param args
*/
public void doit(){
int iterate = 10000000;
boolean valve = true;
StringBuilder s = new StringBuilder();
while (valve) {
StringBuilder str = new StringBuilder();
for (int i = 0; i < 4; i++) {
if (Math.random() < 0.5) str.append('1');
else str.append('0');
}
double p = 0.3;
int target = (int) (p * 10);
int value = Integer.parseInt(str.toString(), 2);
if (value <= 9) {
// [0-15]-->[0,9]-->[0,2](1),[3,9](0);
if (value <= 2) {
s.append('1');
} else {
s.append('0');
}
} else
valve = true;
iterate--;
if (iterate < 0)
break;
}
int countone = 0, countzero = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '1')
countone++;
if (s.charAt(i) == '0')
countzero++;
}
int sum = countone + countzero;
System.out.println(((double)countone/(double)sum) + " " + ((double)
countzero/(double)sum));
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution s = new Solution();
s.doit();
}
} |
p*****2
发帖数: 21240 | 36
你也面F呀？
【在 r*****k 的大作中提到】
: 我还没做到60题 好多都不会。。。
|
r*****k
发帖数: 1281 | 37 要面啊 感觉没准备好
想cancel了
【在 p*****2 的大作中提到】
:
: 你也面F呀？
|
p*****2
发帖数: 21240 | 38
怎么cancel呀？跟recruiter说就行了？还是说delay两个月呢？
【在 r*****k 的大作中提到】
: 要面啊 感觉没准备好
: 想cancel了
|
r*****k
发帖数: 1281 | 39 delay啊 不知道行不行
【在 p*****2 的大作中提到】
:
: 怎么cancel呀？跟recruiter说就行了？还是说delay两个月呢？
|
i**********e
发帖数: 1145 | 40 恭喜！
之前你说你没拿到面试我说怎么可能呢？
好好加油，前途无量！ |
|
|
k***t
发帖数: 276 | 41 怎么说都行吧，感觉上recruiter就是个经纪人，双方的。
他也想做你这单生意，晚一两个月对他的收益没有影响，
除非他绝望到一个月只内再不成交就要走人了才会Push Client：）
【在 p*****2 的大作中提到】
:
: 怎么cancel呀？跟recruiter说就行了？还是说delay两个月呢？
|
l*****a
发帖数: 14598 | 42 问题是对某些特定team的特定职位。不见得是一直有opening的
除非你申请那些common positions
【在 k***t 的大作中提到】
: 怎么说都行吧，感觉上recruiter就是个经纪人，双方的。
: 他也想做你这单生意，晚一两个月对他的收益没有影响，
: 除非他绝望到一个月只内再不成交就要走人了才会Push Client：）
|
k***t
发帖数: 276 | 43 对特定职位的，那当然。
peking2是在面FG的common position吧。
可能要跟recruiter确认一下。从他的角度也有
motivation to encourage the client to prepare the interview。
【在 l*****a 的大作中提到】
: 问题是对某些特定team的特定职位。不见得是一直有opening的
: 除非你申请那些common positions
|
p*****2
发帖数: 21240 | 44
我还真是特定的。看来比较麻烦了。fail了两年只能还不能在申请了。
【在 k***t 的大作中提到】
: 对特定职位的，那当然。
: peking2是在面FG的common position吧。
: 可能要跟recruiter确认一下。从他的角度也有
: motivation to encourage the client to prepare the interview。
|
A**u
发帖数: 2458 | |
l*****a
发帖数: 14598 | 46 why 2 years?
new rules for FB?
【在 p*****2 的大作中提到】
:
: 我还真是特定的。看来比较麻烦了。fail了两年只能还不能在申请了。
|
p*****2
发帖数: 21240 | 47
听vissa说的。
【在 l*****a 的大作中提到】
: why 2 years?
: new rules for FB?
|
k***t
发帖数: 276 | 48 那也需要权衡利弊。就算你是特定职位，看F这架势，
因该还有一段时间要大量全面找人。你那特定职位及其
相关职位应该也不止找一个人。
我觉得尽管时间长一点也不一定就好，但总要你自己
comfortable后再去才好，不留遗憾。
不过，至少赶在IPO股价可能的变化之前好一些。
Good Luck。
【在 p*****2 的大作中提到】
:
: 听vissa说的。
|
p*****2
发帖数: 21240 | 49
recruiter说我那职位就招，5,6个人，已经收到 几千份简历了。不过也无所谓了吧。
如果万一拿到offer又要大伤人品了。
【在 k***t 的大作中提到】
: 那也需要权衡利弊。就算你是特定职位，看F这架势，
: 因该还有一段时间要大量全面找人。你那特定职位及其
: 相关职位应该也不止找一个人。
: 我觉得尽管时间长一点也不一定就好，但总要你自己
: comfortable后再去才好，不留遗憾。
: 不过，至少赶在IPO股价可能的变化之前好一些。
: Good Luck。
|
r*****k
发帖数: 1281 | 50 为啥拿到offer又要大伤人品？
【在 p*****2 的大作中提到】
:
: recruiter说我那职位就招，5,6个人，已经收到 几千份简历了。不过也无所谓了吧。
: 如果万一拿到offer又要大伤人品了。
|
|
|
p*****2
发帖数: 21240 | 51
刚去了新公司，没几天就离职很伤RP。
【在 r*****k 的大作中提到】
: 为啥拿到offer又要大伤人品？
|
r*****k
发帖数: 1281 | 52 哈哈 是哦。
可以先拿offer 推迟报道
【在 p*****2 的大作中提到】
:
: 刚去了新公司，没几天就离职很伤RP。
|
j********l
发帖数: 325 | |
d*******l
发帖数: 338 | |
y******o
发帖数: 225 | |
p*****2
发帖数: 21240 | 56
有没有人说说我这个解对不对？我测试了一下，work的还挺好的，没发现什么问题。
【在 p*****2 的大作中提到】
: 恭喜大牛。刚看了一下题目。还没看回复。这道概率题我是这样考虑的
: static boolean Prob2(double p, boolean expected)
: {
: if(p<0.5)
: {
: expected=!expected;
: p=1-p;
: }
:
: if(Prob()==expected)
|
r*****k
发帖数: 1281 | 57 太高深了 看不懂。。
【在 p*****2 的大作中提到】
:
: 有没有人说说我这个解对不对？我测试了一下，work的还挺好的，没发现什么问题。
|
p*****2
发帖数: 21240 | 58
思路很简单呀。就是先找到概率>=0.5的解。
然后调用Prob， 如果得到需要的解，就结束。如果没有得到需要的解，那么已经浪费
了0.5的概率了。剩下的概率就是P-0.5.
因为得到的解是相反的答案，而且概率是0.5, 所以就要在这个0.5里得到(P-0.5)的概
率。那就是(P-0.5)/0.5。
比如要得到0.6的概率true
如果Prob返回true, 就结束。
如果返回false，那么得到true的概率就剩0.1了。
而得到false的概率是0.5, 在0.5里得到0.1就需要下一次调Fab得到true的概率是0.2.
这样的到true的总概率就是
0.5+0.5*0.2=0.6
【在 r*****k 的大作中提到】
: 太高深了 看不懂。。
|
w**b
发帖数: 989 | |
y*******g
发帖数: 6599 | 60 太牛了
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
|
|
z*****n
发帖数: 447 | 61 不错，
不过题目只要求一个参数，bool Prob2(double p)，返回随机值0、1；
但这个解法多带了个参数，而且返回的是确定值，变成按照概率p返回固定值expected
感觉先将p转化为二进制，再进行比较的思路更好理解些
.
【在 p*****2 的大作中提到】
:
: 思路很简单呀。就是先找到概率>=0.5的解。
: 然后调用Prob， 如果得到需要的解，就结束。如果没有得到需要的解，那么已经浪费
: 了0.5的概率了。剩下的概率就是P-0.5.
: 因为得到的解是相反的答案，而且概率是0.5, 所以就要在这个0.5里得到(P-0.5)的概
: 率。那就是(P-0.5)/0.5。
: 比如要得到0.6的概率true
: 如果Prob返回true, 就结束。
: 如果返回false，那么得到true的概率就剩0.1了。
: 而得到false的概率是0.5, 在0.5里得到0.1就需要下一次调Fab得到true的概率是0.2.
|
i**********e
发帖数: 1145 | 62 peking2 你不愧是北京大爷，思路真的好赞，竟然没人顶，我帮顶一下。
不过你思路看似简单，但其实真不容易想到，尤其你没往这方面想的话。
像我的话，就只想到 rejection sampling 的思路，解这题要复杂些。
.
【在 p*****2 的大作中提到】
:
: 思路很简单呀。就是先找到概率>=0.5的解。
: 然后调用Prob， 如果得到需要的解，就结束。如果没有得到需要的解，那么已经浪费
: 了0.5的概率了。剩下的概率就是P-0.5.
: 因为得到的解是相反的答案，而且概率是0.5, 所以就要在这个0.5里得到(P-0.5)的概
: 率。那就是(P-0.5)/0.5。
: 比如要得到0.6的概率true
: 如果Prob返回true, 就结束。
: 如果返回false，那么得到true的概率就剩0.1了。
: 而得到false的概率是0.5, 在0.5里得到0.1就需要下一次调Fab得到true的概率是0.2.
|
i**********e
发帖数: 1145 | 63 那参数第一次叫函数时传 expected = true 就行了。加一个wrapper也行。
expected
【在 z*****n 的大作中提到】
: 不错，
: 不过题目只要求一个参数，bool Prob2(double p)，返回随机值0、1；
: 但这个解法多带了个参数，而且返回的是确定值，变成按照概率p返回固定值expected
: 感觉先将p转化为二进制，再进行比较的思路更好理解些
:
: .
|
c*h
发帖数: 33018 | |
H***e
发帖数: 476 | 65 我run了下，误差还挺大的
你run了么？
【在 i**********e 的大作中提到】
: peking2 你不愧是北京大爷，思路真的好赞，竟然没人顶，我帮顶一下。
: 不过你思路看似简单，但其实真不容易想到，尤其你没往这方面想的话。
: 像我的话，就只想到 rejection sampling 的思路，解这题要复杂些。
:
: .
|
a********m
发帖数: 15480 | 66 lol. "然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了"
赞！
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
c***p
发帖数: 221 | 67 My 2 cents:
bool prob2(double p)
{
int q;
while ((q =prob()) == (int)(p*=2)) {p -= (int)p;};
return (q < (int)p );
}
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
p*****2
发帖数: 21240 | 68
这是我的测试程序。你测的什么数据？我试了几个P都还行。
import java.util.*;
public class test {
static boolean Prob()
{
Random rand=new Random();
return rand.nextBoolean();
}
static boolean Prob2(double p, boolean expected)
{
if(p<0.5)
{
expected=!expected;
p=1-p;
}
if(Prob()==expected)
return expected;
else
{
return Prob2((p-0.5)/0.5, expected);
}
}
public static void main(String[] args)
{
int count=0;
int times=10000;
double p=0.3;
boolean expected=true;
for(int i=0;i
{
if(Prob2(p,expected)==expected)
count++;
}
System.out.println((double)count/times);
}
}
【在 H***e 的大作中提到】
: 我run了下，误差还挺大的
: 你run了么？
|
p*****2
发帖数: 21240 | 69
多谢大牛。
【在 i**********e 的大作中提到】
: peking2 你不愧是北京大爷，思路真的好赞，竟然没人顶，我帮顶一下。
: 不过你思路看似简单，但其实真不容易想到，尤其你没往这方面想的话。
: 像我的话，就只想到 rejection sampling 的思路，解这题要复杂些。
:
: .
|
H***e
发帖数: 476 | 70 我run误差9%的概览啊
100000 runs
【在 p*****2 的大作中提到】
:
: 多谢大牛。
|
|
|
p*****2
发帖数: 21240 | 71
我的结果：
1. 0.08948
2. 0.0902
3. 0.08971
4. 0.08925
5. 0.09044
还是很接近呀。
【在 H***e 的大作中提到】
: 我run误差9%的概览啊
: 100000 runs
|
H***e
发帖数: 476 | 72 when i run it
p = 0.09;
and the result is 0.18274
...why?
【在 p*****2 的大作中提到】
:
: 我的结果：
: 1. 0.08948
: 2. 0.0902
: 3. 0.08971
: 4. 0.08925
: 5. 0.09044
: 还是很接近呀。
|
p*****2
发帖数: 21240 | 73
能post你的code吗？
【在 H***e 的大作中提到】
: when i run it
: p = 0.09;
: and the result is 0.18274
: ...why?
|
H***e
发帖数: 476 | 74 就用的你的exact code啊。。。
【在 p*****2 的大作中提到】
:
: 能post你的code吗？
|
p*****2
发帖数: 21240 | 75
copy/paste的？
【在 H***e 的大作中提到】
: 就用的你的exact code啊。。。
|
H***e
发帖数: 476 | 76 yes.. :(
【在 p*****2 的大作中提到】
:
: copy/paste的？
|
p*****2
发帖数: 21240 | 77
你试过了你那里random的结果是均匀的吗？
【在 H***e 的大作中提到】
: yes.. :(
|
l****i
发帖数: 51 | 78 double在计算机里是 基数 乘 指数
0.00344 = 0.344 * E-3
Update: 我记错了，指数也是基于2的，所以也是work的。
【在 r*****k 的大作中提到】
: 假设double p 二进制表示是：100011
: call prob 6次
: 如果结果小于100011 返回p
: 大于返回 1-p
: 等于再call prob 6次
: zz from Google
|
q****x
发帖数: 7404 | 79 根本没看懂。
【在 i**********e 的大作中提到】
: peking2 你不愧是北京大爷，思路真的好赞，竟然没人顶，我帮顶一下。
: 不过你思路看似简单，但其实真不容易想到，尤其你没往这方面想的话。
: 像我的话，就只想到 rejection sampling 的思路，解这题要复杂些。
:
: .
|
d***p
发帖数: 29 | 80 我也是这么想的，迭代一下就ok
【在 p*****2 的大作中提到】
:
: 你试过了你那里random的结果是均匀的吗？
|
|
|
l****i
发帖数: 51 | 81 bool Rand2(){ return true or false equally.};
// p is between 0 and 1
// return false for probability of p
bool PCal(double p)
{
p *= 2;
bool b = Rand2();
while(p != 0 && p! = 1)
{
b = Rand2();
if (!b && p > 1)
return false;
else (b && p < 1)
return true;
else
p = p *2;
}
return b;
} |
h********e
发帖数: 1972 | |
g*****i
发帖数: 2162 | |
p********n
发帖数: 20 | 84 prob的那题：
借助于prob，可以如此进行算法：
设第k次调用prob前，目标区间是[a,b]；k=1,2,…。k=1时a=0,b=1。对于这一次调用，
假想prob的工作方式是：随机一个[a,b]上的均匀分布数，如果这个数小于等于(a+b)/2
，则返回true；否则返回false。设x=a+p*(b-a)，prob2的工作方式可假想为：随机一
个[a,b]上的均匀分布数，如果这个数小于等于x，则返回true；否则返回false。于是
可按两种情况处理：
(1) x <= (a+b)/2
如果调用prob返回true，表明prob产生的随机数在[a,(a+b)/2]之间，但无法确定这个
随机数是否在[a,x]之间；此时令a’=a, b’=(a+b)/2，继续在[a’,b’]上重复上面的
过程(第k+1次)。
如果调用prob返回false，表明prob产生的随机数在((a+b)/2,b]之间，必不可能在[a,x
]之间，此时prob2可以返回false。
(2) x > (a+b)/2
如果调用prob返回true，表明prob产生的随机数在[a,(a+b)/2]之间，此时这个随机数
肯定在[a,x]之间，prob2返回true。
如果调用prob返回false，表明prob产生的随机数在((a+b)/2,b]之间，但无法确定这个
随机数是否在[a,x]之间；此时令a’=(a+b)/2，b’=b，继续在[a’,b’]上重复上面的
过程(第k+1次)。
算法很快，是指数收敛的。
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
g*****i
发帖数: 2162 | 85 对,还要避免运气不好的无限循环,循环限制在double的bit位数次就可以了.
【在 h********e 的大作中提到】
: 楼上忘记每次如果p大于1 要把p减1.。。
|
D********g
发帖数: 650 | 86 prob那题，我的code:
static boolean prob() {
Random r = new Random();
if (r.nextDouble() < 0.5) {
return true;
}
return false;
}
static boolean prob(double p) {
double EPS = 1e-8;
if (p >= 1.0) {
return true;
}
if (p <= 0.0) {
return false;
}
int bitPos = 0;
while (p > EPS) {
bitPos ++;
p = p * 2;
if (p >= 1.0) {
// We need to return true with prob 2^(-bitPos),
this can be achieved by calling prob() with bitPos times and return true if
all true
// All false is the prerequesite state for checking
next 1's.
boolean allTrue = true, allFalse = true;
for (int i = 0; i < bitPos; ++i) {
boolean flip = prob();
allTrue = allTrue && flip;
allFalse = allFalse && !flip;
EPS = EPS * 2;
}
if (allTrue) {
return true;
}
if (!allFalse) {
return false;
}
// reset
bitPos = 0;
p = p - 1.0;
}
}
return false;
}
static void testProb() {
int c = 1000000;
double p = 0.75;
int trueCount = 0;
for (int i = 0; i < c; ++i) {
if (prob(p)) {
trueCount++;
}
}
System.out.println("p--" + p + ", tc%--" + (double)trueCount/c);
p=0.125;
trueCount = 0;
for (int i = 0; i < c; ++i) {
if (prob(p)) {
trueCount++;
}
}
System.out.println("p--" + p + ", tc%--" + (double)trueCount/c);
p=0.33;
trueCount = 0;
for (int i = 0; i < c; ++i) {
if (prob(p)) {
trueCount++;
}
}
System.out.println("p--" + p + ", tc%--" + (double)trueCount/c);
}
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
c****e
发帖数: 26 | |
s*******k
发帖数: 1160 | |
a****2
发帖数: 1458 | 89 能不能详细贴一下那个直方题是什么题目
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
p*****2
发帖数: 21240 | 90
关于我那个解结果不对的问题。我是在Macbook上测试的，结果很接近。昨天跟人讨论
，别人是在Windows上测试的。我今天在Linux上测试了一下，确实得到了不正确的结果
。研究了一下发现，Linux上连续的同一个结果的情况比较严重。这里是我run 100次
rand.nextBoolean的结果在Macbook上，等下贴一下linux上的结果。
false
false
false
true
false
false
true
false
true
true
true
true
true
false
true
true
false
false
false
false
true
false
true
false
false
true
true
true
false
false
false
true
true
false
false
false
true
true
false
false
false
false
true
true
false
true
false
false
true
false
true
false
true
true
true
false
false
true
true
false
true
true
true
false
false
false
false
true
true
false
true
false
false
true
true
false
true
false
false
true
true
true
false
false
false
false
true
true
true
false
true
false
true
true
false
false
true
false
true
true
【在 a****2 的大作中提到】
: 能不能详细贴一下那个直方题是什么题目
|
|
|
p*****2
发帖数: 21240 | 91 Linux上的结果
true
true
false
true
false
false
true
false
true
false
false
false
false
true
true
true
false
true
true
true
true
false
false
true
false
true
false
false
true
false
false
false
false
true
false
true
false
false
true
false
false
false
true
true
false
true
true
false
false
true
true
true
true
false
false
true
false
true
false
false
false
false
true
false
true
false
false
true
true
true
true
true
true
true
true
true
true
false
false
true
false
true
true
false
true
false
true
true
true
true
false
true
false
true
false
false
false
false
true
true |
p*****2
发帖数: 21240 | 92 Linux上会出现连续10个true，在Mac上最多连续出现的次数是4次。应该是这个影响了
结果。 |
p*****2
发帖数: 21240 | 93 又做了一个测试，当产生100000个随机boolean的时候
Mac上连续结果的最大次数是10－20这个区间，而Linux上是160－170这个区间。看样子
Mac的随机性要比Linux更高。所以Mac上运行起来很接近结果。 |
o******y
发帖数: 446 | 94 random 函数应该是伪随机，有确定的算法，不是真正的随机。
你new 一个Random 的时候，如果带的seed参数一样，
每次的结果应该都是一样的，我觉得应该是平台无关。
如果new 一个Random不带参数，自动用当前的时间做seed.
public Random() { this(System.currentTimeMillis()); }
所以你取得什么结果，取决于你的seed.如果不带seed,
取决于你运行的时间。
【在 p*****2 的大作中提到】
: 又做了一个测试，当产生100000个随机boolean的时候
: Mac上连续结果的最大次数是10－20这个区间，而Linux上是160－170这个区间。看样子
: Mac的随机性要比Linux更高。所以Mac上运行起来很接近结果。
|
p*****2
发帖数: 21240 | 95
random是Java自己实现的？不是调的OS的random？
【在 o******y 的大作中提到】
: random 函数应该是伪随机，有确定的算法，不是真正的随机。
: 你new 一个Random 的时候，如果带的seed参数一样，
: 每次的结果应该都是一样的，我觉得应该是平台无关。
: 如果new 一个Random不带参数，自动用当前的时间做seed.
: public Random() { this(System.currentTimeMillis()); }
: 所以你取得什么结果，取决于你的seed.如果不带seed,
: 取决于你运行的时间。
|
f******t
发帖数: 7283 | 96 概率那题，coding不是重点，关键在于算法。想了一下有这么个思路，时间紧没有仔细
斟酌，所以不一定对，供参考而已。
Prob()产生True和False的概率都是0.5，就等价于黑箱里一红一黑两个球，让你随机哪
一个，那拿到红色的和黑色球的概率都是一半，这个很容易理解。
假如现在让你连续拿两次（当然是每次拿完之后都放回黑箱去），都能拿到红球的概率
是0.5 x 0.5 = 0.25；所以对于Prob2(double p)，假如p=0.25，那你知道怎么去做了。
问题是p可以任意取，比如说现在我让p=0.75那怎么办？考虑这么一个概率题，假如下
面这件事情最后能称为“成功”的概率是多少：最多让你试两回，第一回只让你取一个
球，假如取到红色的，就马上成功了不用做下去；假如不是红色的，再给你一次机会再
拿一次，假如这回也能拿到红色的，也算你成功了。这个事情成功的概率有多大呢？答
案不难：0.5 + 0.5 x 0.5 = 0.75，请注意这里的条件概率和概率相加时对于互斥事件
的处理。
再来一个复杂一点的，p=0.765625怎么办？请考虑下面这个事件成功的概率：最多让你
试三回，第一回是红色的马上成功了；第一回不成功的话给你第二次机会，再取到红色
的也算你成功；万一很不幸运第二回还不成功那就给你最后一次机会，再拿一次球，假
如是红色的话最后也算是成功的。成功概率是这样的：0.5 + 0.5 x 0.5 + 0.5 x 0.5
x 0.5 = 0.765625。
最后我们要知道这么一个数学知识：对于任何一个大于0小于1的小数，它都可以表达成
某些0.5的幂次项的和。所以假如你能想办法把p表达成某些0.5的幂次项的和，这道题
你就知道怎样做了。 |
D********g
发帖数: 650 | 97 直方图那题，我的code:
static int histogramHoldRainWater(final int[] hist) {
if (hist == null || hist.length == 0) {
throw new IllegalArgumentException();
}
if (hist.length <= 2) {
return 0;
}
int sum = 0;
int histLeft = 0;
int histRight = 0;
while (histLeft < hist.length) {
while (histLeft + 1 < hist.length && hist[histLeft] <= hist[
histLeft+1]) {
histLeft ++;
}
if (histLeft >= hist.length - 2) {
break;
}
histRight = histLeft + 1;
while (histRight + 1 < hist.length && hist[histRight] >= hist[
histRight + 1]) {
histRight ++;
}
if (histRight == hist.length - 1) {
break;
}
while (histRight + 1 < hist.length && hist[histRight] <= hist[
histRight + 1]) {
histRight ++;
}
int hight = Math.min(hist[histLeft], hist[histRight]);
for (int i = histLeft + 1; i < histRight; ++i) {
sum += hight - hist[i];
}
histLeft = histRight;
}
return sum;
}
static void testHistogramHoldRainWater() {
int[] a = new int[] {3,1,5};
System.out.println("Water for " + Arrays.toString(a) + " is " +
histogramHoldRainWater(a));
a = new int[] {3,1,0,5};
System.out.println("Water for " + Arrays.toString(a) + " is " +
histogramHoldRainWater(a));
}
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
p*****2
发帖数: 21240 | 98 这是我的直方图代码
public class test2 {
static int water(int[] arr)
{
int i=0;
int j=arr.length-1;
int count=0;
while(i
{
while(i
i++;
while(j>i && arr[j]
j--;
if(i==j)
break;
int start;
int low;
boolean direct=true;
if(arr[i]<=arr[j])
{
start=i+1;
low=arr[i];
direct=true;
}
else
{
start=j-1;
low=arr[j];
direct=false;
}
while(arr[start]
{
count+=low-arr[start];
if(direct)
start++;
else
start--;
}
if(direct)
i=start;
else
j=start;
}
return count;
}
public static void main(String[] args)
{
int[][] q=new int[][] {{3,1,5},
{3,1,0,5},
{1,2,3},
{3,2,1},
{1,2,3,2,1},
{5,4,3,6,2,3}};
int[] a=new int[] {2,5,0,0,0,4};
for(int i=0;i
{
int r=water(q[i]);
if(a[i]==r)
System.out.print("[Pass]");
else
System.out.print("[Fail]");
System.out.println("expected:"+a[i]+" actual:"+r);
}
}
} |
H***e
发帖数: 476 | 99 高度会改变的啊。
【在 p*****2 的大作中提到】
: 这是我的直方图代码
: public class test2 {
: static int water(int[] arr)
: {
: int i=0;
: int j=arr.length-1;
: int count=0;
:
: while(i: {
|
p*****2
发帖数: 21240 | 100
我还没考虑这个扩展。高度会改变是什么意思呀。能讲讲吗？
【在 H***e 的大作中提到】
: 高度会改变的啊。
|
|
|
p*****2
发帖数: 21240 | 101
高度可以任意改变，还是有一定限制和规律呢？
【在 H***e 的大作中提到】
: 高度会改变的啊。
|
H***e
发帖数: 476 | 102 我也不知道
万一变成最高的，貌似就要重算了
不知道有什么trick没有
【在 p*****2 的大作中提到】
:
: 高度可以任意改变，还是有一定限制和规律呢？
|
p*****2
发帖数: 21240 | 103
如果变化没有规律，变得乱七八糟的肯定得重算呀。所以，题目的要求还不清除。
【在 H***e 的大作中提到】
: 我也不知道
: 万一变成最高的，貌似就要重算了
: 不知道有什么trick没有
|
H***e
发帖数: 476 | 104 我assume是只变化一根
还有你知道第一题那个什么cup题是啥啊？ 能不能给个timu
【在 p*****2 的大作中提到】
:
: 如果变化没有规律，变得乱七八糟的肯定得重算呀。所以，题目的要求还不清除。
|
p*****2
发帖数: 21240 | 105
我找一下。
【在 H***e 的大作中提到】
: 我assume是只变化一根
: 还有你知道第一题那个什么cup题是啥啊？ 能不能给个timu
|
p*****2
发帖数: 21240 | 106
Some engineers got tired of dealing with all the different ways of encoding
status messages, so they decided to invent their own. In their new scheme,
an encoded status message consists of a sequence of integers representing
the characters in the message, separated by spaces. Each integer is between
1 and M, inclusive. The integers do not have leading zeroes. Unfortunately
they decided to compress the encoded status messages by removing all the
spaces!
Your task is to figure out how many different encoded status messages a
given compressed status message could have originally been. Because this
number can be very large, you should return the answer modulo 4207849484 (
0xfaceb00c in hex).
For example, if the compressed status message is "12" it might have
originally been "1 2", or it might have originally been "12". The compressed
status messages are between 1 and 1000 characters long, inclusive. Due to
database corruption, a compressed status may contain sequences of digits
that could not result from removing the spaces in an encoded status message.
Input
The input begins with a single integer, N, the number of compressed status
messages you must analyze. This will be followed by N compressed status
messages, each consisting of an integer M, the highest character code for
that database, then the compressed status message, which will be a string of
digits each in the range '0' to '9', inclusive. All tokens in the input
will be separated by some whitespace.
Output
For each of the test cases numbered in order from 1 to N, output "Case #i: "
followed by a single integer containing the number of different encoded
status messages that could be represented by the corresponding compressed
sequence modulo 4207849484. If none are possible, output a 0.
Constraints
5 <= N <= 25
2 <= M <= 255
1 <= length of encoded status <= 1000
Example inputExample output
5
12
12
255
219
30
1234321
2
101
70 8675309
Case #1: 2
Case #2: 4
Case #3: 6
Case #4: 0
Case #5: 2
【在 H***e 的大作中提到】
: 我assume是只变化一根
: 还有你知道第一题那个什么cup题是啥啊？ 能不能给个timu
|
f**e
发帖数: 1269 | 107 赞最后一句。前阵有人在说用linkedin数据来做一个app，就是把从这些hot company
跳去startup的人统计一下人数，看哪些startup占据最多，那就是你该看的公司了。
这些数据现在在linkedin上不显示，因为网站上显示的是绝对数字最多的公司，那样
大公司自然会被列出来，而不是startup。谁有功夫把这个app做出来造福大家吧。
【在 P*****f 的大作中提到】
: 谁给钱多去谁。
: G跳Twitter/Zynga的更多，Facebook也算比较大公司了，IPO搞头不大。要去动态的，
: 观察下从这些公司跳出来的去哪就可以了
|
y*******g
发帖数: 6599 | 108 特别早期的startup fresh也不太容易进，而且h1b 绿卡政策很可能一般
【在 f**e 的大作中提到】
: 赞最后一句。前阵有人在说用linkedin数据来做一个app，就是把从这些hot company
: 跳去startup的人统计一下人数，看哪些startup占据最多，那就是你该看的公司了。
: 这些数据现在在linkedin上不显示，因为网站上显示的是绝对数字最多的公司，那样
: 大公司自然会被列出来，而不是startup。谁有功夫把这个app做出来造福大家吧。
|
l****i
发帖数: 51 | 109 bool Rand2(){ return true or false equally.};
// p is between 0 and 1
// return false for probability of p
bool PCal(double p)
{
p *= 2;
bool b = Rand2();
while(p != 0 && p! = 1)
{
b = Rand2();
if (!b && p > 1)
return false;
else (b && p < 1)
return true;
else if ( p > 1)
p = (p-1) *2;
else
p * =2;
}
return b;
} |
p*****2
发帖数: 21240 | 110 刚才想了想那个变化长度的。感觉可以转换为interval的问题，但是写起code来挺麻烦
的。 |
|
|
i**********e
发帖数: 1145 | 111 我刚在linux上运行了，没有这方面的问题，不过我的程序是C++ 不是Java。
我测试了你的算法，返回结果都算满意，而且运行越多次，返回的结果越接近理想的 p
值。
你的算法不单简洁，而且复杂度是最优的，递归是 average 两次就返回答案。
expected # calls = 1*0.5 + 2*0.5^2 + 3*0.5^3 + ...
= Summation( k * 0.5^k ), k = 1 .. n
= 2 - (n+2)/2^n
When n = infinity,
expected # calls = 2
贴下code方便大家做测试：
#include
#include
#include
#include
using namespace std;
bool rand2() {
return (rand() % 2 == 0);
}
unsigned long long totalCalls = 0;
bool Prob2(double p, bool expected = true) {
totalCalls++;
if (p < 0.5) {
expected = !expected;
p = 1-p;
}
if (rand2()) {
return expected;
} else {
return Prob2((p-0.5)/0.5, expected);
}
}
int main() {
srand(time(NULL));
unsigned long long n = 100000000;
unsigned long long total = 0;
double p = 0.903013;
unsigned long long calls = 0;
for (unsigned long long i = 0; i < n; i++) {
totalCalls = 0;
if (Prob2(p)) {
total++;
}
calls += totalCalls;
}
double statisticP = ((double)total / n);
cout << "Theoretical p = " << p << endl;
cout << "Prob2 statistical p = " << statisticP << endl;
cout << "Difference from theoretical p: " << (fabs(statisticP - p) / p *
100.0) << "%" << endl;
cout << "Average # calls = " << ((double)calls / n) << endl;
}
【在 p*****2 的大作中提到】
: Linux上会出现连续10个true，在Mac上最多连续出现的次数是4次。应该是这个影响了
: 结果。
|
p*****2
发帖数: 21240 | 112 多谢大牛confirm。
p
【在 i**********e 的大作中提到】
: 我刚在linux上运行了，没有这方面的问题，不过我的程序是C++ 不是Java。
: 我测试了你的算法，返回结果都算满意，而且运行越多次，返回的结果越接近理想的 p
: 值。
: 你的算法不单简洁，而且复杂度是最优的，递归是 average 两次就返回答案。
: expected # calls = 1*0.5 + 2*0.5^2 + 3*0.5^3 + ...
: = Summation( k * 0.5^k ), k = 1 .. n
: = 2 - (n+2)/2^n
: When n = infinity,
: expected # calls = 2
: 贴下code方便大家做测试：
|
t****i
发帖数: 88 | |
p*****2
发帖数: 21240 | 114 多谢大牛更新。
直方图那个我觉得可以用interval来解。 |
R******t
发帖数: 2648 | |
l*******0
发帖数: 176 | 116 感觉你这个FB的PhD package偏低啊～ |
H*****1
发帖数: 4815 | 117 多谢分享！
F的4800K RSU相当于多少啊？
G的phd standard 是 127K base么？
【在 v***a 的大作中提到】
: 只是因为大学开始的时候，G就是dream company了
|
g***y
发帖数: 764 | 118 怎么可能4800k
是4800 shares吧 哈哈
【在 H*****1 的大作中提到】
: 多谢分享！
: F的4800K RSU相当于多少啊？
: G的phd standard 是 127K base么？
|
S*****e
发帖数: 229 | 119 感谢楼主分享面经！
【在 v***a 的大作中提到】
: 只是因为大学开始的时候，G就是dream company了
|
y*******g
发帖数: 6599 | 120 很不错吧？ 不过我也不知道fb给phD是多少
说偏低偏高的说一个标准的？
【在 l*******0 的大作中提到】
: 感觉你这个FB的PhD package偏低啊～
|
|
|
c*****e
发帖数: 737 | 121 1 #include
2 #include
3 #include
4
5 int prob()
6 {
7 return rand() % 2;
8 }
9
10 int prob(double req_, double has_)
11 {
12 int a = prob();
13
14 if (req_ == has_)
15 return a;
16 else if (req_ > has_)
17 {
18 if (a == 1)
19 return a;
20 else
21 return prob(req_ - has_, has_ / 2);
22 }
23 else
24 {
25 if (a == 0)
26 return a;
27 else
28 return prob(req_, has_ / 2);
29 }
30 }
31
32 int main()
33 {
34 srand(time(NULL));
35
36 int k = 0, runs = 100000;
37 ..
38 for (int i = 0; i < runs; ++i)
39 k += prob(0.3, 0.5);
40
41 std::cout << k * 1.0 / runs << "\n";
42 }
【在 b***u 的大作中提到】
: prob()怎么搞？
: 我能想到是你能构造1/2^k。以及或事件造p1+p2-p1p2。怎么逼近p呢？
|
f*******t
发帖数: 7549 | |
h*****g
发帖数: 312 | 123 这个想法能不能展开讲讲？
thanks~
【在 p*****2 的大作中提到】
: 刚才想了想那个变化长度的。感觉可以转换为interval的问题，但是写起code来挺麻烦
: 的。
|
p*****2
发帖数: 21240 | 124
就是把能盛水的各个部分做成各个interval来存储。一旦有高度的变化，就根据相应的
情况调整intervals。比如merge，create new interval, delete interval etc. 各种
情况都要考虑，code会比较麻烦。
【在 h*****g 的大作中提到】
: 这个想法能不能展开讲讲？
: thanks~
|
s******n
发帖数: 3946 | 125 对
【在 p*****2 的大作中提到】
:
: 就是把能盛水的各个部分做成各个interval来存储。一旦有高度的变化，就根据相应的
: 情况调整intervals。比如merge，create new interval, delete interval etc. 各种
: 情况都要考虑，code会比较麻烦。
|
s******n
发帖数: 3946 | 126 peking2那个翻转"expected"太深奥了，这样行不行？
static boolean Prob(double p)
{
while(p) {
int bit = p>0.5?1:0;
int r = rand2();
if (r
else if (r>bit) return false;
p=p*2;
if (bit) p=p-1;
}
return false;
} |
P**********c
发帖数: 3417 | 127 赞。good choice. If G's base is 127k, considering return and risk it is
still the better choice.
【在 v***a 的大作中提到】
: 只是因为大学开始的时候，G就是dream company了
|
g*******n
发帖数: 214 | 128 Cong!
Update:不少人发信问package和题目解答，update一下吧：第一题详细在 http://www.mitbbs.com/article/JobHun........
★ Sent from iPhone App: iReader Mitbbs Lite 7.39
【在 v***a 的大作中提到】
: 只是因为大学开始的时候，G就是dream company了
|
u**l
发帖数: 1043 | 129 hehe, 4800k RSU , that is a lot.
【在 v***a 的大作中提到】
: 只是因为大学开始的时候，G就是dream company了
|
h*********7
发帖数: 811 | 130 本科拿这么好的package起点真是不错，年轻有为啊。:) Cong lz，聪明能干。 |
|
|
H****r
发帖数: 2801 | 131 直方题怎么扫瞄一次得到结果？ 怎么感觉得上stack?
【在 v***a 的大作中提到】
: 只是因为大学开始的时候，G就是dream company了
|
b******t
发帖数: 965 | 132 两个指针一左一右往中间走
类似 sorted array之2sum problem
【在 H****r 的大作中提到】
: 直方题怎么扫瞄一次得到结果？ 怎么感觉得上stack?
|
H****r
发帖数: 2801 | 133 cool!
这个问题要改成两维直方阵求水容积会更有趣？
【在 b******t 的大作中提到】
: 两个指针一左一右往中间走
: 类似 sorted array之2sum problem
|
v***a
发帖数: 365 | 134 Update:
不少人发信问package和题目解答，update一下吧：
第一题详细在 http://www.mitbbs.com/article/JobHunting/32055617_0.html
感谢 peking2 同学贴上来
第二题我当时的算法和 pigsolomon 朋友的差不多：
http://www.mitbbs.com/article/JobHunting/32055195_0.html
是其中一种正确的算法，肯定有更好的，期待大牛
第三题的扩展
每次只有一根柱子变化，减少或者增加k单位
我没有做出来，只是提了一下RMQ或许可以用在里面，面试官没有肯定
不过这个面试结果是 positive，无解了
Package：
FB在知道我有G offer的情况下给了我 entry BS level package 85k base +
3000RSU，G在知道FB给我这么多之后，还是很大方的给了我 PhD Standard，然后我当场就签
了，是我现在工资的8倍了，知足常乐！
随后FB又改成了PhD standard 115k + 4800k RSU + 15k signingbonus, 不过已经签
了，base比G少点，股票多不少
好几个朋友问为啥不去F，只是个人大学时的dream company是Google，更主要的是那边食堂比FB
的好吃
------------------------------------------
积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
FB的新题：
X）Initial Onsite，
题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
于是把公式写出来，顺便程序也写出来，
然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
deploy 到所有机器里，大概百万台，
怎么设计一个系统。
这个新题，正好想到了Gossip，
于是扯了一通 Gossip 算法，给出复杂度O(LogN) 就可以发送完，
随后发现由于带宽限制，网络拓扑结构已知，所以Gossip 不好，
抄袭 mapReduce 的框架，设计了一个有 Master 节点的 Gossip 算法
X) 顺利拿到Onsite, 一个印度 Manager 听我面的很好，对algorithm 和 backend很熟
悉，
于是 onsite 时特地来面我，题目都是behavior，你为啥有激情，为啥想来FB等等，
当然在问之前花了半小时介绍他的工作， 说他们走backend的多牛，多重要，
同时强烈推荐我去他的组，说有多激情，可以改变世界，我边听边在心里说:
我艹烙印
X）Onsite，给你一个函数 bool Prob() ，有50%的概率返回 True，50%的概率返回
False
请你用写一个新的函数：bool Prob2(double p)
要求 p 的概率返回 True， 1 - p 的概率返回 False
当然，肯定使用 Prob 了
这题我用的2分法，花了不少时间，，
然后问了fibonacci的 O(1) Space 或者 O(N) time 的解法，
刚好剩下5分钟问他问题，
结果大跌眼镜，内部推荐的朋友告诉我，这个人给了我个 Negative！！
HR 也没告诉我为啥，莫须有的罪名。
面试是看RP的，RP不好，总能碰到看你不顺眼的
X）Onsite 老题新酒，直方图，天上下雨，求能存多少水
E.G:
3,1,5 => 2
3,1,0,5 => 5
很假单的O(N)扫描就行
扩展是改成Online的算法，就是说：
有些地方高度随时会变，
E.G.
3,1,5 => 3,0,5 => 3
3,1,0,5 => 3,3,0,5 => 3
设计一个算法，最快的返回改变高度之后的结果
----
我的方法：
做题
------------------------------------------------------
非常感谢提供面经的人，没有这些面经，绝对没把握当场作出来！ |
b*****n
发帖数: 453 | 135 gxgx!
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
b***u
发帖数: 12010 | 136 prob()怎么搞？
我能想到是你能构造1/2^k。以及或事件造p1+p2-p1p2。怎么逼近p呢？
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
m******s
发帖数: 165 | 137 比如p=0.3
call prob->
>0.5：返回失败
<0.5：call prob->
<0.5：返回成功
>0.5（0.25-0.5）：call prob。。。
期望大概是扔3次
【在 b***u 的大作中提到】
: prob()怎么搞？
: 我能想到是你能构造1/2^k。以及或事件造p1+p2-p1p2。怎么逼近p呢？
|
b***u
发帖数: 12010 | 138 没看懂。怎么generalize?
【在 m******s 的大作中提到】
: 比如p=0.3
: call prob->
: >0.5：返回失败
: <0.5：call prob->
: <0.5：返回成功
: >0.5（0.25-0.5）：call prob。。。
: 期望大概是扔3次
|
h*********n
发帖数: 11319 | 139 so strong! mark
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
r*******n
发帖数: 266 | 140 cong!
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
|
|
z******w
发帖数: 36 | |
B******5
发帖数: 4676 | |
i******r
发帖数: 793 | 143 我现在对烙印真的有心理阴影
我面F的时候也是个烙印
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
n***a
发帖数: 34 | |
w********n
发帖数: 58 | |
w********n
发帖数: 58 | |
k***t
发帖数: 276 | 147 为啥选G不选F？按说你这样的编程竞赛大拿该选动态、
高速发展的平台，而不是一个相对established环境。
G跳F的比F跳G的要多吧？如果试因为pkg差别，应该可以谈。
尽管F以后如何还不一定，但向上空间同样不可限量。
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
P*****f
发帖数: 2272 | 148 谁给钱多去谁。
G跳Twitter/Zynga的更多，Facebook也算比较大公司了，IPO搞头不大。要去动态的，
观察下从这些公司跳出来的去哪就可以了
【在 k***t 的大作中提到】
: 为啥选G不选F？按说你这样的编程竞赛大拿该选动态、
: 高速发展的平台，而不是一个相对established环境。
: G跳F的比F跳G的要多吧？如果试因为pkg差别，应该可以谈。
: 尽管F以后如何还不一定，但向上空间同样不可限量。
|
P*****f
发帖数: 2272 | 149 welcome to G
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
k***t
发帖数: 276 | 150 同意向钱看和向前看:) 说说从这些公司跳出来的都去哪？
【在 P*****f 的大作中提到】
: 谁给钱多去谁。
: G跳Twitter/Zynga的更多，Facebook也算比较大公司了，IPO搞头不大。要去动态的，
: 观察下从这些公司跳出来的去哪就可以了
|
|
|
m*****a
发帖数: 636 | 151 Congrats!
啥叫带宽限制，toplogic已知 -> master 节点 Gossip
积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
FB的新题：
X）Initial Onsite，
题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
于是把公式写出来，顺便程序也写出来，
然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
deploy 到所有机器里，大概百万台，
怎么设计一个系统。
这个新题，正好想到了Gossip，
于是扯了一通 Gossip 算法，给出复杂度O(LogN) 就可以发送完，
随后发现由于带宽限制，网络拓扑结构已知，所以Gossip 不好，
抄袭 mapReduce 的框架，设计了一个有 Master 节点的 Gossip 算法
X) 顺利拿到Onsite, 一个印度 Manager 听我面的很好，对algorithm 和 backend很熟
悉，
于是 onsite 时特地来面我，题目都是behavior，你为啥有激情，为啥想来FB等等，
当然在问之前花了半小时介绍他的工作， 说他们走backend的多牛，多重要，
同时强烈推荐我去他的组，说有多激情，可以改变世界，我边听边在心里说:
我艹烙印
X）Onsite，给你一个函数 bool Prob() ，有50%的概率返回 True，50%的概率返回
False
请你用写一个新的函数：bool Prob2(double p)
要求 p 的概率返回 True， 1 - p 的概率返回 False
当然，肯定使用 Prob 了
这题我用的2分法，花了不少时间，，
然后问了fibonacci的 O(1) Space 或者 O(N) time 的解法，
刚好剩下5分钟问他问题，
结果大跌眼镜，内部推荐的朋友告诉我，这个人给了我个 Negative！！
HR 也没告诉我为啥，莫须有的罪名。
面试是看RP的，RP不好，总能碰到看你不顺眼的
X）Onsite 老题新酒，直方图，天上下雨，求能存多少水
E.G:
3,1,5 => 2
3,1,0,5 => 5
很假单的O(N)扫描就行
扩展是改成Online的算法，就是说：
有些地方高度随时会变，
E.G.
3,1,5 => 3,0,5 => 3
3,1,0,5 => 3,3,0,5 => 3
设计一个算法，最快的返回改变高度之后的结果
----
我的方法：
做题
------------------------------------------------------
非常感谢提供面经的人，没有这些面经，绝对没把握当场作出来！
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
r*****k
发帖数: 1281 | 152 假设double p 二进制表示是：100011
call prob 6次
如果结果小于100011 返回p
大于返回 1-p
等于再call prob 6次
zz from Google
【在 b***u 的大作中提到】
: prob()怎么搞？
: 我能想到是你能构造1/2^k。以及或事件造p1+p2-p1p2。怎么逼近p呢？
|
z*****n
发帖数: 447 | |
k*********5
发帖数: 1417 | |
p*****2
发帖数: 21240 | 155 恭喜大牛。刚看了一下题目。还没看回复。这道概率题我是这样考虑的
static boolean Prob2(double p, boolean expected)
{
if(p<0.5)
{
expected=!expected;
p=1-p;
}
if(Prob()==expected)
return expected;
else
{
return Prob2((p-0.5)/0.5, expected);
}
} |
p*****2
发帖数: 21240 | |
P**********c
发帖数: 3417 | 157 F现在很多时候给的股票跟G的差不多，大家当然都选G. G的股票基本没有风险。F按
照100B的valuation给，风险很大，涨的potential不大，不怎么划算。
以前从G跳到F的人家拿多少股，你得看去年还有多少人跳过去。不如在G待一段时间再去
一个感觉有前途还很小的startup. F的revenue还只能看作G的一个部门吧，
不觉得从career的角度就有多大差别。比如说G的search组也就跟F差不多大吧, career
角度我觉得是差不多的。不拿出点实际的motivation来，就谈career就是bullshit.
【在 k***t 的大作中提到】
: 为啥选G不选F？按说你这样的编程竞赛大拿该选动态、
: 高速发展的平台，而不是一个相对established环境。
: G跳F的比F跳G的要多吧？如果试因为pkg差别，应该可以谈。
: 尽管F以后如何还不一定，但向上空间同样不可限量。
|
p*****2
发帖数: 21240 | 158
再去
upside
G有一个不好就是拿到offer的时候不知道去哪个组。如果被分到一个不喜欢的组也没意
思吧？好像换组也得等18个月吧？那看来现在从待遇来说G已经Top了。要不怎么
Fortune 100 G今年排了第一。不过不知道收购moto之后会有不会有什么变化。moto人
可不少。
【在 P**********c 的大作中提到】
: F现在很多时候给的股票跟G的差不多，大家当然都选G. G的股票基本没有风险。F按
: 照100B的valuation给，风险很大，涨的potential不大，不怎么划算。
: 以前从G跳到F的人家拿多少股，你得看去年还有多少人跳过去。不如在G待一段时间再去
: 一个感觉有前途还很小的startup. F的revenue还只能看作G的一个部门吧，
: 不觉得从career的角度就有多大差别。比如说G的search组也就跟F差不多大吧, career
: 角度我觉得是差不多的。不拿出点实际的motivation来，就谈career就是bullshit.
|
r*****k
发帖数: 1281 | 159 moto应该和原来的g分开运营把。招人和发工资都分开。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****2 的大作中提到】
:
: 再去
: upside
: G有一个不好就是拿到offer的时候不知道去哪个组。如果被分到一个不喜欢的组也没意
: 思吧？好像换组也得等18个月吧？那看来现在从待遇来说G已经Top了。要不怎么
: Fortune 100 G今年排了第一。不过不知道收购moto之后会有不会有什么变化。moto人
: 可不少。
|
p*****2
发帖数: 21240 | 160
那简历上能写Google吗？
【在 r*****k 的大作中提到】
: moto应该和原来的g分开运营把。招人和发工资都分开。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
|
|
v***a
发帖数: 365 | 161 只是因为大学开始的时候，G就是dream company了
【在 k***t 的大作中提到】
: 为啥选G不选F？按说你这样的编程竞赛大拿该选动态、
: 高速发展的平台，而不是一个相对established环境。
: G跳F的比F跳G的要多吧？如果试因为pkg差别，应该可以谈。
: 尽管F以后如何还不一定，但向上空间同样不可限量。
|
r*****k
发帖数: 1281 | 162 google moto啊。
就像现在intel mcafee。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****2 的大作中提到】
:
: 那简历上能写Google吗？
|
p*****2
发帖数: 21240 | 163
大牛再贴几道F的题吧，应该还有其他吧？
【在 v***a 的大作中提到】
: 只是因为大学开始的时候，G就是dream company了
|
p*****2
发帖数: 21240 | 164
那也有点用。起码有Google这个keyword了。如果老员工已经离开公司的能不能也用
Google Moto呢？
【在 r*****k 的大作中提到】
: google moto啊。
: 就像现在intel mcafee。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
r*****k
发帖数: 1281 | 165 北京也要面了 ？
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****2 的大作中提到】
:
: 那也有点用。起码有Google这个keyword了。如果老员工已经离开公司的能不能也用
: Google Moto呢？
|
p*****2
发帖数: 21240 | 166
过了一面，现在想是不是拖两个月。因为复习的还不够，很多老题我还没做过。而且也
还没做到600道题。
【在 r*****k 的大作中提到】
: 北京也要面了 ？
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
r*****k
发帖数: 1281 | 167 我还没做到60题 好多都不会。。。
【在 p*****2 的大作中提到】
:
: 过了一面，现在想是不是拖两个月。因为复习的还不够，很多老题我还没做过。而且也
: 还没做到600道题。
|
y*****z
发帖数: 9 | 168 这个是概率题。。
先生成 4个bit的 二进制 true代表1，false代表0
这样我们能生成0-15的 等概率的 distribution
然后 [0,15] 当中 选[0,10] -->[0,2](true), [3,9](false)
public class Solution {
/**
* @param args
*/
public void doit(){
int iterate = 10000000;
boolean valve = true;
StringBuilder s = new StringBuilder();
while (valve) {
StringBuilder str = new StringBuilder();
for (int i = 0; i < 4; i++) {
if (Math.random() < 0.5) str.append('1');
else str.append('0');
}
double p = 0.3;
int target = (int) (p * 10);
int value = Integer.parseInt(str.toString(), 2);
if (value <= 9) {
// [0-15]-->[0,9]-->[0,2](1),[3,9](0);
if (value <= 2) {
s.append('1');
} else {
s.append('0');
}
} else
valve = true;
iterate--;
if (iterate < 0)
break;
}
int countone = 0, countzero = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '1')
countone++;
if (s.charAt(i) == '0')
countzero++;
}
int sum = countone + countzero;
System.out.println(((double)countone/(double)sum) + " " + ((double)
countzero/(double)sum));
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution s = new Solution();
s.doit();
}
} |
p*****2
发帖数: 21240 | 169
你也面F呀？
【在 r*****k 的大作中提到】
: 我还没做到60题 好多都不会。。。
|
r*****k
发帖数: 1281 | 170 要面啊 感觉没准备好
想cancel了
【在 p*****2 的大作中提到】
:
: 你也面F呀？
|
|
|
p*****2
发帖数: 21240 | 171
怎么cancel呀？跟recruiter说就行了？还是说delay两个月呢？
【在 r*****k 的大作中提到】
: 要面啊 感觉没准备好
: 想cancel了
|
r*****k
发帖数: 1281 | 172 delay啊 不知道行不行
【在 p*****2 的大作中提到】
:
: 怎么cancel呀？跟recruiter说就行了？还是说delay两个月呢？
|
i**********e
发帖数: 1145 | 173 恭喜！
之前你说你没拿到面试我说怎么可能呢？
好好加油，前途无量！ |
k***t
发帖数: 276 | 174 怎么说都行吧，感觉上recruiter就是个经纪人，双方的。
他也想做你这单生意，晚一两个月对他的收益没有影响，
除非他绝望到一个月只内再不成交就要走人了才会Push Client：）
【在 p*****2 的大作中提到】
:
: 怎么cancel呀？跟recruiter说就行了？还是说delay两个月呢？
|
l*****a
发帖数: 14598 | 175 问题是对某些特定team的特定职位。不见得是一直有opening的
除非你申请那些common positions
【在 k***t 的大作中提到】
: 怎么说都行吧，感觉上recruiter就是个经纪人，双方的。
: 他也想做你这单生意，晚一两个月对他的收益没有影响，
: 除非他绝望到一个月只内再不成交就要走人了才会Push Client：）
|
k***t
发帖数: 276 | 176 对特定职位的，那当然。
peking2是在面FG的common position吧。
可能要跟recruiter确认一下。从他的角度也有
motivation to encourage the client to prepare the interview。
【在 l*****a 的大作中提到】
: 问题是对某些特定team的特定职位。不见得是一直有opening的
: 除非你申请那些common positions
|
p*****2
发帖数: 21240 | 177
我还真是特定的。看来比较麻烦了。fail了两年只能还不能在申请了。
【在 k***t 的大作中提到】
: 对特定职位的，那当然。
: peking2是在面FG的common position吧。
: 可能要跟recruiter确认一下。从他的角度也有
: motivation to encourage the client to prepare the interview。
|
A**u
发帖数: 2458 | |
l*****a
发帖数: 14598 | 179 why 2 years?
new rules for FB?
【在 p*****2 的大作中提到】
:
: 我还真是特定的。看来比较麻烦了。fail了两年只能还不能在申请了。
|
p*****2
发帖数: 21240 | 180
听vissa说的。
【在 l*****a 的大作中提到】
: why 2 years?
: new rules for FB?
|
|
|
k***t
发帖数: 276 | 181 那也需要权衡利弊。就算你是特定职位，看F这架势，
因该还有一段时间要大量全面找人。你那特定职位及其
相关职位应该也不止找一个人。
我觉得尽管时间长一点也不一定就好，但总要你自己
comfortable后再去才好，不留遗憾。
不过，至少赶在IPO股价可能的变化之前好一些。
Good Luck。
【在 p*****2 的大作中提到】
:
: 听vissa说的。
|
p*****2
发帖数: 21240 | 182
recruiter说我那职位就招，5,6个人，已经收到 几千份简历了。不过也无所谓了吧。
如果万一拿到offer又要大伤人品了。
【在 k***t 的大作中提到】
: 那也需要权衡利弊。就算你是特定职位，看F这架势，
: 因该还有一段时间要大量全面找人。你那特定职位及其
: 相关职位应该也不止找一个人。
: 我觉得尽管时间长一点也不一定就好，但总要你自己
: comfortable后再去才好，不留遗憾。
: 不过，至少赶在IPO股价可能的变化之前好一些。
: Good Luck。
|
r*****k
发帖数: 1281 | 183 为啥拿到offer又要大伤人品？
【在 p*****2 的大作中提到】
:
: recruiter说我那职位就招，5,6个人，已经收到 几千份简历了。不过也无所谓了吧。
: 如果万一拿到offer又要大伤人品了。
|
p*****2
发帖数: 21240 | 184
刚去了新公司，没几天就离职很伤RP。
【在 r*****k 的大作中提到】
: 为啥拿到offer又要大伤人品？
|
r*****k
发帖数: 1281 | 185 哈哈 是哦。
可以先拿offer 推迟报道
【在 p*****2 的大作中提到】
:
: 刚去了新公司，没几天就离职很伤RP。
|
j********l
发帖数: 325 | |
d*******l
发帖数: 338 | 187 楼主终于来到了跟自身水平相符的位置上，祝贺！ |
y******o
发帖数: 225 | |
p*****2
发帖数: 21240 | 189
有没有人说说我这个解对不对？我测试了一下，work的还挺好的，没发现什么问题。
【在 p*****2 的大作中提到】
: 恭喜大牛。刚看了一下题目。还没看回复。这道概率题我是这样考虑的
: static boolean Prob2(double p, boolean expected)
: {
: if(p<0.5)
: {
: expected=!expected;
: p=1-p;
: }
:
: if(Prob()==expected)
|
r*****k
发帖数: 1281 | 190 太高深了 看不懂。。
【在 p*****2 的大作中提到】
:
: 有没有人说说我这个解对不对？我测试了一下，work的还挺好的，没发现什么问题。
|
|
|
p*****2
发帖数: 21240 | 191
思路很简单呀。就是先找到概率>=0.5的解。
然后调用Prob， 如果得到需要的解，就结束。如果没有得到需要的解，那么已经浪费
了0.5的概率了。剩下的概率就是P-0.5.
因为得到的解是相反的答案，而且概率是0.5, 所以就要在这个0.5里得到(P-0.5)的概
率。那就是(P-0.5)/0.5。
比如要得到0.6的概率true
如果Prob返回true, 就结束。
如果返回false，那么得到true的概率就剩0.1了。
而得到false的概率是0.5, 在0.5里得到0.1就需要下一次调Fab得到true的概率是0.2.
这样的到true的总概率就是
0.5+0.5*0.2=0.6
【在 r*****k 的大作中提到】
: 太高深了 看不懂。。
|
w**b
发帖数: 989 | |
y*******g
发帖数: 6599 | 193 太牛了
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
z*****n
发帖数: 447 | 194 不错，
不过题目只要求一个参数，bool Prob2(double p)，返回随机值0、1；
但这个解法多带了个参数，而且返回的是确定值，变成按照概率p返回固定值expected
感觉先将p转化为二进制，再进行比较的思路更好理解些
.
【在 p*****2 的大作中提到】
:
: 思路很简单呀。就是先找到概率>=0.5的解。
: 然后调用Prob， 如果得到需要的解，就结束。如果没有得到需要的解，那么已经浪费
: 了0.5的概率了。剩下的概率就是P-0.5.
: 因为得到的解是相反的答案，而且概率是0.5, 所以就要在这个0.5里得到(P-0.5)的概
: 率。那就是(P-0.5)/0.5。
: 比如要得到0.6的概率true
: 如果Prob返回true, 就结束。
: 如果返回false，那么得到true的概率就剩0.1了。
: 而得到false的概率是0.5, 在0.5里得到0.1就需要下一次调Fab得到true的概率是0.2.
|
i**********e
发帖数: 1145 | 195 peking2 你不愧是北京大爷，思路真的好赞，竟然没人顶，我帮顶一下。
不过你思路看似简单，但其实真不容易想到，尤其你没往这方面想的话。
像我的话，就只想到 rejection sampling 的思路，解这题要复杂些。
.
【在 p*****2 的大作中提到】
:
: 思路很简单呀。就是先找到概率>=0.5的解。
: 然后调用Prob， 如果得到需要的解，就结束。如果没有得到需要的解，那么已经浪费
: 了0.5的概率了。剩下的概率就是P-0.5.
: 因为得到的解是相反的答案，而且概率是0.5, 所以就要在这个0.5里得到(P-0.5)的概
: 率。那就是(P-0.5)/0.5。
: 比如要得到0.6的概率true
: 如果Prob返回true, 就结束。
: 如果返回false，那么得到true的概率就剩0.1了。
: 而得到false的概率是0.5, 在0.5里得到0.1就需要下一次调Fab得到true的概率是0.2.
|
i**********e
发帖数: 1145 | 196 那参数第一次叫函数时传 expected = true 就行了。加一个wrapper也行。
expected
【在 z*****n 的大作中提到】
: 不错，
: 不过题目只要求一个参数，bool Prob2(double p)，返回随机值0、1；
: 但这个解法多带了个参数，而且返回的是确定值，变成按照概率p返回固定值expected
: 感觉先将p转化为二进制，再进行比较的思路更好理解些
:
: .
|
c*h
发帖数: 33018 | |
H***e
发帖数: 476 | 198 我run了下，误差还挺大的
你run了么？
【在 i**********e 的大作中提到】
: peking2 你不愧是北京大爷，思路真的好赞，竟然没人顶，我帮顶一下。
: 不过你思路看似简单，但其实真不容易想到，尤其你没往这方面想的话。
: 像我的话，就只想到 rejection sampling 的思路，解这题要复杂些。
:
: .
|
a********m
发帖数: 15480 | 199 lol. "然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了"
赞！
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
c***p
发帖数: 221 | 200 My 2 cents:
bool prob2(double p)
{
int q;
while ((q =prob()) == (int)(p*=2)) {p -= (int)p;};
return (q < (int)p );
}
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
|
|
p*****2
发帖数: 21240 | 201
这是我的测试程序。你测的什么数据？我试了几个P都还行。
import java.util.*;
public class test {
static boolean Prob()
{
Random rand=new Random();
return rand.nextBoolean();
}
static boolean Prob2(double p, boolean expected)
{
if(p<0.5)
{
expected=!expected;
p=1-p;
}
if(Prob()==expected)
return expected;
else
{
return Prob2((p-0.5)/0.5, expected);
}
}
public static void main(String[] args)
{
int count=0;
int times=10000;
double p=0.3;
boolean expected=true;
for(int i=0;i
{
if(Prob2(p,expected)==expected)
count++;
}
System.out.println((double)count/times);
}
}
【在 H***e 的大作中提到】
: 我run了下，误差还挺大的
: 你run了么？
|
p*****2
发帖数: 21240 | 202
多谢大牛。
【在 i**********e 的大作中提到】
: peking2 你不愧是北京大爷，思路真的好赞，竟然没人顶，我帮顶一下。
: 不过你思路看似简单，但其实真不容易想到，尤其你没往这方面想的话。
: 像我的话，就只想到 rejection sampling 的思路，解这题要复杂些。
:
: .
|
H***e
发帖数: 476 | 203 我run误差9%的概览啊
100000 runs
【在 p*****2 的大作中提到】
:
: 多谢大牛。
|
p*****2
发帖数: 21240 | 204
我的结果：
1. 0.08948
2. 0.0902
3. 0.08971
4. 0.08925
5. 0.09044
还是很接近呀。
【在 H***e 的大作中提到】
: 我run误差9%的概览啊
: 100000 runs
|
H***e
发帖数: 476 | 205 when i run it
p = 0.09;
and the result is 0.18274
...why?
【在 p*****2 的大作中提到】
:
: 我的结果：
: 1. 0.08948
: 2. 0.0902
: 3. 0.08971
: 4. 0.08925
: 5. 0.09044
: 还是很接近呀。
|
p*****2
发帖数: 21240 | 206
能post你的code吗？
【在 H***e 的大作中提到】
: when i run it
: p = 0.09;
: and the result is 0.18274
: ...why?
|
H***e
发帖数: 476 | 207 就用的你的exact code啊。。。
【在 p*****2 的大作中提到】
:
: 能post你的code吗？
|
p*****2
发帖数: 21240 | 208
copy/paste的？
【在 H***e 的大作中提到】
: 就用的你的exact code啊。。。
|
H***e
发帖数: 476 | 209 yes.. :(
【在 p*****2 的大作中提到】
:
: copy/paste的？
|
p*****2
发帖数: 21240 | 210
你试过了你那里random的结果是均匀的吗？
【在 H***e 的大作中提到】
: yes.. :(
|
|
|
l****i
发帖数: 51 | 211 double在计算机里是 基数 乘 指数
0.00344 = 0.344 * E-3
Update: 我记错了，指数也是基于2的，所以也是work的。
【在 r*****k 的大作中提到】
: 假设double p 二进制表示是：100011
: call prob 6次
: 如果结果小于100011 返回p
: 大于返回 1-p
: 等于再call prob 6次
: zz from Google
|
q****x
发帖数: 7404 | 212 根本没看懂。
【在 i**********e 的大作中提到】
: peking2 你不愧是北京大爷，思路真的好赞，竟然没人顶，我帮顶一下。
: 不过你思路看似简单，但其实真不容易想到，尤其你没往这方面想的话。
: 像我的话，就只想到 rejection sampling 的思路，解这题要复杂些。
:
: .
|
d***p
发帖数: 29 | 213 我也是这么想的，迭代一下就ok
【在 p*****2 的大作中提到】
:
: 你试过了你那里random的结果是均匀的吗？
|
l****i
发帖数: 51 | 214 bool Rand2(){ return true or false equally.};
// p is between 0 and 1
// return false for probability of p
bool PCal(double p)
{
p *= 2;
bool b = Rand2();
while(p != 0 && p! = 1)
{
b = Rand2();
if (!b && p > 1)
return false;
else (b && p < 1)
return true;
else
p = p *2;
}
return b;
} |
h********e
发帖数: 1972 | |
g*****i
发帖数: 2162 | |
p********n
发帖数: 20 | 217 prob的那题：
借助于prob，可以如此进行算法：
设第k次调用prob前，目标区间是[a,b]；k=1,2,…。k=1时a=0,b=1。对于这一次调用，
假想prob的工作方式是：随机一个[a,b]上的均匀分布数，如果这个数小于等于(a+b)/2
，则返回true；否则返回false。设x=a+p*(b-a)，prob2的工作方式可假想为：随机一
个[a,b]上的均匀分布数，如果这个数小于等于x，则返回true；否则返回false。于是
可按两种情况处理：
(1) x <= (a+b)/2
如果调用prob返回true，表明prob产生的随机数在[a,(a+b)/2]之间，但无法确定这个
随机数是否在[a,x]之间；此时令a’=a, b’=(a+b)/2，继续在[a’,b’]上重复上面的
过程(第k+1次)。
如果调用prob返回false，表明prob产生的随机数在((a+b)/2,b]之间，必不可能在[a,x
]之间，此时prob2可以返回false。
(2) x > (a+b)/2
如果调用prob返回true，表明prob产生的随机数在[a,(a+b)/2]之间，此时这个随机数
肯定在[a,x]之间，prob2返回true。
如果调用prob返回false，表明prob产生的随机数在((a+b)/2,b]之间，但无法确定这个
随机数是否在[a,x]之间；此时令a’=(a+b)/2，b’=b，继续在[a’,b’]上重复上面的
过程(第k+1次)。
算法很快，是指数收敛的。
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
g*****i
发帖数: 2162 | 218 对,还要避免运气不好的无限循环,循环限制在double的bit位数次就可以了.
【在 h********e 的大作中提到】
: 楼上忘记每次如果p大于1 要把p减1.。。
|
D********g
发帖数: 650 | 219 prob那题，我的code:
static boolean prob() {
Random r = new Random();
if (r.nextDouble() < 0.5) {
return true;
}
return false;
}
static boolean prob(double p) {
double EPS = 1e-8;
if (p >= 1.0) {
return true;
}
if (p <= 0.0) {
return false;
}
int bitPos = 0;
while (p > EPS) {
bitPos ++;
p = p * 2;
if (p >= 1.0) {
// We need to return true with prob 2^(-bitPos),
this can be achieved by calling prob() with bitPos times and return true if
all true
// All false is the prerequesite state for checking
next 1's.
boolean allTrue = true, allFalse = true;
for (int i = 0; i < bitPos; ++i) {
boolean flip = prob();
allTrue = allTrue && flip;
allFalse = allFalse && !flip;
EPS = EPS * 2;
}
if (allTrue) {
return true;
}
if (!allFalse) {
return false;
}
// reset
bitPos = 0;
p = p - 1.0;
}
}
return false;
}
static void testProb() {
int c = 1000000;
double p = 0.75;
int trueCount = 0;
for (int i = 0; i < c; ++i) {
if (prob(p)) {
trueCount++;
}
}
System.out.println("p--" + p + ", tc%--" + (double)trueCount/c);
p=0.125;
trueCount = 0;
for (int i = 0; i < c; ++i) {
if (prob(p)) {
trueCount++;
}
}
System.out.println("p--" + p + ", tc%--" + (double)trueCount/c);
p=0.33;
trueCount = 0;
for (int i = 0; i < c; ++i) {
if (prob(p)) {
trueCount++;
}
}
System.out.println("p--" + p + ", tc%--" + (double)trueCount/c);
}
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
c****e
发帖数: 26 | |
|
|
s*******k
发帖数: 1160 | |
a****2
发帖数: 1458 | 222 能不能详细贴一下那个直方题是什么题目
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
p*****2
发帖数: 21240 | 223
关于我那个解结果不对的问题。我是在Macbook上测试的，结果很接近。昨天跟人讨论
，别人是在Windows上测试的。我今天在Linux上测试了一下，确实得到了不正确的结果
。研究了一下发现，Linux上连续的同一个结果的情况比较严重。这里是我run 100次
rand.nextBoolean的结果在Macbook上，等下贴一下linux上的结果。
false
false
false
true
false
false
true
false
true
true
true
true
true
false
true
true
false
false
false
false
true
false
true
false
false
true
true
true
false
false
false
true
true
false
false
false
true
true
false
false
false
false
true
true
false
true
false
false
true
false
true
false
true
true
true
false
false
true
true
false
true
true
true
false
false
false
false
true
true
false
true
false
false
true
true
false
true
false
false
true
true
true
false
false
false
false
true
true
true
false
true
false
true
true
false
false
true
false
true
true
【在 a****2 的大作中提到】
: 能不能详细贴一下那个直方题是什么题目
|
p*****2
发帖数: 21240 | 224 Linux上的结果
true
true
false
true
false
false
true
false
true
false
false
false
false
true
true
true
false
true
true
true
true
false
false
true
false
true
false
false
true
false
false
false
false
true
false
true
false
false
true
false
false
false
true
true
false
true
true
false
false
true
true
true
true
false
false
true
false
true
false
false
false
false
true
false
true
false
false
true
true
true
true
true
true
true
true
true
true
false
false
true
false
true
true
false
true
false
true
true
true
true
false
true
false
true
false
false
false
false
true
true |
p*****2
发帖数: 21240 | 225 Linux上会出现连续10个true，在Mac上最多连续出现的次数是4次。应该是这个影响了
结果。 |
p*****2
发帖数: 21240 | 226 又做了一个测试，当产生100000个随机boolean的时候
Mac上连续结果的最大次数是10－20这个区间，而Linux上是160－170这个区间。看样子
Mac的随机性要比Linux更高。所以Mac上运行起来很接近结果。 |
o******y
发帖数: 446 | 227 random 函数应该是伪随机，有确定的算法，不是真正的随机。
你new 一个Random 的时候，如果带的seed参数一样，
每次的结果应该都是一样的，我觉得应该是平台无关。
如果new 一个Random不带参数，自动用当前的时间做seed.
public Random() { this(System.currentTimeMillis()); }
所以你取得什么结果，取决于你的seed.如果不带seed,
取决于你运行的时间。
【在 p*****2 的大作中提到】
: 又做了一个测试，当产生100000个随机boolean的时候
: Mac上连续结果的最大次数是10－20这个区间，而Linux上是160－170这个区间。看样子
: Mac的随机性要比Linux更高。所以Mac上运行起来很接近结果。
|
p*****2
发帖数: 21240 | 228
random是Java自己实现的？不是调的OS的random？
【在 o******y 的大作中提到】
: random 函数应该是伪随机，有确定的算法，不是真正的随机。
: 你new 一个Random 的时候，如果带的seed参数一样，
: 每次的结果应该都是一样的，我觉得应该是平台无关。
: 如果new 一个Random不带参数，自动用当前的时间做seed.
: public Random() { this(System.currentTimeMillis()); }
: 所以你取得什么结果，取决于你的seed.如果不带seed,
: 取决于你运行的时间。
|
f******t
发帖数: 7283 | 229 概率那题，coding不是重点，关键在于算法。想了一下有这么个思路，时间紧没有仔细
斟酌，所以不一定对，供参考而已。
Prob()产生True和False的概率都是0.5，就等价于黑箱里一红一黑两个球，让你随机哪
一个，那拿到红色的和黑色球的概率都是一半，这个很容易理解。
假如现在让你连续拿两次（当然是每次拿完之后都放回黑箱去），都能拿到红球的概率
是0.5 x 0.5 = 0.25；所以对于Prob2(double p)，假如p=0.25，那你知道怎么去做了。
问题是p可以任意取，比如说现在我让p=0.75那怎么办？考虑这么一个概率题，假如下
面这件事情最后能称为“成功”的概率是多少：最多让你试两回，第一回只让你取一个
球，假如取到红色的，就马上成功了不用做下去；假如不是红色的，再给你一次机会再
拿一次，假如这回也能拿到红色的，也算你成功了。这个事情成功的概率有多大呢？答
案不难：0.5 + 0.5 x 0.5 = 0.75，请注意这里的条件概率和概率相加时对于互斥事件
的处理。
再来一个复杂一点的，p=0.765625怎么办？请考虑下面这个事件成功的概率：最多让你
试三回，第一回是红色的马上成功了；第一回不成功的话给你第二次机会，再取到红色
的也算你成功；万一很不幸运第二回还不成功那就给你最后一次机会，再拿一次球，假
如是红色的话最后也算是成功的。成功概率是这样的：0.5 + 0.5 x 0.5 + 0.5 x 0.5
x 0.5 = 0.765625。
最后我们要知道这么一个数学知识：对于任何一个大于0小于1的小数，它都可以表达成
某些0.5的幂次项的和。所以假如你能想办法把p表达成某些0.5的幂次项的和，这道题
你就知道怎样做了。 |
D********g
发帖数: 650 | 230 直方图那题，我的code:
static int histogramHoldRainWater(final int[] hist) {
if (hist == null || hist.length == 0) {
throw new IllegalArgumentException();
}
if (hist.length <= 2) {
return 0;
}
int sum = 0;
int histLeft = 0;
int histRight = 0;
while (histLeft < hist.length) {
while (histLeft + 1 < hist.length && hist[histLeft] <= hist[
histLeft+1]) {
histLeft ++;
}
if (histLeft >= hist.length - 2) {
break;
}
histRight = histLeft + 1;
while (histRight + 1 < hist.length && hist[histRight] >= hist[
histRight + 1]) {
histRight ++;
}
if (histRight == hist.length - 1) {
break;
}
while (histRight + 1 < hist.length && hist[histRight] <= hist[
histRight + 1]) {
histRight ++;
}
int hight = Math.min(hist[histLeft], hist[histRight]);
for (int i = histLeft + 1; i < histRight; ++i) {
sum += hight - hist[i];
}
histLeft = histRight;
}
return sum;
}
static void testHistogramHoldRainWater() {
int[] a = new int[] {3,1,5};
System.out.println("Water for " + Arrays.toString(a) + " is " +
histogramHoldRainWater(a));
a = new int[] {3,1,0,5};
System.out.println("Water for " + Arrays.toString(a) + " is " +
histogramHoldRainWater(a));
}
【在 v***a 的大作中提到】
: 积攒RP，回报版面，签了G家，所以他家信息基本不透露了，直接上题目：
: FB的新题：
: X）Initial Onsite，
: 题目：Facebook HackerCup Round 1 的 Squished Status，比这个还简单些
: 告诉他做过了，DP就行，他就说那些解法是O(N) Space的，O(1)空间怎么解，
: 于是把公式写出来，顺便程序也写出来，
: 然后很霸气的告诉他，这种简单的题目没想过O(N)的，他镇精了
: 随后Open题，一个分布式系统，每次要把一个新的 OS binary file 有 100MB，
: deploy 到所有机器里，大概百万台，
: 怎么设计一个系统。
|
|
|
p*****2
发帖数: 21240 | 231 这是我的直方图代码
public class test2 {
static int water(int[] arr)
{
int i=0;
int j=arr.length-1;
int count=0;
while(i
{
while(i
i++;
while(j>i && arr[j]
j--;
if(i==j)
break;
int start;
int low;
boolean direct=true;
if(arr[i]<=arr[j])
{
start=i+1;
low=arr[i];
direct=true;
}
else
{
start=j-1;
low=arr[j];
direct=false;
}
while(arr[start]
{
count+=low-arr[start];
if(direct)
start++;
else
start--;
}
if(direct)
i=start;
else
j=start;
}
return count;
}
public static void main(String[] args)
{
int[][] q=new int[][] {{3,1,5},
{3,1,0,5},
{1,2,3},
{3,2,1},
{1,2,3,2,1},
{5,4,3,6,2,3}};
int[] a=new int[] {2,5,0,0,0,4};
for(int i=0;i
{
int r=water(q[i]);
if(a[i]==r)
System.out.print("[Pass]");
else
System.out.print("[Fail]");
System.out.println("expected:"+a[i]+" actual:"+r);
}
}
} |
H***e
发帖数: 476 | 232 高度会改变的啊。
【在 p*****2 的大作中提到】
: 这是我的直方图代码
: public class test2 {
: static int water(int[] arr)
: {
: int i=0;
: int j=arr.length-1;
: int count=0;
:
: while(i: {
|
p*****2
发帖数: 21240 | 233
我还没考虑这个扩展。高度会改变是什么意思呀。能讲讲吗？
【在 H***e 的大作中提到】
: 高度会改变的啊。
|
p*****2
发帖数: 21240 | 234
高度可以任意改变，还是有一定限制和规律呢？
【在 H***e 的大作中提到】
: 高度会改变的啊。
|
H***e
发帖数: 476 | 235 我也不知道
万一变成最高的，貌似就要重算了
不知道有什么trick没有
【在 p*****2 的大作中提到】
:
: 高度可以任意改变，还是有一定限制和规律呢？
|
p*****2
发帖数: 21240 | 236
如果变化没有规律，变得乱七八糟的肯定得重算呀。所以，题目的要求还不清除。
【在 H***e 的大作中提到】
: 我也不知道
: 万一变成最高的，貌似就要重算了
: 不知道有什么trick没有
|
H***e
发帖数: 476 | 237 我assume是只变化一根
还有你知道第一题那个什么cup题是啥啊？ 能不能给个timu
【在 p*****2 的大作中提到】
:
: 如果变化没有规律，变得乱七八糟的肯定得重算呀。所以，题目的要求还不清除。
|
p*****2
发帖数: 21240 | 238
我找一下。
【在 H***e 的大作中提到】
: 我assume是只变化一根
: 还有你知道第一题那个什么cup题是啥啊？ 能不能给个timu
|
p*****2
发帖数: 21240 | 239
Some engineers got tired of dealing with all the different ways of encoding
status messages, so they decided to invent their own. In their new scheme,
an encoded status message consists of a sequence of integers representing
the characters in the message, separated by spaces. Each integer is between
1 and M, inclusive. The integers do not have leading zeroes. Unfortunately
they decided to compress the encoded status messages by removing all the
spaces!
Your task is to figure out how many different encoded status messages a
given compressed status message could have originally been. Because this
number can be very large, you should return the answer modulo 4207849484 (
0xfaceb00c in hex).
For example, if the compressed status message is "12" it might have
originally been "1 2", or it might have originally been "12". The compressed
status messages are between 1 and 1000 characters long, inclusive. Due to
database corruption, a compressed status may contain sequences of digits
that could not result from removing the spaces in an encoded status message.
Input
The input begins with a single integer, N, the number of compressed status
messages you must analyze. This will be followed by N compressed status
messages, each consisting of an integer M, the highest character code for
that database, then the compressed status message, which will be a string of
digits each in the range '0' to '9', inclusive. All tokens in the input
will be separated by some whitespace.
Output
For each of the test cases numbered in order from 1 to N, output "Case #i: "
followed by a single integer containing the number of different encoded
status messages that could be represented by the corresponding compressed
sequence modulo 4207849484. If none are possible, output a 0.
Constraints
5 <= N <= 25
2 <= M <= 255
1 <= length of encoded status <= 1000
Example inputExample output
5
12
12
255
219
30
1234321
2
101
70 8675309
Case #1: 2
Case #2: 4
Case #3: 6
Case #4: 0
Case #5: 2
【在 H***e 的大作中提到】
: 我assume是只变化一根
: 还有你知道第一题那个什么cup题是啥啊？ 能不能给个timu
|
f**e
发帖数: 1269 | 240 赞最后一句。前阵有人在说用linkedin数据来做一个app，就是把从这些hot company
跳去startup的人统计一下人数，看哪些startup占据最多，那就是你该看的公司了。
这些数据现在在linkedin上不显示，因为网站上显示的是绝对数字最多的公司，那样
大公司自然会被列出来，而不是startup。谁有功夫把这个app做出来造福大家吧。
【在 P*****f 的大作中提到】
: 谁给钱多去谁。
: G跳Twitter/Zynga的更多，Facebook也算比较大公司了，IPO搞头不大。要去动态的，
: 观察下从这些公司跳出来的去哪就可以了
|
|
|
y*******g
发帖数: 6599 | 241 特别早期的startup fresh也不太容易进，而且h1b 绿卡政策很可能一般
【在 f**e 的大作中提到】
: 赞最后一句。前阵有人在说用linkedin数据来做一个app，就是把从这些hot company
: 跳去startup的人统计一下人数，看哪些startup占据最多，那就是你该看的公司了。
: 这些数据现在在linkedin上不显示，因为网站上显示的是绝对数字最多的公司，那样
: 大公司自然会被列出来，而不是startup。谁有功夫把这个app做出来造福大家吧。
|
l****i
发帖数: 51 | 242 bool Rand2(){ return true or false equally.};
// p is between 0 and 1
// return false for probability of p
bool PCal(double p)
{
p *= 2;
bool b = Rand2();
while(p != 0 && p! = 1)
{
b = Rand2();
if (!b && p > 1)
return false;
else (b && p < 1)
return true;
else if ( p > 1)
p = (p-1) *2;
else
p * =2;
}
return b;
} |
p*****2
发帖数: 21240 | 243 刚才想了想那个变化长度的。感觉可以转换为interval的问题，但是写起code来挺麻烦
的。 |
i**********e
发帖数: 1145 | 244 我刚在linux上运行了，没有这方面的问题，不过我的程序是C++ 不是Java。
我测试了你的算法，返回结果都算满意，而且运行越多次，返回的结果越接近理想的 p
值。
你的算法不单简洁，而且复杂度是最优的，递归是 average 两次就返回答案。
expected # calls = 1*0.5 + 2*0.5^2 + 3*0.5^3 + ...
= Summation( k * 0.5^k ), k = 1 .. n
= 2 - (n+2)/2^n
When n = infinity,
expected # calls = 2
贴下code方便大家做测试：
#include
#include
#include
#include
using namespace std;
bool rand2() {
return (rand() % 2 == 0);
}
unsigned long long totalCalls = 0;
bool Prob2(double p, bool expected = true) {
totalCalls++;
if (p < 0.5) {
expected = !expected;
p = 1-p;
}
if (rand2()) {
return expected;
} else {
return Prob2((p-0.5)/0.5, expected);
}
}
int main() {
srand(time(NULL));
unsigned long long n = 100000000;
unsigned long long total = 0;
double p = 0.903013;
unsigned long long calls = 0;
for (unsigned long long i = 0; i < n; i++) {
totalCalls = 0;
if (Prob2(p)) {
total++;
}
calls += totalCalls;
}
double statisticP = ((double)total / n);
cout << "Theoretical p = " << p << endl;
cout << "Prob2 statistical p = " << statisticP << endl;
cout << "Difference from theoretical p: " << (fabs(statisticP - p) / p *
100.0) << "%" << endl;
cout << "Average # calls = " << ((double)calls / n) << endl;
}
【在 p*****2 的大作中提到】
: Linux上会出现连续10个true，在Mac上最多连续出现的次数是4次。应该是这个影响了
: 结果。
|
p*****2
发帖数: 21240 | 245 多谢大牛confirm。
p
【在 i**********e 的大作中提到】
: 我刚在linux上运行了，没有这方面的问题，不过我的程序是C++ 不是Java。
: 我测试了你的算法，返回结果都算满意，而且运行越多次，返回的结果越接近理想的 p
: 值。
: 你的算法不单简洁，而且复杂度是最优的，递归是 average 两次就返回答案。
: expected # calls = 1*0.5 + 2*0.5^2 + 3*0.5^3 + ...
: = Summation( k * 0.5^k ), k = 1 .. n
: = 2 - (n+2)/2^n
: When n = infinity,
: expected # calls = 2
: 贴下code方便大家做测试：
|
t****i
发帖数: 88 | |
p*****2
发帖数: 21240 | 247 多谢大牛更新。
直方图那个我觉得可以用interval来解。 |
R******t
发帖数: 2648 | |
l*******0
发帖数: 176 | 249 感觉你这个FB的PhD package偏低啊～ |
H*****1
发帖数: 4815 | 250 多谢分享！
F的4800K RSU相当于多少啊？
G的phd standard 是 127K base么？
【在 v***a 的大作中提到】
: Update:
: 不少人发信问package和题目解答，update一下吧：
: 第一题详细在 http://www.mitbbs.com/article/JobHunting/32055617_0.html
: 感谢 peking2 同学贴上来
: 第二题我当时的算法和 pigsolomon 朋友的差不多：
: http://www.mitbbs.com/article/JobHunting/32055195_0.html
: 是其中一种正确的算法，肯定有更好的，期待大牛
: 第三题的扩展
: 每次只有一根柱子变化，减少或者增加k单位
: 我没有做出来，只是提了一下RMQ或许可以用在里面，面试官没有肯定
|
|
|
g***y
发帖数: 764 | 251 怎么可能4800k
是4800 shares吧 哈哈
【在 H*****1 的大作中提到】
: 多谢分享！
: F的4800K RSU相当于多少啊？
: G的phd standard 是 127K base么？
|
S*****e
发帖数: 229 | 252 感谢楼主分享面经！
【在 v***a 的大作中提到】
: Update:
: 不少人发信问package和题目解答，update一下吧：
: 第一题详细在 http://www.mitbbs.com/article/JobHunting/32055617_0.html
: 感谢 peking2 同学贴上来
: 第二题我当时的算法和 pigsolomon 朋友的差不多：
: http://www.mitbbs.com/article/JobHunting/32055195_0.html
: 是其中一种正确的算法，肯定有更好的，期待大牛
: 第三题的扩展
: 每次只有一根柱子变化，减少或者增加k单位
: 我没有做出来，只是提了一下RMQ或许可以用在里面，面试官没有肯定
|
y*******g
发帖数: 6599 | 253 很不错吧？ 不过我也不知道fb给phD是多少
说偏低偏高的说一个标准的？
【在 l*******0 的大作中提到】
: 感觉你这个FB的PhD package偏低啊～
|
c*****e
发帖数: 737 | 254 1 #include
2 #include
3 #include
4
5 int prob()
6 {
7 return rand() % 2;
8 }
9
10 int prob(double req_, double has_)
11 {
12 int a = prob();
13
14 if (req_ == has_)
15 return a;
16 else if (req_ > has_)
17 {
18 if (a == 1)
19 return a;
20 else
21 return prob(req_ - has_, has_ / 2);
22 }
23 else
24 {
25 if (a == 0)
26 return a;
27 else
28 return prob(req_, has_ / 2);
29 }
30 }
31
32 int main()
33 {
34 srand(time(NULL));
35
36 int k = 0, runs = 100000;
37 ..
38 for (int i = 0; i < runs; ++i)
39 k += prob(0.3, 0.5);
40
41 std::cout << k * 1.0 / runs << "\n";
42 }
【在 b***u 的大作中提到】
: prob()怎么搞？
: 我能想到是你能构造1/2^k。以及或事件造p1+p2-p1p2。怎么逼近p呢？
|
f*******t
发帖数: 7549 | |
h*****g
发帖数: 312 | 256 这个想法能不能展开讲讲？
thanks~
【在 p*****2 的大作中提到】
: 刚才想了想那个变化长度的。感觉可以转换为interval的问题，但是写起code来挺麻烦
: 的。
|
p*****2
发帖数: 21240 | 257
就是把能盛水的各个部分做成各个interval来存储。一旦有高度的变化，就根据相应的
情况调整intervals。比如merge，create new interval, delete interval etc. 各种
情况都要考虑，code会比较麻烦。
【在 h*****g 的大作中提到】
: 这个想法能不能展开讲讲？
: thanks~
|
s******n
发帖数: 3946 | 258 对
【在 p*****2 的大作中提到】
:
: 就是把能盛水的各个部分做成各个interval来存储。一旦有高度的变化，就根据相应的
: 情况调整intervals。比如merge，create new interval, delete interval etc. 各种
: 情况都要考虑，code会比较麻烦。
|
s******n
发帖数: 3946 | 259 peking2那个翻转"expected"太深奥了，这样行不行？
static boolean Prob(double p)
{
while(p) {
int bit = p>0.5?1:0;
int r = rand2();
if (r
else if (r>bit) return false;
p=p*2;
if (bit) p=p-1;
}
return false;
} |
P**********c
发帖数: 3417 | 260 赞。good choice. If G's base is 127k, considering return and risk it is
still the better choice.
【在 v***a 的大作中提到】
: Update:
: 不少人发信问package和题目解答，update一下吧：
: 第一题详细在 http://www.mitbbs.com/article/JobHunting/32055617_0.html
: 感谢 peking2 同学贴上来
: 第二题我当时的算法和 pigsolomon 朋友的差不多：
: http://www.mitbbs.com/article/JobHunting/32055195_0.html
: 是其中一种正确的算法，肯定有更好的，期待大牛
: 第三题的扩展
: 每次只有一根柱子变化，减少或者增加k单位
: 我没有做出来，只是提了一下RMQ或许可以用在里面，面试官没有肯定
|
|
|
g*******n
发帖数: 214 | 261 Cong!
Update:不少人发信问package和题目解答，update一下吧：第一题详细在 http://www.mitbbs.com/article/JobHun........
★ Sent from iPhone App: iReader Mitbbs Lite 7.39
【在 v***a 的大作中提到】
: 只是因为大学开始的时候，G就是dream company了
|
u**l
发帖数: 1043 | 262 hehe, 4800k RSU , that is a lot.
【在 v***a 的大作中提到】
: Update:
: 不少人发信问package和题目解答，update一下吧：
: 第一题详细在 http://www.mitbbs.com/article/JobHunting/32055617_0.html
: 感谢 peking2 同学贴上来
: 第二题我当时的算法和 pigsolomon 朋友的差不多：
: http://www.mitbbs.com/article/JobHunting/32055195_0.html
: 是其中一种正确的算法，肯定有更好的，期待大牛
: 第三题的扩展
: 每次只有一根柱子变化，减少或者增加k单位
: 我没有做出来，只是提了一下RMQ或许可以用在里面，面试官没有肯定
|
h*********7
发帖数: 811 | 263 本科拿这么好的package起点真是不错，年轻有为啊。:) Cong lz，聪明能干。 |
H****r
发帖数: 2801 | 264 直方题怎么扫瞄一次得到结果？ 怎么感觉得上stack?
【在 v***a 的大作中提到】
: Update:
: 不少人发信问package和题目解答，update一下吧：
: 第一题详细在 http://www.mitbbs.com/article/JobHunting/32055617_0.html
: 感谢 peking2 同学贴上来
: 第二题我当时的算法和 pigsolomon 朋友的差不多：
: http://www.mitbbs.com/article/JobHunting/32055195_0.html
: 是其中一种正确的算法，肯定有更好的，期待大牛
: 第三题的扩展
: 每次只有一根柱子变化，减少或者增加k单位
: 我没有做出来，只是提了一下RMQ或许可以用在里面，面试官没有肯定
|
b******t
发帖数: 965 | 265 两个指针一左一右往中间走
类似 sorted array之2sum problem
【在 H****r 的大作中提到】
: 直方题怎么扫瞄一次得到结果？ 怎么感觉得上stack?
|
H****r
发帖数: 2801 | 266 cool!
这个问题要改成两维直方阵求水容积会更有趣？
【在 b******t 的大作中提到】
: 两个指针一左一右往中间走
: 类似 sorted array之2sum problem
|
w***y
发帖数: 6251 | 267 直方图那个题, 我没有见过原题啊
题目到底是什么样的?//汗
E.G:
3,1,5 => 2
3,1,0,5 => 5
没看懂什么意思 |
y*******g
发帖数: 6599 | |
