a********r
发帖数: 217 | 1 面的是Relevance algorithm engineer职位，两题，烙印面试官，估计挂了。
第一题，是给定array of int，A， 均匀分布到n个buckets，每个buckets里面的数目
是多少。基本就是bucket sort，思路比较容易，找出max 和min， 然后分割为n个
buckets，统计每个bucket里面个数。
第二题，是第一题的一个延伸，问如果每个buckets的上下届是给定的，怎么来求每个
buckets里面的count的。
例如，array A is
1, 200, 52, 2, 4, 1003
bucket的范围为，
1---100
101-- 1000
1001--2000
那么就等价于给你一个range vector, 表示每个bucket的下界， i.e. {1, 101, 1001}
问此时怎么求每个bucket里面元素的个数。
我当时的想法是，对每个array 里面的number，做binary search找出它属于那个
bucket，然后count，然后感觉是不是要sort array，会有帮助，讨论了一会儿，只是
意识到sort array可以把下次binary search的范围缩小。还没有来得及深入想，时间
就不够了，于是只写了这个binary search子程序。 不知道大家有什么好的想法没有？
面试完我想了想，如果range vector数目比较小的话，可以先sort input array A，然
后可以用bucket下界来在这个array A 里面binary search 这个bucket上下界的范围，
找出相应的属于这个bucket的元素的范围，由index来算bucket里面的数目，也不知道
靠谱不靠谱。 | b**k
发帖数: 268 | | r*****h
发帖数: 505 | 3 不需要sort array吧，对bucket做binary search,复杂度只要nlogx, x= number of
buckets |
|
