热气腾腾的纽约狗家面经，估计我是挂了，给后来人积累点经验吧，另外求大米。

zzz6222 发表于 2020-6-9 05:08
Hashset没有get的
只能O(1)查contains
只是set的本质

你的分析是对的，但是楼主并没有要求O(1) get吧

ThinkDeeper2 发表于 2020-6-9 05:23
为什么还要一个set装key。感觉一个装object的就够了。
主要就是COMPARE的时候，比较OBJECT的KEY就可以了 ...

哈哈，因为我没有在newclass里面写getkey（），
按照你这个说法，好像是可以的呢，add的时候，要循环一边所有的元素，然后compare是否存在object的key和value 相同，如果相同，就不加了；key相同value不相同就替换value；key 和value都不存在就新加入一个元素。

julia_b 发表于 2020-6-9 05:27
哈哈，因为我没有在newclass里面写getkey（），
按照你这个说法，好像是可以的呢，add的时候，要循环一 ...

ADD的时候如果, new Oject(string key) equals existing Object with key and value, 就可以直接找到吧。
”然后compare是否存在object的key和value 相同，如果相同，就不加了“
只需要COMPARE KEY 就可以，如果VALUE相同，覆盖就可以了，不用比较VALUE。

ThinkDeeper2 发表于 2020-6-9 05:32
ADD的时候如果, new Oject(string key) equals existing Object with key and value, 就可以直接找到吧。
...

没法直接找到value，必须遍历才能找到

set本质就是用map实现的，value随便填即可
map用set实现实在不懂，你的set只能做3件事情：add，contains，remove。。 我也没看明白你写的，还请赐教

julia_b 发表于 2020/06/09 04:48:35
是啊，居然没有考算法，我拿到题目的时候，一度怀疑我是不是没有睡醒。

我多么希望是道算法题啊，我刷题刷了那么久～～～...

我觉得是不是狗家压根就不想招人了...

克洛伊家 发表于 2020/06/09 05:50:17
set本质就是用map实现的，value随便填即可
map用set实现实在不懂，你的set只能做3件事情：add，co...

不对吧，map和set底层是RB-tree

julia_b 发表于 2020/06/09 04:45:28
好吧，到10颗大米了，谢谢大家， 现在给出我觉得可行的答案哈，面试的人也说是可以的，因为他只要求实现add， conta...

不错的思路，很清楚

克洛伊家 发表于 2020-6-9 05:50
set本质就是用map实现的，value随便填即可
map用set实现实在不懂，你的set只能做3件事情：add，contains， ...

作为map，得要实现四个函数，add，remove，contains，get
add，set<newclass> 里面装的是newclass object，每个object里面保留了K，V pair，每次加入，都需要遍历当前set，比较key，有个旧key，直接替换V，
get，也需要遍历set，比较key，然后返回Value
contain 和remove都是同理

julia_b 发表于 2020/06/09 04:45:28
好吧，到10颗大米了，谢谢大家， 现在给出我觉得可行的答案哈，面试的人也说是可以的，因为他只要求实现add， conta...

用一个hashset装k, v pair就够了 override一下（C++里面unordered_map会要求你自己写hash function）hash&lt; Pair&lt;k, v&gt; &gt; 改成只根据key给hash值 这样就解决了contains(key)的问题

实际在get(key)的时候还是得全遍历一遍才能找到结果

补充内容 (2020-6-8 15:38):
打错，是unordered_set