推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3638|回复: 17
收起左侧

uber 店面

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

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

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

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

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.1point3acres缃
// ['a', 'b', 'c'], "abes" -> False
// ['a', 'a'], "as" -> False
// ['a', 'a'], "asaa" -> True.1point3acres缃
第一问很快写完,编译运行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。。。又瞎扯了一通,然后时间就差不多了,说你有什么问题要问我的,问完问题就结束了
周三收到通知说,由于这是个很短的面试(面试官迟到了十几分钟),代码写的不是太多(followup一直在讨论,没有写代码)所以要做第二轮店面。
想问地里的各位大牛对follow up有什么好的想法啊,希望能分享下,尤其是那种要large scale的优化(昨天在亚麻onsite也碰到了,歇会儿发面经),这方面毫无经验,还望各位赐教。

.鏈枃鍘熷垱鑷1point3acres璁哄潧

. visit 1point3acres.com for more.




评分

1

查看全部评分

本帖被以下淘专辑推荐:

kangx 发表于 2016-12-19 16:02:21 来自手机 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
follow up用bst做
回复 支持 0 反对 2

使用道具 举报

jeager 发表于 2016-3-15 04:12:41 | 显示全部楼层
关注一亩三分地微博:
Warald
关于scale,既然不准分块儿,我猜只能是同一个程序要跑在n个机器上。那么,就需要一个array,记录哪些已经访问过了,需要有几个lock,用于更新array与当前最短词条。换句话说,就是concurrency。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
关于long list of word,难道第一问时,楼主没有对dict预处理么?就建立一个map,存储每个字母出现的次数。其他的我也没想出更好的方法。
回复 支持 反对

使用道具 举报

 楼主| guokan 发表于 2016-3-15 05:06:52 | 显示全部楼层
jeager 发表于 2016-3-15 04:12
关于scale,既然不准分块儿,我猜只能是同一个程序要跑在n个机器上。那么,就需要一个array,记录哪些已经 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
谢谢分享。第一问我写错了不好意思,输入应该是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,然后合并下。. visit 1point3acres.com for more.
不知道行不行啊!
回复 支持 反对

使用道具 举报

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 | 显示全部楼层
我感觉这题考的不是时间复杂度 而是空间. 1point 3acres 璁哄潧
因为最优最优的解法至少也得把两个串都看一遍吧 没有任何途径可以省 那就是O(n+k)
空间 看你要用什么了 比如哈希 比如字表示 bitset表示 比如int 数组(看数字范围多大,这样空间与字符串长完全无关) 如何省空间才是考点
这题省空间最好用bitset 或者位移动
因为只问包含与否 与出现次数无关
比如位移动 出现则设置1 两个数组进行这样操作之后一个xor就好了
不过对于xor结果要进行判断 如果a^b == a-b (a是dict string位移之后的值 b是数组的位置值)则包含 空间做到最小 时间n+k
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-12-2 09:24:03 | 显示全部楼层
guokan 发表于 2016-3-15 05:06
谢谢分享。第一问我写错了不好意思,输入应该是char list 和 str, 我就是hashmap做的,遍历str 一遍,记 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
CHAR LIST是字典么,我觉得应该是预处理字典,然后遍历HASHMAP吧,他后面摆明了说很多STRING,你每次预处理STRING干什么
回复 支持 反对

使用道具 举报

喜马拉雅疯子 发表于 2017-1-21 04:08:25 | 显示全部楼层
请问LZ这个follow up是说这个list of words 会被固定下来。每次call的时候array 哦分

补充内容 (2017-1-21 04:09):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
array of chars 都会改变这样的?如果是这样的话。用trie tree或者hashmap 一下应该可以的
回复 支持 反对

使用道具 举报

翻滚吧豆子 发表于 2017-4-6 15:49:41 | 显示全部楼层
用Inverted Index
Index是字母和其出现的次数。每个index entry中的单词按其长短排序。
比如搜索[“a”,"a","b"]
我就把有两个"a"的单词和有一个"b"的单词拿来找第一个intersection. Waral 鍗氬鏈夋洿澶氭枃绔,

如果单词量很大,就把index做的tricky一点
比如把char array先排序,然后每三个一组拿来做index
回复 支持 反对

使用道具 举报

magicat 发表于 2017-4-17 08:45:48 | 显示全部楼层
楼上是正解,我也也觉得是考查revert index
回复 支持 反对

使用道具 举报

zouy1216 发表于 2017-6-8 15:07:24 | 显示全部楼层
借楼问一下,我面过一道差不多的题目,只是返回不是true/false而是string里包含所有character的最短substring长度。当时用two pointer做的,请问这样做是对的吗
回复 支持 反对

使用道具 举报

wwendywang 发表于 2017-6-20 06:32:46 | 显示全部楼层
我觉得可以借用group of anagram 的思想,对dictionary预处理。同样anagram的words 放到一个list里,然后anagram作为key. 用array of chars构造一个key,如果能找到,那返回的就是最短的word list.
回复 支持 反对

使用道具 举报

翻滚吧豆子 发表于 2017-6-20 08:02:05 | 显示全部楼层
wwendywang 发表于 2017-6-20 06:32
我觉得可以借用group of anagram 的思想,对dictionary预处理。同样anagram的words 放到一个list里,然后an ...

首先是anagram的重复率应该不算高
其次,你按anagram排了以后,并没有形成特别有效的索引啊
. more info on 1point3acres.com
比如给的['k', 'z']
你要怎么找到所有对应的anagram呢?
貌似还是要O(n)的复杂度吧
回复 支持 反对

使用道具 举报

wwendywang 发表于 2017-6-20 13:37:43 | 显示全部楼层
对dictionary 预处理肯定是要O(n)的时间复杂度。 anagram 的索引可以用prime 做,或者直接做成 string。譬如['k', 'z'] 可以是 31*103, 也可以是KZ.
如果你要找 ['z', 'k'], O(1) 就可以 找到。
回复 支持 反对

使用道具 举报

翻滚吧豆子 发表于 2017-6-20 15:39:01 | 显示全部楼层
我们先不讨论质数溢出的问题   

你能讲解下O(1)的步骤吗?
我理解你的方法是用anagram的积挨个儿去除31×103
回复 支持 反对

使用道具 举报

翻滚吧豆子 发表于 2017-6-20 15:40:18 | 显示全部楼层
wwendywang 发表于 2017-6-20 13:37
对dictionary 预处理肯定是要O(n)的时间复杂度。 anagram 的索引可以用 prime 做,或者直接做成 string。譬 ...

我们先不讨论质数溢出的问题   

你能讲解下O(1)的步骤吗?
我理解你的方法是用anagram的积挨个儿去除31×103
回复 支持 反对

使用道具 举报

wwendywang 发表于 2017-6-20 22:54:30 | 显示全部楼层
['z', 'k']是103*31, 等于31*103. 在预处理好的字典map里可以直接找到. 如果假设array是排好序的,只有 ['k', 'z'] 这一种情况,那build一个string - KZ, 也可以直接在预处理好的字典map里找到。如果KZ没有, 那就加一个a, 看看akz 是不是在map里,然后加一个b, 看看bkz在不在,依此类推,可以找到最短的string. 这样的情况,就不是O(1)了。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-27 22:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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