i**********e
发帖数: 1145 | 1 第二题是 wordladder 游戏的实现问题，本版有讨论过。
最基本的实现方法是用 BFS，但是level越深就越多节点。
利用一些剪枝 可以进行优化
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
f*******7
发帖数: 943 | 3 之前已经面了三轮电话面试，题目也贴出来了。
本来说的是onsite，结果最后改成了4 轮Skype Interview
一
[1, 2, 3] => false
[1, 2, 3, 2] => true
[1, 2, 3, 2, 3] => false
[1, 2, 3, 4, 4, 4, 5, 5, 5] => false
Given an integer array, determine whether there exists an element such that
the number of occurrences of the element strictly exceeds the number of
occurrences of any other element.
中间还问了很多细节问题， 比如HashMap， Heap 等
最让我摸不到头脑的问题， heap的两个属性？？？ 我说了一堆，也没答到点上，最终
的答案是
1) binary tree 构成
2) the relation between the upper level and lower level no... 阅读全帖 |
|
s********u
发帖数: 1109 | 4 老印面试，人挺nice的，就是说话还是听不太清楚。特别是带了耳塞接电话，声音很“
刺”，免提又怕更听不清楚。
0.以为电面不问behavior的，没想到问我平时用不用ebay，如何提高用户体验等。。幸
好我用的比较多，随便扯了些。但是很担心突然说让我根据我说的design一下，所以战
战兢兢。
1.用stack实现一个queue，careercup书原题。我在dequeue里面用了shiftstack，他问
我能不能将enqueue的time cost降低到O(1),我说可以，只要每次enqueue时候都
shiftstack就可以了。他问我哪种更好（enqueue和dequeue几率相同），我说前者更好
，因为dequeue的时候，只要leftstack不空，是不需要shiftstack的。
2.// Input -> "I have 36 books, 40 pens2, and 1 notebook."
// Output -> "I evah 36 skoob, 40 2snep, dna 1 koobeton."
如果是数字，原样输出，如果不是，那么倒序。
挺简单的题目... 阅读全帖 |
|
|
|
s********u
发帖数: 1109 | 7 感觉准备过程中走了很多弯路，一开始看很多经验说是大多数公司cc150就够用了，是
神书，结果我做了三遍，版上很多题目只要没见过还是不会做。然后我就开始做
leetcode，目前做到一半，不会的就看看discuss版面，有一定成效。
我觉得真正提高最大的是最近看面经。感觉自己思路见识广了很多，也开始大致明白为
什么有些人一看题就知道应该用backtracking，或者dp什么的。
其实原因并不是面经这个题有什么区别，而是如果做careercup书，不会做就看答案，
答案只会告诉你这道题目怎么解，这是我觉得cc150写的不好的地方。比如他每个章节
有一点基础知识，但不会把这些跟题目对应起来。结果你还是不会分类。
做leetcode就好一点点，因为discuss上面很多人会写自己的分析过程。就是“为什么
想到这样做”。
做面经是收获最大的，因为做一道题目的时间最长，没有现成答案，不会做只能去搜资
料。虽然找资料有很多冗余的过程，但是反而开拓了见识，了解了很多分析和分类的方
法。其实就是一种“模式识别”
比如一个boggle game题，搜到网上很多人总结这个题，比如暴力回溯算法，建立trie... 阅读全帖 |
|
s********u
发帖数: 1109 | 8 嗯，我好像理解你的意思了。
就像这一段（维基百科）：
In other words, a greedy algorithm never reconsiders its choices. This is
the main difference from dynamic programming, which is exhaustive and is
guaranteed to find the solution. After every stage, dynamic programming
makes decisions based on all the decisions made in the previous stage, and
may reconsider the previous stage's algorithmic path to solution
一个简单的例子是，找硬币的问题，比如硬币面值是1,3,4.要组成6，贪心法就会得到(
4,1,1)，而dp则能解出（3,3）。
但我奇怪的是，如果按照这样的说法，我们平时绝大多数的dp题，难道实际上都是贪心
算法了。（或者把贪心... 阅读全帖 |
|
k*********6
发帖数: 738 | 9 我觉得下面这个例子从'a'到‘c’就是一步啊，把'a'直接换成‘c’不就行了吗？为什
么报错说答案是2 呢？ 我觉得我肯定没理解题让干什么
Input: "a", "c", ["a","b","c"]
Output: 1
Expected: 2 |
|
s***e
发帖数: 403 | 10 就是一个图论的dijkstra问题。
始态必须经过过渡态才能到达终态而已。 |
|
|
|
p***e
发帖数: 111 | 13 代码很难看，晚上有时间再修改。 同样单向bfs需要1200ms左右ac。
class Solution:
def ladderLength(self, start, end, dict):
dict.add(end)
current, distance, visited = [start], 1, {start:0}
bcurrent, bdistance, bvisited = [end], 1, {end:0}
while current and bcurrent:
pre, bpre,next, bnext = [], [], [], []
for word in current:
for i in xrange(len(word)):
left, right = word[:i], word[i + 1:]
for j in ... 阅读全帖 |
|
|
i*********7
发帖数: 348 | 15 这一题大部分人应该都知道是用BFS解。
我只是想自己试验一下DFS的解。
DFS解如果要避免TLE，重点在于需要截枝和截枝后的答案更新。
这就是我自己新建一个class和对应的HashMap去记录进行截枝。
我的观念是这个样子的，在遇到重复出现过的节点单词的时候，首先考虑的是这个节点
往下遍历过后是否出现过解，如果没有的话只有两种情况：1，这个节点往下走是没有
解的。（在不变回去的情况下）2.变回去了。 这种情况下都当做无效访问往上一层走。
如果有的话，就比较该节点之前有解的情况下它所居的递归层数是否比当前重复访问的
时候深，如果否，则不更新，如果是，则根据层数差来修正结果。这相当于把之前遍历
过的结果默认放在这一层下面了。
好吧，问题来了。。这个解只能过leetcode 80%的cases。在一个字典很大的case中比
Expected answer多了1. 有没有人能告诉我听我的代码或者逻辑问题出在哪儿了？=。=
class DataSet{
int level, res;
DataSet(){
level = 0;
... 阅读全帖 |
|
c*****e
发帖数: 3226 | 16 public class Solution {
class Record {
Record prev;
String cur;
public Record(Record prev, String cur) {
this.prev = prev;
this.cur = cur;
}
}
public List> findLadders(String start, String end, Set<
String> dict) {
List> r = new LinkedList>();
if (start == null || end == null || dict == null || start.length() =
= 0 || start.length() != end.len... 阅读全帖 |
|
|
c*****e
发帖数: 3226 | 18 leetcode 狗屎，
我把建立新的string 换成 这个就过了： String n = replace(cur, i, c);
private String replace(String str, int index, char c) {
StringBuilder sb = new StringBuilder(str);
sb.setCharAt(index, c);
return sb.toString();
} |
|
c*********w
发帖数: 65 | 19 String.substring 的实现在java 1.7里被改了，本来是 constant time,现在是
linear.
和GC有关。 |
|
j******o
发帖数: 4219 | 20 leetcode这种只要最佳解的做法和国人的心态一样。 |
|
a***a
发帖数: 739 | 21 This rule works for WordLadder, but it is not applicable to BFS in general. |
|
