c**y
发帖数: 172 | 1 AMZ 两轮店面
第一轮：
1.实现一个hash函数，输入string，输出一个hash值。
考虑复杂了，面试官提示说不用考虑太复杂的hash函数实现。
2.实现一个hash table用来存储strings。
这个后来用STL的map做的。
第二轮：
1.口述array, linked list, binary tree, hash table的区别和特点
随便说了说，这个问题被不同的公司问过好多次了。
2.给定一个binary tree，判断是不是一个binary search tree
google一下，网上有比较好的code，很简单，用recursive方法
3.实现a deck of cards class，具体要求实现两个函数(1) DealACard (2) Shuffle
DealACard就是从当前deck中抽取一张card，怎么抽自己定义，我就说从top抽
Shuffle就是洗排。
两个面试官都很nice。 |
H**d
发帖数: 152 | |
h********m
发帖数: 116 | 3 array, linked list, binary tree, hash table的区别和特点
array和linked list区别还好说，这个binary tree怎么比较呢？感觉完全不是一类东
西啊？能不能就说可以用前两者来表示？ |
c**y
发帖数: 172 | 4 我的回答主要从dictionary operations的角度出发的。分别回答了这四种数据结构在
search, insert, delete操作下的算法复杂度。另外附加了memory consumption的讨论。
binary tree通常用来和hash table比较。binary tree的traversal比hash table方便
一些。另外虽然hash table的上述操作都是O(1)，但是suffer的collision问题。
binary tree可以扩展到binary search tree
哦，如果知道在计算机系统里什么是用binary tree和hash table实现的好像更能
impress面试官。是不是文件系统就是binary tree做的？
【在 h********m 的大作中提到】
: array, linked list, binary tree, hash table的区别和特点
: array和linked list区别还好说，这个binary tree怎么比较呢？感觉完全不是一类东
: 西啊？能不能就说可以用前两者来表示？
|
r******n
发帖数: 363 | |
c**y
发帖数: 172 | 6 还没有onsite呢。
问了能不能onsite自己租车，没有什么确定的回复
【在 r******n 的大作中提到】
: offer到手没？
|
l*******g
发帖数: 4894 | 7 Try to think more.
why hashmap would cause collision and how to save a binary tree in memory.
Good luck!
论。
【在 c**y 的大作中提到】
: 我的回答主要从dictionary operations的角度出发的。分别回答了这四种数据结构在
: search, insert, delete操作下的算法复杂度。另外附加了memory consumption的讨论。
: binary tree通常用来和hash table比较。binary tree的traversal比hash table方便
: 一些。另外虽然hash table的上述操作都是O(1)，但是suffer的collision问题。
: binary tree可以扩展到binary search tree
: 哦，如果知道在计算机系统里什么是用binary tree和hash table实现的好像更能
: impress面试官。是不是文件系统就是binary tree做的？
|
c**y
发帖数: 172 | 8 Can you give some hint on how to save a binary tree in memory?
【在 l*******g 的大作中提到】
: Try to think more.
: why hashmap would cause collision and how to save a binary tree in memory.
: Good luck!
:
: 论。
|
