面试官对我说containsKey的复杂度是O(n) ？

当时面试到手撕代码环节，写完了给面试官看，他问我这个算法的复杂度是多少，我说是O(n)，他说你这用了containsKey，不是O(n^2)吗？我说不啊，containsKey的复杂度是O(1)并且解释了一下，结果面试官坚持说containsKey是要遍历的，复杂度就是O(n)blablabla……把我说的开始怀疑自己了，就没再坚持，于是面试到这儿就结束了。复盘面试的时候听录音听到这再次心生疑惑，于是查了下发现containsKey的时间复杂度确实就是O(1)呀……可惜我面试经验还是太少，当时怂了没敢怼他

#面经#

全部评论

推荐最新楼层

我不叫A-aron

门头沟学院 Java

我好像被问过同样的问题（但不是美团）。我那时候回答的是正常情况下是O(1)，您说的O(n)应该存在于极端情况下例如collision发生后并且因为hashcode的问题所有node都生成同样的hashcode并且处理collision时用的是链表，JDK 1.8后由于采用了红黑树所以当n大于8之后就算出现此类极端情况也只会是O(logn)。

1 回复分享

发布于 2020-04-20 15:45

搬砖的程序员007

门头沟学院 Java

怎么算也算不出来O(n)啊，怼他，让他回去多读读源码😂

1 回复分享

发布于 2020-04-20 15:34

能否来个成都offer

西安交通大学算法工程师

大佬，这样的公司不值得你加入

点赞回复分享

发布于 2020-04-20 15:29

07-11 10:37

大连理工大学机械工程师

百度测评

难怪不开摄像头，全是简单的性格题，比大疆友善多了

NULL10086：今早上发的测评，我这还没做呢，官网上已经显示挂了

投递大疆等公司7个岗位

点赞评论收藏

不愿透露姓名的神秘牛友

07-11 12:31

我从来没想过我会出轨

以前小时候我最痛恨出轨、偷情的人，无论男女，为什么会出轨？现在我成了自己最讨厌的人，没想到分享的东西在牛客会被这么多人看，大家的评价都很中肯，我也认同，想过一一回复，但我还是收声了，我想我应该说说这件事，这件事一直压在我心里，是个很大的心结，上面说了人为什么出轨，我大概能明白了。我们大一下半年开始恋爱，开始恋爱，我给出了我铭记3年的承诺，我对她好一辈子，我永远不会背叛，我责任心太重，我觉得跟了我，我就要照顾她一辈子，我们在一起3年我都没有碰过她，她说往东我就往东，她说什么我做什么，她要我干什么，我就干什么！在学校很美好，中途也出过一些小插曲，比如男闺蜜、男闺蜜2号等等等。但我都强迫她改掉了，我...

牛客刘北：两个缺爱的人是没有办法好好在一起的，但世界上哪有什么是非对错？你后悔你们在一起了，但是刚刚在一起的美好也是真的呀，因为其他人的出现，你开始想要了最开始的自己，你的确对不起自己，21岁的你望高物远，你完全可以不谈恋爱，去过你想要的生活，你向往自由，在一起之后，你要想的不是一个人，而是两个人，你不是变心了，就像你说的，你受够了，你不想包容了，冷静几天是你最优的选择，爱人先爱己。

社会教会你的第一课

点赞评论收藏