关注小程序 找一找教程网-随时随地学编程

Go教程

Google Foobar Challenge

image

- 引子 -

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

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

image

另有一个印度老哥,在简历上写了 “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?

image

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

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

- 入坑 -

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

image

(仿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 联系你(这招聘项目可算是很上心了)。

image

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

最后,如果你试来试去也没解锁游戏,可以考虑给我们投个简历,我们的面试也是个闯关游戏,每一面都会有算法题,而且编码时间更紧,挑战绝不亚于 foobar 的 level 3 ~

↓↓↓ 长期招聘 ↓↓↓

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

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

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

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

字节跳动所有职位

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

- 欢迎关注 -

weixin1.png

- 参考资料 -

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