b*********h
发帖数: 103 | 1 f 家有两种推，一种是推荐人保证你是他认识的某个团体的前两名 就会保证短时间联
系 另一种说不准... |
|
x********y
发帖数: 14 | 2 来自主题: JobHunting版 - G 家面经 bless 楼主.
第二题应该用dp。
如果一个人在位置（i，j）时向上走，就说这个位置是这个人的“折点”。
然后这个问题每个state是（i，j，k），i是当前row，（i，j） 是第一个人的折点，
（i，
k) 是第二个人折点.
递推关系是 state（i，j，k) = max {state（i+1， j1, k1), where j1 <= j and k1
<= k}
sample code:
const int M = 4;
const int N = 4;
int a[M][N] = {
{1, 2, 3, 4},
{1, 0, 3, 0},
{1, 20, 3, 0},
{10, 10, 3, 0}};
int dp_two_max_gold() {
int state[M][N][N];
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
for (int k = 0; k < N; ++k)
state[i][j][k] = 0;
// Firs... 阅读全帖 |
|
x********y
发帖数: 14 | 3 来自主题: JobHunting版 - G 家面经 bless 楼主.
第二题应该用dp。
如果一个人在位置（i，j）时向上走，就说这个位置是这个人的“折点”。
然后这个问题每个state是（i，j，k），i是当前row，（i，j） 是第一个人的折点，
（i，
k) 是第二个人折点.
递推关系是 state（i，j，k) = max {state（i+1， j1, k1), where j1 <= j and k1
<= k}
sample code:
const int M = 4;
const int N = 4;
int a[M][N] = {
{1, 2, 3, 4},
{1, 0, 3, 0},
{1, 20, 3, 0},
{10, 10, 3, 0}};
int dp_two_max_gold() {
int state[M][N][N];
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
for (int k = 0; k < N; ++k)
state[i][j][k] = 0;
// Firs... 阅读全帖 |
|
f*********m
发帖数: 726 | 4 原帖：
http://www.mitbbs.com/article_t1/JobHunting/32293265_0_1.html
题目：
给一个筛子， 最大可以抛3次， 每次可以选择是否继续丢， 给一个策略让最后筛子的
点数最大化。
比如如果第一次丢就得到1点，很明显需要继续下去
如果第一次丢得到6点，很明显没必要继续下去，因为后面再丢的两次最大也不会超过
六点
如果第一次丢得到5点，可能要考虑是不是博一下了。
扩展问题是把3次推广到N次。
*****
Leetcode大牛给的答案：
给个数学公式。这道题应该也可以用递推来解，但还没想清楚怎么弄。
Define:
n = number of trials.
m = max value of all trials.
P(m, n) = (1/6^n) * Sum(k = 1 .. n) C(n, k) * (m - 1)^(n - k)
Therefore,
Expected value of max value after n trials:
E = Sum(k = 1 .. 6) k * P(k, n)
E(Max when... 阅读全帖 |
|
n****r
发帖数: 120 | 5 最近这题是F家的高频题啊，我只知道基于Heap的算法，但又看好多童鞋被要求更快的
算法，好像基于quick select，还要推导递推公式？完全不了解啊，请高手指点。。。 |
|
i*********7
发帖数: 348 | 6 我觉得他说的推导公式应该是DP解的递推公式？=。= |
|
k***x
发帖数: 6799 | 7 没必要，我面过挺多码工和硅工的职位，其中以qualcomm偏research性质的职位问这类
问题最多，但基本也就是给你N个棍／球／绳，让你算一些概率和数学期望，基本的离
散模型和递推足够了（当然，这种问题也能出得很难，学过随机的都知道）。。。不知
道一些牛鼻的lab会不会问得更难 |
|
f*********m
发帖数: 726 | 8 来自主题: JobHunting版 - 贴个概率题 对于任何一个非1和非N的k, p[k]表示落到k点的概率，p[k]= p[k-1]/2+p[k+1]/2,这个
应该是递推公式。我觉得到1和N位置的概率可能需要用这个公式算converge后的概率。
请赐教。 |
|
t****a
发帖数: 1212 | 9 memoize是相当聪明而且省事的办法。它只算需要算的，复杂度不会比递推高。
建议楼主耐心下来把两种方法都做做看以后再下结论。 |
|
p********s
发帖数: 15 | 10 标题比较蹩脚，但是想不出特别好的表示方式，请见谅。
博士毕业，但是不想搞科研，觉得不是当faculty的料。很想到工业界工作，一些相关
公司的网站都去过了，觉得还是R&D的招工启事更靠谱。以前一直都是在学术界混，不
了解工业界是怎么运作的。经常看到大家说，有熟人推荐，就算不一定能拿到OFFER，
但是能获得面试的机会还是比较大的。前些天开会，碰到了已经在公司里工作了几年的
学姐，虽然我们不是同一个导师，但是我们做的课题都差不多，她读博士的时候我们经
常能见到面，有时她还解答我的问题。所以碰到她，就想和她聊聊转行工业界的事。但
是我真的不知道问什么问题，而且她也是问一句答一句，多的没有了。现在想问问过来
人，在这种场合都应该问什么方向的问题才能聊得起来呢？
还有一个问题就是，认识几个在公司或其他机构工作的朋友，想联系他们，看看以后有
什么工作机会。是不是在联系的时候附上个人简历，请他们帮忙留意工作机会就行了？
还是一定要告诉他们以后具体想做什么？因为有时候看到那些公司里确实没有新的
POSITION贴出来，觉得除了给朋友和同学递上我的简历，对以后具体想做什么实在没什
么可说的。
请有经历... 阅读全帖 |
|
n**********3
发帖数: 13 | 11 求好心人帮忙递个简历，头衔software engineer。 |
|
t****a
发帖数: 1212 | 12 来自主题: JobHunting版 - 一道电面题 首先，构造f(n)=n(n-1)/2结果的方法可以用递推产生：
f(1)=0
f(2)=1
..
f(n+1)=f(n)+n # 第n+1个点指向点1..n，所以加入n条边且不会产生环
其次，n(n-1)/2最大的原因是再加任何一条边进去都会形成a<=>b |
|
|
z****e
发帖数: 54598 | 14 先取一个n高的高度
然后把n顶端的那个1往右边走
比如5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1
总共有n行，每一行都不超过n个数，你要做的就是筛选掉不合格的组合
而所谓不合格的就是当前高度大于左边的高度的情况，比如
2+2+1之后的
2+1+2，最后一个2大于左边的1，干掉
如果合格的组合，就放到result list里面去
所以最后复杂度是n^2
递推公式别管了，用欧拉命名的公式和定理，可想而知了 |
|
|
e*******8
发帖数: 94 | 16 yes, you are right. 我知道为啥我开始认为不是了（我看成11211325了 -_-bbb）。
另外大家说的dp到底怎么个dp法啊？递推公式是？ |
|
|
|
D**********d
发帖数: 849 | 19 不是大牛，尝试回答。
关键是找到递推公式,
1. S[k] 的长度是 2^k - 1;
2. for k = 0, 1 时 单独考虑
3. for k > 1 时
if j == 2^k -1, 中间那个数 k
if j < 2^k -1, S[k-1][j];
if j > 2^k -1, S[k-1][j - 2^k]; |
|
l*n
发帖数: 529 | 20 有递推关系的不是直接的min值，而是i左右的b字符和a字符个数，所以好像没有办法针
对min值做dp。还是直接scan比较直观。
int minChange(String s) {
int[] countABackword = new int[s.length() + 1];
countABackword[s.length()] = 0;
for (int i = s.length() - 1; i >= 0; i--) {
char c = s.charAt(i);
countABackword[i] = c == 'a' ? countABackword[i + 1] + 1
: countABackword[i + 1];
}
int countBForward = 0;
int min = countABackword[0]; // case: all b
for (int i = 0; i < s.length(); i++) {
char c = s.char... 阅读全帖 |
|
A*****o
发帖数: 284 | 21 valid string这题蛮有意思的, 也许可以简化为二维的dp, 写个思路供大家拍砖:
dp[i][x] 表示了下标位置为i 以字符 x (x = A B C) 结尾的valid string个数
有递推式
dp[i]['A'] = (dp[i-1]['B'] - dp[i-2]['C']) + (dp[i-1]['C'] - dp[i-2]['B'])
+ dp[i-1]['A']
上式的原理不难理解,类似容斥原理吧
初始条件可以为
dp[0]['A'] = dp[0]['B'] = dp[0]['C'] = 1;
dp[1]['A'] = dp[1]['B'] = dp[1]['C'] = 3;
最终答案取 dp[n]['A'] + dp[n]['B'] + dp[n]['C']
实现上我觉得直接开 dp[N][255]数组好了,省得计算下标,面试实现比较容易
本质上可能跟楼上的牛牛解法是一样的, 不过确实没读懂....
Bless lz 成功:) |
|
h*******e
发帖数: 1377 | 22 先检查首位为一位的情况 a****** a a+ 1 a+ 2... check 唯一
之后 分情况 a != 9 ab***** b!= 9 这时候 如果 两位 ab ab+ 1 ab +
2
的搜 或者 ab ab 的搜 ab cdefgh ab **** ab**** 的情况 abcdefgh +1 在不
在下一个 如没有 则 abcdefgh abijklmnopqab**** abcdefgh abijklmnopq 的下一
个
a!= 9 ab**** b== 9 两位 ab (a+ 1) 0 唯一 或者
a b****ab**** ab**** 的搜 同上
a == 9 a b***** b!= 9 两位 多位 都 搜 同上
a == 9 b == 9 ab **** 两位 100 往下搜 否则 99* 同上
a == 9 b == 9 c == 9 三位 搜 1000 否则 搜 999
一直递推 q位都是 9 的情况
上面 数种情况有一种满足 ... 阅读全帖 |
|
t*****y
发帖数: 25 | 23 我的思路是这样，每一步需要计算两个变量,
f(i,j):从起点走到f(i,j)后能取得的能量和
g(i,j):在从走到f(i,j)的过程中，力量的最小值（整条旅途最艰难灰暗的时刻）
打个比方，哈利波特从(0,0)走到(i,j)的途径中，力量为10，-30，20，15，
那么 f(i,j) = 10 - 30 + 20 + 15 = 15, 而g(i,j) = -20.
这题的DP主要是求最后一个的g(i,j);如果g(i,j) < 0 那么输出为 -g(i,j), 反之输出
0.
DP的递推公式（要maximize g(i,j),选择一条不那么艰难的路哈）：
if g(i,j-1) <= g(i-1,j){
f(i,j) = f(i-1，j) + w(i,j)
g(i,j) = min(g(i-1,j),f(i,j)) // update旅途中最艰难时刻。
}else{
f(i,j) = f(i，j-1) + w(i,j)
g(i,j) = min(g(i,j-1),f(i,j))
} |
|
X*4
发帖数: 101 | 24 这个好复杂
其实可以优化armstrong12的方法
假设初设strength为0，然后找从左上到右下角的最大strength。
结果路径最大，那么中间每一步都最大。
所以 f(i,j) = max( f(i-1,j), f(i,j-1) ) + grid(i,j) .
初始值f(0,1)=grid(0,1), f(1,0)=grid(1,0)，从(0,0)算到(n-1,m-1).
这个方法的问题在于 能保证 任何时刻如果你的strength > 0
先看一维的情况
-5 1 -3
armstrong12方法给出的结果 f[n-1] = grid[n] + f[n-1], 从后往前
f = [-7, -2, -3], 有的地方strength < 0, 所以不对
改进, 增加一个数目m, m[i]表示进入grid[i]之前需要的最小strength
grid[2] = -3.
所以要想保证 每步strength > 0, 进入grid[2]之前， strength 至少 > 3
m[i] = 3,
f = [,,0]
m = [,,3]
grid[1] = 1, 根据公式
f = [,... 阅读全帖 |
|
|
s********o
发帖数: 3783 | 26 面试遇到的题目有非常多都是leetcode原题
比如我上面提到的2sum，跟leetcode一模一样
下面是一些题，不分先后，不分公司，全混在一起说
1，leetcode 2sum，用O(nlogn)和O(n)怎么做
2，leetcode 2sum，如果是小于不是等于怎么做，3sum怎么做，小于x怎么做
4sum怎么做，小于x怎么做，只输出符合条件（小于x）的总个数但是不需要输出具体数
怎么做，不但输出总个数还要输出具体答案怎么做，k sum 小于x怎么做，
k sum有没有多项式解？证明之
3，一个城市的地图（mxn矩阵），求从左上到右下一共有多少种可能的路线（只能向右
和向下）。先用程序写（利用通项公式递推），然后让我在白板上写close form公式
其实close form非常非常简单，只不过我没见过这道题，当场没有看出来。但是我硬挺
着从通项公式开始用矩阵分解去求解close form，最后在面试官的一点帮助下还是写出
来了公式，最后面试官表示我的数学基本功非常令他吃惊。（我心里想好歹也是学过几
门数学课的）。。。
4，还是数学题，求k个数的最大公约数。其实就几行代码，辗转相... 阅读全帖 |
|
s********o
发帖数: 3783 | 27 面试遇到的题目有非常多都是leetcode原题
比如我上面提到的2sum，跟leetcode一模一样，一模一样的我就不说了。
下面是一些题，不分先后，不分公司，全混在一起说
1，leetcode 2sum，用O(nlogn)和O(n)怎么做
2，leetcode 2sum，如果是小于不是等于怎么做，3sum怎么做，小于x怎么做
4sum怎么做，小于x怎么做，只输出符合条件（小于x）的总个数但是不需要输出具体数
怎么做，不但输出总个数还要输出具体答案怎么做，k sum 小于x怎么做，
k sum有没有多项式解？证明之
3，一个城市的地图（mxn矩阵），求从左上到右下一共有多少种可能的路线（只能向右
和向下）。先用程序写（利用通项公式递推），然后让我在白板上写close form公式
其实close form非常非常简单，只不过我没见过这道题，当场没有看出来。但是我硬挺
着从通项公式开始用矩阵分解去求解close form，最后在面试官的一点帮助下还是写出
来了公式，最后面试官表示我的数学基本功非常令他吃惊。（我心里想好歹也是学过几
门数学课的）。。。
4，还是数学题，求k个数的最大公约数... 阅读全帖 |
|
K*****k
发帖数: 430 | 28 年轻老美问了个机器人走网格的题，虽然没有做过，不过类似的题目看过一些，所以很
容易就用dp写了一个。
和下面这题是一个意思么？
一个城市的地图（mxn矩阵），求从左上到右下一共有多少种可能的路线（只能向右和
向下）。先用程序写（利用通项公式递推），然后让我在白板上写close form公式其实
close form非常非常简单，只不过我没见过这道题，当场没有看出来。但是我硬挺着从
通项公式开始用矩阵分解去求解close form，最后在面试官的一点帮助下还是写出来了
公式，最后面试官表示我的数学基本功非常令他吃惊。（我心里想好歹也是学过几门数
学课的）。。。 |
|
f******t
发帖数: 18 | 29 要算出最后结果好像挺复杂的~没理解错你的题目意思的话应该是要求
P(X
意思就是X两次时，Y大于两次的概率
X三次时，Y大于三次的概率 ... 最后全部加起来。
P(X=2) = 1/4, P(X=3) = 1/8
P(X=i) = P(第一次反面)*P(X=i-1) + P(第一次反面第二次正面)*P(X=i-2)
= 0.5*P(X = i-1) + 0.25*P(X=i-2);
有了初始值跟递推公式，用特征方程也好，用高中的数列知识也好，可以求出P(X=i)的
解析表达式；
同理求P(Y=j)。P(Y=j)比前面求X多了一项，算起来就更麻烦了~
最后求P(X
如果要算出最后结果，这个题好像挺变态，都不是整数值~如果只是列式子应该还好。
是哪里的面试题？求来源~ |
|
f******t
发帖数: 18 | 30 刚刚手算了一下P(Y=j)，多了一项确实不好求。mathematica不会用~
P(Y=j) = 0.5*P(Y=j-1)+0.25*P(Y=j-2)+0.125*P(Y=j-3)
不过如果是面试题，可能写出递推式用代码计算到某个精度的结果也是可以接受的，那
就不用纠结怎么求解析式了。 |
|
V*********r
发帖数: 666 | 31 能写出Bellman递推等式的就有optimal substructure，fib那个递归式就是
规避重复计算靠的是overlapping subproblems
substructure |
|
z******h
发帖数: 22 | 32 integer那题我给个暴力解法，用DP。
先把所有的数排序，从小到大依次处理。用OPT(m,n,i)表示：剩下i个数没处理，当前
第二，第三大的堆分别和为m和n的时候，能够得到的最小的差。这样OPT(m,n,i)的递推
公式不难得到。OPT(0，0，N)就是所需要的结果，N是integer的数量。
复杂度...O(M^2*N)，M是所有整数的和。
这个方法非常直接，但是应该是对的... |
|
s******c
发帖数: 1920 | 33 可以和1维那样类似的想法来2维dp
只是每隔子问题的解不能简单用dp_sol[i]来表示,
而是用一个长度n的 vector来index每个子问题的解dp_sol[i1,i2,...i_n]，
i1,i2,...i_n 描述了一个把2d矩阵切成两块的一个界面
i_k表示第k列上这个界面的坐标.
对每一个子问题, 从界面的边界开始尝试添加word
总共有n^n个子问题, 然后每个子问题的递推式可以在n^2时间搞定
(需要preprocess这个矩阵, 计算从每点出发可以cover那些word)
or
of |
|
l**********g
发帖数: 16 | 34 请教一道DP问题，大概是这样的：
有一个长为L的木料需要割开，切的位置在一个数组里A[0...N]，从一个地方切开的
cost是当前所切木料的长度。按不同的顺序切割，得到的total cost是不一样的，问怎
么切cost最
小。
我对题意的理解是，比如一个木料现在10米长，然后切的位置是2米处，4米处和7米处
（就是说arr A里A[0]是2，A[1]是4， A[2]是7）。那么比如先切2米，那么得到cost是
10（因为现在木料长度为10），然后切4米处，那么cost变成10 + 8(因为8是现在切的
时候木料的长度)。然后切7米处，cost变成10 + 8 + 6。那么这种切法总共的cost是24。
这题DP应该怎么写？递推关系是什么？谢谢！ |
|
l*********8
发帖数: 4642 | 35 来自主题: JobHunting版 - 问一道题目 S = "ababca", T="aa"这个例子
count[0][0], count[1][0]... count[5][0]的值是：
1 1 2 2 2 3
count[0][1], count[1][1]... count[5][1]的值是：
0 0 1 1 1 3
递推:(没写边界情况）
if (S[i] == T[j])
count[i][j] = count[i-1][j] + count[i-1][j-1];
else
count[i][j] = count[i-1][j];
|
|
|
e***l
发帖数: 710 | 37 我是说你的dp不对。递推只和上面和左边的位置有关, 跟斜上方的无关 |
|
c*******r
发帖数: 610 | 38 好吧，我也跟着你发我的面经，昨天面的，攒个RP。
周一面完了FB，接下来周二面领英，实在是累啊。我嘴巴都说干了，面试真是个苦力活
啊......
签了nda，不能透露具体题目细节。
进去，HR 带着绕一圈，介绍介绍吃饭啊，体育馆之类的
接下来高级HR， 接着扯淡。
正式面试第一轮， 烙印高级经理， behavior questions,问了一个什么key-value
store design，接着扯,首先那哥们迟到15分钟，然后谈了30分钟说我只期望我们聊天
聊30分钟，然后让我问他几个问题结束。
代码第一轮，亚裔男和同胞男，第一轮字符串替换，搞得有点急，跑测试发现有bug，
改好了以后亚裔大哥说不是很明白我的代码（我写c++，他用java），同胞说改完了应
该是对的（明显感到同胞在帮我，只怪我太菜）。 第二题实现哈希表，开始的扯淡加
上第一题花去了40分钟，15分钟让我实现哈希表，我就只写了一半，另一个函数亚裔大
哥说你说你准备写什么吧，不用写完了，估计到这我知道已经挂了.然后问了点多线程
的问题就结束了。
接下来午餐，同胞男，随便扯扯，餐厅里国人很多，烙印也很多
第二轮，美国男加同... 阅读全帖 |
|
s*******y
发帖数: 12 | 39
DP无非就是用空间换时间, 先试着找找有没有递推关系吧. |
|
h**********w
发帖数: 39 | 40
我只记得要二维数组从i到j bottom up，和那个递推公式了，他说good enough我就没
写code |
|
M*******a
发帖数: 1633 | 41 我一上来就直着排呢？
DP你写个递推式来看看，不要好像碰到个难题就说DP两个字母就算把问题解决了 |
|
|
l******e
发帖数: 54 | 43 就是普通的状态压缩 DP 或者递推
我都把算法描述出来了 看不懂只好丢给你个程序了
int mask = (1 << m) - 1;
f[0][0] = 1;
// 一行一行的来
for (int i = 0; i < n; ++i) {
FILL(f[(i + 1) & 1], 0);
// 枚举本行的铺法
for (int j = 0; j <= mask; ++j) {
// 上一行的铺法
for (int k = 0; k <= mask; ++k) {
// 检查相容
if (check(j, k, mask)) {
// 累加
f[(i + 1) & 1][j] += f[i & 1][k];
}
}
}
}
// 输出解
cout << f[n & 1][0] << endl;
bool check(int ... 阅读全帖 |
|
|
l******e
发帖数: 54 | 45 递推式不是在 code 里吗
f[(i + 1) & 1][j] += f[i & 1][k];
i, j, k 已经解释了的
这个我做空间优化了 你把 & 1 都忽略掉好了 |
|
|
c*******y
发帖数: 98 | 47 我没有明白楼上大牛们的思路，我画了个表
0 1 0 1 0 1 0 1
1 2 3 4 5 6 7 8
0 3 0 7 0 11 0 15
1 4 7 14 21 32 43 58
初始化第一行0 1 0 1 ...
第一列0 1 0 1...
递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
中间遇到(row+1)*(col+1)为奇数的，设为0。
不知道对不对。 |
|
c*******y
发帖数: 98 | 48 我没有明白楼上大牛们的思路，我画了个表
0 1 0 1 0 1 0 1
1 2 3 4 5 6 7 8
0 3 0 7 0 11 0 15
1 4 7 14 21 32 43 58
初始化第一行0 1 0 1 ...
第一列0 1 0 1...
递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
中间遇到(row+1)*(col+1)为奇数的，设为0。
不知道对不对。 |
|
c*******y
发帖数: 98 | 49 我没有明白楼上大牛们的思路，我画了个表
0 1 0 1 0 1 0 1
1 2 3 4 5 6 7 8
0 3 0 7 0 11 0 15
1 4 7 14 21 32 43 58
初始化第一行0 1 0 1 ...
第一列0 1 0 1...
递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
中间遇到(row+1)*(col+1)为奇数的，设为0。
不知道对不对。 |
|
l******e
发帖数: 54 | 50 楼上大牛介绍的是“刷表法” 由上一行刷下一行
我给出的例程其实是从当前行找上一行的“填表法” 可自行 Google 这两种方法的更
多信息
更喜欢刷表法 加 continue 是一个很大的优化 另外还需要改的是递推式里的 j 和 k
要换一下位置其他不变
f[(i + 1) & 1][k] += f[i & 1][j];
最后变成：
int mask = (1 << m) - 1;
f[0][0] = 1;
for (int i = 0; i < n; ++i) {
FILL(f[(i + 1) & 1], 0);
for (int j = 0; j <= mask; ++j) {
if (f[i & 1][j] == 0) continue;
for (int k = 0; k <= mask; ++k) {
if (check(j, k, mask)) {
f[(i + 1) & 1][k] += f[i & 1][j];
}
... 阅读全帖 |
|
