《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1610|回复: 33
收起左侧

[找工就业] 11/10 脸书全职挂经 非leetcode题!!!!!!!!!!

[复制链接] |试试Instant~ |关注本帖
woshilindan 发表于 2017-11-11 13:24:23 | 显示全部楼层 |阅读模式

2017(10-12月)-[16]CS硕士+<3个月短暂实习/全职 - 内推| 码农类全职@Facebookfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x

. From 1point 3acres bbs
白人小哥 直接做题 hello都没说 给一个array 比如 [9,9,5,3,3,7,1] 里面的数字都是0到9之间 inclusive 给你个k 给出top k largest number sum

比如 top 3 = 9+9+7

讨论就讨论了20分钟 我先说用priorityqueue 扫一遍加进去然后从后面开始往前扫拿出k个 解释完 正准备写的时候小哥说如果1有一百万个咋办我问他怎么想 他给了一个提示说如果count frequency呢 我至今没有get到他的点(count frequency不还是要扫一遍才能知道frequency嘛。。。) 后来就建了一个array[10] index代表数字 element代表frequency 先扫一遍count frequency(不是跟pq一样吗。。。) 然后在array从后往前加。。。后来脑子越写越乱 不知道他到底想要我干啥。。 就写了一提bug还很多。。。准备了那么多leetcode tag题白准备了 后来上网查了一下要用bucket sort或radix sort。。 哪位大神来解释一下。。。.鐣欏璁哄潧-涓浜-涓夊垎鍦

找工作不容易 求问犬只挂了还能申请实习吗 换个名字邮箱有用吗。。

本帖被以下淘专辑推荐:

硅谷吴彦祖 发表于 2017-11-11 13:40:58 | 显示全部楼层
如果都用heap的话 add n次 + poll k次 复杂度是nlogn + klogn = (n + k)logn

如果用bucket sort n个元素排序是 n, 拿k个出来是常数复杂度, 因为只有0-9十个数字 所以复杂度是n

public int topkSum(int[] nums, int k) {-google 1point3acres
        int[] counter = new int[10];
        for(int num : nums) {. Waral 鍗氬鏈夋洿澶氭枃绔,
            counter[num - 0]++;
        }
        int kSum = 0, remain = k;
        for(int i = 9; i >= 0 && remain > 0; i--) {
            if(remain >= counter[i]) {
                kSum += counter[i] * i;
                remain -= counter[i];
            } else {
                kSum += remain * i;
                break;. Waral 鍗氬鏈夋洿澶氭枃绔,
            }
        }
        return kSum;
    }. 鍥磋鎴戜滑@1point 3 acres
回复 支持 2 反对 0

使用道具 举报

ls2882177 发表于 2017-11-11 13:42:46 | 显示全部楼层
小哥的意思是不是你用pq太费空间了?
你只用array记录然后直接根据k返回结果就可以了。. visit 1point3acres.com for more.
比如test case是{9,9,5,3,3,7,1},对应的array就是{0,1,0,2,0,0,0,1,0,2}
k=3从大往小返回就可以了,先是2个9,然后没有8,然后1个7
回复 支持 反对

使用道具 举报

cutehuazai 发表于 2017-11-11 13:47:46 来自手机 | 显示全部楼层
楼主后来的做法是对的呀
回复 支持 反对

使用道具 举报

CinL 发表于 2017-11-11 14:02:34 | 显示全部楼层
所以这题不是leetcode那道top k largest number?只是从求top k largest numbers 变成求top k largest numbers的sum了吧?道理不应该还是那个道理么。先count frequency存到hashmap里,然后bucket sort hashmap values,然后求top k的sum。是我哪里没想到吗?

补充内容 (2017-11-11 18:18):
啊看错题了_(:з」∠)_
确实不是leetcode题。不好意思。
回复 支持 反对

使用道具 举报

HNAKXR 发表于 2017-11-11 14:17:40 | 显示全部楼层
0-9之间这么小的范围算是挺明显的bucket或者radix sort暗示了吧,算法课只要讲到基本都会这么考,当然counting sort也行啊
回复 支持 反对

使用道具 举报

oio14644 发表于 2017-11-11 15:14:55 | 显示全部楼层
这是面经原题, 之前 mitbbs 报过
回复 支持 反对

使用道具 举报

qwerty940828 发表于 2017-11-11 15:30:21 | 显示全部楼层
同问,fb全职挂了还能投实习么?
回复 支持 反对

使用道具 举报

 楼主| woshilindan 发表于 2017-11-11 16:36:07 | 显示全部楼层
ls2882177 发表于 2017-11-11 13:42
小哥的意思是不是你用pq太费空间了?
你只用array记录然后直接根据k返回结果就可以了。
比如test case是{ ...

priorityqueue和array不都是一样的复杂度?到要先扫一遍???
回复 支持 反对

使用道具 举报

 楼主| woshilindan 发表于 2017-11-11 16:37:49 | 显示全部楼层
cutehuazai 发表于 2017-11-11 13:47
楼主后来的做法是对的呀

对在哪里 不是跟priorityqueue做法一样的吗 都要先遍历原数组一遍 如果原数组1有1 million个不是很浪费时间???
回复 支持 反对

使用道具 举报

 楼主| woshilindan 发表于 2017-11-11 16:38:49 | 显示全部楼层
HNAKXR 发表于 2017-11-11 14:17
0-9之间这么小的范围算是挺明显的bucket或者radix sort暗示了吧,算法课只要讲到基本都会这么考,当然count ...

当时面试时查到了但是早忘了怎么搞的
回复 支持 反对

使用道具 举报

AlanWu 发表于 2017-11-11 16:46:25 来自手机 | 显示全部楼层
woshilindan 发表于 2017-11-11 16:36. visit 1point3acres.com for more.
priorityqueue和array不都是一样的复杂度?到要先扫一遍???

空间吧,pq空间n,array只有10个~
回复 支持 反对

使用道具 举报

 楼主| woshilindan 发表于 2017-11-11 16:48:51 | 显示全部楼层
AlanWu 发表于 2017-11-11 16:46
空间吧,pq空间n,array只有10个~

嗷嗷嗷....
回复 支持 反对

使用道具 举报

AlanWu 发表于 2017-11-11 16:55:33 来自手机 | 显示全部楼层
woshilindan 发表于 2017-11-11 16:48
嗷嗷嗷....
. visit 1point3acres.com for more.
标准pq做法是维护size k的,那样空间只有k
回复 支持 反对

使用道具 举报

 楼主| woshilindan 发表于 2017-11-11 16:55:53 | 显示全部楼层
硅谷吴彦祖 发表于 2017-11-11 13:40
如果都用heap的话 add n次 + poll k次 复杂度是nlogn + klogn = (n + k)logn

如果用bucket sort n个元素 ...

bucket sort解法和array[index]解法都差不多都是O(n)?
回复 支持 反对

使用道具 举报

 楼主| woshilindan 发表于 2017-11-11 16:58:15 | 显示全部楼层
AlanWu 发表于 2017-11-11 16:55
标准pq做法是维护size k的,那样空间只有k

对对对.......
回复 支持 反对

使用道具 举报

ivywu_94 发表于 2017-11-11 17:40:57 | 显示全部楼层
你面试的小哥是不是名字开头是r啥啥 看起来像印度人名字?
回复 支持 反对

使用道具 举报

zachzuogwu 发表于 2017-11-12 01:26:17 | 显示全部楼层
利口原题 top k。size n的pq是nlogn, size k的pg是nlogk, 最好用bucket sort到O(n)
回复 支持 反对

使用道具 举报

iwantanintern 发表于 2017-11-12 01:32:18 | 显示全部楼层
zachzuogwu 发表于 2017-11-12 01:26-google 1point3acres
利口原题 top k。size n的pq是nlogn, size k的pg是nlogk, 最好用bucket sort到O(n)

这明明跟leetcode 题不一样
回复 支持 反对

使用道具 举报

zachzuogwu 发表于 2017-11-12 01:41:07 | 显示全部楼层
iwantanintern 发表于 2017-11-12 01:32
这明明跟leetcode 题不一样

楼主的例子 [9,9,5,3,3,7,1] k =3, top 3 = 9+9+7。请问下,找top k个和找top k个出来再相加,有区别吗?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-23 02:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表