Z*****Z
发帖数: 723 | 1 1面：
1、introduce yourself
2、why amazon
3、BST和Hashtable的比较，有什么区别
4、一个integer array，找sum为1给定值的pair（这个题有2种做法，sort和hashtable
，2个都提了一下，就跳过了）
5、手机上给了电话号码求人名索引，提了hashtable，不满意，提示说手机上，空间很
小。又提prefix tree，满意，coding。犯了个小错误，每个树节点的孩子应该用array
存，我用了个list，被指出这样影响复杂度。
2面：
1、一个integer array，只有一个数出现1次，剩下的都出现2次，找到那个特殊的。问
了3种解法。
解法1：XOR。问复杂度，O（N）
解法2：hashtable。问hashtable 的size。（N-1）/2+1。他说对，同时N/2+1也是对的
，为什么？答：因为N永远为奇数。
解法3：sorting，复杂度
2、详细比较ArrayList和LinkedList的实现，优缺点。
3、设计parking lot。（这个不是OOD问题）
3.1 只有1个valet，这个系统如 |
r****o
发帖数: 1950 | 2 多谢。想问两个问题:
1. 像字符串索引这样的题目什么时候用prefix tree好，什么时候用suffix tree好呢?
2. 一个integer array，只有一个数出现1次，剩下的都出现2次，找到那个特殊的。
为什么hashtable大小是(N-1)/2+1呢? 如果array里面的数可以任意，不局限于[1..n]
，这个hashtable的大小还是(N-1)/2+1吗？
[在 ZhangBZ (向日葵) 的大作中提到: 】
hashtable
array |
h**k
发帖数: 3368 | 3 prefix 一定是要从头开始匹配，而suffix允许从字符串的任何一个位置开始匹配。
所以prefix相当于generalized suffix tree的边的一个子集。
呢?
【在 r****o 的大作中提到】
: 多谢。想问两个问题:
: 1. 像字符串索引这样的题目什么时候用prefix tree好，什么时候用suffix tree好呢?
: 2. 一个integer array，只有一个数出现1次，剩下的都出现2次，找到那个特殊的。
: 为什么hashtable大小是(N-1)/2+1呢? 如果array里面的数可以任意，不局限于[1..n]
: ，这个hashtable的大小还是(N-1)/2+1吗？
: [在 ZhangBZ (向日葵) 的大作中提到: 】
: hashtable
: array
|
a*d
发帖数: 47 | 4 I think the "upper limit" of the size of hashtable is N/2 +1.
Because duplicate keys appear exactly twice, when looking up, there is hit,
I can delete the item from hash.
Therefore, depends on the order of items, my hashtable could be smaller that
N/2 + 1.
Also depends on the hash function, not all slots may be used.
hashtable
array
【在 Z*****Z 的大作中提到】
: 1面：
: 1、introduce yourself
: 2、why amazon
: 3、BST和Hashtable的比较，有什么区别
: 4、一个integer array，找sum为1给定值的pair（这个题有2种做法，sort和hashtable
: ，2个都提了一下，就跳过了）
: 5、手机上给了电话号码求人名索引，提了hashtable，不满意，提示说手机上，空间很
: 小。又提prefix tree，满意，coding。犯了个小错误，每个树节点的孩子应该用array
: 存，我用了个list，被指出这样影响复杂度。
: 2面：
|
r****o
发帖数: 1950 | 5 我觉得hash function的选择是一个问题。
如果这1到N个数是随机分布的话，怎么把这些数map到大小为N/2+1的hashtable里面去
呢？
,
that
【在 a*d 的大作中提到】
: I think the "upper limit" of the size of hashtable is N/2 +1.
: Because duplicate keys appear exactly twice, when looking up, there is hit,
: I can delete the item from hash.
: Therefore, depends on the order of items, my hashtable could be smaller that
: N/2 + 1.
: Also depends on the hash function, not all slots may be used.
:
: hashtable
: array
|
s********l
发帖数: 998 | 6 5、手机上给了电话号码求人名索引，提了hashtable，不满意，提示说手机上，空间很
小。又提prefix tree，满意，coding。犯了个小错误，每个树节点的孩子应该用array
存，我用了个list，被指出这样影响复杂度。
请问一下
你这个prefix tree是对电话号码做的？
在这个tree的每个叶子上连着人名？
hashtable
array
【在 Z*****Z 的大作中提到】
: 1面：
: 1、introduce yourself
: 2、why amazon
: 3、BST和Hashtable的比较，有什么区别
: 4、一个integer array，找sum为1给定值的pair（这个题有2种做法，sort和hashtable
: ，2个都提了一下，就跳过了）
: 5、手机上给了电话号码求人名索引，提了hashtable，不满意，提示说手机上，空间很
: 小。又提prefix tree，满意，coding。犯了个小错误，每个树节点的孩子应该用array
: 存，我用了个list，被指出这样影响复杂度。
: 2面：
|
s******i
发帖数: 44 | |
Z*****Z
发帖数: 723 | 8 嗯，我的每个节点都有个data字段，只不过叶子上是人名，非叶子上是null
array
【在 s********l 的大作中提到】
: 5、手机上给了电话号码求人名索引，提了hashtable，不满意，提示说手机上，空间很
: 小。又提prefix tree，满意，coding。犯了个小错误，每个树节点的孩子应该用array
: 存，我用了个list，被指出这样影响复杂度。
: 请问一下
: 你这个prefix tree是对电话号码做的？
: 在这个tree的每个叶子上连着人名？
:
: hashtable
: array
|
Z*****Z
发帖数: 723 | 9 借你吉言，现在还在等消息，呵呵
【在 s******i 的大作中提到】
: bless... 我觉得还是有希望的
|
s********l
发帖数: 998 | 10 你这data存的是到目前为止的数字？
如果定义root为0层 那么
比如第三层的某个节点data存的 是808
这样子？
“非叶子上是null”？
你这是说 每个节点 还有个char * ?
【在 Z*****Z 的大作中提到】
: 嗯，我的每个节点都有个data字段，只不过叶子上是人名，非叶子上是null
:
: array
|
|
|
s********l
发帖数: 998 | 11 bless lz~ //刚才忘说了:P
你的parking lot的设计不就是ood嘛？ |
f*********5
发帖数: 576 | 12 i want to confirm that whether the request of this issue is as below:
要求每输入一个数字，显示出所有可能的人名，
接着输入下一个，更新所有可能的人名。。
【在 Z*****Z 的大作中提到】
: 嗯，我的每个节点都有个data字段，只不过叶子上是人名，非叶子上是null
:
: array
|
f*********5
发帖数: 576 | 13 关于你这个design题的回答，我看得还是很困惑的。。。
3.2 有多个valet，有什么最简单的优化方案？
关于什么的优化方案，关于空位search算法？
hashtable
array
【在 Z*****Z 的大作中提到】
: 1面：
: 1、introduce yourself
: 2、why amazon
: 3、BST和Hashtable的比较，有什么区别
: 4、一个integer array，找sum为1给定值的pair（这个题有2种做法，sort和hashtable
: ，2个都提了一下，就跳过了）
: 5、手机上给了电话号码求人名索引，提了hashtable，不满意，提示说手机上，空间很
: 小。又提prefix tree，满意，coding。犯了个小错误，每个树节点的孩子应该用array
: 存，我用了个list，被指出这样影响复杂度。
: 2面：
|
z****n
发帖数: 1379 | 14 应该是打一个c，就输出所有名字c开头的record，打一个ca，就输出所有名字ca开头的
record，record里当然包括电话号码，换句话说，用人名做索引（key），这个跟真实手
机contact里的查找功能一样。
我关心的是它让你coding是写怎么建prefix树，还是建好了怎么用？
【在 f*********5 的大作中提到】
: i want to confirm that whether the request of this issue is as below:
: 要求每输入一个数字，显示出所有可能的人名，
: 接着输入下一个，更新所有可能的人名。。
|
Z*****Z
发帖数: 723 | 15 是这样的，每个节点有个char digit成员，还有个String data成员，digit存的是数字
，data存的是数据：）
【在 s********l 的大作中提到】
: 你这data存的是到目前为止的数字？
: 如果定义root为0层 那么
: 比如第三层的某个节点data存的 是808
: 这样子？
: “非叶子上是null”？
: 你这是说 每个节点 还有个char * ?
|
Z*****Z
发帖数: 723 | 16 没有没有，要是这样的话，那个hashtable也不work吧。他就是想，给了个phone numbe
r，求人名
【在 f*********5 的大作中提到】
: i want to confirm that whether the request of this issue is as below:
: 要求每输入一个数字，显示出所有可能的人名，
: 接着输入下一个，更新所有可能的人名。。
|
Z*****Z
发帖数: 723 | 17 他要找的优化方案很简单，就是选最近的停车位。这样一个valet可以尽快的完成停车任
务，回到入口，服务下一个人。
至于空车位搜寻算法，在这个问题里不是重点。因为停车位是个常数，用brute force算
法也是常数时间。
btw：我遇到的这个parking lot问题看起来很open，说什么都可以。但是他有明确的想
要听的东西。
【在 f*********5 的大作中提到】
: 关于你这个design题的回答，我看得还是很困惑的。。。
: 3.2 有多个valet，有什么最简单的优化方案？
: 关于什么的优化方案，关于空位search算法？
:
: hashtable
: array
|
Z*****Z
发帖数: 723 | 18 两个函数，一个建树，一个查询，都写了。
实手
【在 z****n 的大作中提到】
: 应该是打一个c，就输出所有名字c开头的record，打一个ca，就输出所有名字ca开头的
: record，record里当然包括电话号码，换句话说，用人名做索引（key），这个跟真实手
: 机contact里的查找功能一样。
: 我关心的是它让你coding是写怎么建prefix树，还是建好了怎么用？
|
w*****1
发帖数: 245 | |
Z*****Z
发帖数: 723 | 20 强烈建议你自己练习一下。核心代码就是一个loop，6、7行就能搞定
【在 w*****1 的大作中提到】
: 建树好像挺复杂的, 有什么好的学习资源吗?
|
|
|
z****n
发帖数: 1379 | 21 实现trie的方法太多了，其实关键就是选什么结构表示trie的每个节点
比较常规的就是用个Node[]表示所有可能的children（如果key是小写字母string这个数
组大小就是26，如果key是数字串这个数组大小就是10).再用一个field表示这个这个节
点是不是表示了某个key的结束;还需要一个field存与key对应的value
节点的数据结构想好了，建树时候无非就是递归调用addNode函数，填好节点的每一个f
ield，就比较容易了，跟普通建树差不多
【在 w*****1 的大作中提到】
: 建树好像挺复杂的, 有什么好的学习资源吗?
|
y*c
发帖数: 904 | 22
请给一个reference好么？那里可以找到这个核心代码，谢谢
【在 Z*****Z 的大作中提到】
: 强烈建议你自己练习一下。核心代码就是一个loop，6、7行就能搞定
|
h**6
发帖数: 4160 | 23 电面考prefix tree啊，这种东西我只懂理论，从未实践，看来还是需要练习一下的了
。 |
c******f
发帖数: 2144 | |
Z*****Z
发帖数: 723 | 25 玩儿code jam的，这个是小case :D
【在 h**6 的大作中提到】
: 电面考prefix tree啊，这种东西我只懂理论，从未实践，看来还是需要练习一下的了
: 。
|
