20230829得物笔试AK代码

属于经典题型,动态规划、贪心,给的纯白板,自己写

一、 是否存在长度为x的回文子串

二、n栋楼总高度m,每栋楼之间高度差不超过1,求第x栋楼的最高高度

场景题:类似于LCR 033. 字母异位词分组

  1. A和B有相同K个收藏品认为爱好相似
  2. 具有传递性,即AB、AC相似则BC相似。
  3. 求爱好相似的用户(为一个群组),使用伪代码,并描述数据结构和时间复杂度

我的做法(并查集):对每个用户,判断是否和已在群组的用户相似,若相似则加入该用户所在群组

时间复杂度不确定,求讨论

  1. 对每个用户A,判断是否和已在群组的用户B相似
  2. 首先是循环获取两个用户A、B,两层循环就已经是O(n2)
  3. 判断两个用户是否相似
  4. 使用set存储用户的藏品
  5. 计算两个用户相同藏品数量O(n)
  6. 若相似,将A加入B用户所在群组
  7. 并查集union的时间复杂度是多少?
全部评论
并查集的复杂度主要在于findParent,尽量往平衡树去设置A,B的父子关系,查找和合并复杂度都在O(h)或者说O(logn)
1 回复 分享
发布于 2023-08-29 13:16 浙江
第二题的这个思路好巧,我今天用二分,想了半天才把公式推导明白
点赞 回复 分享
发布于 2023-08-30 18:27 辽宁
大佬,能不能解释一下为什么第二题的for循环里,第一次就要-3啊(如果不考虑到边上的情况)
点赞 回复 分享
发布于 2023-08-29 17:21 上海
第一题遍历所有长为x的子串判断是否为回文串,但是一直55%不知道哪里有问题
点赞 回复 分享
发布于 2023-08-29 15:33 浙江
老哥,第二题你的这种写法挺巧妙的,应该属于什么算法?不能算是贪心吧?
点赞 回复 分享
发布于 2023-08-29 14:56 江苏
太强啦大佬❤️❤️
点赞 回复 分享
发布于 2023-08-29 14:20 广东
第一题哪儿要得了这么复杂?
点赞 回复 分享
发布于 2023-08-29 13:31 浙江
第一题一直卡91
点赞 回复 分享
发布于 2023-08-29 13:27 广东

相关推荐

昨天 08:58
已编辑
门头沟学院 Java
ttl: 3.19一面晚上过3.20二面3.23oc3.25offerbase:末9有一段中小厂实习一面面经:(总体时长一个小时二十分钟左右没什么八股,主要都是问项目和场景题1.实习(问了有四十分钟,感觉面试官很看重实习这一块,一直在拷打,问到后面我都要疯了,好在准备得比较充分1️⃣用的是什么中间件,有参与技术选型吗,实习的项目里为什么选这个RabbitMQ而不是kafka,为什么不用RocketMQ,为什么放弃异步,自己的项目里面使用的是kafka,那你觉得项目和实习的中间件选型有差异的原因是什么,他们之间的区别在哪里,底层的原因知道吗(高柱到这里已经快疯了,但是硬着头皮答完了,主要是从一致性吞吐量和框架的契合度答,面试官说答得挺好的,应该是没什么问题,这一块就问了快半个小时,到这里我已经快疯了2️⃣项目怎么对接上下游3️⃣介绍项目的难点重点4️⃣微服务(高柱实习是单体项目没涉及这一块5️⃣Redis的使用2.项目:1️⃣智能客服是怎么应用在项目里的(langchain4j➕rag➕functioncalling)2️⃣RAG了解多少3️⃣文本向量化的难点是什么,了解哪些大模型的知识(我一点不懂,纯瞎扯,但貌似扯对了4️⃣对ai的态度是什么,aicoding相关5️⃣怎么保证多节点下Caffeine缓存里面数据都是一致的(答的是短ttl,面试官不是很满意,但是我确实不太懂这个怎么保证,后来查了还是不懂怎么保证6️⃣Redis的使用,和你的实习项目的使用有区别吗,还有一些引申问题3.八股(含量不高,就是走个过场1️⃣进程的内存布局2️⃣Redis三剑客3️⃣微服务相关知识(高柱已经忘得差不多了…勉强答上来4️⃣JVM5️⃣线程状态6️⃣线程安全,在你的实习项目里怎么保证线程安全的(又绕回来了4.智商题找异常球5.手撕:1️⃣五道sql,不难2️⃣力扣不重叠的滑动窗口数组,贪心➕双指针秒了强度拉满了这个一面,高柱到后面人都是傻的二面面经:(就半个小时实习拷打,简历上写了几点就问了几点,问完就结束了,无手撕
查看19道真题和解析
点赞 评论 收藏
分享
评论
10
43
分享

创作者周榜

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