谷歌电面面经

分享一个前两天的狗家电面面经。只问了一道题。
给你一堆学生成绩的数字成绩（比如99,98,97,96,95,94,93,92,91,90），按照排名转换为A,B,C,D,E的letter grade。前20%得A，20%~40%得B，依次类推。要求必须用贪心法做。
这个例子中就是99, 98的人拿A，97,

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

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

出最小成绩放入B所在的PQ中。不过这样好像必须先知道每个PriorityQueue的大小。
如果有更好的思路还请指教。

另外第一次发面经，求好心人赏大米！

最高分数100分 用长度为100的array 做bucket sort 然后从高往低assign grade 复杂度为哦哦夫嗯加一百 也就是哦哦夫嗯

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

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

建一个hashmap，key是分数，value是比这个分数大的分数的个数 v，loop through map，每次用v和分数总个数比看这个分数在哪个区间得出grade。 时间空间都是O（n）？

用priority queue的话也是nlogn的复杂度呀？跟排序比有什么优势呢？
想不出来有什么O(n)的方法。

第一种方法可不可以排序之后按百分比计算然后check这个letter grade的最后一个分数，把相同分数的人全部算作这个letter grade？

pengdu 发表于 2019-1-16 12:21
用priority queue的话也是nlogn的复杂度呀？跟排序比有什么优势呢？
想不出来有什么O(n)的方法。

面试官说要用贪心的做法。排序在这里好像体现不出贪心？

请问这个在leetcode上有吗

感觉用priorityqueue也有问题啊，比如5个100分，如果第一个pq溢出了，你随便pop一个出来也不对啊

Euromms9341 发表于 2019/01/16 15:04:02
请问这个在leetcode上有吗

我面完后找了下，好像没有

感觉bucket sort之后在倒序算letter很合理
但是想问如何体现贪心啊？