📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: Sendoh2015
跳转到指定楼层
上一主题 下一主题
收起左侧

[数组] 问一道salesforce的面试题

🔗
 楼主| Sendoh2015 2017-3-26 14:30:27 | 只看该作者
全局:
再试一次 发表于 2017-3-26 12:37
这题目不让用hashmap,听着更像是考Distributed的数据设计,key-value files,类似mango那种设计,每个key ...

对了我能再请教下具体的细节吗?如果是map-reduce具体应该是怎么样的?非常感谢啊
回复

使用道具 举报

🔗
jasymine 2017-8-13 10:56:13 | 只看该作者
全局:
能用Trie吗?在每一个TrieNode里加一个frequency
回复

使用道具 举报

🔗
jasymine 2017-8-13 10:57:05 | 只看该作者
全局:
嗯 如果input 可以是numbers貌似用Trie是不行的
回复

使用道具 举报

🔗
fentoyal 2017-8-14 03:47:01 | 只看该作者
全局:
内存不够的情况,一般是不建议用高级数据结构的,因为overhead太大。你想想你用trie,平均每单词花费的空间大小?你一个node就有26甚至更多个指针。这就几十byte出去了。hash稍微好点,但也是overhead太大。而你用数组存呢?一个数字一个坑,几乎没有overhead。空间利用率高很多。
面试官说不要用hashmap,我猜他的意思是内存大小对给每个unique的数字建一个key都不够。
这题如果是问我,我会这么做:利用这题关键点a sorted array。
For simplicity, 假设数组长度是100,内存长为30.
我们保留20的空间用来存数据结构,把10的空间拿出来做为buffer。一次读一buffer的数字,做处理,所以大概是这么读:
第一趟:1122334444
第二趟:4455566777
第三趟:7778888888
第四趟:999........
那保留的20存什么呢?存每一趟的起始数字和这一趟在disk上的offset
1: offset 5
4: offset30
7: offset70 ...

然后怎么query每个数字频率?
比如查6的频率,那么现在你得数据结构里二分查找6. 你会发现6在4 ~ 7之间。这样你再把4那趟的数字load到内存里(你有offset),然后再在4那趟数字:4455566777 里二分查找6的起始和结束位置,这样6的频率揪出来了。(对于跨多个block的数据,方法类似,不再赘述)

这个复杂度是log10 + log10的. 不是O(1),但足够好了。因为O(1)方案要把所有key全load进来,我默认这是无法实现的。
这题有很多可以探讨优化的地方,可以跟面试官聊。比如你的硬盘是否还有额外空间?你可以存多级表在硬盘。你硬盘里数据是否连续?那么连offset都不用存了,顺序往下读即可。。等等
回复

使用道具 举报

🔗
zdonking 2017-8-15 05:18:01 | 只看该作者
全局:
Quick sort吧
回复

使用道具 举报

🔗
zdonking 2017-8-15 05:19:27 | 只看该作者
全局:
看错题了,汗。sorted array,那直接two pointers,再维护一个最大值不就行了?
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
Felix1218 2017-8-18 04:01:04 | 只看该作者
全局:
楼主面的是什么组呢?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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