吖嘛训 2018/10 New Grad Final Virtual Interview

bycfly 发表于 2018-10-28 15:27
谢谢！！ 第一题hashmap你是怎样optimize, time complexity 怎样解释的？

你要像这样想 worst case是不是全部(k,v)都在同一个bucket里面 所以insert和get的worst case的time complexity是O(N)
怎样optimize (面试的时候没有让我implement，具体讲一讲就行)
可以增加bucket，也可以参考C++里面map的implementation

求问楼主 实现hashmap的k和v的类型是什么呀 只要普通的string，int这样就可以么 还是要支持任意object呀

另外实现hashmap楼主用的啥数据结构存呀QAQ 我的理解是一个存<k,v>的数组 然后实现一下hashCode(), get(), put(), remove()？

point8808 发表于 2018-10-29 05:14
另外实现hashmap楼主用的啥数据结构存呀QAQ 我的理解是一个存的数组 然后实现一下hashCode(), get(), put() ...

我是用Python写 所以我用List of List
首先有List of Bucket, 每个Bucket是List of (k,v) 因为会有hash collision

point8808 发表于 2018-10-29 05:09
求问楼主 实现hashmap的k和v的类型是什么呀 只要普通的string，int这样就可以么 还是要支持任意object呀

你要问清楚面试官这个hashmap存什么<k,v>
然后python里面有个built-in的hash function可以用
detail还是要和面试官讨论 随机应变就行

yhl666 发表于 2018-10-30 07:01
你要问清楚面试官这个hashmap存什么
然后python里面有个built-in的hash function可以用
detail还是要和 ...

好的嘛 蹭蹭楼主的喜气 希望可以顺利通过！！！