【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
硅谷知名AI创业公司
图灵视频
招聘多个工程师职位
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
查看: 4200|回复: 49
收起左侧

google onsite

[复制链接] |试试Instant~ |关注本帖
我的人缘0
lyytju 发表于 2018-5-16 07:06:21 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩

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

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

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

x
今天的onsite.1point3acres网
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)'
4.给两个string,比如 lee和eel,找到一个最短的string,它的substring包含这两个stirng,比如 leel.(应该是KMP,然而忘了怎么写了,弄了个hashSet存一个string的所有prefix,跟另一个比较,O(n^2))
  follow up: 给一堆string怎么办?(这轮血炸,一开始思路就错了,一直在想greedy的方法,实际上不是greedy的,dfs遍历就好。。最后画了个dfs树,没时间写代码了。。)
总体来说题目不难,但是最后一轮思路错了,也没有hint..很僵硬

评分

参与人数 8大米 +24 收起 理由
enjoynet + 3 很有用的信息!
lakeshore + 3 给你点个赞!
zhuyingcau + 5 给你点个赞!
Barbados + 3 给你点个赞!
wenyitiger + 1 多谢lz分享面经~
oceanator + 3 很有用的信息!
reliveinfire + 3 给你点个赞!
duangduangduang + 3 给你点个赞!

查看全部评分


上一篇:SnapChat
下一篇:彭勃社新鲜面经(店面)

本帖被以下淘专辑推荐:

我的人缘0
wenyitiger 发表于 2018-5-16 15:36:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (2)   【踩】
全局: 顶  87% (21)
 
 
12% (3)  踩
写了下 试了几个基本case好像还行.留学论坛-一亩-三分地
  1. words = ["lee","abcde","eel","cdefg","uiab","oop"]
  2. print findshortest(words)
复制代码

虽然写的有点奇怪~

  1. def shortest(word1,word2):
  2.     for index in xrange(len(word1)):
  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.本文原创自1point3acres论坛

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

使用道具 举报

我的人缘0
miayolanda 发表于 2018-6-7 09:55:07 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  90% (29)
 
 
9% (3)  踩
请问第一题是什么意思呢?是要每次放离所有人距离加起来最远,还是离最近的人最远?
回复

使用道具 举报

我的人缘0
ushergod 发表于 2018-5-19 13:11:12 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
请问 楼主 第一题 有对应蠡口 或者 详细的面经吗?
回复

使用道具 举报

我的人缘0
Barbados 发表于 2018-5-18 13:46:47 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  70% (17)
 
 
29% (7)  踩
我找到一个第四轮的题目链接,greedy是可以解的:https://www.geeksforgeeks.org/shortest-superstring-problem/

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
duangduangduang 发表于 2018-5-16 08:44:49 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (49)
 
 
0% (0)  踩
感谢感谢,请问一下第四题,找到的那个最短string是需要两个给出的string concat一起吗? 类似 leet, etcode, 这两个的话是leetcode, 但是如果是test, code那么就是worst case: testcode 这样的?
回复

使用道具 举报

我的人缘0
 楼主| lyytju 发表于 2018-5-16 09:31:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
duangduangduang 发表于 2018-5-16 08:44
感谢感谢,请问一下第四题,找到的那个最短string是需要两个给出的string concat一起吗? 类似 leet, etcod ...

对,需要concat

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
wuwei123 发表于 2018-5-16 09:45:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
预祝人品大爆发
回复

使用道具 举报

我的人缘0
luobaobao3 发表于 2018-5-16 12:57:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (38)
 
 
0% (0)  踩
第4题 dfs遍历思路是什么呀   谢谢楼主~
回复

使用道具 举报

我的人缘0
辛苦小农民 发表于 2018-5-16 14:18:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (20)
 
 
13% (3)  踩
感谢楼主分享。offer马上来

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
wenyitiger 发表于 2018-5-16 14:20:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (21)
 
 
12% (3)  踩
第四题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 这种的来减少重复计算
回复

使用道具 举报

我的人缘0
flyaaaa 发表于 2018-5-16 16:27:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
4不是longest common substring 马?
回复

使用道具 举报

我的人缘0
 楼主| lyytju 发表于 2018-5-17 05:50:38 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
wenyitiger 发表于 2018-5-16 15:36.本文原创自1point3acres论坛
写了下 试了几个基本case好像还行

虽然写的有点奇怪~

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

使用道具 举报

我的人缘0
 楼主| lyytju 发表于 2018-5-17 05:52:19 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
flyaaaa 发表于 2018-5-16 16:27
4不是longest common substring 马?

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

使用道具 举报

我的人缘0
wenyitiger 发表于 2018-5-18 06:45:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (21)
 
 
12% (3)  踩
lyytju 发表于 2018-5-17 05:50
对,题目实际不难,但是我自己想歪了,一直想着greedy方法做,然后就炸了.面试官也没有提醒....然后第一 ...

确实没想到corner case 哈哈 不过我觉得这题也不算简单了吧 主要是不给hint这有点坑 面试官是扑克脸?
回复

使用道具 举报

我的人缘0
amber110 发表于 2018-5-18 10:00:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (38)
 
 
7% (3)  踩
感谢分享,感觉第四轮的思想和蠡口气雾散 cracking safe有点像?
回复

使用道具 举报

我的人缘0
ljl.lee 发表于 2018-5-18 12:47:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (9)
 
 
0% (0)  踩
感谢分享!祝好运!. 1point3acres
第四题 多个string的情况,是两两求出覆盖长度,按覆盖长度从多到少的顺序拼接,直到所有string拼接完成吗?
回复

使用道具 举报

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

使用道具 举报

我的人缘0
wenyitiger 发表于 2018-5-18 14:53:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (21)
 
 
12% (3)  踩
果然是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.
回复

使用道具 举报

我的人缘0
dododidibaba 发表于 2018-5-19 07:00:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
谢谢楼主分享!祝好运!

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

使用道具 举报

我的人缘0
ushergod 发表于 2018-5-19 10:03:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
wenyitiger 发表于 2018-5-16 15:36
写了下 试了几个基本case好像还行

虽然写的有点奇怪~
. 一亩-三分-地,独家发布
手抖 没想反对的 sorry!不知道如何撤销了
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-20 08:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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