h**o
发帖数: 548 | 1 Given a string s, partition s such that every substring of the partition is
a palindrome. Return all possible palindrome partitioning of s.
For example, given s = "aab", Return
[
["aa","b"],
["a","a","b"]
]
知道是用backtracking + DP. 但只知道判断是否Palindrome 可以DP. 不知道为何有贴
说有两个地方可以DP？
复杂度如何求？
time: 每个node 分成 n 支， 有n 层树， 难道 是 time = n^n?
space: n (recursive)+ n^2 (存 isPalindrome 的结果） = n^2? |
|
h**o
发帖数: 548 | 2 请问你哪里用到DP了？
我看着就是一般的backtracking recursive, 没存下什么可以再利用的结果啊？
我是吧bool isPalindrome(string s, int start, int end)第一次的结果存在一个
array 里， 省得老算老算的，我觉得这叫DP. |
|
g****o
发帖数: 547 | 3 我是第5版书
（1）4.7题 求不带parent指针的binary tree的LCA(不考虑node不在tree里的情况）
书上的解法很罗嗦，很容易漏掉某种情况,leetcode的代码就简洁多了，如下：
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // either one of p,q is on one side OR p,q is not in L&
R subtrees
}
想确认下leetcode的代吗覆盖所有corner case了吗？ 至少我没看出什么问题。
(2)9.5题 Write a meth... 阅读全帖 |
|
l*n
发帖数: 529 | 4 计算是否能split直接dfs & backtrack是不错。不过需要输出所有组合的话，还是需要
memoization的。比如feelink，可以是fee+link也可以是feel+ink，所以dp还是要的。 |
|
h**o
发帖数: 548 | 5 cc18.7.我怎么觉得是O（n^n）如果不考虑 DP 的话？
谁说是O(2^n）？
given |
|
h**o
发帖数: 548 | 6 cc18.7.我怎么觉得是O（n^n）如果不考虑 DP 的话？
谁说是O(2^n）？
given |
|
|
s********u
发帖数: 1109 | 8 我现在对这类题目是这么思考的：
1.问题的起点（字符串首）和终点（字符串尾）都是“收敛”的，因此可以考虑用dp。
2.用dp的话，就是从起点开始（终点其实也行，因为空字符串的解都是true，都已知）
，根据1~n-1个节点的情况，推断n的情况。因为需要记录path，又不是backtracking，
所以用prev数组（每个节点的前驱节点）来记录。
3.可能有多条path，所以prev是一个vector >。记录完毕之后需要从终点
出发，回溯遍历这些路径，直到prev取出来的index是-1。 |
|
s********u
发帖数: 1109 | 9 Phone interview，美国人，说话很清楚。不过太健谈了，导致他每次描述问题，说一
大堆，还各种打比方，要搞清楚whole picture真是太费劲了。。
不过人比较nice，希望好运吧。
1.他说warm up一下，说了一大堆，我才搞明白他的意思是，电影里经常有人拿报纸剪
下很多字母，然后拼成一句话去给别人发威胁message之类。（他一上来就说kidnap小
女孩之类，把我吓坏了，以为要写个绑匪和cops的design题。。。。）
然后让我实现一个function，看看能不能拼成一个message。
因为时间过了挺久，我就有点着急，赶紧写了一个hashtable的方法。然后他问我如果
这个message有重复单词怎么办，我才发现自己的bug（只是考虑newspaper里有没有这
个字母，而没有考虑字母的数量），改了一下。
bool compose( string msg, string newspaper){
unordered_map ccnt;
for(auto it = newspaper.begin(); it != newspa... 阅读全帖 |
|
s********u
发帖数: 1109 | 10 体会：
1.英语听力差了点，碰到老印嫌听不清楚，碰到健谈的老美，又被他东扯西扯搞晕了，
不能get whole picture of the question
2.google电面过两次，每次都是warmup题（主要考数据结构） + 递归题，两次我都被
考了backtracking
3.题目都不算难，还是要提高熟练度，否则面试一紧张很容易没有平时练习的那个状态
。 |
|
l*n
发帖数: 529 | 11 backtracking的时候push整个数据结构会有很大问题的。正确做法是只用一个
container数据结构来记录状态，有时候甚至借助原数据结构来省空间。
i++比++i似乎少那么一点效率，不过这点也无所谓了，保持个人习惯能流畅书写最重要。
end |
|
s********u
发帖数: 1109 | 12 Phone interview，美国人，说话很清楚。不过太健谈了，导致他每次描述问题，说一
大堆，还各种打比方，要搞清楚whole picture真是太费劲了。。
不过人比较nice，希望好运吧。
1.他说warm up一下，说了一大堆，我才搞明白他的意思是，电影里经常有人拿报纸剪
下很多字母，然后拼成一句话去给别人发威胁message之类。（他一上来就说kidnap小
女孩之类，把我吓坏了，以为要写个绑匪和cops的design题。。。。）
然后让我实现一个function，看看能不能拼成一个message。
因为时间过了挺久，我就有点着急，赶紧写了一个hashtable的方法。然后他问我如果
这个message有重复单词怎么办，我才发现自己的bug（只是考虑newspaper里有没有这
个字母，而没有考虑字母的数量），改了一下。
bool compose( string msg, string newspaper){
unordered_map ccnt;
for(auto it = newspaper.begin(); it != newspa... 阅读全帖 |
|
s********u
发帖数: 1109 | 13 体会：
1.英语听力差了点，碰到老印嫌听不清楚，碰到健谈的老美，又被他东扯西扯搞晕了，
不能get whole picture of the question
2.google电面过两次，每次都是warmup题（主要考数据结构） + 递归题，两次我都被
考了backtracking
3.题目都不算难，还是要提高熟练度，否则面试一紧张很容易没有平时练习的那个状态
。 |
|
l*n
发帖数: 529 | 14 backtracking的时候push整个数据结构会有很大问题的。正确做法是只用一个
container数据结构来记录状态，有时候甚至借助原数据结构来省空间。
i++比++i似乎少那么一点效率，不过这点也无所谓了，保持个人习惯能流畅书写最重要。
end |
|
s********l
发帖数: 998 | 15 恭喜通过~
我问一下 你的backtracking是从(0,0) 点开始的
为什么 要其他所有neighbour点都小于当前点的值啊？
我看你题目的描述是 应该是东西海岸的海拔低 中间的高 才算有效路径的把~
比如 1, 2, 3, 2, 1 |
|
s********u
发帖数: 1109 | 16 感觉准备过程中走了很多弯路，一开始看很多经验说是大多数公司cc150就够用了，是
神书，结果我做了三遍，版上很多题目只要没见过还是不会做。然后我就开始做
leetcode，目前做到一半，不会的就看看discuss版面，有一定成效。
我觉得真正提高最大的是最近看面经。感觉自己思路见识广了很多，也开始大致明白为
什么有些人一看题就知道应该用backtracking，或者dp什么的。
其实原因并不是面经这个题有什么区别，而是如果做careercup书，不会做就看答案，
答案只会告诉你这道题目怎么解，这是我觉得cc150写的不好的地方。比如他每个章节
有一点基础知识，但不会把这些跟题目对应起来。结果你还是不会分类。
做leetcode就好一点点，因为discuss上面很多人会写自己的分析过程。就是“为什么
想到这样做”。
做面经是收获最大的，因为做一道题目的时间最长，没有现成答案，不会做只能去搜资
料。虽然找资料有很多冗余的过程，但是反而开拓了见识，了解了很多分析和分类的方
法。其实就是一种“模式识别”
比如一个boggle game题，搜到网上很多人总结这个题，比如暴力回溯算法，建立trie... 阅读全帖 |
|
l*n
发帖数: 529 | 17 来自主题: JobHunting版 - G新鲜面经 1.2应该是个combination题目吧。任选三个数，比如156,然后1<6,6>5，但是要求5<{4
，2},所以fail之，继续新组合。recursion+backtracking。
1
big |
|
r*******n
发帖数: 3020 | 18 vector wordBreak(string s, unordered_set &dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
vector result;
int n = s.size();
vector> table(n, vector(n,false));
int max_len=0;
for(auto& word:dict){
if(max_len
max_len=word.size();
}
//DP
for(int i=0; i
for(int j=i;j阅读全帖 |
|
r*******n
发帖数: 3020 | 19 多谢，改了后过了OJ。
如你所说，我加了1-D bool table来记录有没有解
后面DFS根据这个如果没有解就停止递归搜索
把整个code贴下面
vector wordBreak(string s, unordered_set &dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
vector result;
int n = s.size();
vector> table(n, vector(n,false));
int max_len=0;
for(auto& word:dict){
if(max_len
max_len=word.size();
}
... 阅读全帖 |
|
s********u
发帖数: 1109 | 20 还只是胡思乱想，也不太严谨。欢迎指正。（只讨论目前算法面试题一般涵盖的范围）
前言：
我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
个条件个人感觉不太实用。
1.比如不overlap的时候也可以用dp，只是效率不提高，还增加了space cost而已。（
所以这个原则应该是“适合用dp”，而不是“可以用dp”
另外且不说最优子结构，overlap有时候也较难判断，比如boggle game这个，路径一定
是有重复的，但是
subproblem却未必，因为前驱的访问节点会影响后驱节点的"胜利条件"。
2.另外，就算是有overlap，从实用的角度来说，dp（bottom-up）未必方便实现。比如
用DFS来判定二叉树中是否有某个节点(cc150的4.7），bool cover( root, p )本身是
单纯的DFS访问，subproblem不存在overlap；但对整个问题而言，cover不停的调用，
对整个问题而言subproblem存在overlap。同样的还有4.1.因为这两个题目都在DFS中使
用了DFS，递归函数中调用了递归... 阅读全帖 |
|
s********u
发帖数: 1109 | 21 今天想了一想，觉得可以分为两类问题：
1.节点空间两端收敛，中间可以发散，但是两端必须收敛。因此前驱节点一定能决定当
前节点（唯一解）。最典型的，就是leetcode的unique path，或者fibnacci数列。这
类问题，总是可以用dp bottom-up的做。
2.节点空间一端发散，也就是说前驱节点不能决定当前节点（可能有很多方向，很多解
）。这类问题一般可以用backtracking做。最典型的，自然是tree的dfs |
|
s********u
发帖数: 1109 | 22 今天想了一想，觉得可以分为两类问题：
1.节点空间两端收敛，中间可以发散，但是两端必须收敛。因此前驱节点一定能决定当
前节点（唯一解）。最典型的，就是leetcode的unique path，或者fibnacci数列。这
类问题，总是可以用dp bottom-up的做。
2.节点空间一端发散，也就是说前驱节点不能决定当前节点（可能有很多方向，很多解
）。这类问题一般可以用backtracking做。最典型的，自然是tree的dfs |
|
c**********g
发帖数: 28 | 23 小弟是某二流学校，数学PHD，因为从小就喜欢数学，所以之前打算做学术工作。
导师已经跟我说可以准备毕业了，我前一阵就在找学术界工作，可是找了半天，找不到。
position很少，极少数position也不要我。
看见job版各位大牛，争相报offer，眼花缭乱。
我想了很久，决定还是找个CS工作。
我以前就喜欢cs，同时怕找不到学术界工作，所以也有一些cs的训练
算法导论前面十几章看了很多遍，对sorting search之类的基本概念各种变化很熟。
C加加基本语法很熟，一些trick的细节也很清楚，design pattern也会一些。
大概两万行的水平，不会multi threading。
C语言也比较熟悉，大概一万行的水平。
Matlab写过几千行代码。
Python会一些语法，现在都忘了。
machine learning data mining一些经典算法也会。做过一个project，用到logistic,
nonlinear, weighted regression和MC cross validation算法来分析数据。
在面试方面：
leetcode 大概100道题，我看... 阅读全帖 |
|
m*****y
发帖数: 120 | 24 But this only ask for exist a path or not, plus, it has restriction on where
it can move to. (the Backtracking Solution doesn't help too much, basically
it search from end to start instead, which is the same as search from start
to end)
cell to another cell following non-descreasing path. |
|
y*****3
发帖数: 451 | 25 leetcode上的140题才只做了32道，做了2-3遍，主要就是集中在array和linked list和
一些简单的树的题目上，DP和Graph的题目还都没看，带backtracking的树的题目都还
没看。。我这进展是不是太慢了？目标是打算１２月底开始找工作。
感想：
１。array和linked list的题目现在做得比较有底了，特别是今天把有关reverse node
的题目的解法总结了下，以前一沾了reverse node的题目就一脑袋糨糊。树的题还是喜
欢用递归解，不用递归就比较发毛。。。
２。看版上大家的讨论，大部分还是看不懂，什么trie, haffman tree什么的，还有怎
么实现计数器什么的，还有greedy algorithm什么的，实在是着急啊！请问大家，这些
都是通过哪里学习的？貌似leetcode里并没有这些概念啊？以前读书时候学的东西早都
还给老师了，呵呵。
请教大牛们，我是应该把各种题目都先刷一遍好呢，还是把每种题目都先刷熟了、总结
清楚了再进行下一类题目？大牛看我这么样的进度，到１２月底有戏吗？？ |
|
l*n
发帖数: 529 | 26 prefix就是用来check viability的吧，楼上说的没错，还是sodoku的思路。
就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。 |
|
e******0
发帖数: 291 | 27 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
是这样的吗？
这样空间复杂度 和 时间复杂度 岂不是特别特别大？
谢谢。 |
|
l*n
发帖数: 529 | 28 prefix就是用来check viability的吧，楼上说的没错，还是sodoku的思路。
就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。 |
|
e******0
发帖数: 291 | 29 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
是这样的吗？
这样空间复杂度 和 时间复杂度 岂不是特别特别大？
谢谢。 |
|
l*********d
发帖数: 78 | 30 尝试过许多解法，但老是 TLE. 有高人能帮忙看一下这一段代码吗？
基本上就是 double queue + backtracking，跟这里的http://blog.csdn.net/niaokedaoren/article/details/8884938
很相似。但是问题出在哪里呢？
提前谢谢了！
------------------------------------------------------------------------
import java.util.Map;
public class Solution {
public void fillPaths(String start, String cur, Map>
map,
ArrayList> result, LinkedList post
) {
post.addFirst(cur);
if (start.equals(cur)) {
... 阅读全帖 |
|
|
|
J****3
发帖数: 427 | 33 试着写写， 楼主看看， 大家一起总结：
1. Clone Graph-> BFS+HashMap
2. Gas Station->DP
3. Candy->Two Pointers
4. Single Number-> Xor, HashMap, or Sum or Product way to find
5. Single Number II -> Xor, HashMap
6. Copy List with Random Pointers -> Two Pointers, HashMap with two times
traverse(like clone graph)
7. List Cycle, List Cycle II, Reorder List-> Two Pointers
8. Binary Tree Preorder, Postorder recursive -> Using stack to mock
recursive way, or implement like morris way.
9. LRU Cache-> HashMap + list
10. Inse... 阅读全帖 |
|
s********u
发帖数: 1109 | 34 最直观的想法自然是backtracking，每次三个方向dfs。不过他是要求最优选择。 |
|
j*********g
发帖数: 36 | 35
对的，你的backtrack work就是因为Eulerian tour存在 |
|
m****c
发帖数: 252 | 36 backtrack, 一次DP就搞定了。
这个题目类似于crack the coding interview 8.2 题。 |
|
e********3
发帖数: 18578 | 37 Backtrack, recursive, and dynamic programming.
Here is the code (changes size to see the solution for matrices of different
sizes), the time complexity is O(n) (n = size*size) and the memory usage is
O(n) as well:
import java.util.*;
public class HarryPotter{
private static Random rand = new Random();
private static int[][] matrix;
private static Map cache = new HashMap
Integer>();
static class CacheKey{
public int x, y;
public Cac... 阅读全帖 |
|
b*********s
发帖数: 115 | 38 昨天onsite完的，趁还记得上来写一下，面的不好，求bless。
一轮店面
第一题判断一个string的开头第一个字母是不是大写，两行代码就能写完，没有任何陷
阱。第二题让我用Java（因为我本来用python）写判断binary tree是不是bst。两个题
都很简单，然后还让我说一下自己做过的最challenging的一个project，整个面试不到
二十分钟就说问完了问我还有没有问题，我连忙问他为什么这么快是不是我什么地方做
错了他不愿继续问下去。答曰他在G工作七年多面了不下一百人，十分清楚哪些人去
onsite不是在浪费他们engineer的时间，觉得我没有问题。。。
过了一周果然hr说去onsite，由于我所在的城市有G的office，所以去那里面，早上三
轮然后吃午餐，下午再两轮，一共五轮
第一轮
给一个矩阵，每个格子上有三种可能，空房，阻碍物或者是保安，阻碍物不能进，空房
四个方向都能进，要写代码给每个空房标记其离最近的保安的距离，比如
000
BGG
B00
B表示障碍物，G表示保安，0表示空房，应该标记为
211
BGG
B11
我说扫一遍矩阵，然后遇到每个G就bf... 阅读全帖 |
|
e********3
发帖数: 18578 | 39 BFS+DP,而且需要maintain两个距离，一个是到终点的最小距离，一个是到起点的最小
距离，计算终点的距离需要backtrack,到起点的简单比较保存最小值就行了，类似
Dijkstra算法。电面就考这个有点偏难了，尤其还是同胞就操蛋了，要是老中这么考老
印我绝对赞成。简单的实现还可以把障碍物那个的距离设成100啥的，这样自然就知道
要绕过了。
这个题目的难度比reverse linkedlist, atoi难了几个数量级。。。
我贴两个我自己写的代码抛砖引玉一下，第一个是Harry Potter最小的strength通关，
第二个是经典的Dijkstra algorithm,都是附带了测试数据自动生成的方法，你把这两
个组合一下基本就能解这道题了,过两天我有空了来写一下这道题的具体实现。
import java.util.*;
public class HarryPotter{
private static Random rand = new Random();
private static int[][] matrix;
private static ... 阅读全帖 |
|
m*****n
发帖数: 204 | 40
AVL is easier but may backtrack, so rotation cost is not
guaranteed O(1). Total cost is still O(n) but the constant factor is worse. |
|
p**o
发帖数: 3409 | 41 (Please use monospaced font to read)
Example:
i: 0 1 2 3 4 5 6 7 8 9
S0: a a b x c a b x c b
T0: a b c b
expected output: [5,10)
n=len(S0), m=len(T0)
Collect indices in S0: O(n) time
a: 0 1 5
b: 2 6 9
c: 4 8
I wanted to use dynamic programming,
but I did not find any optimal substructure.
So I chose to backtrack on these indices instead.
T0: a b c b
i: 0 1 2 3 4 5 6 7 8 9
S0: a a b x c a b x c b
S1: a _ b _ c _ b _ _ _ -> [0,7)
S2: a _ b _ c _ _ _ _ b -> [0,10)
S3: a _ b _ _ _ _ _ c b -> [0... 阅读全帖 |
|
w***s
发帖数: 17 | 42 第三题，preorder traversal,
选第一个结点，看看如果有子结点，就DFS, mark visited,
backtrack回来，然后看第二个结点，如果访问过了就过，没访问过就重复刚刚的方法？
如果访问到第三个结点时候，发现第三个结点是第一个的父结点怎么办？
这样的话空间复杂度是O(|v|)？
1&5的答案晚点送上。 |
|
f******h
发帖数: 45 | 43 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
x***y
发帖数: 633 | 44 Backtracking with cutting branches that cannot be optimal; A good start is
to have the columns sorted by how many 1s they have; and then start from the
column with the smallest number. |
|
f***s
发帖数: 112 | 45 面试官最后接受了我的解法，我用的是backtracking + 剪支去重复
combination sum
公司第一个字母是D |
|
R******9
发帖数: 267 | 46 M面经
两个月前面的，乘着记得回报本版。
Phone: lowest common ancestor of two nodes in a binary tree. Binary tree
node doesn’t have parent pointer.
What if the nodes have parent pointer?
Onsite:
1. Print the boundary of binary tree anti-clockwise.
2. a. Given a linked list, put all the even numbers before odd numbers.
e.g. 3->4->2->7->null
should become 4->2->3->7->null
b. A small design problem. Shuttle is picking up passages on a lane. The
arrival of passengers are random. Design such a system.
3. Find t... 阅读全帖 |
|
a********r
发帖数: 218 | 47 Zhuimeng1314大牛：
why do we need to
"solution.pop_back();"
after each backtrack?
I am 菜鸟，don't really understand recursion, can you explain it in plain
text? |
|
y***n
发帖数: 1594 | 48 其实就几个思路。
1. DFS / BackTracking.
2. BFS
3. DP
4. Greedy。
然后常用的数据结构。
Design的题总归可以讲两句，小时候课文让你总结中心思想，总能讲两句。
一个都套不上，这个工作不是你的。 |
|
|
|
