google new grad OA

OA有两题coding
1) 浇花
有一个水桶容量是C，每朵花需要的水量是Ai(1<=i<=N)，i=0是补水站
需要依序浇水，如果水桶剩余水量不够就必须i=0补水
一开始在i=0，问浇完所有花的最少移动步数
sample:
C = 3, A = [2, 2, 1, 1

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

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

8/27  recruiter寄application invitation，当天收到OA并完成
8/30  recruiter通知约onsite

allenwhale 发表于 2019-9-1 00:06
直接照着规则模拟就好
从第一朵花开始遍历，可以浇花就浇花，剩余水量不够就回去补水

你描述的似乎是贪心算法？那举个例子，1 2 2，c=4，贪心的结果是0-1-2-0-3，这个步数是7，不是最少的步数呀

lz 没有电面吗 好厉害，为什么可以没有电面呀

LZ有Google OA的整理吗？看地里new grad的OA好像很少
感激不尽～！

楼主第二题怎么做呀

Nebulus 发表于 2019/08/31 15:23:54
楼主第二题怎么做呀

先统计一下每个数字出现的次数判断是否有解
有解的话就直接数一下要翻几次就好

请问楼主的时间线，谢谢

hulei125 发表于 2019/08/31 16:56:33
请问楼主的时间线，谢谢

咦 我写在帖子的最后面了啊

没有店面直接onsite？

感觉第二题就是模拟暴力，找最小。应该是O（n）解法。将x从1遍历到6，判断A[i] B[i] 是否都有x，然后遍历AB，如果两组任意一组有x，判断一下翻转次数，记录就OK了。

1. ret = 100000
   
2.         for x in range(1, 7):
   
3.             ca = cb = 0
   
4.             for i in range(len(A)):
   
5.                 if A[i] != x and B[i] != x:
   
6.                     break
   
7.             else:
   
8.                 for i in range(len(A)):
   
9.                     if A[i] != x:
   
10.                         ca += 1
    
11.                     if B[i] != x:
    
12.                         cb += 1
    
13.                 ret = min(ca, cb)
    
14.                 return ret
    
15.         return -1

复制代码

谢谢分享

可以问一下第一题怎么个思路吗？怎么求到最小呢？

第一个dp，第二个贪心，lc1007