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呢?