周末了,八卦下什么是好的manager

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2607|回复: 34
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
woshilindan 发表于 2017-11-11 13:24:23 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  76% (32)
 
 
23% (10)  踩

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

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

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

x


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

比如 top 3 = 9+9+7. more info on 1point3acres

讨论就讨论了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。。 哪位大神来解释一下。。。

找工作不容易 求问犬只挂了还能申请实习吗 换个名字邮箱有用吗。。. 留学申请论坛-一亩三分地

上一篇:小众squarespace + databricks 面经
下一篇:报一个小众公司 lender price春季实习

本帖被以下淘专辑推荐:

我的人缘0
硅谷吴彦祖 发表于 2017-11-11 13:40:58 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  86% (56)
 
 
13% (9)  踩
如果都用heap的话 add n次 + poll k次 复杂度是nlogn + klogn = (n + k)logn
. more info on 1point3acres
如果用bucket sort n个元素排序是 n, 拿k个出来是常数复杂度, 因为只有0-9十个数字 所以复杂度是n

public int topkSum(int[] nums, int k) {
        int[] counter = new int[10];
        for(int num : nums) {
            counter[num - 0]++;
        }
        int kSum = 0, remain = k;
        for(int i = 9; i >= 0 && remain > 0; i--) {
            if(remain >= counter[i]) {. visit 1point3acres for more.
                kSum += counter[i] * i;
                remain -= counter[i];
            } else {
                kSum += remain * i;
                break;
            }. 围观我们@1point 3 acres
        }
        return kSum;
    }
回复

使用道具 举报

我的人缘0
ls2882177 发表于 2017-11-11 13:42:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (33)
 
 
0% (0)  踩
小哥的意思是不是你用pq太费空间了?
你只用array记录然后直接根据k返回结果就可以了。. visit 1point3acres 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
回复

使用道具 举报

我的人缘0
cutehuazai 发表于 2017-11-11 13:47:46 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (101)
 
 
13% (16)  踩
楼主后来的做法是对的呀
回复

使用道具 举报

我的人缘0
CinL 发表于 2017-11-11 14:02:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (98)
 
 
8% (9)  踩
所以这题不是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题。不好意思。
回复

使用道具 举报

我的人缘0
HNAKXR 发表于 2017-11-11 14:17:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (85)
 
 
9% (9)  踩
0-9之间这么小的范围算是挺明显的bucket或者radix sort暗示了吧,算法课只要讲到基本都会这么考,当然counting sort也行啊
回复

使用道具 举报

我的人缘0
oio14644 发表于 2017-11-11 15:14:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (206)
 
 
6% (15)  踩
这是面经原题, 之前 mitbbs 报过
回复

使用道具 举报

我的人缘0
qwerty940828 发表于 2017-11-11 15:30:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  76% (429)
 
 
23% (131)  踩
同问,fb全职挂了还能投实习么?
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
 楼主| woshilindan 发表于 2017-11-11 16:36:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  76% (32)
 
 
23% (10)  踩
ls2882177 发表于 2017-11-11 13:42
小哥的意思是不是你用pq太费空间了?
你只用array记录然后直接根据k返回结果就可以了。
比如test case是{ ...

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

使用道具 举报

我的人缘0
 楼主| woshilindan 发表于 2017-11-11 16:37:49 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  76% (32)
 
 
23% (10)  踩
cutehuazai 发表于 2017-11-11 13:47
楼主后来的做法是对的呀

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

使用道具 举报

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

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

使用道具 举报

我的人缘0
AlanWu 发表于 2017-11-11 16:46:25 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (47)
 
 
2% (1)  踩
woshilindan 发表于 2017-11-11 16:36. more info on 1point3acres
priorityqueue和array不都是一样的复杂度?到要先扫一遍???
. Waral 博客有更多文章,
空间吧,pq空间n,array只有10个~
回复

使用道具 举报

我的人缘0
 楼主| woshilindan 发表于 2017-11-11 16:48:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  76% (32)
 
 
23% (10)  踩
AlanWu 发表于 2017-11-11 16:46
空间吧,pq空间n,array只有10个~

嗷嗷嗷....
回复

使用道具 举报

我的人缘0
AlanWu 发表于 2017-11-11 16:55:33 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (47)
 
 
2% (1)  踩
woshilindan 发表于 2017-11-11 16:48
嗷嗷嗷....

标准pq做法是维护size k的,那样空间只有k
回复

使用道具 举报

我的人缘0
 楼主| woshilindan 发表于 2017-11-11 16:55:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  76% (32)
 
 
23% (10)  踩
硅谷吴彦祖 发表于 2017-11-11 13:40. 牛人云集,一亩三分地
如果都用heap的话 add n次 + poll k次 复杂度是nlogn + klogn = (n + k)logn

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

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

使用道具 举报

我的人缘0
 楼主| woshilindan 发表于 2017-11-11 16:58:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  76% (32)
 
 
23% (10)  踩
AlanWu 发表于 2017-11-11 16:55.1point3acres网
标准pq做法是维护size k的,那样空间只有k

对对对.......
回复

使用道具 举报

我的人缘0
ivywu_94 发表于 2017-11-11 17:40:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  0% (0)
 
 
0% (0)  踩
你面试的小哥是不是名字开头是r啥啥 看起来像印度人名字?
回复

使用道具 举报

我的人缘0
zachzuogwu 发表于 2017-11-12 01:26:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (22)
 
 
4% (1)  踩
利口原题 top k。size n的pq是nlogn, size k的pg是nlogk, 最好用bucket sort到O(n)
回复

使用道具 举报

我的人缘0
iwantanintern 发表于 2017-11-12 01:32:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  73% (53)
 
 
26% (19)  踩
zachzuogwu 发表于 2017-11-12 01:26
利口原题 top k。size n的pq是nlogn, size k的pg是nlogk, 最好用bucket sort到O(n)

这明明跟leetcode 题不一样
回复

使用道具 举报

我的人缘0
zachzuogwu 发表于 2017-11-12 01:41:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (22)
 
 
4% (1)  踩
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个出来再相加,有区别吗?
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-7-22 05:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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