s*****i
发帖数: 355 | 1 为啥不sort，你可以指点一下我嘛，不要这么凶 谢谢
还有一个办法是把字典做成trie map，DFS |
|
v****s
发帖数: 1112 | 2 i vote for trie in problem 4 as well |
|
j**l
发帖数: 2911 | 3 被面到的概率大么？
是递归还是动态规划？要用到trie或者suffix tree么？
谁有简洁清晰的思路？ |
|
r**u
发帖数: 1567 | 4 backtracking, if needs optimization, maybe organize the dictionary to trie
for easy checking valid word. |
|
S******A
发帖数: 1002 | 5 用trie处理字典，递归的时候避免dead end |
|
S******A
发帖数: 1002 | 6 2 is boggle problem
load dic as trie to stop searching immediately upon a dead-end, i guess you
also need to avoid re-using any cell (char) more than once when constructing
a valid word |
|
f****e
发帖数: 30 | 7 I mentioned trie and that guy asked me to implement it. I said I can not
implement it in just 10 min.
Yes, the problem requires that no char can be used more than once when
constructing a valid word.
you
constructing |
|
B*****t
发帖数: 335 | 8 for the 2nd problem, recursion is not efficient.
Trie or AC-Automation is the only choice! Do 8 direction search on them and
need lots of optimizations and some tricks I think. |
|
|
m******9
发帖数: 968 | 10 谢谢分享, 像你所说的,第3个问题可能最大. 他让你现场写trie吗? |
|
a*u
发帖数: 97 | 11 请问这个题的讨论在哪里？
应该是用trie，是不是可以bottom up built只插入那些high frequency word |
|
s******t
发帖数: 2374 | 12 来自主题: JobHunting版 - 一道算法题 可以存trie吧。 |
|
l*********r
发帖数: 26 | 13 来自主题: JobHunting版 - 面经+求助 amazon电话两轮，隔的时间比较长，把记得的题目贴一下
1.java gabage collector, how to work?
2.java, final, finally, finalize()的用法和区别
3. 怎样serialize一个binary tree, general tree(not binary)
4. N way merge sort
剩下主要是简历上面的东西，觉得amamzon的重点就是 scalability,总是问以前的
project如果upgrade scalability会怎么样。
要去onstie, 看到大家以前总是频繁的要求些hashtable, 请问是应该写哪种collision
solutions呢？changing, linear probing? 如果hash string,hash function 就用
ascii码的那个常用方法可以嘛？ 如果是数字，就取 %?
记得以前大家讨论过一个手机键盘输入的pop-up菜单的设计题，好像要写trie， 怎么
也找不到，完全不明白题目的意思，请大侠们指点一下。
回来贴面经:) |
|
g*****u
发帖数: 298 | 14 谢谢楼主！第6题你怎么答的？用trie？如果是设计整个phone book那么应该怎么做？
两个thread，一遍处理用户输入，一边查找？ |
|
|
|
|
|
|
s**9
发帖数: 207 | 20
前缀相同的关键字在Patricia Trie上查找、存储的开销都小。
可不可以建一个指针数组，每个指针指一行？
最后给了近似解， |
|
j**l
发帖数: 2911 | 21 如果题目看过弄懂了，开国大老的题做起来也就和新手上路一样了。
关键是锻炼自己的思维，举一反三。这样在做从没见过的长老级以上的题目时候很有用。
Hash表算中高级站友，就怕问到解决冲突，再Hash的一些细节。
Suffix和trie，弄懂原理也快，就是怕让你实际写个完整代码，据说在面试短短时间是
不够的。 |
|
|
z*j
发帖数: 42 | 23 hashtable or trie tree?
both look up fast. |
|
w******1
发帖数: 520 | 24 trie tree , suffix tree |
|
|
B*****t
发帖数: 335 | 26 bloom filter 好像需要根据字符串的个数才能确定位数组大小和hash的个数，任意无
穷字符串流怎么用bloom filter？
能不能搞个外部的trie？ 也许有更好的方法。
对 |
|
I**********s
发帖数: 441 | 27 没错, 上面blueants说的"根据字符串的个数才能确定位数组大小和hash的个数"也对.
无穷多输入就把整个bit-array都变成1了. 当时面试的GG说的是很大的输入, 似乎没说
无穷. 我也问过trie, 但是他说可能会用很多内存也不合适. |
|
I**********s
发帖数: 441 | 28 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co... 阅读全帖 |
|
|
m*****n
发帖数: 2152 | 30 要是我遇到这种题，就在硬盘上建trie，看谁狠。 |
|
X*********n
发帖数: 570 | 31 但实际上 m总是有限的, 但n可以无数多, 比如说dictionary
所以一般意义上m远小logn |
|
r****o
发帖数: 1950 | 32 谢谢，我没搞明白为什么是lg(n) of m character comparison for BST.
我觉得对于BST就是lg(n)啊. |
|
|
f*********5
发帖数: 576 | 34 lookup for BST is O(lgn)
but pay attention now u want to compare a word each time,
you need to compare the target word with the word in current node
u need to compare each letter of the word... |
|
f*********5
发帖数: 576 | 35 list to BST with O(n)
please refer to DSW algorithm |
|
|
n*****0
发帖数: 133 | 37 如果单词可以放在bst的internal node和leaf node的话
可以根据每个单词的字母排列为node创建一个unique的index
lookup的时候比较node的index就可以了，所以整个过程只需要O(lgn) ，假设树是
balance的
而tire的lookup需要O(m)
所以关键还是单词长度m和单词个数n的关系。
不知道理解的对不对 |
|
|
|
b********h
发帖数: 119 | 40 如果这个unique的index可以创建，那O（1）不就可以找到了（直接index到一个hash
table里），还要bst干嘛？ |
|
a*d
发帖数: 47 | 41 In BST, it is not always exactly m character comparison, however, the deeper
you go down the tree, more likely you will need to compare more characters.
(strings are more similar) |
|
n*****0
发帖数: 133 | 42 嗯 用unique的index,用hash table就可以查询了，O(1)就行了。我想的有点多了。。。
不过unique的index还是要handle overflow的问题。 |
|
j**l
发帖数: 2911 | 43 这些难题要么涉及不容易找到状态转移方程的DP，要么需要想到很巧妙的trick，要么
涉及trie, suffix tree等一些高级的数据结构，不准备的话现场短时间确实很难做出来。
但是这些题只是锦上添花，而且这些题的变体无穷无尽，你不能保证在有限的复习时间中把它们全部都背下来。所以，关键是总结出它们的思想方法而不是背诵题目本身。
就好比高考数学，压轴的大题能做出来最好，但是前面的容易题和中等题，绝对是拿分
的重点。又好比欧洲足球联赛，联赛冠军经常在小四强联赛中拿分不多，但对中下游的
球队几乎不会翻船，总是一场又一场的全取三分。利物浦双杀曼联又如何，平局太多还
是让曼联拿走了冠军。
面试官不问难题不等于不能考察你的能力了，甚至可能要求更苛刻。比如求x的n次方，
能想到利用二进制数得到log(N)的方法么，能想到结合矩阵把结论推广到求菲波纳切数
列么？比如统计句子中单词的个数，能想到只用一重循环的检测脉冲技巧么？再比如求
n的阶乘，能同时想到迭代法，递归法，尾递归法，动态规划法么？能很好的解决
overflow问题么？能否实现大数阶乘么？能否想到如何求出结尾的0的个数么？能否想
到如何求 |
|
N*D
发帖数: 3641 | 44 顶，说出了俺的肺腑之言啊
这些难题要么涉及不容易找到状态转移方程的DP，要么需要想到很巧妙的trick，要么
涉及trie, suffix tree等一些高级的数据结构，不准备的话现场短时间确实很难做出
来。
但是这些题只是锦上添花，而且这些题的变体无穷无尽，你不能保证在有限的复习时间
中把它们全部都背下来。所以，关键是总结出它们的思想方法而不是背诵题目本身。
就好比高考数学，压轴的大题能做出来最好，但是前面的容易题和中等题，绝对是拿分
的重点。又好比欧洲足球联赛，联赛冠军经常在小四强联赛中拿分不多，但对中下游的
球队几乎不会翻船，总是一场又一场的全取三分。利物浦双杀曼联又如何，平局太多还
是让曼联拿走了冠军。
面试官不问难题不等于不能考察你的能力了，甚至可能要求更苛刻。比如求x的n次方，
能想到利用二进制数得到log(N)的方法么，能想到结合矩阵把结论推广到求菲波纳切数
列么？比如统计句子中单词的个数，能想到只用一重循环的检测脉冲技巧么？再比如求
n的阶乘，能同时想到迭代法，递归法，尾递归法，动态规划法么？能很好的解决
overflow问题么？能否实现大数阶乘么？能否想到如何求出结 |
|
r****c
发帖数: 2585 | 45 两个应用不同啊
suffix tree一般用来表达一个或多个string internal, like substring of a string
prefix tree (trie) 只是表达几个strings' substring which starts from
beginning |
|
p********7
发帖数: 549 | 46 4. HashTable 和 Binary Search Tree(BST)的区别，他们的lookup，insert的time
complexity. 之后针对 HashTable 和 BST 分别做了展开：要从电话本中列出一定范围
的人名
（比如某个姓的），要用哪个数据结构？hash。 还谈了些别的应用情境，我记不大清
了。
电话号码典型用trie啊。
谢谢面经 |
|
l*******g
发帖数: 4894 | 47 我也同意用trie，所以confusing为什么是hash？ |
|
K******g
发帖数: 1870 | 48 请问用trie可不可以呢？每个leave结点代表一个完整的URL，它的key可以建立一个
session ID的链表。
这个跟hashtable 和 B tree比起来，怎么样呢。多谢。 |
|
g*******y
发帖数: 1930 | 49 另外一个idea是，把B数组的每个数分解(分解为质数之积)，然后做成一个trie。不过
分解数本来就是hard的问题了，不过我看楼上的方法的复杂度(理论上)也不低 |
|
I**A
发帖数: 2345 | 50 你说的这个减少求HASH的次数是个good point
可是要考虑到建立Trie的复杂性。。。。
我一向比较favor简单的东西。。
aaa |
|
