i**********n
发帖数: 196 | 1 还是可以的，这几天练的backtracking题刚好熟练。感觉没有准备的话还是很难写完..
. |
|
k*******n
发帖数: 16 | 2 尝试推了一下，不知道对不对
T(n) = n * T(n - 1) + n
= n * (n - 1) * T(n - 2) + n * (n - 1) + n
= n * (n - 1) * ... * (n - k + 1) * T(n - k)
+n * (n - 1) * ... * (n - k + 1)
+ ... + n * (n - 1) + n
When k =n, T(n - k) = T(0) = 1
T(n) = (n!) + (n!) + (n!) / 2 + ... + n = O(n!) = O(n^n) |
|
t*****3
发帖数: 112 | 3 permutation的复杂度应该是O(n!)，算法过程恰好遍历了所有的排列可能。更general
的感觉复杂度就是试探了的可能解的规模。 |
|
|
s****i
发帖数: 65 | 5 perm(num,k+1,n,res);
后面3句，
tmp = num[k];
num[k]=num[i];
num[i]=tmp;
原先i,k上的值换了，现在又换回来了，下一个for循环跟下一个数换 |
|
C*******n
发帖数: 193 | 6 class Solution {
public:
bool valid(string &str, int st, int ed){
while (st
if (str[ed]!=str[st]){
return false;
}else{
st++;
ed--;
}
}
return true;
}
void find(string s, int st, vector &r, vector > &
res){
if (st>=s.size()){
res.push_back(r);
}else{
for (int i=st;i
if (val... 阅读全帖 |
|
|
a********e
发帖数: 53 | 8 还有valid的时间复杂度呢？这题我看到有的博客里说复杂度是O(2^n), 因为有 n &#
8722; 1 个地方可以砍断,每个地方可断可不断。 |
|
M******9
发帖数: 10 | 9 基本都面完了，前一段刚注册了一个帐号，上来发文，大概说下自己的经历，抛个砖头
，希望对大家有用，也祝愿大家都能找到满意的工作。有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 | 10 基本都面完了，前一段刚注册了一个帐号，上来发文，大概说下自己的经历，抛个砖头
，希望对大家有用，也祝愿大家都能找到满意的工作。有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, 但... 阅读全帖 |
|
|
S********0
发帖数: 5749 | 12
据说是google的，我觉得面试能用backtracking做出来就可以了。 dp好像效率也没高
太多 |
|
M*********n
发帖数: 4839 | 13 这个是个backtracking吧？
原理上每次改变一个字母，可以回到原点，并包括所有的组合。 |
|
w**********o
发帖数: 140 | 14 給個這個思路: 用DFS找sub-graph, 然後用backtracking來做. |
|
r****7
发帖数: 2282 | 15 哪个公司的电面？感觉有点儿难啊
暴力解的话，就类似lc上的正则匹配，不停的backtracking
不知道能不用用后缀树数组解。 |
|
r****7
发帖数: 2282 | 16 哪个公司的电面？感觉有点儿难啊
暴力解的话，就类似lc上的正则匹配，不停的backtracking
不知道能不用用后缀树数组解。 |
|
r*******h
发帖数: 315 | 17 对的，感觉这里也是难点所在，无法简单的标记visited来做backtracking |
|
a******d
发帖数: 82 | 18 Sub array具体是指？
一段连续的数 还是可以从不连续的位置取？
前者 on 后者只能dp 还要backtracking 求最长路径 |
|
a***a
发帖数: 739 | 19 This indeed can be solved by DP.
Since DP[i][j] is always false if abs(i-j) >=2
So when iterating,
there are only 3 things need to be stored: DP[i][i], DP[i+1][i], DP[i-1][i]
So this DP actually just needs 3 extra space, which is O(1). And there is no
need to backtrack; just use the two iterators to scan the files once. |
|
h***k
发帖数: 161 | 20 G onsite碰到这道题。思路是首先满足第二个条件，就是先random一个valid move，然
后开始一边fill board一边查相邻是否valid，是用sudoku那题的backtracking。表示
完整写完code时间不够，只写了个主要的结构，查valid的helper method跟面试官讨论
了下如何实现就没有写出来。 |
|
|
|
a****r
发帖数: 87 | 23 同意chenm8. 就是一个backtracking.
有k个position, and each position can have list[k] 可能。 |
|
r********7
发帖数: 102 | 24 抛个砖~ 自己写了一个， stack 然后 backtracking。 其实写完感觉stack多此一
举，不想改了。 请大神们无视
public class Solution {
public void printCombo(List> input){
if (input == null || input.size()==0){
return;
}
Stack> stc = new Stack>();
for (int i=0; i
stc.push(input.get(i));
}
List> res = new ArrayList>();
while(!stc.isEmpty()){
List ... 阅读全帖 |
|
|
r*******h
发帖数: 315 | 26 已经提交hc，但是属于borderline的case，分享面经求通过（之前1m3cd发过简单版）
，相关behavior问题都省略了。
一共五轮，午饭前三轮，午饭后两轮，其中两轮系统设计。因为从国内过来，
recruiter（印度女）特别跟第一个面试官讲我的时差反应，还请他向后面的面试官讲。
1.系统设计，面试官应该是摩洛哥人
给一个url和一个给定的方法genNextUrls可以返回所有从这个url可以直接链接到的url
。要求统计所有能访问到url数。
结果先让我coding，我以为搞错了，问要不要考虑一台机器处理不了的情况，面试官笑
了，说那是followup问题。
就用一个queue和一个hashset走bfs解决之（这里可以反衬我后面一个错误）。面试官
问如果要求判断一个url无效怎么办，我提到了exception处理两种思路，以及
genNextUrls可以怎么处理，面试官说可以，但是如果要求我的方法不能throw
exception出来，怎么让caller知道一开始的url给错了，我blabla。
面试官说现在回到你提到的scalable的问题，你的代码中有哪些地方是bo... 阅读全帖 |
|
H********n
发帖数: 99 | 27 可能说的是backtracking，就是一个个试，试不通就回溯。 |
|
e****x
发帖数: 148 | 28 就是backtracking，然后用一个list来记录剩余硬币的数量
不过我没想到如何在过程中去重，直接用set了，OJ妥妥会超时……
def centsChange(cents):
# pennies, nickles, dimes, quarters
quantity = [7,5,4,2]
value = [1,5,10,25]
path = [0,0,0,0]
result = []
dfs(cents, cents, path, result, quantity, value)
return list(set(result))
def dfs(remaining, cents, path, result, quantity, value):
if remaining < 0: return
if centsSum(path, value) == cents:
result.append(tuple(path))
for i,v in ... 阅读全帖 |
|
d******l
发帖数: 98 | 29 谢谢
就是backtracking，然后用一个list来记录剩余硬币的数量不过我没想到如何在过程中
去重，直接用set了，OJ妥妥会超时……def centsChange(cents)........ |
|
e****x
发帖数: 148 | 30 来自主题: JobHunting版 - 一个店面题 dfs with backtracking? |
|
v*****y
发帖数: 68 | 31 我on site的时候也遇到了这个题，我在优化上遇到了问题。
不谈优化的话，我觉得就是典型的backtracking，把每一个可能的数字都都试一下，如
果对方一定不能赢，那就我们可以赢。reg的答案就是这样的。
哪位能说说优化？当时面试的时候我想这种方法是否有重复计算？我们是否能把一些结
果cache一下？比如说maxChoosableInteger = 10， desiredTotal=10的话，如果第一
次我们取1，对方取2，和第一次我们取2，对方取1，都需要计算canWin([3..10], 7)。
所以我们是否可以以各一个set为key，boolean为value的hashmap来cache结果？
求大神们指点，谢谢。 |
|
m**********2
发帖数: 6 | 32 上周面亚麻，一个犹太人，上来先是一道常规OOD，还没讲完就被打断，说时间有限，
下一道。
然后是道coding的题目。这道题目看似简单，但是感觉有不少边界条件要考虑。
题目如下：
安卓手机解锁画面，给定任意一个解锁图形，不知道起始点，输出所有可能的path。
本能的觉得应该用DFS遍历，但是花了很多时间思考何时应该backtrack返回。估计这题
应该是挂了。
有没有大神能给点思路啊 |
|
y*****e
发帖数: 712 | 33 lz, trie + dfs那题你能再解释一下吗？ *是不是不用放到字典里， 比如说abc*de，
在trie里记录abc，然后skip一个character,再在后面找de? 不是太清楚具体怎么实现
的。。。
另外就是regex那题，DP的complexity是 n^2 + n^2; recursion + backtracking的复
杂度怎么考虑？最坏是2^n吧，怎么说服recursion是更优的办法呢？
另外感觉lz答得不错，phd应该有很高的级别吧，羡慕。。。
sliding |
|
c*****n
发帖数: 95 | 34 ＊可以和任意非空字符匹配 e.g. a - z
DP 复杂度应该是 m * n
recursion + backtracking 是 2^n. recursion好处是，如果没有很多＊时，可能结束
的更早。
， |
|
m********e
发帖数: 9 | 35 请问一下大家，好几位朋友都说如果还没有绿的话，就应该留。
我对绿卡的理解是这样子的，在140已经approved的情况之下，如果换工作而且前雇主
不withdraw 140 application（most won't)，PD可以保留，但是新雇主必须做h1b
transfer以及labor certificate。唯一的风险，就是如果在新的labor certificate被
批准之前PD变成current，我也不能够递交485。一个例子就是PD突然往前很多（例如最
近），我的PD变成current，但由于pending labor certificate不能及时递交485，然
后PD又突然backtracks，到我labor certificate下来的时候PD又不是current的了。
换工作对绿卡还有别的坏处吗？ |
|
|
|
w*******g
发帖数: 9932 | 38 if you miss a number in the correct sequence, you have to backtrack by one
number, so your example actually fails to pass the test.
了0 |
|
l******s
发帖数: 3045 | 39 我咋觉得是经典backtracking呢？能不能解释一下DP如何解？ |
|
s********l
发帖数: 998 | 40 这是我见过的 用的最有实际意义的backtracking 赞~
谢谢 大侠~ |
|
b*****n
发帖数: 618 | 41 backtracking？没懂什么意思，你是说用DFS？ |
|
h****e
发帖数: 2125 | 42 你好像是拿过FLG offer的吧，连backtracking都不知道？？ |
|
h****e
发帖数: 2125 | 43 谁说不能用recursion？你丫到底懂不懂backtracking？唧唧歪歪废话真特么多。
下？ |
|
h****e
发帖数: 2125 | 44 这题一看让你把1变0，自然就是考backtracking。三个方向：dirs = {{0,-1},{0,1},{
1,0}}，当前coordinate要loop through这三个方向。如果新坐标的值是1的话，就要先
变成0同时total变化数量加一，然后call recursive method。在recursive call之后
你还得把新坐标变回1，再try下一个方向。
懂了？ |
|
i*******e
发帖数: 114 | 45 请问你backtracking的时间复杂度多少？假设 n x n 的空间。
BFS的话，每个iteration 处理 某一个单一cost的所有cell。 每层之后cost + 1.
时间复杂度可以 O(n^2)， 因为每个cell只处理一遍。
,{ |
|
b*****n
发帖数: 618 | 46 " 二维matrix，含0，1。 1是障碍。
00011
11100
从左上角出发到右下角， 可以往上，往下，往右移动。
把1变成0，使得你可以从左上角到右下角。
求最小的变化数字。"
这是原来的描述，二维matrix，所以我觉得是m×n
我题都没看懂傻逼了，你牛逼你继续喷吧，你还可以继续用你牛逼的backtracking来解
这个只有两行的matrix |
|
b*****n
发帖数: 618 | 47 这个只能DFS backtracking了吧，找到所有的unique path |
|
l******s
发帖数: 3045 | 48 谢谢，算是top down的递归dp+backtracking，跟我的想法一致了。 |
|
m****t
发帖数: 23 | 49 can I ask why we can not do this problem using backtracking? as long as I
found a position when the 1st player picked at first will win, I can just
return that position.
not sure if that will work. |
|
l******s
发帖数: 3045 | 50 谢谢，算是top down的递归dp+backtracking，跟我的想法一致了。 |
|
