San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 1522|回复: 30
收起左侧

google onsite

[复制链接] |试试Instant~ |关注本帖
lyytju 发表于 2018-5-16 07:06:21 | 显示全部楼层 |阅读模式

2018(4-6月) 码农类General 硕士 全职@Google - 网上海投 - Onsite  | Other | fresh grad应届毕业生

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

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

x
今天的onsite
1. 面经题,凳子上坐人的最大距离, follow up: 凳子上一开始没有人,然后一个一个往里面放,每次放的时候O(1)时间求放在哪里距离最大(数学问题 )
2. 面经题,leetcode 399, unionfind O(1)check
3. 给一个pattern, check true or false, 比如abbba->cdddc就是true,每个字母一种映射(两个hashmap), follow up: 一次check很多string, 比如给abbba,check一个字典里面所有跟他pattern相同的,返回一个List
    编码, abbba->12221,然后check(这一轮我有点蠢,犯了一个bug)'. visit 1point3acres for more.
4.给两个string,比如 lee和eel,找到一个最短的string,它的substring包含这两个stirng,比如 leel.(应该是KMP,然而忘了怎么写了,弄了个hashSet存一个string的所有prefix,跟另一个比较,O(n^2))
  follow up: 给一堆string怎么办?(这轮血炸,一开始思路就错了,一直在想greedy的方法,实际上不是greedy的,dfs遍历就好。。最后画了个dfs树,没时间写代码了。。)
总体来说题目不难,但是最后一轮思路错了,也没有hint..很僵硬

评分

7

查看全部评分

本帖被以下淘专辑推荐:

wenyitiger 发表于 2018-5-16 15:36:56 | 显示全部楼层
写了下 试了几个基本case好像还行. Waral 博客有更多文章,
  1. words = ["lee","abcde","eel","cdefg","uiab","oop"]
  2. print findshortest(words)
复制代码

虽然写的有点奇怪~

  1. def shortest(word1,word2):
  2.     for index in xrange(len(word1)):. From 1point 3acres bbs
  3.         if word2.startswith(word1[index:]):
  4.             return word1[:index] + word2
  5.     for index in xrange(len(word2)):
  6.         if word1.startswith(word2[index:]):
  7.             return word2[:index] + word1
  8.     return word1+word2.留学论坛-一亩-三分地

  9. def findshortest(words):
  10.     data = {}
  11.     def dfs(visited):
  12.         if visited not in data:. from: 1point3acres
  13.             data[visited] = ""
  14.             lvisited = list(visited)
  15.             for index in xrange(len(lvisited)):
  16.                 if lvisited[index] == False:
  17.                     lvisited[index] = True-google 1point3acres
  18.                     k = shortest(dfs(tuple(lvisited)),words[index])
  19.                     if not data[visited]:
  20.                         data[visited] = k
  21.                     else:
  22.                         if len(k) <= len(data[visited]):. 一亩-三分-地,独家发布
  23.                             data[visited] = k. more info on 1point3acres
  24.                     lvisited[index] = False-google 1point3acres
  25.         return data[visited]
  26.     return dfs(tuple([False for x in xrange(len(words))]))
复制代码
回复 支持 0 反对 2

使用道具 举报

ushergod 发表于 7 天前 | 显示全部楼层
请问 楼主 第一题 有对应蠡口 或者 详细的面经吗?
回复 支持 1 反对 0

使用道具 举报

duangduangduang 发表于 2018-5-16 08:44:49 | 显示全部楼层
感谢感谢,请问一下第四题,找到的那个最短string是需要两个给出的string concat一起吗? 类似 leet, etcode, 这两个的话是leetcode, 但是如果是test, code那么就是worst case: testcode 这样的?
回复 支持 反对

使用道具 举报

 楼主| lyytju 发表于 2018-5-16 09:31:05 | 显示全部楼层
duangduangduang 发表于 2018-5-16 08:44
感谢感谢,请问一下第四题,找到的那个最短string是需要两个给出的string concat一起吗? 类似 leet, etcod ...

对,需要concat
回复 支持 反对

使用道具 举报

wuwei123 发表于 2018-5-16 09:45:16 | 显示全部楼层
预祝人品大爆发
回复 支持 反对

使用道具 举报

luobaobao3 发表于 2018-5-16 12:57:53 | 显示全部楼层
第4题 dfs遍历思路是什么呀   谢谢楼主~
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

辛苦小农民 发表于 2018-5-16 14:18:38 | 显示全部楼层
感谢楼主分享。offer马上来
回复 支持 反对

使用道具 举报

wenyitiger 发表于 2018-5-16 14:20:33 | 显示全部楼层
第四题DFS+memorization?第一问来做然后memo  memo(1,k) =  min( merge(memo[1:j],memo[j:k]) for j in k)?
比如 ["lee","eel","ltt"]  然后 memo(1,2) = leel  memo(1,3) = leeltt 这种的来减少重复计算
回复 支持 反对

使用道具 举报

flyaaaa 发表于 2018-5-16 16:27:31 | 显示全部楼层
4不是longest common substring 马?
回复 支持 反对

使用道具 举报

 楼主| lyytju 发表于 2018-5-17 05:50:38 来自手机 | 显示全部楼层
wenyitiger 发表于 2018-5-16 15:36
写了下 试了几个基本case好像还行

虽然写的有点奇怪~

对,题目实际不难,但是我自己想歪了,一直想着greedy方法做,然后就炸了.面试官也没有提醒....然后第一问需要check一下一个string是不是在另一个里面,这是一个corner case
回复 支持 反对

使用道具 举报

 楼主| lyytju 发表于 2018-5-17 05:52:19 来自手机 | 显示全部楼层
flyaaaa 发表于 2018-5-16 16:27.1point3acres网
4不是longest common substring 马?

不是,两个string 要能够接到一起,实际是比较前后缀
回复 支持 反对

使用道具 举报

wenyitiger 发表于 2018-5-18 06:45:14 | 显示全部楼层
lyytju 发表于 2018-5-17 05:50
对,题目实际不难,但是我自己想歪了,一直想着greedy方法做,然后就炸了.面试官也没有提醒....然后第一 ...
. 1point3acres
确实没想到corner case 哈哈 不过我觉得这题也不算简单了吧 主要是不给hint这有点坑 面试官是扑克脸?
回复 支持 反对

使用道具 举报

amber110 发表于 2018-5-18 10:00:39 | 显示全部楼层
感谢分享,感觉第四轮的思想和蠡口气雾散 cracking safe有点像?
回复 支持 反对

使用道具 举报

ljl.lee 发表于 2018-5-18 12:47:12 | 显示全部楼层
感谢分享!祝好运!. 1point3acres
第四题 多个string的情况,是两两求出覆盖长度,按覆盖长度从多到少的顺序拼接,直到所有string拼接完成吗?
回复 支持 反对

使用道具 举报

markpen 发表于 2018-5-18 13:26:34 | 显示全部楼层
第四轮 follow up 是不是哈密顿回路问题?edge(A, B) A 和 B 合在一起时的最短长度(A 在前,B在后),edge(B, A) 同理。这样建完图后,原命题等价于找一条路,通过所有点,且权重最小?
回复 支持 反对

使用道具 举报

Barbados 发表于 2018-5-18 13:46:47 | 显示全部楼层
我找到一个第四轮的题目链接,greedy是可以解的:https://www.geeksforgeeks.org/shortest-superstring-problem/
回复 支持 反对

使用道具 举报

wenyitiger 发表于 2018-5-18 14:53:56 | 显示全部楼层
果然是NP-Hard.. 楼上的解法不能保证完全正确 只能是“大概”: 原文摘抄哈哈
The above Greedy Algorithm is proved to be 4 approximate (i.e., length of the superstring generated by this algorithm is never beyond 4 times the shortest possible superstring). This algorithm is conjectured to 2 approximate (nobody has found case where it generates more than twice the worst). Conjectured worst case example is {abk, bkc, bk+1}. For example {“abb”, “bbc”, “bbb”}, the above algorithm may generate “abbcbbb” (if “abb” and “bbc” are picked as first pair), but the actual shortest superstring is “abbbc”. Here ratio is 7/5, but for large k, ration approaches 2.
回复 支持 反对

使用道具 举报

dododidibaba 发表于 7 天前 | 显示全部楼层
谢谢楼主分享!祝好运!

请问面的过程中就是不停的出题和讨论题目吗? 会不会串着问一些语言方面的基础问题?比如说说说java的继承多态啊,static是怎么回事之类的?
回复 支持 反对

使用道具 举报

ushergod 发表于 7 天前 | 显示全部楼层
wenyitiger 发表于 2018-5-16 15:36
写了下 试了几个基本case好像还行

虽然写的有点奇怪~

手抖 没想反对的 sorry!不知道如何撤销了
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-26 18:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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