12/2017 - 01/2018 Google 电面汇总

题 源来自一亩三分地以及geeksforgeeks

1/18

给两个char array，其中有一些char为backspace就是删除前面的字符，要求输出一个boolean判断两个char array是否相同，时间要求O(n) , 空间要求O(1)

例如：

[a,b,'\b',d,c] 和[a,d,c] true

[a,b,'\b','\b','\b',d,c] 和 [d,c] true

[a,b,d,'\b'] 和 [a,d] false

先给了用Stack的方法，TimeO(n), SpaceO(n)，没让写code

之后要求TimeO(n), SpaceO(1)，po主试着从前往后parse没成功，好久之后小哥给提示从后往前parse

1/12

給你兩個string

if function(s1) == function(s2) return true

else return false.

function做的事情 遇到b 就刪除前面一個字元 其他就不管 當b太多的時候 return ""

for example

accc => accc

accb => ac

abdd => dd

如果string 非常大

無法fit memory 怎麼辦

答案: 用iterator 然後從後面開始讀

不過hint 從後面開始的 iterator 隔了20min才跟我說 從前面我怎麼試 都不行

10/31

Build robot: you are given a list of parts of the robot, and for each part, you also have a list of parts needed to be finished before building this e. Find out the order

题很简单，就是topological sort，问了时间空间复杂度

12/31

问了一道题

给一个数组，n的长度（n >=1），含有所有1 - n的数字，要求得到一个最小的index，满足条件: 如果把数组小于等于index的部分排序好，并且把数组大于index的部分排序好，那么整个数组就排序好了。

看题目可能有点绕，以下是当时给的两个examples：

3 1 2 5 4

返回的index为2，即如果(3,1,2)和(5,4)分别排序完成，那么整个数组就排序好了。

2 4 3 1

返回的index为3

注意由于含有所有的1-n的数字，所以数组里是没有重复元素的。

1/17

刚面完GG,399, evaluate division,就是把字母换成了币币之间的汇率,建个map 存下edge, graph dfs 或者bfs，搜索一下。

gg的风格感觉变了，不能一上来就写题，他会要求我问一些关于这个input，output的问题，感觉这个答得不好。很快写好代码，面试官特意强调不写代码，接下来讨论，如果有多条路径都能从起点到终点，但是得出的转换汇率不同，这种情况你怎么处理。我反正懵逼了。。当时我就以为他要找个最短路径，他说不是。之后我说那就返回这些路径结果的平均值。他又说不是..我就反问他，这题设有问题吧，这汇率转换，虽然路径不一样，但是结果应该 一样的吧。之后他说不同的交易所肯定有价差的呀，他要的是，最低的汇率，和最高的汇率.... 原来他是想搬砖套利赚钱..目测面试官是个玩币的

1/18

题目是 increasing triplet subsequence。

这个应该是地里的老题了。然而悲剧的是，我并没有见过这道题，当时给我的时候，我是硬想了一个算法。时间是O（n）但是空间也是O（n）。后来在面试官的提醒下，把空间降为了O（1），不过也没有时间写代码了，就这么结束。

11/18

刚刚结束的电面，人品爆发遇上亚裔小姐姐，英文巨好，应该是abc.

上来让自我介绍一下，然后做题

类似利口 64 不过是求最大和

8/16

Given a robot cleaner in a room modeled as a grid. Each cell in the grid can be empty or blocked. The robot cleaner can move forward, turn left or turn right. When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.

The control API:

interface Robot {

// returns true if next cell is open and robot moves into the cell.

// returns false if next cell is obstacle and robot stays on the current cell.

boolean Move();

// Robot will stay on the same cell after calling Turn*. k indicates how

// many turns to perform.

void TurnLeft(int k);

void TurnRight(int k);

// Clean the current cell.

void Clean();

boolean Move(Direction d);

}

sample input

++++++++++

+........+

+...^....+

+.+......+

++++.+++++

+.....+

+++++++

要求用给定的API打扫完所有empty格子。

楼主一开始想用bfs做，后来发现我连robot的位置都不知道。。

于是面试官简化

简化1：robot自己可以知道自己当前的位置。就是两个新API：robot.x(), robot.y()

楼主到这里还是一脸懵逼，于是面试官又提示：你怎样让robot从一个点走到格子里的另一个点。

楼主最后磕磕绊绊把最后一个提示想出思路来了，但是没写完就到时间了。

1/6

第一题，后序遍历二叉树，要用迭代法来做

第二题，给一个数组，里面可能有重复的数，实现int pick(int target)，返回target的index, 如果target出现多次，要求返回每个index的概率一样

比如：｛1， 2， 3， 3， 3｝

pick(3) 要求随机返回2， 3， 4其中的一个，并且概率一样

1/17

电话面试一共45min，一共面试了60分钟左右

首先介绍了一下做过的项目，大概10min时间吧，主要考察个人表达能力吧

然后做题，在Google Doc上写代码，问题大概是，美国大选，有很多选票，Vote，每个Vote有两个属性，一个name一个timestamp,表示投票给谁以及投票的timestamp

大概问了三个问题

1.给定一个timestamp,找到这个timestamp之前的得票最高的人，借助于HashMap实现即可，说了下思路，不需要写代码

2.如果是给定一个timestamp,找到Top K的投票最多的人怎么办呢，corner case是如果有两个人投票一样怎么办，基本思路是HashMap统计每个人得票次数，刚开始考虑用Heap来实现，找TopK，但是追问，如果投票相同的人算一名，找Top K名改怎么找，思路是用TreeMap来实现，用数量作为Key,值是List，然后又追问，如果不考虑数量相同的人，怎么找Top K,除了用堆之外，还有没有其它更好的方法，答用类似Quick Sort的找第K大算法，感觉还比较满意，写代码实现一下

3.如果给定的是一个List of name，name按照投票数量从大到小排序，找到一个timestamp，使得到达这个timestamp之后，Top K的人选和给定List一致，基本思路就是先排序，然后不断的用HashMap和TreeMap做统计，如何添加和删除元素，分析时间复杂度.

然后让问我有没有问题，原来不是一个team的同学面的，所以就问了下，在Google每天的工作状态是什么样的，大概介绍了下，感觉还是非常自由的，最后遥祝了一下，Good Luck!

1/17

刚结束的狗家店面，国人大哥出的原题， 人挺nice的

蠡口恶气就

楼主当时想dfs，bfs都可以做，想都没想就直接bfs了，后来想了想好像dfs简单很多。面试官大哥估计没想到有人拿bfs解，我拿bfs写完之后一直说very good， 估计心里想的是“还真有二货用bfs解这个题”。

1/17

中国大姐 上来就做题，binary tree serialize and deserialize

9/18

9.18电面，白人小哥准时打来，没问简历直接上题。一道题，有个整数数组，求是否在其中有出现频率至少是N/4的数字，N是数组长度。lz和小哥依次讨论了brute force，排序，和二分方法，前两个写了代码和test case。在讨论二分法时，小哥假定数组已经排好序。lz想的是出现频率至少是N/4的数字应该不多于4个，从左右两端向中间二分同时检查左边相同数字的个数。然而时间太短了这个没说好。。估计也不对。。面试官的想法是从最左开始以N/4的跨度向右边扫。如果左右两端数字相等则返回true，否则二分查找区间内第一个元素在数组中首次出现的位置，再用N/4的跨度查下去。。不过lz觉得还需要查区间内最后一个元素，比如遇到[3,4,4,4,4,4]，总是从3开始查的话就死循环了。后来在leetcode上看到了相似的题目majority element，discuss里面的解法个人认为还是更好一些。希望能帮助到大家吧。

12/17

设计一个类

class EncodingChecker {

EncodingChecker(String pattern) { ... } // constructor

boolean isEncoded(String s) { ... } // for any string s, check whether s is encoded from pattern, see below

}

pattern = 'abcabc'

s = '123123' -> True.

   = 'cbzabc'   -> False

   = 'xyzxyz'    -> True

二问：如果pattern不是一个而是一百万个，怎么写isEncoded?

12/16

第一轮两道题，一个数组中有重复元素，指定元素的重复次数（非常巧和BB的电面一样）；第二题是给出n个数的全部排列，脑子有点抽和nextPermutation想混了没写完

当晚收到邮件挂掉但是给了加面

第二轮只有一道题，一个数组非常长，给订一个目标值求加和超过该值的最短连续子数组，写出来之后follow up问当数组特别大要跨主机存储时该怎么搜索，说了一下思路当晚就收到邮件过了，目前正在加紧准备，希望一月有个好结果

1/12

一个多小时前刚刚结束的狗电话。楼主16Fall转的计算机，申请的是18年的SDE NewGrad。

一道完整的题，一点点的展开，很狗，很狗。

让我写一个"人"类，含有名字跟年龄。用private+setter/getter，楼主琢磨考encapsulation

让我写一个“码工”类，楼主琢磨考inheritance

让我区分“码工”类里面，各种variables跟methods，是public/protected/private/default和why.

让我写一个"给予"跟“接收”的方法

把第四步的方法，多线程化，考multi-threading + synchronization

哪里会锁死和如何解锁 （时间到了，就没细问）

10/12

一道题

有一个游戏，有人名和分数，实现两个function

void update(String name, int score).

int getByRank(int rank)