giftcards点com的vgc还能买mo吗？# Money - 海外理财
a*2
1 楼
原来的面经是:
*****************************************************
设计一个Map，满足下面的复杂度。
add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of
elements)。
提示：
如果我们用randomly accessed array，复杂度如下：
add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate:
O(size of array)
如果我么用sequential array, 复杂度如下：
add: O(1) deletion: O(number of elements) lookup:O(number of elements)
clear: O(1) iterate:O(number of elements)
所以我们需要把这两个方法整合起来。
*******************************************************
很显然这道题要用到hash table,但是一般而言，hash table的clear(删除整个table)
需要O(n), 怎么做到O(1)的clear呢？
*****************************************************
设计一个Map
add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of
elements)。
提示：
如果我们用randomly accessed array，复杂度如下：
add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate:
O(size of array)
如果我么用sequential array, 复杂度如下：
add: O(1) deletion: O(number of elements) lookup:O(number of elements)
clear: O(1) iterate:O(number of elements)
所以我们需要把这两个方法整合起来。
*******************************************************
很显然这道题要用到hash table,但是一般而言，hash table的clear(删除整个table)
需要O(n), 怎么做到O(1)的clear呢？
