乐趣区

关于google:Google-Foobar-Challenge

– 引子 –

这几年因为招聘的须要,筛过很多简历,也因而看到了很多很有意思的简历。

比方有两个印度老哥在简历里顺便写上“Father’s Name”,用 Google 搜到了其中一个,貌似是个祖上就主持祭祀的家族,种姓(caste)大略得是婆罗门(Brahmin),像是借机显摆本人家族的煊赫;有些人则会用 Jain(印度耆那教)或者 Islam 作为其 family name,或者是用宗教信仰来拆穿本人的低种姓吧。

另有一个印度老哥,在简历上写了“Completed all 5 levels in Google foobar challenge”,看着也不明所以,搜了一下,发现还挺有意思。

– 这啥 –

搜到的是 @xiaohanyu 老哥在 2017 年写的一篇博客 [1],说他某次搜寻“Haskell QuickCheck”,看到页面上播放了一段动画,并问他是否要加入一个挑战,他抉择了承受,而后开启了一段微妙的旅程 —— 做了一个算法套题,被 Google 的 recruiter 邀请到悉尼加入了一场 onsite 面试( 惋惜最初面挂了)。

于是我也搜了同一个 Query,过后没看到啥反馈;回头把他的经验看完,筹备敞开搜寻页的时候,发现我错过了那段动画,只看到它最初的问题:

Curious developers are known to seek interesting problems. Solve one from Google?

(页面内容下陷,露出了暗藏空间)

当然我也抉择了“I want to play”,开启了这个暗藏空间[2]。

– 入坑 –

下图是收场界面,Google 把它做成了一个仿 Linux 命令行的闯关游戏,有一个 storyline —— 你潜入了 Command Lambda 的太空飞船,工作是阻止他启动“末日安装”覆灭兔子星球,并且拯救飞船上的兔子们。

(仿 Linux 命令行的闯关游戏)

你能够用 help 查看可用命令,或者用 request 开启挑战(支付一道题目),Google 会依据题目的难度,给每一题留出相应的工夫(2 到 30 天不等),你能够用 Java 或 Python2.7 来编码。

编码实现后可用 verify solution.py 校验答案,如果 10 个 case(2 个在题面中给出,8 个暗藏)都通过,再用 submit solution.py 提交,而后用 request 支付下一题。

– 题目 –

这套题共 5 个 level,每个 level 别离会从题库中随机选出 1、2、3、2、1 题。因为题面比拟长,这里只简略介绍下,感兴趣的同学能够到我的 Github 查看[3]。

其中 Level 1 & 2 的题目大抵对应 LeetCode Easy 级别,比方我做的这几题别离是质数筛法、数列找法则、版本号比拟,不太须要花心思。

Level 3 的题目大抵对应 LeetCode Medium 级别,我遇到的某题是二维迷宫搜寻的一个简略变种(对 BFS 略加革新即可),其余 2 题比拟琐碎,这里不开展。

Level 4 对应的应该是 LeetCode Hard,题目也比拟有意思。我做的其中一题须要判断有向图中是否有负环(bellman-ford)、再枚举所有组合,暴力求解(因为只有 5 只兔子);另一题带点计算几何的意思,不过想分明了也很简略,最初也是枚举了所有可能的组合,鼎力出奇观。

Level 5 就比拟麻烦了,所以给了 30 天工夫。题面粗心是 w * h 矩阵中的每个元素能够有 s 种状态,对矩阵的操作 [替换任意两行 / 两列] 失去的后果属于同一等价类 —— 求总共有几个等价类。

因为可能的状态总共有 pow(w * h, s) 中,鼎力曾经不能出奇观了;我没想到解法,只好偷偷去搜了一下题解,发现不仅要用到波利亚计数定理(Pólya enumeration theorem),而且还得做一些额定的推导(例如 |G| = w! * h!),具体就不在这里开展了(因为我还没 AC)。

– 其余 –

尽管这个游戏的网址 [2] 能够间接拜访,然而须要邀请码能力开始挑战,如果你也感兴趣的话,能够试着搜搜其他人中过奖的 Query(比方前述“Haskell QuickCheck”),碰碰运气。

值得一提的是,在 Level 3 完结的时候,游戏会给你一个邀请码,并且问你是否违心留下你的个人信息,以便 Google Recruiter 分割你(这招聘我的项目可算是很上心了)。

(图中邀请码曾经用掉了,别试了)

最初,如果你试来试去也没解锁游戏,能够思考给咱们投个简历,咱们的面试也是个闯关游戏,每一面都会有算法题,而且编码工夫更紧,挑战绝不亚于 foobar 的 level 3 ~

↓↓↓ 长期招聘 ↓↓↓

投放研发工程师 — 穿山甲 @上海

https://job.toutiao.com/s/JP6…

后端研发工程师 – 穿山甲 @北京

https://job.toutiao.com/s/JP6…

字节跳动所有职位

https://job.toutiao.com/s/JP6…

– 欢送关注 –

– 参考资料 –

1. Google foo.bar 面试记 – xiaohanyu
2. Foobar with google
3. My solution to google foobar challenge

退出移动版