班加罗尔谷歌软件工程师面试

恢复筛选器： 我接到一位招聘人员打来的电话，他问我的工作经历。她还就某些排序算法的复杂性、最坏情况和最佳情况提出了一些基本问题。

之后，我有大约20天的时间进行第一轮电话面试。

电话采访： 这是一个45分钟的通话，分享了谷歌文档。他直接跳到这个问题上。

问： 给定一个只包含I和D的模式。I表示增加，D表示减少。设计一个算法，按照这个模式打印最小的数字。1-9之间的数字和数字不能重复。

在对algo进行了简短的讨论后，我在shared doc上编写了代码。他对代码很熟悉，我们提前5分钟完成了。

这一轮结束20天后，我被要求进行现场采访。

第一轮： 给定（x，y）坐标，创建一个函数，使每个坐标唯一映射到一个整数。还要确保给定一个整数，您应该能够找到（x，y）坐标。所以F（x，y）=z，还有逆F（z）=（x，y）。

第二轮： 你会得到一个由一百万个数字组成的数组，并提供一系列索引（比如左、右）。对于多个查询，每个查询都有左索引和右索引，输出该范围内的最大值。

第三轮：

Q1）假设房间左侧有小偷，且传感器数量有限。他必须从右边伸出手，但没有抓住传感器。每个传感器都放置在房间的任意点上，其覆盖范围在半径r内。找出窃贼是否可以在不接触任何传感器范围的情况下到达右侧。

问题2）假设一条长凳上有n个座位，坐着的人很少，每次当一个新人坐在长凳上时，告诉他座位号，这样他与其他人的距离就最大了。

午休时间： 我和一位谷歌员工在一起，我们就他正在从事的项目、工作文化和其他方面进行了非正式讨论。

第四轮： 如果可能的话，给出一个0和1的字符串，告诉需要多少次拆分，这样每个拆分部分都是一个数字，可以用二进制中的5的幂表示，并告诉最少的拆分次数。