一亩三分地论坛

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

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

uber 店面

[复制链接] |试试Instant~ |关注本帖
guokan 发表于 2016-3-13 02:40:31 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Uber - 内推 - 技术电面 |Pass在职跳槽

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

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

x
这周一(3/7)的面试,一直没来得及来地里发面经,趁着还记得大概赶紧过来发下list of words (dictionary) + array of characters ->  return boolean contains(array, words) to check if a string in dict contains all chars in array.Test cases:
// ['a', 'b', 'e'], "abes" -> True
// ['a', 'b', 'c'], "abes" -> False. visit 1point3acres.com for more.
// ['a', 'a'], "as" -> False
// ['a', 'a'], "asaa" -> True. 1point3acres.com/bbs
第一问很快写完,编译运行test cases通过。然后follow up: long list of words, return Shortest word in dictionary such that contains(array, word) is true.
面试官说完follow up还提示了下你可能需要对dict预处理。没想到什么太好的办法,一开始说是先对dict的words按长度排序,这样在找string的时候长度少于array size的就可以直接忽略了,面试官对这个好像不太满意,我又说可不可以把单词压缩下,这样占用空间就小了,这样一来好像之前的排序也没啥用了。。。他不置可否,继续提问,你这个算法如果要scale要多个机器上,要做什么优化,我说能不能把字典分块,每个机器负责一部分工作,他说我不是要你做load balancing。。。又瞎扯了一通,然后时间就差不多了,说你有什么问题要问我的,问完问题就结束了.1point3acres缃
周三收到通知说,由于这是个很短的面试(面试官迟到了十几分钟),代码写的不是太多(followup一直在讨论,没有写代码)所以要做第二轮店面。
想问地里的各位大牛对follow up有什么好的想法啊,希望能分享下,尤其是那种要large scale的优化(昨天在亚麻onsite也碰到了,歇会儿发面经),这方面毫无经验,还望各位赐教。







评分

1

查看全部评分

jeager 发表于 2016-3-15 04:12:41 | 显示全部楼层
关于scale,既然不准分块儿,我猜只能是同一个程序要跑在n个机器上。那么,就需要一个array,记录哪些已经访问过了,需要有几个lock,用于更新array与当前最短词条。换句话说,就是concurrency。. 1point 3acres 璁哄潧

关于long list of word,难道第一问时,楼主没有对dict预处理么?就建立一个map,存储每个字母出现的次数。其他的我也没想出更好的方法。
回复 支持 反对

使用道具 举报

 楼主| guokan 发表于 2016-3-15 05:06:52 | 显示全部楼层
jeager 发表于 2016-3-15 04:12
关于scale,既然不准分块儿,我猜只能是同一个程序要跑在n个机器上。那么,就需要一个array,记录哪些已经 ...

谢谢分享。第一问我写错了不好意思,输入应该是char list 和 str, 我就是hashmap做的,遍历str 一遍,记录字符及出现的次数,然后再遍历char list。第二问最后实在没有什么好办法,也提到了用hashmap先处理,算是挺暴力的方法的吧。
回复 支持 反对

使用道具 举报

Michael_tseng 发表于 2016-3-18 10:30:11 | 显示全部楼层
讨论下用trie方案:
1. trie来预处理下list of wards
2. hash来预处理char list
3. bfs搜出最短的那个word。

对于scalable的话,可以先把words分块,然后对于不同的块求出最小长度的word,然后合并下。
不知道行不行啊!
回复 支持 反对

使用道具 举报

ok123 发表于 2016-3-28 06:32:08 | 显示全部楼层
Michael_tseng 发表于 2016-3-18 10:30
讨论下用trie方案:
1. trie来预处理下list of wards
2. hash来预处理char list

trie 没法处理这种吧
// ['a', 'a'], "asaa" -> True

dict 怎么处理的?能说详细点吗?
回复 支持 反对

使用道具 举报

traceroute_su 发表于 2016-4-8 12:54:17 | 显示全部楼层
我感觉这题考的不是时间复杂度 而是空间
因为最优最优的解法至少也得把两个串都看一遍吧 没有任何途径可以省 那就是O(n+k)
空间 看你要用什么了 比如哈希 比如字表示 bitset表示 比如int 数组(看数字范围多大,这样空间与字符串长完全无关) 如何省空间才是考点
这题省空间最好用bitset 或者位移动 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
因为只问包含与否 与出现次数无关 . visit 1point3acres.com for more.
比如位移动 出现则设置1 两个数组进行这样操作之后一个xor就好了
不过对于xor结果要进行判断 如果a^b == a-b (a是dict string位移之后的值 b是数组的位置值)则包含 空间做到最小 时间n+k
回复 支持 反对

使用道具 举报

liurudahai 发表于 前天 09:24 | 显示全部楼层
guokan 发表于 2016-3-15 05:06
谢谢分享。第一问我写错了不好意思,输入应该是char list 和 str, 我就是hashmap做的,遍历str 一遍,记 ...

CHAR LIST是字典么,我觉得应该是预处理字典,然后遍历HASHMAP吧,他后面摆明了说很多STRING,你每次预处理STRING干什么
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 14:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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