由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 请教一道面试题
相关主题
请教一道数据结构的设计题两个面试题
Pure Storage面经又一道linkedin题
请问pure storage 的那道map 数据结构题问道题目 Map的iterator
问一道F家面试题Java 面试关于map 和set
请教个面经里的设计题请教个面试题, tree和hashmap的区别
一个实际碰到的问题请教一道LinkedIn面试的经典题
请教个面试题gg面试题
Amazon常见设计题——设计电话簿求解攒人品,twitter二面面经
相关话题的讨论汇总
话题: clear话题: elements话题: array话题: iterate话题: deletion
进入JobHunting版参与讨论
1 (共1页)
a*********2
发帖数: 187
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呢?
p*****2
发帖数: 21240
2
这个HashMap为什么不行?clear再生成一个新的instance不行吗?留给GC解决。
a*********2
发帖数: 187
3
Hashmap的存储必须要是连续空间,才可以直接clear掉吧? 如果有conflict,每个
cell里面是一个linkedlist,那应该得一个cell一个cell的clear,不能直接clear掉
hashtable吧?

【在 p*****2 的大作中提到】
: 这个HashMap为什么不行?clear再生成一个新的instance不行吗?留给GC解决。
t********5
发帖数: 522
4
我也觉得直接remove reference让referenceCount = 0就行了
p*****2
发帖数: 21240
5
直接扔掉就行了

【在 a*********2 的大作中提到】
: Hashmap的存储必须要是连续空间,才可以直接clear掉吧? 如果有conflict,每个
: cell里面是一个linkedlist,那应该得一个cell一个cell的clear,不能直接clear掉
: hashtable吧?

c*****m
发帖数: 271
6
这个想法真可以

【在 p*****2 的大作中提到】
: 这个HashMap为什么不行?clear再生成一个新的instance不行吗?留给GC解决。
1 (共1页)
进入JobHunting版参与讨论
相关主题
攒人品,twitter二面面经请教个面经里的设计题
google 面试题疑问一个实际碰到的问题
请教一个新鲜算法面试题请教个面试题
问一个狗狗的OnSite题Amazon常见设计题——设计电话簿求解
请教一道数据结构的设计题两个面试题
Pure Storage面经又一道linkedin题
请问pure storage 的那道map 数据结构题问道题目 Map的iterator
问一道F家面试题Java 面试关于map 和set
相关话题的讨论汇总
话题: clear话题: elements话题: array话题: iterate话题: deletion