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

当时面试到手撕代码环节,写完了给面试官看,他问我这个算法的复杂度是多少,我说是O(n),他说你这用了containsKey,不是O(n^2)吗?我说不啊,containsKey的复杂度是O(1)并且解释了一下,结果面试官坚持说containsKey是要遍历的,复杂度就是O(n)blablabla……把我说的开始怀疑自己了,就没再坚持 ,于是面试到这儿就结束了。复盘面试的时候听录音听到这再次心生疑惑,于是查了下发现containsKey的时间复杂度确实就是O(1)呀……可惜我面试经验还是太少,当时怂了没敢怼他#面经#
全部评论
我好像被问过同样的问题(但不是美团)。我那时候回答的是正常情况下是O(1),您说的O(n)应该存在于极端情况下例如collision发生后并且因为hashcode的问题所有node都生成同样的hashcode并且处理collision时用的是链表,JDK 1.8后由于采用了红黑树所以当n大于8之后就算出现此类极端情况也只会是O(logn)。
1 回复 分享
发布于 2020-04-20 15:45
怎么算也算不出来O(n)啊,怼他,让他回去多读读源码😂
1 回复 分享
发布于 2020-04-20 15:34
大佬,这样的公司不值得你加入
点赞 回复 分享
发布于 2020-04-20 15:29

相关推荐

04-08 23:14
已编辑
南阳理工学院 算法工程师
本人情况:26届双非本科,两段实习经历,目前拿到的都是实习的offer,一个校招的都没有,他们都说先实习,然后等拿到毕业证了直接转正,我又害怕干三个月给我叉出去面试题也发一下吧### 杭州问尔信息技术后端登录你是怎么做的?JWT令牌你了解过吗?他虽然是一段字符串,他表达了什么东西?怎么解析出来信息和过期时间?JWT令牌怎么续期?如果我拉黑一个账号,要怎么做?两种方案(有无redis)mongodb和mysql的区别?mongodb和mysql分别实用于什么项目?选型你会怎么选?数据库的事务,那些地方需要使用,那些地方不需要使用?他会影响什么性能?mysql和pgsql有什么差异你知道吗?消息队列 redis也有,为什么要用mq?前后端会部署吗?docker会用吗?内部通信前端 async和 await你知道吗?异步编程的原理是什么?vue3 为什么你改变一个字符串 前端会跟着改动AI工具会用什么?你会怎么用?### 仲财通常用的锁有哪些synchronize和ReentrantLock的区别分布式锁了解吗?分布式事务mysql表字段sql优化什么时候用索引索引什么时候会失效mysql事务ioc一些项目应用问题### 观妙科技项目问题...zset的架构是什么样子的线程池突然队列被打满了怎么办?如果上游和下游都无法控制,该怎么维护select * from user where age>20 order by update_time 索引设计检索过程是什么样的冒泡排序和快排,有什么区别怎么判断链表有没有环### 观妙科技-二面项目部分...线程池的核心参数有哪些你是怎么用线程池的JMMG1模型跳表介绍一下平衡二叉树TCP为什么要三次握手?说一下hashmap红黑树的特征你有什么学习的方法
牛马人的牛马人生:对学院本而言很强了
点赞 评论 收藏
分享
05-15 14:58
已编辑
南昌航空大学科技学院 C++
mcart:上海150怎么活,睡公司吗
点赞 评论 收藏
分享
评论
4
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务