k***e
发帖数: 556 | 1 bfs＋backtracking就可以了吧
一个面试题就去高篇paper看，这个时间精力都应付不过来阿 |
|
g*******y
发帖数: 1930 | 2 今天晚上刚刚开始学习backtrack+剪枝(大家不要笑，我刚刚转行的，算法背景不行的)
，呵呵，正好看到这个做做练习，不知道有没有大牛来看看我这个有没有什么问题。 |
|
|
g*******y
发帖数: 1930 | 4 一般是DP！backtracking的话，是指数复杂度了吧 |
|
g*******y
发帖数: 1930 | 5 yes, it's NPC
set partition
正号和符号其实就是对数组的一个partition，F等于0，就是要求partition的两个subset相等。这不就是NPC了嘛。
可以用knapsack类似的DP，或者用backtracking的方法做。
1 |
|
c*********t
发帖数: 2921 | 6 如果你多多回答问题，我就去借伪币，在发给你。呵呵！
还有一个愚蠢的问题，请别见笑，你多次在回答别的问题时提到 backtracking的方法
，我找了 CLR 的算法导论的书，好像没有提到过这个算法呀？什么书讲过这个算法？
谢谢！ |
|
g*******y
发帖数: 1930 | 7 呵呵，其实我也是新手，前几天才学的backtracking，用来做一些状态空间搜索的问题
比较普适的。
我是自己看的一个中文的算法书，估计你找不到。不过你可以在网上搜搜
"回溯法 剪枝"
另外就是我知道刘汝佳的那本算法竞赛的书里面有讲的，不过不知道那本书对新手会不
会太难了一些 |
|
t********e
发帖数: 25 | 8 Maybe backtrack + stack for operator priority?
With terminate condition when the temp result > T (specified result) |
|
g*******y
发帖数: 1930 | 9 递归的backtrack就可以省掉explicit stack了
剪枝是必定需要的 |
|
H*M
发帖数: 1268 | 10 来自主题: JobHunting版 - 一道MS题 这题除了backtrack prune之外还有啥好法子啊？
prune还得看字典的数据结构。如果是trie还好，hashtable的话，prune都没发prune吧？ |
|
|
b*********n
发帖数: 1258 | 12 O(n)可以找到最大的价值总和
但是却找不到具体每一件商品是否被pick
我想问的是如果想知道每一件商品是否被pick，
是不是只有O(n^2)space的那个算法才可以? |
|
g*******y
发帖数: 1930 | 13 November 07
学习了backtrack(回溯法)
之前做了一些回溯的题，比如打印permutation，打印任意n对括号等等，都是瞎蒙的。
还真凑巧，上午做了打印n括号的题，下午就看见有人说到回溯法，想想自己还没系统
学过这个，找了本基础的中文算法书来看了看，虽然书上讲的很浅显，发现自己貌似瞎
蒙还蒙对了思路，呵呵。正好凑巧的是，刚刚看了一点点，网上就有个人问怎么做
Vertex Cover的问题，正好让我来做做练习。
1. 打印任意合法的n对括号：
void printParenthes(int N, int left, int right, stack &stk){
if(left == N && right == N){
printStack(stk);
return;
}
if(left>right){
stk.push(')');
printParenthes(N, left,right+1, stk);
stk.pop();
}
if |
|
b********h
发帖数: 119 | 14 backtracking and pruning?
Since its time complexity is O(3^k), it only works for small k. |
|
x***y
发帖数: 633 | 15 1. You can use LCS, backtracking and take the one with minimum sequence in B or
using the elements in A(assume A is fixed) as key of hash table, and then
hash elements in B(assume B varies a lot) with the index as the hash value,
and try all the indice in the sequential way to find the answer.( for
example, find the first index of h, then the next possbile index of e, and
go on, find a length and corresponding lower index and upper index of the
subsequence; then starting from next index of h, re |
|
|
g*******y
发帖数: 1930 | 17 再说说附加的有些有用的东西可以学学：
trie,
suffix tree,
bit operations(推荐一个stanford的网页)
more hashing techniques:{dynamic hashing, extensible hashing, 还有个分级的
hashing不知道正规叫法叫什么}
backtracking
欢迎补充
排序什么这类基础问题就假定大家都会了，你要不会或者不熟可以去看看把基础打牢)
是至少弄懂明白个意思/思路，面试考到的机会不大就是了，不要求你能写出来code来(
不过要是遇到bt的公司然后RBT的code也别来怪我啊，呵呵)，14的思想值得学习和体会
，14都属于比较进阶一点的内容了，涉及到的面试题也算是难度等级较高的题目了
常重要，非常有用
是有些用处的，对于一些large scale题或者涉及到数据库实现的，19 20看看结论就好
了，从没看面试题目中出现过，21呢是高级进阶的东西，你如果学会了正好遇上用武之
地能说一说也会是很impressive的
coding？22肯定要熟悉的，23 24 25很少见到有直接考的(见过一道care |
|
g*****u
发帖数: 298 | 18 对NPC问题来说greedy algorithm一般是approximation solution。如果找exact
solution,TSP除了backtracking(其实就是permutation啦)，有dynamic programming解
法，我印象里wikipedia上就有。 |
|
r**u
发帖数: 1567 | 19 backtracking, if needs optimization, maybe organize the dictionary to trie
for easy checking valid word. |
|
h****h
发帖数: 75 | 20 我也被面到了第二个问题。我给的就是recursive function with backtracking and
also walking in trie tree.
我到没有被要求实现trie tree, 但是说明了在recursive function的那些地方检查
trie tree。 |
|
E***n
发帖数: 166 | 21 dynamic programming,
和费波纳契数列比较类似
Backtracking可能需要返回不止一次，所以太麻烦了 |
|
z*j
发帖数: 42 | 22 Co-ask. thanks
TSP is in NPC?
I can only think of backtracking. |
|
a*u
发帖数: 97 | 23 恩，DP可以O(CN)解出来。
另外一个想法：保持n个queue for each denomination,用backtrack的方法解? 好处就
是可以跳过不可能的amount，但是还没想清楚具体操作。 |
|
s*i
发帖数: 388 | 24 that was my first thought, but bitmap cannot backtrack to the file name (
maybe 100 files will be put into the same bitmap slot), so it's not enough.
so i go for hash table. |
|
q**f
发帖数: 21 | 25 在本版收益良多，详细面经稍后奉上。
FB: onsite题比较简单，电话面试印象深刻题就是recursive+backtracking。
Oracle: 无电话，直接通知onsite。onsite面5组，纯聊天基本没有technic。有趣的是
在本部接受分部的两个组的电话面
试。
Amazon：同其他人的面经无甚特别。 |
|
j***n
发帖数: 301 | 26 能举个例子么？
比如：
63 24 78 15
第一轮比较之后：
36 24 78 15
第二轮比较之后：
34 26 75 18
第三轮比较之后：
34 26 75 18
此时得到8为最大值，6为第二大值。如何backtrack呢？
you
of |
|
B*****t
发帖数: 335 | 27 找出最大的2^k<=n的k， 然后backtrack， 复杂度O(2^k), 也许可以剪枝
4=‘ |
|
B*****t
发帖数: 335 | 28 two approaches. first sort the jobs according the starting time.
1) backtracking + branch pruning
2) dp, f[i][j] = max(f[k][j], f[k-1][t.start[i]] + value[i]) 0<=k=t.
end[i]; greedy search the max value in above dp equation would optimize it. |
|
l******c
发帖数: 2555 | 29 there might be a solution or not
we can try.
1. sort the children with number of friends,
2, sort each child friends list based on 1
3 . process starting with the child with least friend based on 1, by
selecting the 9 kids with most friends based 2
4 if every kid is put in a group, done;
otherwise, backtrack, ie. change the last selection in 3
when back to the first selection and enum all the posibility for the first
selection, and fail, no solution |
|
l******c
发帖数: 2555 | 30 if do not require optimization, backtrack is enough, no need sort.
first |
|
l******c
发帖数: 2555 | 31 normal backtrack recursive, like maze problem |
|
I**A
发帖数: 2345 | 32 据说有lucky的成分在里面。。
能否说说最后一道题你说的backtracking是怎样的？ |
|
d****2
发帖数: 6250 | 33 starting from maximizing coefficient for d_n first, d_{n-1} next and so on,
when fail, backtracking. |
|
x***y
发帖数: 633 | 34 another way to use backtracking
//find all the commbination
typedef vector::size_type VecIndex;
void find_all_comb ( unsigned target, vector & vec, vector
>& eleCount, VecIndex vIndex){
//vec is assumed sorted
if(vIndex==vec.size())
return ;
unsigned mul = target/vec[vIndex];
eleCount[vIndex] = mul;
if(!(target%vec[vIndex])){
for(VecIndex vi=0; vi
for(VecIndex vc=0; vc
cout<< vec[vi] << |
|
d****2
发帖数: 6250 | 35
scanning always forward, no backtracking. |
|
A*********r
发帖数: 564 | 36 看了一下pearls， 觉得之前讨论的那个DP公式还是对的，跟pearls的预处理有同样的
效果。。
Define m(k,i,j) to be the maximum sum submatrix ending with the line A[k,i..
j]. （k is the row number, i, j is the left and right column number)
then the DP formula is m(k,i,j)=max{ 0, m(k-1,i,j)+sum{A[k,i..j]}}
注意到 m(k,1,j)其实就是第k行中从左到第j列的所有和，跟预处理的效果一样。。
你的这个例子，得到的 m(1, i,j) m(2, i,j), m(3, i, j)分别为：
（只考虑i<=j的情况）
0 0 0
0 1
3
3 5 3
2 1
1
4 7 4
4 1
0
最大和是7, m(3,1,2)也就是以第3行，第一列到第二列为最下面一条边的矩形。通过
backtrack应该可以找到前面的。。 |
|
d****j
发帖数: 293 | 37 可以转化为解多元方程的问题.
假设x1 is 'a', x2 is 'b', ..., x26 is 'z',这个问题就变成：
给定：
hello--> 1*x8 + 1*x5 + 2*x12 + 1 * x15 = 1
hi --> 1*x8 + 1*x9 = 1
...
求解: hlleowlord-->
1*x8 + 3*x12+1*x5+...... = ?
当然并不是真正要解出每个xi，而是要用已知方程式组合出求解的式子。
能变成矩阵的什么相关通用问题了？数学达人解决一下？
不行的话，就只好用DP+backtrack+heuristics策略来匹配这些系数，如何？ |
|
f****g
发帖数: 313 | 38 举个例子就清楚了
比如说：4 0 2 5 6 这个maze就是solvable的 4就代表最多可以走4步，这样就跳到了
0，2，5，6这
个数上。 6就是目的地了：S
再比如： 1 0 1 0 1 0 这个maze一看就没解了。 已开始在maze的头，也就是1这个位
置，走一步是
0，动不了，无论怎么跳也挑不到目的地了。
我当时用的是backtracking的做法，从目的地找是否有路回到开始点。 |
|
g**u
发帖数: 583 | 39
用2个hashMap做？
第一个hashMap, < user_id, Arraylist of page_id>;
然后更新第二个hashMap, <（page_id1, page_id2,page_id3, user_id）, count>.
eg.
A 1
A 2
A 3
A 4
在第一个hashmap中保存 < A, 1->2->3->4 >
在第二个hashmap中保存 <(A,1->2->3), 1 >
< (A,2->3->4), 1>
最后找对于每个用户访问最多的3连击就在第二个hashmap中遍历。
3。给一个maze：for example:4 0 5 6 1 0， 每个number代表最多可以走的步数，问
是否能从a[0]走到a[n-1];
马上想到的是backtracking， 不知道这个题可否用最大的单调递增序列求解？ |
|
s********l
发帖数: 998 | 40 round 2 B 就是用backtracking把~ |
|
f****g
发帖数: 313 | 41 It looks like a typical backtracking problem, and generates all the
combination
of the walks. |
|
h***n
发帖数: 276 | 42 My solution is based on backtracking
Given:
- n: # of types (can be viewed as some credits)
- b: # of A in the buffer
- m: # of A is shown
Three types of (simple and complex) actions
A: m = m + 1, n = n - 1 (only valid when b=0, already analyzed above why it
is only shown at the beginning of type sequence)
Crtl+A, Crtl+C, Crtl+V, Crtl+V: b = m, m = 2*m, n = n - 4
Crtl+V: m = m + b, n = n - 1
Source codes are as follows:
void get_max_A(int n, int b, int m, int *max)
{
if (n == 0) {
if... 阅读全帖 |
|
m****i
发帖数: 650 | 43 一本很好的书，基本把现在面试的基本题题目有了解答和代码，但是不足是没有给出算
法分类，比如dynamic, backtracking。 |
|
|
g*******s
发帖数: 490 | 45 不过感觉上可能还是backtracking快点吧。。就穷举一下所有硬币的可能组合 |
|
i**9
发帖数: 351 | 46 This is a classic backtracking algorithm question.
int coins[3]={2, 3, 5}
void printCombinations(int sum,int number){
static int combinations[MAX_SIZE];//MAX_SIZE=sum/2;
if(sum ==0){
printArray(combinations,number);
}
else{
if(sum >0){
for(int i=0;i<3;i++){
combinations[number]=coins[i];
printCombinations(sum-coins[i],number+1);
}
}
}
}
void printArray(int a[],int length){
for(int i=0;i
std::c... 阅读全帖 |
|
g*******s
发帖数: 490 | 47 我想了下，DP的过程应该可以更简化
假设你要面值S的所有组合，而你已知面值1 - (S-1)的所有组
合。
S的组合就是：
（S-任意单个硬币面值）的组合+该硬币的任意配对
删除重复
这样应该会比backtracking要快 |
|
h**k
发帖数: 3368 | 48 backtracking解法是硬币种类的exponential的复杂度，DP是关于S的线性的复杂度 |
|
d******a
发帖数: 238 | 49 Thanks for everyone's reply. I find backtracking is very great for solving
this problem. The code will become more clean when using it. |
|
g*******s
发帖数: 490 | 50 嗯，是的，如果有n个硬币种类,backtracking就相当于欠套了n个loop。n一大就没法做了 |
|
