3.25美团算法笔试

a了3.18,那个0.18自认为思路没问题,自测也没问题,不知道为什么只对了0.18

python版本代码如下:

第一题

数火车,其实就是一个栈,给一个入栈顺序,一个出栈顺序,问你这种情况是不是可能的

T = int(input())

for _ in range(T):

    flag = True

    n = int(input())

    x_list = list(map(int, input().split()))

    y_list = list(map(int, input().split()))

    def is_possible_order(x_list, y_list):

        stack = []

        i = 0

        for x in y_list:

            while not stack or stack[-1] != x:

                if i == len(x_list):

                    return False

                stack.append(x_list[i])

                i += 1

            stack.pop()

        return True if not stack else False

    flag = is_possible_order(x_list, y_list)

    if flag is True:

        print('Yes')

    else:

        print('No')

第二题

糖果美味值

经典动态规划,就是看现在这个选不选。这个选了,意味着前两个都不能选了,所以是a[i]+dp[i-3],如果不选,那就等于选到前面为止的美味值即dp[i-1]

n = int(input())

a = [int(x) for x in input().split()]

dp = [0] * n

dp[0] = a[0]

dp[1] = max(a[1], a[0])

dp[2] = max(a[2], a[0], a[1])

for i in range(3,n):

    dp[i] = max(dp[i-3] + a[i], dp[i-1])

print(dp[n-1])

第三题

也是很经典的动态规划,就是不知道为什么只a了18%,这个dp就是现在能拿几块巧克力,dp[?]这个?是当前背包的容量,每选一个,就要减去当前巧克力的重量(cho[i]^2),同时多一个巧克力

import sys

n, m = map(int, sys.stdin.readline().strip().split())

cho = list(map(int, sys.stdin.readline().strip().split()))

ask = list(map(int, sys.stdin.readline().strip().split()))

bagsize = max(ask)

dp = [0] * (bagsize + 1)

for i in range(n):

    for j in range(bagsize, cho[i] * cho[i]-1, -1):

        dp[j] = max(dp[j], dp[j-cho[i] * cho[i]] + 1)

res = []

for i in range(m):

    print(dp[ask[i]])

第四题

给一个字符串,以分号分割。每个key=value当做一个键值对存到字典里。给一串字符串查找,如果没有这个key输出empty,如果有一个就输出value,如果有多个就输出最新的(可以直接覆盖,这样找到的就是最新的)。唯一要注意的就是直接按照“;”分割会导致最后多一个空字符串,删了就可以

S = list(input().strip().split(';'))[:-1]

dic_ = {}

for i in S:

    left, right = i.split('=')

    dic_[left] = right

q = int(input())

for _ in range(q):

    q_str = input().split()

    if q_str[0] not in dic_:

        print('EMPTY')

    else:

        print(dic_[q_str[0]])

#我的实习求职记录##软件开发2023笔面经#
全部评论
第三题,直接排序先取小的,所以整成前缀和,用二分做,毕竟人家不是说了背包最大1e18么,这玩意多大心里没数么?
3 回复 分享
发布于 2023-03-25 23:34 青海
正解应该是排序,排序之后前缀和二分把,第一时间想到了背包好像不太行
点赞 回复 分享
发布于 2023-03-26 00:32 江西
纳尼,第四题我就这里q_str = input().split() 没有用split(),我只过了18%,淦!
点赞 回复 分享
发布于 2023-03-26 10:10 福建
第三题贪心算法,排序一下就行
点赞 回复 分享
发布于 2023-03-26 17:05 江苏

相关推荐

9.14一面介绍项目项目中的ETL项目中的拉链表项目中的UDF项目中的Kmeans和DBSCAN八股说一下HDFS说一下进程和线程说一下数据倾斜说一下kafka说一下数仓的建模(雪花,星形,星座)说一下数仓分层的作用OLAP和OLTP的区别说一下数据库三范式手撕两道SQL手写冒泡排序(一面全部答出来了)9.18二面,二面感觉很考验对大数据的理解介绍项目项目中感觉做的最好的地方是哪些介绍一下中国软件杯的比赛你觉得你的项目和比赛在哪些地方体现出了大数据的思路讲讲你对大数据的理解讲讲你对数仓分层的理解讲讲你对数据仓库和数据库的区别的理解数仓和数据库都是SQL Boy, 你对两个SQL Boy的区别的理解有没有用过Doris和clickhouse(没有)说一下LSM Tree说一下Bit Map我看你项目里有lambda框架,讲一下lambda框架说一下Hive中的去重说一下模糊去重(这是真的不会。。。)说一下Kmeans和KNN的区别讲一下Java的集合框架手撕力扣原题,二叉树的层序遍历反问9.23 HR面介绍一下你自己为什么选择大数据你是保研的,你的成绩排名是多少为什么不选择考公或者读博你认为现在公司需要什么样的人才你在秋招的时候是怎么介绍自己的你自己有什么优势(疯狂推销自己,我学习能力强)你说你学习能力强,怎么体现出来的(幸亏我脑子转的快,答上来了)两道场景题1.你入职后,你的师傅负责带你学习,但是刚过了一周,你的师傅被紧急抽调了。这种情况下你如何学习技术。2.入职后,有人得到了晋升,而你没有。但是你感觉你自己的付出不少于他们。你会怎么做。反问9.26 oc #美团求职进展汇总#
点赞 评论 收藏
分享
09-29 17:39
已编辑
门头沟学院 Java
BG:双9,一段携程后端实习【流程】9.7笔试,9.26一面 9.29二面【一面】自我介绍实习项目介绍及问题延申:责任链设计模式;模版模式;模板方法为啥要抽象出来;redis库存管理decr和加锁;redis setnx用的k-v是啥;setnx会有并发效率很低的问题吗,有更好的改进效率的方案吗;redis 超时失败如何处理;redis中不知道是不是执行成功是抛异常还是继续流程;为什么用kafka不用其他的消息队列;kafka消息丢失怎么办;压测怎么测试流量;非科班一般遇到计算机领域的知识不懂怎么解决部分八股:threadlocal的原理,key和value是什么;hashmap的初始化大小,扩容机制是怎样的,为什么扩容得是原来的2倍;java集合;final,finally和finalize;操作数组时如何边遍历边移除;死锁的发生的必要条件和手段;手撕一道:重排链表,双指针做的,问有没有无需额外空间的做法(左右部分逆序 找中点)额外:为什么想做后端开发;抗压能力强的例子;付出了很多但是结果不符合预期怎么办是一位很温柔的小姐姐,体验感很好~【二面】自我介绍实习项目介绍 实习里遇到比较困难的点 主要是对具体所做一些业务的延伸 大概快半小时线程池的原理线程池核心线程数是5 任务执行完线程状态是什么 这个时候如果有新的任务提交应该怎么执行主线程提交任务整体流程手撕一道伪代码的题热点数据获取,10s内出现1000次的数据视为热点数据,如果缓存有数据直接读缓存,缓存没有直接读数据库应该是部门的负责人,感觉很多技术深度问的比较多,人很友善,一开始手撕思路写错了还提示了一下🥹
点赞 评论 收藏
分享
6 24 评论
分享
牛客网
牛客企业服务