s*******n
发帖数: 452 | 1 原链接
http://www.mitbbs.com/article_t/JobHunting/31544893.html
http://www.mitbbs.com/article_t1/JobHunting/31540541_0_1.html
我理解各位大侠的讨论结果是这样的，大家看看对不对：
after sorting, if we select one number, the array is
divided into 2 parts, and consider taking numbers from each part. So, 从k-1
到 k 的递推公式：
f(k,head) = max_{
for i in (head+1, end-k) {
min{dis(head,i), f(k-1,i,end)}
}
} |
|
h**6
发帖数: 4160 | 2 来自主题: JobHunting版 - 一道面试题 递推方法如下：
假设不取最后一位，有f(N-1, x)种
假设取最后一位，有f(N-2, x-1)种
总和是f(N, x) = f(N-1, x)+f(N-2, x-1)
数学方法如下：
假设从1到N中取出的x个数由小到大分别是n1, n2, ..., nx
设m1=n1, m2=n2-1, m3=n3-2, ..., mx=nx-(x-1)
则mx<=N-x+1
1到N中任取x不相邻的数与1到N-x+1任取x常规组合数一一对应
即f(N, x) = c(N-x+1, x) |
|
a***9
发帖数: 364 | 3 估计是面试者想要的解答，从递推公式的角度想很简洁，
如果能想到，程序还是可能在规定时间内写出来的，很牛！ |
|
c********4
发帖数: 18 | 4 通俗的描述是：给你N种硬币，每种硬币的面额D[i]也给你。规定每种硬币可以取任意
个（可以是0个），问
最少用几枚硬币可以组成面额Y。这个题目可以用动态规划，设一个数组ans[i][j],表
示用0到i种硬
币，拼出j面额所需要的最小数量。然后递推式为：
ans[i][j] = Min {n + ans[i-1][j-n*D[i]]} (0 <= n <= j/D[i])
意思是：对于第i种硬币，遍历可以取的个数n，然后看剩下的面额j-n*D[i]最少可以用
多少枚0到(i-
1)种硬币拼出来。 |
|
d****j
发帖数: 293 | 5 哈哈. 我也在面试中被问过这个问题，当时没有回答出来，已经没有时间了
简单的说，根据给n次机会的期望值E(n)来确定当前是否停止。
用递推的思想，把投掷的n次机会分成第一次和后(n-1)次。
如果第一次的值大于E(n-1)，那么马上停止，否则的话，用(n-1)的投掷策略。
假定第n次投掷骰子的值为 v_n，
用 avg(1:v_n)表示1,2,...,v_n的期望/均值，
avg(v_n:6)表示v_n, v_n+1,...,6的期望/均值，
那么可以得出这样的迭代:
E(1) = 3.5 (=1/6 * 1 + 1/6 *2 ....+ 1/6 * 6)
E(2) = P(v_1E(1))* avg(v_1:6)
= 1/2 * 3.5 + 1/2 * avg(4,5,6) = 4.25
E(3) = P(v_2E(2)) * avg(5,6)
= 4/6 * 4.25 + 2/6 * 5.5
....
E(n) = P( v_(n-1) < E(n-1) ) * |
|
A*********r
发帖数: 564 | 6 对，我刚开始也试了二进制和四进制，发现都比１０进制的递推公式简单一些，而且套
不起来。。 |
|
e**********6
发帖数: 78 | 7
answer
即便用stl容器，他也要靠一个递推的过程（我是指递归的过程，不一定需要递归函数
来实现）来实现，
不然用什么呢？
对于stl里面的permutation，它给出的定义说：A permutation is each one of the N
!
possible arrangements the elements can take (where N is the number of
elements in the range). 我感觉他会assume已经给出的是一个set。。但是你说得对
，这是一
个陷阱，应该提前问好是否会有重复的字符出现。。唉又被阿三给阴了。。 |
|
j***y
发帖数: 2074 | 8 又看了一会儿，似乎有些明白，的确是巧妙的递推。但有些疑问：
1. char result[PHONE_NUMBER_LENGTH];应改为char result[PHONE_NUMBER_LENGTH+1]？
2. void printTelephoneWords( int phoneNum[] ){
char result[PHONE_NUMBER_LENGTH];
doPrintTelephoneWords( phoneNum, 0, result );
}似乎应该改为：
void printTelephoneWords( int phoneNum[] ){
char result[PHONE_NUMBER_LENGTH+1]; /* +1 for the string-ending 0x0
character */
for (int i = 0; i < 3; i++) {
doPrintTelephoneWords( phoneNum, 0, result );
}
}
否则出来的似乎只是da、db、dc而已。
我不太懂算法和... 阅读全帖 |
|
g***s
发帖数: 3811 | 9 你这个可以。不过，更简单点，可以f(x,y,0)=true
基本上，你写出递推公式，面试官就知道你会了。 |
|
g***s
发帖数: 3811 | 10 我给的是递推公式，他是问DP的初始值如何设。f(x,y,0)=true |
|
g***s
发帖数: 3811 | 11 解释一下我的算法：
所有两个节点，如果以它为根的树相同，就mark成相同的元素（或数字）
所有两个节点，如果它们的左子树和右子树都被mark成相同了，那么这两个节点也认为
相同。
例如，所有的叶节点，都相同。我们mark成0
然后，看depth=1的节点。如果（left,right)=(0，NULL)的节点mark成1 （NULL，0）
的mark成2
再看depth=3的。。。一直递推到root
有点像DP。
改进的算法，就是不用0,1,2,3..来mark，而是用满足的第一个点来mark。这样，第二
个相同的点就可以和第一个点构成相同子树。 |
|
h*****g
发帖数: 312 | 12 用1*2的瓷砖覆盖8*8的地板，有多少种方式呢？如果是N*M的地板呢?
用递归咋解呢？ |
|
c****p
发帖数: 6474 | 13 铺上一块砖之后，未被覆盖的地面的摆法。
递归终止条件是最后刚好摆满最后一块砖或者无解。
个人愚见。 |
|
d*******l
发帖数: 338 | 14 来自主题: JobHunting版 - 问个面试题 只能想到搜索的办法，好像找不到什么递推或者是能简化问题的规律 |
|
j*******r
发帖数: 52 | 15 答案是正确的，代码不好懂啊，x[i][j]代表0到10^i-1中各个位之和大于j的个数？这
个递推用得很巧妙啊。。 |
|
j**l
发帖数: 2911 | 16 有个种子，然后有个递推公式产生伪随机数的序列。
如果种子相同，则序列完全相同，所以一般要先调用srand(time(NULL)), 来使得种子
不同。 |
|
c*********t
发帖数: 2921 | 17 如果不先调用srand()去设个seed的话，直接调用rand()返回的是什么值？
是不是根据上次的seed，和有那个递推公式产生的一个值？
如果不设seed,连续两次调用rand()，得到两个不同的值？还是相同的两个值？
谢谢！ |
|
|
|
|
k******1
发帖数: 16 | 21 第一部分我也只给了递推的答案，不知道有没有closed form solution.
第二部分我也是每次bet一半，从面试官反应来看是对的，我也想知道怎么证明这是最
优的。 |
|
S**I
发帖数: 15689 | 22 ☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 13:45:24 2012, 美东) 提到:
稍微扩展了一下。
Boggle game。从一个字符开始找邻居字符然后继续找，形成一个word。条件是，形成
了word之后要继续找，因为可能有更长的word。一旦用了一个字符以后，就不可以重复
使用了。
返回可以找到最多word情况的所有word。
更新一下：可以同时从不同的位置开始找，不一定只从一个字符开始。
☆─────────────────────────────────────☆
autumnworm (虫子，秋天的) 于 (Tue Jan 17 13:46:32 2012, 美东) 提到:
看起来好像是基本的背包问题吧。
☆─────────────────────────────────────☆
mark (花生，微爷远爷的爸爸) 于 (Tue Jan 17 14:08:07 2012, 美东) 提到:
☆───────────────────... 阅读全帖 |
|
S**I
发帖数: 15689 | 23 ☆─────────────────────────────────────☆
sugarbear (sugarbear) 于 (Thu Apr 7 00:42:48 2011, 美东) 提到:
找 二叉树 两个最大的相同子树
没答上来。
见了四个，被拒了。 第二个是manager，后来主动写信跟我联系，说把我推荐给industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求祝福！
☆─────────────────────────────────────☆
boohockey (Pursuit of Dreams!) 于 (Thu Apr 7 10:27:03 2011, 美东) 提到:
bless
这道题有没有正解
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！
☆─────────────────────────────────────☆
grass (美丽人生) 于 (Thu Apr... 阅读全帖 |
|
i******r
发帖数: 793 | 24 Fibonacci直接递推就是O(n)了
其实可以做到O(lgn)，如果你知道公式甚至是O(1)
1) |
|
k***t
发帖数: 276 | 25 第一个，为何不直接写递推或cached/DP的代码?
第二个，assume a heap was used to do N-way merge。
第三个，准确的讲，kill cmd is used to send signal. By default, SIGTERM is
sent. 9 is SIGKILL, 7 is SIGBUS.
1) |
|
b****e
发帖数: 35 | 26 发现一个position比较匹配我的背景
哪位好心的兄弟姐妹能帮忙递个简历么？
多谢! |
|
r*****6
发帖数: 58 | 27 发现一个Andover, MA 的position比较匹配我的背景
哪位好心的兄弟姐妹能帮忙递个简历么？有经验和身份
多谢! |
|
O******i
发帖数: 269 | 28 DP就是利用一维或者二维的数组，找递推关系式，也就是状态转移方程。常数空间和三
维以上空间在实际面试中不多见。
难就难在写出递归方程。
不用说背包问题，就连经典的扔鸡蛋题(虽然有巧妙的小学生算法, 1+2+...+14恰好刚
大于100)本质也是DP。 |
|
l********n
发帖数: 49 | 29 个人觉得DP学习看算法导论很好~ 特别注意他的那几步求解模式，然后比较深入的理解
他的证明。然后多做题熟悉那三步曲。
我自己的算法一般，但是DP貌似不错，基本上面试官一出DP题，就能很快想到DP解。我
觉得当时老师说的一点很重要，一定敢于去下第一刀划分子问题，不要怕。然后就是写
出递推式，设计memo结构，保留搜索的trace，然后自底向上coding完事。
个人拙见。。。 |
|
s******n
发帖数: 3946 | 30 这个题目能用DP的关键是每个数都大于等于0：
总和为sum
A(i,Y) 表示前i项选任意个之和小于Y且与Y最接近的差。
所以我们要求：A(N, sum/2)
递推:
A(i, Y) = min(A(i-1, Y), A(i-1, Y-a[i]))
代码
============================================
dp[N][SUM/2];
for (int i=1; i
for (int j=0; j
dp[i][j]=MAX_INT;
for (int i=0; i
int calculate(int i, int sum)
{
if (dp[i,sum]!=MAX_INT) return dp[i,sum];
assert(i>0);
int solution1 = calculate(i-1, sum);
int solution2 = MAX_INT;
if (Y>a[i]) solution2 = calculate(i... 阅读全帖 |
|
|
g*********e
发帖数: 14401 | 32 偶是半路出家的 懂的很少
当时上算法课，就觉得对DP特有感觉，就像解中学数学的题目那种感觉。
DP主要是寻找递推公式，看到题目，凭着经验多试试一般都会有些思路的。 |
|
g*********e
发帖数: 14401 | 33 没有刻意练过，觉得DP的思路其实挺清晰的，就是解决小问题，然后找递推。不像一些
O(n)复杂度的问题那么tricky。DP对复杂度的要求也很低，通常是polinomial的。
另外，我看的书是algorithm design by Jon Kleinberg, Cornell. |
|
h****e
发帖数: 928 | 34 但是你怎么找出左右子树的分隔点，我觉得这样得先扫描字符串一次，
平均扫描N/2次。找到分隔点以后，左右再分开做，递推公式是:
T(N) = N/2 + 2T(N/2)
复杂度就是O(NlogN)了。 |
|
g*****g
发帖数: 34805 | 35 楼主很厚道，这题不算难，又没要求多高效率，就是考coding，我来写。
void spacing(String prefix, String sen, HashMap dict) {
if(dict.get(sen)!=null) {
print((prefix + " " + sen).trim());
}
if(sen.length() <= 1) return;
for(int i = 1; i < sen.length(); i++) {
String word = sen.substring(0, i);
if(dict.get(word)!=null) {
spaceSentence(prefix + " " + word, sen.substring(i);
}
}
}
void spaceSentence(String sentence, HashMap dict) {
if(sentence =... 阅读全帖 |
|
g*****g
发帖数: 34805 | 36 楼主很厚道，这题不算难，又没要求多高效率，就是考coding，我来写。
void spacing(String prefix, String sen, HashMap dict) {
if(dict.get(sen)!=null) {
print((prefix + " " + sen).trim());
}
if(sen.length() <= 1) return;
for(int i = 1; i < sen.length(); i++) {
String word = sen.substring(0, i);
if(dict.get(word)!=null) {
spaceSentence(prefix + " " + word, sen.substring(i);
}
}
}
void spaceSentence(String sentence, HashMap dict) {
if(sentence =... 阅读全帖 |
|
p********s
发帖数: 37 | 37 有个非常浪费空间的递推，大牛们看看对不：
设cmb(n,m)为从n个里面选m个并按要求的顺序解集合，其中每个解用一个长度n的
bitset，其中m个1表示元素是否出现，比如
(3,2) 011 110 101
(4,2) 0011 0110 0101 1100 1010 1001
有
cmb(n,n) = n个1
cmb(n,0) = n个0
设[cmb(n,m)+'a']为给所有cmb(n,m)末尾加个a(1或0),
设~[x]为[x]的倒序,有
cmb(n,m) = [cmb(n-1,m)+'0'] + ~[cmb(n-1,m-1)+'1']
代码如下
vector all[50][50];
void init() {
for(int i = 1; i < 20; i++) {
all[i][0].push_back(0);
all[i][i].push_back((1 << i) - 1);
for(int j = 1; j < i; j++) {
for(int k = 0; ... 阅读全帖 |
|
A****e
发帖数: 310 | 38 谢谢lz分享～
快排是O(nlgn),因为T(n)=2T(n/2) + O(n),但是用它找top k的时候，每次扔掉一半，
只需要考虑一半的数，递推关系是T(n)=T(n/2)+O(n)
复杂度就是O(n)了。 |
|
f*********m
发帖数: 726 | 39 据说所有recursion都有对应的iteration,但有的不好转变。
说是可以用stack模拟递推过程，但有很多细节要结合具体的题，这就不好搞了。 |
|
h****n
发帖数: 1093 | 40 来自主题: JobHunting版 - 亚麻电面！ pat pat，硬币找零用DP来做
递推式：
设 钱币种类 T1 。。。Tm
f(n) = min(f(n-Ti)+1)；
dog |
|
l*********8
发帖数: 4642 | 41 编程序算？还是写出数学解析表达式（不是递推式）？ |
|
s*********l
发帖数: 103 | 42 有解析表达式最好，能给出递推公式就足够好，用程序模拟也可以。 |
|
p*g
发帖数: 141 | 43 1.如果往左/右的概率是 p/1-p
这个程序应该怎么写?
2. 总觉得这种recursive的不如递推的好
3. 觉得那两行
probabilty(n - 1, x - 1, cnt, totalCnt);
probabilty(n - 1, x + 1, cnt, totalCnt);
不需要乘 0.5么
多谢 |
|
p*g
发帖数: 141 | 44 1.如果往左/右的概率是 p/1-p
这个程序应该怎么写?
2. 总觉得这种recursive的不如递推的好
3. 觉得那两行
probabilty(n - 1, x - 1, cnt, totalCnt);
probabilty(n - 1, x + 1, cnt, totalCnt);
不需要乘 0.5么
多谢 |
|
K*****k
发帖数: 430 | 45 二爷的方法看不懂，郁闷。
能否把思路，主要是动态规划的递推方程给详细讲解一下？
动态规划估计不多刷题很难提高，另外也要有很强的bottom up的题感才行。 |
|
l*******b
发帖数: 2586 | 46 res * res <= x < (res+1) * (res+1)
满足这个条件的 res 就好啦，开始我也没想到，哈哈
牛顿法是这个递推式 y = (x + x/y) / 2，得用浮点数逼近，然后初值得选好，不然得
走10几次。
没想出什么好的选取办法来，(x >> 5) + 16这类的貌似太糙了 |
|
|
i**********e
发帖数: 1145 | 48 给个数学公式。这道题应该也可以用递推来解，但还没想清楚怎么弄。
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 Trials = 1) = 3.5
E(Max when Trials = 2) = 4.4722
E(Max when Trials = 3) = 4.9583
E(Max when Trials = 4) = 5.2446
所以，只要看期望值，就知道需不需要再扔筛子了。 |
|
i**********e
发帖数: 1145 | 49 给个数学公式。这道题应该也可以用递推来解，但还没想清楚怎么弄。
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 Trials = 1) = 3.5
E(Max when Trials = 2) = 4.4722
E(Max when Trials = 3) = 4.9583
E(Max when Trials = 4) = 5.2446
所以，只要看期望值，就知道需不需要再扔筛子了。 |
|
k*******r
发帖数: 355 | 50 为什么不能简单的按 p[k][n]=p[k][n-1]+(1-p[k][n-1])*(6-k)/6 来递推?
这里p[k][n]表示当前点数为k，未来最大允许n次抛骰子的情况下，得到最终点数大于k
的概率。 |
|
