一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1325|回复: 11
收起左侧

爆一个从来没见过的bb题,顺便求问下有没有人面过三轮最后一轮是hr的。。。

[复制链接] |试试Instant~ |关注本帖
348210207 发表于 2016-2-5 06:57:14 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Bloomberg - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
刚面的bb,遇到了一个从没见过的题,发出来攒个人品:
给一个数列:[6,1,2,2,1,3,3,3,9] 按照数字出现次数从多到少依次打印出数字。同时必须保持数字的原顺序:
比如这题输出:3,1,2,6,9.
.1point3acres缃
这题我当时做的时候给出了两种n2做法,后来在等待的20分钟中找出来了nlogn做法,目前我真想不出来更好做法。
nlogn做法就是使用map(c艹的)和 priority queue来做,pq中比较的是index。

直观感受是可以on,但想不出来了。。。。

顺便一提:楼主很奇葩的面了三轮。前两轮技术面,之后等了半小时,来了俩hr当时心里一凉,还想:bb真是大公司,送我出门还来了俩hr。结果这俩hr问了好多behavior,然后问了楼主opt开始了么,想要多少工资。. visit 1point3acres.com for more.

然后她俩就走了。。。。。。

又过了20分钟,没等来manager,等来了小hr直接送走了。

有人有过这种奇葩经历么?

.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2016-2-9 05:07):
刚刚收到邮件,跪了。。。。
hurtlocker 发表于 2016-3-5 20:36:05 | 显示全部楼层
[6,1,2,2,1,3,3,3,9]
1. 先统计<数字, 出现的次数>
6 -- 1
1 -- 2
2 -- 2
3 -- 3
9 -- 1. Waral 鍗氬鏈夋洿澶氭枃绔,
2. bucket(i)表示出现i次的数字序列, 最多也就n个bucket(比n小很多应该...)
bucket(1) -- [6,9]
bucket(2) -- [1,2]
bucket(3) -- [3]
最后结果是[3,1,2,6,9]
回复 支持 1 反对 0

使用道具 举报

tltzhsajsdr 发表于 2016-2-5 07:35:13 | 显示全部楼层
顺着遍历,得到各个数的次数,然后radix sort或者count sort对出现次数排序,然后输出即可。耗时O(N)

补充内容 (2016-2-5 07:36):
由于数字的出现次数一定是[1,n]之间的某个数,所以count sort最快
回复 支持 1 反对 0

使用道具 举报

AndrewFish 发表于 2016-2-5 07:17:00 | 显示全部楼层
two hashmaps. first for < number,occurences> second for<order, number>  

补充内容 (2016-2-4 16:18):
I misunderstood something...
回复 支持 反对

使用道具 举报

AndrewFish 发表于 2016-2-5 07:25:30 | 显示全部楼层
First we build  <number,occurences>, then we scan through list again and build <occurences, List<Integer>>, add number to corresponding list according to occurences. Then we output numbers in List<Integer> in order of occurences, just remember not to output duplicate numbers.
回复 支持 反对

使用道具 举报

 楼主| 348210207 发表于 2016-2-5 22:28:23 | 显示全部楼层
同意二楼做法。但建议使用这个做法时候和主考官讨论tradeoff。
回复 支持 反对

使用道具 举报

Hardys 发表于 2016-2-6 22:00:42 | 显示全部楼层
稳了稳了稳了
回复 支持 反对

使用道具 举报

zzzfeeling 发表于 2016-2-7 03:48:29 | 显示全部楼层
多谢楼主分享,一定会offer的!
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-2-7 04:18:28 | 显示全部楼层
楼主offer到手了嘛?
回复 支持 反对

使用道具 举报

 楼主| 348210207 发表于 2016-2-9 00:46:49 | 显示全部楼层
借这楼所有大哥吉言。楼主正在心惊胆战的等拒信或者电话。。。。。
回复 支持 反对

使用道具 举报

xintai404 发表于 2016-2-14 13:57:24 | 显示全部楼层
AndrewFish 发表于 2016-2-5 07:25
First we build  , then we scan through list again and build , add number to corresponding list accor ...

build <occurences, List<Integer>>的过程就要按照 occurneces 排序吧
回复 支持 反对

使用道具 举报

pengds 发表于 2016-2-16 08:59:02 | 显示全部楼层
应该可以用java的linkedhashmap来记录每个数的出现次数来保证插入的顺序, 然后counting sort entry<occurrence, number> 实现stable sorting, 再construct number array
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 09:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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