一亩三分地论坛

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

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

Google onsite

[复制链接] |试试Instant~ |关注本帖
紫英 发表于 2015-6-16 11:35:45 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
今天刚结束Google onsitem,发面经回馈地里。. visit 1point3acres.com for more.

第一轮:merge K lists变形。变简单,你可以定义一个class来描述输入list.

第二轮: 讨论算法,没有写代码。输入是一串字符和一个字典。找出字典里面包含所有输入字符的最短序列。

比如:输入时"ca", 字典里面有 [“cat”,"tac","act","sdf","asdf"]
那么返回:  "cat","tac“
面试官期望的应该是用tree来做的,但是我没想到最优的tree结构。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第三轮。一个图像用byte[]表示。然后把图像左右的像素位交换。

第四轮,merge two list。面试官说遍历list的时候要用iterator.因为当你输入的list变得特别大的时候,arrayList不是一个好选择,如果用LinkedList,那么get方法就会cost a lot.
             然后是merge interval.

没有遇到过三哥,没有system design。

评分

2

查看全部评分

本帖被以下淘专辑推荐:

newlxnewlx 发表于 2015-10-12 01:54:46 | 显示全部楼层
第二题可以用类似于搜索引擎的inverted list, 把字典预处理, 形成这样的一个map:
a : ['act', 'cat', 'tac', 'asdf']
c : ['act', 'cat', 'tac']
d : ...
f : .... 鍥磋鎴戜滑@1point 3 acres
s : ...
. 鍥磋鎴戜滑@1point 3 acres
然后对每个要查询的string做一次merge k-array。
import heapq
def find_shortest_word(words):
    inverted_list = {}
    for word in words:
        for ch in word:
            if ch not in inverted_list:.鏈枃鍘熷垱鑷1point3acres璁哄潧
                inverted_list[ch] = [word]
            else:
                inverted_list[ch].append(word)
. 1point 3acres 璁哄潧
    for ch, word_list in inverted_list.items():. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        word_list.sort(key = lambda w : (len(w), w))

    def query(input):. visit 1point3acres.com for more.
        word_lists = [inverted_list[ch] for ch in input]
        pq = [(len(word_lists[i][0]), word_lists[i][0], i) for i in range(len(word_lists))]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        heads = [0 for w in pq]

        def all_eq():
            for i in range(1, len(heads)):
                if word_lists[i][heads[i]] != word_lists[i-1][heads[i-1]]:
                    return False
            return True

        heapq.heapify(pq)
        while len(pq) > 0: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            if all_eq():
                return word_lists[0][heads[0]]
            top = heapq.heappop(pq)
            idx = top[2]
            if heads[idx] < len(word_lists[idx]):
                heads[idx] += 1
                next_word = word_lists[idx][heads[idx]]
                heapq.heappush(pq, (len(next_word), next_word, idx))
        return None

    return query


def test():
    dict_words =  ["cat","tac","act","ta","sdf","asdf"]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    query = find_shortest_word(dict_words). 1point3acres.com/bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,
    inputs = ["ca", "ac", "at", "fd"]
    for input in inputs:
        print input, '->', query(input) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

回复 支持 2 反对 0

使用道具 举报

houqingniao 发表于 2015-6-16 11:54:03 | 显示全部楼层
题目很常规~~ bless 楼主。
LZ 是fresh吗?
回复 支持 反对

使用道具 举报

say543 发表于 2015-6-22 13:48:38 | 显示全部楼层
第二轮有想到用tree 怎么improve吗? 谢谢
回复 支持 反对

使用道具 举报

头像被屏蔽
zxy4159526 发表于 2015-6-22 15:11:24 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

outtime 发表于 2015-6-22 17:19:48 | 显示全部楼层
第二题没看懂,例子的输出里面应该还有“act”吧。感觉用trie的话也需要好多层
回复 支持 反对

使用道具 举报

liutr90 发表于 2015-6-22 23:43:01 | 显示全部楼层
同没看懂第二题,输出没有“act”吗,这个题有点难度哇
回复 支持 反对

使用道具 举报

volcano 发表于 2015-6-24 08:13:04 | 显示全部楼层
LZ能clarify一下“最短序列” 是什么意思吗? 我推测是包含输入字符串的最短的word,比如你给的例子里“cat"算,但是“cate" 就不算。
回复 支持 反对

使用道具 举报

mhwkanon 发表于 2015-7-18 07:07:32 | 显示全部楼层
第二轮可不可以先对字母排序,类似leetcode上的Anagrams ,然后建trie,找到最短hash到原单词
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-7 04:47:57 | 显示全部楼层
请问lz第二题怎么做?lz的意思是用trie来做吗?为什么我觉得trie还不如brute force来的效率高?求大神解答。。。。. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2015-10-7 04:49):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
还有第三题是什么意思啊?左右交换是怎么做?
回复 支持 反对

使用道具 举报

tomdarling 发表于 2015-10-7 20:39:25 | 显示全部楼层
请问lz是在哪里onsite的呢
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-10-8 02:28:16 | 显示全部楼层
请问lz第三轮是什么意思?
回复 支持 反对

使用道具 举报

 楼主| 紫英 发表于 2015-10-9 03:05:03 | 显示全部楼层
tomdarling 发表于 2015-10-7 20:39
请问lz是在哪里onsite的呢
. visit 1point3acres.com for more.
Moutain View
回复 支持 反对

使用道具 举报

 楼主| 紫英 发表于 2015-10-9 03:05:22 | 显示全部楼层
nothingtrouble 发表于 2015-10-8 02:28
请问lz第三轮是什么意思?

就第三个面试官
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-10-9 11:17:58 | 显示全部楼层
紫英 发表于 2015-10-9 03:05
就第三个面试官

哈哈,我是问lz,第三轮的题目是什么意思?flip image吗?
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-10-9 11:56:54 | 显示全部楼层
紫英 发表于 2015-10-9 03:05
就第三个面试官

另外,如果按照第二轮的描述,可以用建立两个Trie,一个正prefix,一个反。找ca 在cat的Trie里面,tac反过来的Trie 也是cat所以ca也在里面,是这个意思吗?
回复 支持 反对

使用道具 举报

returning 发表于 2015-10-12 00:55:51 | 显示全部楼层
貌似lz弃楼了,后面3题都完全看不懂考点啊,特别是第三题都是啥啊。
第二题也很奇怪,为何要tree/trie,难道不应该是维护个hashmap就行了,你用trie的话还要涉及字符出现的次序问题。
回复 支持 反对

使用道具 举报

colfighter 发表于 2015-10-25 02:42:36 | 显示全部楼层
newlxnewlx 发表于 2015-10-12 01:54
第二题可以用类似于搜索引擎的inverted list, 把字典预处理, 形成这样的一个map:
a : ['act', 'cat', 'ta ...

很好的想法!赞一个!
回复 支持 反对

使用道具 举报

returning 发表于 2015-10-25 15:29:02 | 显示全部楼层
colfighter 发表于 2015-10-25 02:42
很好的想法!赞一个!

你好,方便详细讲一下第二题什么意思吗,谢谢了。
回复 支持 反对

使用道具 举报

colfighter 发表于 2015-10-25 19:03:31 | 显示全部楼层
returning 发表于 2015-10-25 15:29
你好,方便详细讲一下第二题什么意思吗,谢谢了。

感觉就是比如给你ac 要找含ac的最短单词,如果长度一样就全部输出
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 14:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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