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,跟我的想法一致了。 |
|