我就是好奇,男生女生找工作真的有什么区别?

一亩三分地论坛

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

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 3078|回复: 42
收起左侧

google onsite

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

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)'
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)   【踩】
全局: 顶  86% (13)
 
 
13% (2)  踩
写了下 试了几个基本case好像还行
  1. words = ["lee","abcde","eel","cdefg","uiab","oop"]
  2. print findshortest(words)
复制代码
. 1point 3acres 论坛
虽然写的有点奇怪~. visit 1point3acres for more.

  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
  9. . Waral 博客有更多文章,
  10. def findshortest(words):
  11.     data = {}
  12.     def dfs(visited):
  13.         if visited not in data:
  14.             data[visited] = ""
  15.             lvisited = list(visited). Waral 博客有更多文章,
  16.             for index in xrange(len(lvisited)):
  17.                 if lvisited[index] == False:
  18.                     lvisited[index] = True
  19.                     k = shortest(dfs(tuple(lvisited)),words[index])
  20.                     if not data[visited]:
  21.                         data[visited] = k
  22.                     else:
  23.                         if len(k) <= len(data[visited]):
  24.                             data[visited] = k
  25.                     lvisited[index] = False
  26.         return data[visited]
  27.     return dfs(tuple([False for x in xrange(len(words))]))
复制代码
回复

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

对,需要concat
回复

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

我的人缘0
wenyitiger 发表于 2018-5-16 14:20:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (13)
 
 
13% (2)  踩
第四题DFS+memorization?第一问来做然后memo  memo(1,k) =  min( merge(memo[1:j],memo[j:k]) for j in k)?.1point3acres网
比如 ["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% (13)
 
 
0% (0)  踩
wenyitiger 发表于 2018-5-16 15:36
写了下 试了几个基本case好像还行

虽然写的有点奇怪~
. 留学申请论坛-一亩三分地
对,题目实际不难,但是我自己想歪了,一直想着greedy方法做,然后就炸了.面试官也没有提醒....然后第一问需要check一下一个string是不是在另一个里面,这是一个corner case
回复

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

我的人缘0
ljl.lee 发表于 2018-5-18 12:47:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩
感谢分享!祝好运!
第四题 多个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
Barbados 发表于 2018-5-18 13:46:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  69% (9)
 
 
30% (4)  踩
我找到一个第四轮的题目链接,greedy是可以解的:https://www.geeksforgeeks.org/shortest-superstring-problem/
回复

使用道具 举报

我的人缘0
wenyitiger 发表于 2018-5-18 14:53:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (13)
 
 
13% (2)  踩
果然是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)  踩
谢谢楼主分享!祝好运!
. From 1point 3acres bbs
请问面的过程中就是不停的出题和讨论题目吗? 会不会串着问一些语言方面的基础问题?比如说说说java的继承多态啊,static是怎么回事之类的?
回复

使用道具 举报

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

虽然写的有点奇怪~

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

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

custom counter

GMT+8, 2018-7-20 20:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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