didi lab new grad oa

滴滴new grad oa，和地里报出来的oa一样的两道题，graph circle和一道prefix sum题。 做完oa之后被拒，听说是隐藏case没过，把代码和思路也发上来，各位给挑挑毛病。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

求加米～

第一题n个点n条变，所以每个点入度和出度都是1，用一个一维数组建图就行，建图过程检查出入度，建完图跑一遍dfs确保只有一个连通块

第二题不用prefix数组，你可以确定一个target value，就是sum(A) / 2，之后逐一累加，只要当前A和B的前缀累加和都等于这个target，cnt就加一，当然累加前可以先判断sum(A) == sum(B)，以及sum(A)是不是偶数，不符合条件直接return 0

我prefix sum那题觉得可能是在accumulate sum的时候要用long int，如果用每一位数字的上限 * array length的上限的话int的位数就不够了

jasonfxuk 发表于 2020-09-01 22:09:30
老哥你第二题是怎么解的，图的那一题，是楼上说的建图的时候直接判断的还是建好图之后用dfs判断？

你想，这题是不是刚好只有一种情况，就是N个点，然后N条边刚好形成一个圈。

我写的好像是，建图的时候顺便看下有没有一对多有就直接false,  然后从第一个点dfs进去，顺便给dfs多个counter参数设置为N，即dfs(1，N），每次进一层就减1，等于0就返回，，。看最后返回的是不是还是1以及访问到所有的点

请问做完多久被拒？

第一题楼主是不是想复杂了，题目中给定N个顶点N条边，在建图的时候就可以查出来吧，不需要dfs了

salvadorsyc 发表于 2020-9-2 06:00
第一题楼主是不是想复杂了，题目中给定N个顶点N条边，在建图的时候就可以查出来吧，不需要dfs了

我看他题目里的hint给的差不多是这个意思

jyyzzj 发表于 2020-9-2 05:38
请问做完多久被拒？

一天之后就悲剧了

同被拒，想不出来 OA 哪里出问题了 =_=

cws2818 发表于 2020-09-01 15:12:23
一天之后就悲剧了

行吧我刚问完你就收到了面试....

jyyzzj 发表于 2020-9-2 11:23
行吧我刚问完你就收到了面试....

老哥你第二题是怎么解的，图的那一题，是楼上说的建图的时候直接判断的还是建好图之后用dfs判断？

jyyzzj 发表于 2020-9-4 01:26
你想，这题是不是刚好只有一种情况，就是N个点，然后N条边刚好形成一个圈。

我写的好像是，建图的时候顺 ...

谢啦