G面经4

2016年11月05日 湾区

两周前面的G家实习，两轮电面，前天收到hr消息，拿到open offer，可以guarantee internship，但还要和team host聊，由Google定项目。

第一轮

一个m*n的matrix , 从左上到左下有多少种走法。用dp

follow up 1 : 有一个点(x,y)必须要经过，有多少走法。然后优化内存，用rolling array

follow up 2 : 有一个set的点都要经过，有多少走法。我说要用HashSet来快速找点，然后问Point class怎么做hashing，写了hashCode function

第二轮

先是两道特简单的字符串题，然后面试官说"Here comes the real question"

给一个字符串的abbreviation ，就是把一些连续的字符转成数字，比如apple -> a2l1 , 然后让写一个函数验证一个带数字缩写是不是另一个字符串的缩写。two pointer秒过

第二道是给一个排好序的字符串数组，有n个字符串，还有一个前缀prefix字符串，长为m,要求函数返回start index和end index，其中所有字符串都以prefix开始，先用binary search，达到m*log(n)复杂度，面试官挺满意，然后我又给了个Trie树预处理O(所有字符串长之和)，之后每个prefix都可以有O(m)的查找。面试官挺高兴，又聊了聊java 8的新feature，保证lamda和stream api。

题挺简单的，代码都写完了，后来想起来个exception,面试官下线后趁还没把我踢出去给改了