热乎乎的Petuum实习一面面经

海投的Petuum software internship职位，第一次phone screening，用skype打的电话。
1. 题目和地里的一样，也是给一个String, 求每个char的frequency，但要根据descending排序。我就是把

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

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

de 347啊。。。。。。。真是笨死了。。。还是题没刷熟

补充内容 (2018-1-12 03:58):
面的这么差，还居然收到下一轮面试了。。。

Null1122 发表于 2017-12-17 06:50
感谢楼主分享，请问follow-up什么思路

sorry回复晚了，一直没看到。

你们都很聪明，基本思路很类似count sorting。

假设: "aaabbc"
那么map是{a : 3, b : 2, c : 1}
所以直接就是：建立int[] arr
arr[1] = 'c';
arr[2] = 'b';
arr[3] = 'a';
当然这是没有duplicate的简化情况。

其实这种trick很常见的。比如涉及到26个字母a-z的时候，我过去也经常做array[char - 'a'] = XX 这种事情

但我当时说“禁止使用sort“的时候我直接懵逼了，压根想不到这个方法 (还是怪我刷题没刷熟练)；我说我可以用priorityqueue，但那个本质也是sort啊。 然后他说他的意思是，请做O(n)。。。然后那个小哥很好，一直擦边说，你想想use memory to boost speed....或者你看all these numbers have constraint ..最后终于在他各种暗示提醒下，才终于开窍。。。大概写了一下code就结束了。

我觉得还是我题刷的不够熟练。另外leetcode上sort的题比较少，我至今只要听到sort就很心虚，然后思路就乱了。

希望能帮到大家。

先算出frequency，follow up本质上是用O(N)时间排序总和为N的若干个大于0的数，用insertion sort + amortized analysis, charge each comparison to the larger number. Assuming there are no duplicates, the i-th largest number is at least i and will be charged at most i times, so the total cost is at most the sum.

xutopia 发表于 2017-12-17 07:48
先算出frequency，follow up本质上是用O(N)时间排序总和为N的若干个大于0的数，用insertion sort + amortiz ...

我觉得层主的想法其实就是counting sort吧？不知道我理解的对不对。http://www.geeksforgeeks.org/counting-sort/

感谢楼主分享，祝好运

感谢楼主分享，请问follow-up什么思路

counting sort 也行吧
先算出一个map，然后基于freq对map entry做counting sort

oneexy 发表于 2017-12-17 08:41
我觉得层主的想法其实就是counting sort吧？不知道我理解的对不对。http://www.geeksforgeeks.org/counti ...

差不多就是这个意思。。请看我刚才发的解释

biomedicineman 发表于 2017-12-18 12:30
sorry回复晚了，一直没看到。

你们都很聪明，基本思路很类似count sorting。

谢谢楼主喔！

是451....