Google LA onsite

round 5：leetcode House Robber III
开始给了个recursive的算法，面试官不太满意，一再提示下写了个dp的

recursion的也是dp吧我记得，好像是个后序遍历，每个节点向父节点返回两个值；楼主的dp咋写的

laiguojiuhao 发表于 2017-1-29 03:56
recursion的也是dp吧我记得，好像是个后序遍历，每个节点向父节点返回两个值；楼主的dp咋写的

是的我也觉得，这是网上最通用的解法

求问楼主，是因为楼主选了以后工作地点在LA呢还是因为楼主现在人在LA，所以才在LA面的？

OracleDesire 发表于 2017-1-29 11:47
求问楼主，是因为楼主选了以后工作地点在LA呢还是因为楼主现在人在LA，所以才在LA面的？

同问，google LA office是做啥的？ 不太熟悉

laiguojiuhao 发表于 2017-1-29 03:56
recursion的也是dp吧我记得，好像是个后序遍历，每个节点向父节点返回两个值；楼主的dp咋写的

最开始我就是不断地call函数本身来求它的左，右子树，后来他说可以再优化用dp返回两个值，这样就不用不停地call了

OracleDesire 发表于 2017-1-29 11:47
求问楼主，是因为楼主选了以后工作地点在LA呢还是因为楼主现在人在LA，所以才在LA面的？

因为人在LA，所以就去LA面的

muyunhai 发表于 2017-1-29 03:04
总共有10000种情况，所以最次40000个数一定要出解，目标就是要做的比他优。那么如果你非常的倒霉，worstcas ...

我Google了一下 De Brujin Sequence, 觉得实质上就是一个找哈密顿链的问题吧, 如果只是单单用backtrack的思路去求哈密顿链, 这个问题是不难的. 但是能想到把这个问题转化成一个哈密顿链问题, 很有难度..

OMG，前两天看早些时候的面经有这道题，以为现在已经不考了，结果居然最近12月份又出现了！最通用的DFS解法不难写，就是想到这步有点难，bless楼主找到更好的offer！

bearkoala 发表于 2017-1-30 08:53
OMG，前两天看早些时候的面经有这道题，以为现在已经不考了，结果居然最近12月份又出现了！最通用的DFS解法 ...

我刚才亲测用python实现了一下, 暴力DFS backtrack只能算出2位密码的破解方法... 到了3位就栈溢出了...

sherry11115 发表于 2017-1-29 14:29
最开始我就是不断地call函数本身来求它的左，右子树，后来他说可以再优化用dp返回两个值，这样就不用不停 ...

弱问Lz怎么用dp返回2个值？。。。