w*******2
发帖数: 8 | 1 尾递归和普通递归的区别就是其栈的空间大小是不随着函数的调用而增长的，所以不会
有stack overflow的问题，通过将所需信息直接通过参数传进调用的子函数，这样的过
程很迭代其实没什么区别，对于一些语言，编译器就直接会把尾递归转化成迭代.
对于简单的递归转化成尾递归，可以通过传递参数的方法来保存之前的状态，但是对于
一些多次调用递归，简单的增加传入参数就不行了，可以使用continuation-passing
style(CPS)来实现，此方法仅适用在函数式编程
就执行效率来说，memorization并不迭代差（不考虑空间复杂度的话） |
|
t****a
发帖数: 1212 | 2 我不会把任意的递归问题转换成尾递归。比如，
1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
自变量为一维的问题。
2. 程序依赖多个子递归问题，应该怎么办？
3. 多个子函数相互嵌套递归怎么办？
如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
我只会用memorize function。效率跟iteration还是差一大截。 |
|
y*******g
发帖数: 6599 | 3 有些就是不能转
不过你确定memorize比iteration差一大截？ 举个例子？ |
|
w*******2
发帖数: 8 | 4 尾递归和普通递归的区别就是其栈的空间大小是不随着函数的调用而增长的，所以不会
有stack overflow的问题，通过将所需信息直接通过参数传进调用的子函数，这样的过
程很迭代其实没什么区别，对于一些语言，编译器就直接会把尾递归转化成迭代.
对于简单的递归转化成尾递归，可以通过传递参数的方法来保存之前的状态，但是对于
一些多次调用递归，简单的增加传入参数就不行了，可以使用continuation-passing
style(CPS)来实现，此方法仅适用在函数式编程
就执行效率来说，memorization并不迭代差（不考虑空间复杂度的话） |
|
l*******b
发帖数: 2586 | 5 嗯，functional里面的lazy evaluation sequence不知道怎么实现的．这个和
memorization有点像吧，像fibonacci数列那样的．不知道是bottom up的实现还是top
down的实现，bottom up貌似不需要stack 调用，top down就是递归了，当然这个例子
两个是等价的可以互相转化，可以写成尾递归的形式．一般的就不知道了．看看那位大
牛讲讲 |
|
s***0
发帖数: 117 | 6 Did it too quick, no one expects you to get through the first 2 in a phone
interview.
Sounds like you memorized all the answers. |
|
|
l***i
发帖数: 1309 | 8 1. DFS, if a component can reach border, no change needed
2. try each prefix from length=1 to n, if prefix is palindrome, solve the
rest recursively. You need to use either recursion+memorization or bottom-up
dp for this. |
|
P*******y
发帖数: 168 | 9 电面一面：
给一堆F的用户，以及朋友关系，朋友之间的关系是双向的。问能否将朋友的关系图分
成两个partition。使得任何有直接朋友关系的两个人必须处在不同的partition里。
电面二面：
leetcode的手机键盘给数字，求各种字母组合的题。但是让给出recursive和iterative
方法。recursive很简单，iterative之前没写过，比较难想，当时卡了一会儿。后来写
出来了。
onsite五轮，每轮45分钟：
第一轮coding为主：先聊了下他的项目和我的research，几分钟的样子，然后写了个二
进制字符串相加的。另外一题是一个直角坐标系，上面和N个点，找出离原点最近的k个
点，就是top k问题
第二轮系统设计：让设计分布式的large scale的producer和consumer问题。就是有一
堆机器是producer，一堆机器是consumer。后来顺便写了一道coding题，范围变成是单
机的producer和consumer，实现produce和consume函数，其实就是相当于fix size的
cache的add和pop问题，不用考虑多线程... 阅读全帖 |
|
b*****a
发帖数: 70 | 10 I like the authors' point that you should not memorize those problems;
instead, practicing hard problems makes you feel much more confident when
facing
interviews. |
|
w******j
发帖数: 185 | 11 来自主题: JobHunting版 - f 的面经 最后一道就是leetcode上的Wildcard Matching吗？
和regular expression matching 差不多吧，用backtracking recursion +
memorization 当然也可以用dp.... |
|
c******a
发帖数: 789 | 12 DP优于递归，考虑到递归calculate the same things over and over again.
也可以递归＋memorize，跟dp就一个道理了。
我要是面试官，我两种都接受。前提是你能说清楚哪个好，为啥，怎么优化。 |
|
r**h
发帖数: 1288 | 13 从来没想过DP的解法，待会儿试试看~
递归+memorize的原理是什么呢？递归的时候带上一个表示状态的二维矩阵，查询子问
题的时候先查询解有没有被计算过？ |
|
f*******b
发帖数: 520 | 14 总体来说时间复杂度应该是：
Sort:O（nlogn)+找P:O(n)+DP:O(n)=O(nlogn)
DP代码：用recursive做的bottom down，虽然是直接用数组的值，但不知道这个算不算
memorized了？？就是2爷说的cache
int CalMax(Interval[] inputs,int end, int[] P)
{
if(end<0)
return 0;
return Math.max(CalMax(inputs,P[end],P)+inputs[end].weight,
CalMax(inputs,--end,P) );
} |
|
f*******b
发帖数: 520 | 15 总体来说时间复杂度应该是：
Sort:O（nlogn)+找P:O(n)+DP:O(n)=O(nlogn)
DP代码：用recursive做的bottom down，虽然是直接用数组的值，但不知道这个算不算
memorized了？？就是2爷说的cache
int CalMax(Interval[] inputs,int end, int[] P)
{
if(end<0)
return 0;
return Math.max(CalMax(inputs,P[end],P)+inputs[end].weight,
CalMax(inputs,--end,P) );
} |
|
g**G
发帖数: 767 | 16 or use a hashmap to memorize the intermediate results |
|
m*****n
发帖数: 204 | 17 DP, 15 min using top-down approach (memorization) |
|
s*w
发帖数: 729 | 18 codeeval.com 上的一个题
给n个东西，每个东西有重量和价值，要求在重量小于给定值的时候，尽量价值大
在重量是浮点数的情况下，怎么做 bottomup 的 dp table?
我现在的解是 recursion, 而且没 memorization, 因为不知道怎么存这个 table.
帖下代码，请指教一下
#include
#include
#include
#include
#include
#include
using namespace std;
class Solution {
int weightLimit;
int n;
vector weights;
vector costs;
public:
Solution(const string &line) {
istringstream iss(line);
iss >> weightLimit;
int in... 阅读全帖 |
|
j*********6
发帖数: 407 | 19 求高人指点 有什么好办法？
用了memorized 但还是不行~
Time Limit Exceeded
Last executed input: "
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
, ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","
aaaaaaaaaa"] |
|
|
y***n
发帖数: 1594 | 21 should by fine if you pass by reference |
|
p*****3
发帖数: 488 | 22
signature是
，
全局变量不大好吧，我的话一般会用一个wrapper函数和一个helper函数，helper传在
wrapper里创建的map |
|
|
l*n
发帖数: 529 | 24 // wrapper
public boolean doable(String s) {
int[] memo=new int[s.length()+1];
Arrays.fill(memo, -1);
return doable(s, 0, memo)==1;
}
// helper
int doable(String s, int i, int[] memo) {
......
if (memo[i+1]==-1) memo[i+1] = doable(s, i+1, memo);
......
} |
|
|
|
b*****a
发帖数: 70 | 27 I think you mean recursion with memorization (i.e., DP). I probably won't
call it DP, however, since they all use recursion, its feeling is similar
and I agree what you said :) |
|
p*****2
发帖数: 21240 | 28
key。
昨天发现原来clojure本身就支持memorize呀。这样的话，用clojure做dp不是太爽了，
cache都不用自己搞了。
dfs＋cache dp王道呀。 |
|
k*********6
发帖数: 738 | 29 是的，greedy一旦made choice,就不再多考虑了，以后都base on这个choice. sub
problem 的其他借解都扔掉了。 通过local optimal try to 找到global optimal，可
以是近似的最优解。当然有的书说一定要保证greedy能找到最优解。但实际上有时候可
以根据具体问题采用greedy simplify problem.
DP是不放弃所有的choice, 保持所有sub problem 的solutions都考虑，最后因该一定
会找到最优解。所以DB经常有sub problem大量的重复计算，搞个大表memorize一下去
避免重复计算。 |
|
p*****2
发帖数: 21240 | 30 发现更高一层的境界是语言本身支持memorize，这样自己只是需要写一般的程序，语言
自动就做cache了。 |
|
p*****2
发帖数: 21240 | 31 发现更高一层的境界是语言本身支持memorize，这样自己只是需要写一般的程序，语言
自动就做cache了。 |
|
d**********x
发帖数: 4083 | 32 1. memorization and search branch trimming. try to solve this: http://poj.org/problem?id=3076
2. bit mask for ASCII and hashtable for complex encodings.
subbox |
|
n****e
发帖数: 678 | 33 请问：
第一题sudoku puzzle, 怎么用memorization 进行优化，只会backtracing的方法。
第二题，一直不清楚c/c++ bit mask 用什么STL比较好，ASCII有256个characters。用
Int[]比较费，可是也没有32Byte的data structure. |
|
s********u
发帖数: 1109 | 34 Of course it can be done by DP.Or, actually it;s slightly better to do with
recursion + memorization for some cases.
for example: "leetleet", for bottom-up dp, you need to judge "leet" twice |
|
d***n
发帖数: 832 | 35 DP跟recursion没有冲突呀
DP一般有两种实现方法
1.top down memorization用的就是recursion
2.bottom up tabulation用的loop |
|
w**t
发帖数: 893 | 36 greedy for sure does not work.
eg. step 0 -- 1, 3
step 1 -- 100
step 3 -- 1
first to 1 is better than to 3
this is a dp with memorization. should be space o(n), time o(n2), the best I
can come up. |
|
r******j
发帖数: 92 | 37 关于dp的top down和bottom up。一般我都是先从top down的recursion开始考虑，然后
找出重复计算的地方，如果用memorization的话，直接存一下，以后再查就好了。如果
这样考虑的时候，我们存的一般都是尾巴上的结果，然后一点一点的递归到头，就有结
果了。可是我们bottom up的时候是从头一点一点的到尾巴。感觉这是两种不同的思路
啊。也就是说，是不是所有能用top down解的dp问题都能用bottom up解呢？我发现我
做的题好像都是呢。如果是的话，为什么呢？ |
|
l*******g
发帖数: 82 | 38 dp是啥的缩写？
关于dp的top down和bottom up。一般我都是先从top down的recursion开始考虑，然后
找出重复计算的地方，如果用memorization的话，直接存一........ |
|
A*********c
发帖数: 430 | 39 不是大牛，表达能力有限，试着解释一下。
我估计你不懂的是这两行：
12 f[j] = max(f[j], g[j-1]) + diff;
13 g[j] = max(g[j], f[j]);
你看懂了算法，就按着算法说。
该算算法的核心是这个：f[i][j] = max(g[j-1] + a[i], f[i-1][j] + a[i]).
第12行就是算这个，其中diff就是a[i].
第13行做得就是“memorize the optimal j-1segments”
算法仅仅用了常数空间的原因是因为f仅仅依赖于前一个f，而不是前面所有的f值。而g
仅仅依赖于f和当前的g。
完了。 |
|
t********e
发帖数: 344 | 40 Two pointer traversal + memorization. 这类题目是不是都差不多这样 |
|
t********e
发帖数: 344 | 41 Two pointer traversal + memorization. 这类题目是不是都差不多这样 |
|
t********n
发帖数: 611 | 42 楼主明显来黑文科大妈的。
作为自学两年的文科大妈，从来没背过半行代码，谁都知道那明显是玩笑。我上的培训
班，老师第一天就说，如果你memorize anything, you are on the wrong track.
leetcode上面的题，随便改一点，解法就完全不一样了。我做第一遍时，如果实在没思
路，最多偷看一眼是应该用dp还是dfs或者其他方法解，然后朝那个思路想。这已经是
cheat了，没人在面试时会告诉你用dp做这道题。还有谁都知道，如果做不出来，看别
人的思路，自己写代码，远远比直接看代码搞懂思路容易的多。当然这也是cheat，因
为面试时你得自己找思路。
我不相信任何写过10行代码的人会相信背代码可以做题。除非面试官智商为0. 而且碰
到原题的几率比买彩票还小。
我碰到一个warm up的题是原题，然后下一道是从原题引申出来的，我用dp解的。一开
始我就纳闷怎么出那么简单的题嘛，原来陷阱在后面。 |
|
x****k
发帖数: 34 | 43 对，worst case是指数的。用memorize就可以解决了。 |
|
p*****p
发帖数: 379 | 44 需要memorization，不然复杂度似乎是O(n!)级的（不是很确定这个怎么算）
result |
|
l***i
发帖数: 1309 | 45 Let dp(k, n) be the probability that you get sum = k with n rolls
then you answer is sum_{n=0 to 2014} dp(2014, n) because every roll is at
least 1 so you must finish after 2014 rolls.
dp(k, n) = 1/6 * ( dp(k-1, n-1) + dp(k-2, n-1) + ... + dp(k-6, n-1) )
because your n-th roll can be 1, 2, ... or 6
dp(k, 0) = 0 for any k != 0 and dp(0,0) = 1
For this problem, k is at most 2014, and n is at most 2014, so just
implement this simple recursion use memorization or dp would give you the
solution, of c... 阅读全帖 |
|
M******9
发帖数: 10 | 46 基本都面完了，前一段刚注册了一个帐号，上来发文，大概说下自己的经历，抛个砖头
，希望对大家有用，也祝愿大家都能找到满意的工作。有NDA就不说onsite具体题目了
，感觉也没什么必要说，会大概说说面到的知识点，可能比较乱，大家将就着看。
基本情况：fresh cs phd, 找的都是SE的工作，为啥不找教职或者research lab这里就
不讨论了. FLGT(2 offers, 1家withdraw, 1家简历被刷), startups UPASD(2 offers,
2家电面挂，1家没申请)
pros：背景还不错，都是top school, GPA高。。(fresh貌似公司还是会稍微看看这个)
cons: 没有intern经验是硬伤，PhD期间，上完课后代码写得不多
package还没开始谈，initial offer都差不多200k+的样子，大公司hr明确表示等我都
面完了可以谈, startup都是late stage, 股票都是十万分之5-10, 感觉不好谈。LD目
前在一家大公司，说其实先去大公司几年也不错，比较稳定，貌似股票refresh也可能
不错，work/life... 阅读全帖 |
|
M******9
发帖数: 10 | 47 基本都面完了，前一段刚注册了一个帐号，上来发文，大概说下自己的经历，抛个砖头
，希望对大家有用，也祝愿大家都能找到满意的工作。有NDA就不说onsite具体题目了
，感觉也没什么必要说，会大概说说面到的知识点，可能比较乱，大家将就着看。
基本情况：fresh cs phd, 找的都是SE的工作，为啥不找教职或者research lab这里就
不讨论了. FLGT(2 offers, 1家withdraw, 1家简历被刷), startups UPASD(2 offers,
2家电面挂，1家没申请)
pros：背景还不错，都是top school, GPA高。。(fresh貌似公司还是会稍微看看这个)
cons: 没有intern经验是硬伤，PhD期间，上完课后代码写得不多
package还没开始谈，initial offer都差不多200k+的样子，大公司hr明确表示等我都
面完了可以谈, startup感觉不好谈。LD目前在一家大公司，说其实先去大公司几年也
不错，比较稳定，貌似股票refresh也可能不错，work/life balance比较好。我自己是
想去startup, 但... 阅读全帖 |
|
w*******i
发帖数: 186 | 48 不允许用extra space 这个比较狠啊 否定了用dp或者memorization。
感觉如果增加时间复杂度的话可以是不是可以允许iterator的copy呢？这里copy一个
iterator感觉可以不断调用next直到新的iterator的val的地址与另一个旧的相等。这
样即使iterator不能回走也可以完成递归。 |
|
b*****n
发帖数: 618 | 49 recursion + memorization就行了吧，最简单直观的方法。
排序有什么太大的必要么，空间复杂度也没降。
对每个格子，看它四个方向的邻居组成的最长递增序列是多长，如果之前已经算过了就
不用再算了，如果没算过就recursion算一下 |
|
s***k
发帖数: 50 | 50 是啊，DFS + 保存中间状态 ==> memorization, 典型DP。 |
|
