Chapter 41 Google 2017 03
41.1 587. Erect the Fence
https://leetcode.com/problems/erect-the-fence
round 1:
黑白棋.给一个棋盘和一个棋子的坐标,判断这个棋子是不是活的.Leetcode也有类似的比这个难得题目.DFS/BFS看能不能走到棋盘的边缘就好.分析复杂度.
给一堆点,问怎么画凸包,说思路就好.这个面经上没见过,lz当时是完全不知道凸包的概念.
round 2:
写有weight的随机数生成器,请参见以前的面经.写完之后问了如何测试.
给一个int array,和一个这个array里面存在的数字,把这个数移到array的最后面.two pointers就好.
round 3:
给一个int array,找任意一个popular number, popular number就是出现次数大于等于array length 的 1/4 的数.其实就是 Leetcode 169, 229 Mojority Element. 第一问unsorted array 用的hashmap. 第二问sorted array用的binary search.lz没有说moore’s voting algorithm的做法感觉有点假.第二问复杂度,worst case问的很细.
round 4:
类似Leetcode 26, 80, remove adjacent duplicate elements from a list of characters.
array.html#remove-duplicates-from-sorted-array-ii
类似Lint code data stream median, 写个API,有两个方法,addURL(String url) 和 getURL(),getURL()返回的是目前为止所有URL长度的中位数.lz使用两个heap做的.follow-up: what if we know the range of the input,比如我们知道URL的大小不会超过2k,那有没有别的implement的方法.这个没想出来请大家指教
Convex Hull
http://www.1point3acres.com/bbs/thread-168330-1-1.html
http://cyw3.github.io/YalesonChan/2016/ConvexHull.html
http://algs4.cs.princeton.edu/99hull/
https://www.coursera.org/learn/algorithms-part1/lecture/KHJ1t/convex-hull
Check this animation
41.2 Othello Game
http://massivetechinterview.blogspot.com/2015/07/cc150v5-88-design-othello-game.html
https://zh.wikipedia.org/wiki/%E9%BB%91%E7%99%BD%E6%A3%8B
41.3 RLEIterator - run-length encoding
Given an Iterator class interface with methods: next() and hasNext(), design and implement a
RLEIterator.
RLE的定義:
每兩個數字是一個pair,前者是要印出的次數,後者是要印出的數字
input 是一串壓縮過的數字, 3 9 0 1 2 4 -> output則為 9 9 9 4 4
input 是 Iterator-> output也是 Iterator
和LC284類似,都是要implement Iterator interface.
Call的方式會是這樣:
Iteratorvalues = …
while (values.hasNext()) {
… do something with values.next()
}
在call RLEIterator.next()時,要照上面的規則一一印出.
一開始光要搞懂題目就花了一些時間,
我之前寫過的Iterator題目都是List或TreeNode,
這次題目是要return Iterator我疑惑了很久.. 1point 3acres 璁哄潧
是面試官把上面call的方式寫出來我才領悟.
中間一直寫的卡卡的,還有跟面試官問了很多提示,
沒有懸念的掛了～
順帶一提,電面一面是LC340.
http://www.1point3acres.com/bbs/thread-236019-1-1.html
https://en.wikipedia.org/wiki/Run-length_encoding
这道题是Run Length Encoding的逆序.
bloomberg-2016.html#histogram-iterator
报一个谷歌onsite面经,二月份的时候面的,当时遇到两个国人一个ABC小哥一个三哥,感觉还是比较幸运而且和面试官交流的也不错,最后还是跪了,不知道实际标准是什么,贡献出来仅作参考. 第一轮给一个数组,找一个index使index左边的数字之和等于右边的数字之和,用双线扫描法秒了,第二题是地里有的word square,生成一个二维数组包含word list里面的所有单词,单词可以竖向、横向、斜向排列,楼主记得当时见过这道题但没仔细想过,想了一会说用dfs,面试官说可行,然后就写代码,然而写了一半并没有写完就结束了.. 第二轮小乌龟在二维坐标系上爬,可以顺时针调转方向,实现两个函数前进和turn right,记录乌龟当前所在坐标,如果x或y坐标小于0要throw exception,然后给一串字符串例如2T3T5, 表示乌龟先向上爬2步,向右转爬3部在向右转爬5步,调用之前的两个函数得到乌龟最后的坐标,有一个tricky的地方比如32T不是爬32步再右转,而是3*2T=6T, 我写完面试官才指出来,然后follow up是在字符串里加括号比如3(4T2T)5T, 就是把4T2T的动作重复3遍,这个我写的不是很好,最后没写完解释了一下,面试官说可以了懂我意思了.. 第三轮blur image. 有一个记录pixel的大矩阵,用一个小的window矩阵在大矩阵上扫描,把window里面的每个数换成window里面所有数的平均数,window每次平移一格,和国人姐姐讨论了很久开始写,最后虽然没写完但国人姐姐很好的给我指出了两个错误让我改了才拍照. 第四轮和LC43有点像,不过是multiply两个任意大的3进制数,国人大叔特别好说只要把这道题做出来就好了,最后纠结了一下写出来了, 大叔有质疑同个位置上的数相加的时候会有integer overflow的情况,我就改了一下每次加完就mod一下然后增加进位,大叔说可以拍了照就愉快的结束了. 当时面完感觉还可以,但是现在想想可能还是写代码的速度不够快前三轮都没写完,不过狗家题目真是难,全写完感觉还是很不容易de…
链接: https://instant.1point3acres.com/thread/255005
2017(1-3月) 码农类 博士 全职Google - 猎头 - Onsite |Fail在职跳槽
去年年底g家猎头主动找上门, SRE. 然后赶紧刷题, 面试前基本把lc上g家的题刷完了.2月底onsite,MTV.
第1轮 API设计. 就是timestamp那一类的
第2轮 输入是 “+ 1 1 ( * 3 5 4 6)” 这种字符串,有+-/(). 求值. 也就是求 1+1+(3456)
第3轮 第一题类似regular expression匹配这种的. 输入两个字符串, 输出bool是否匹配 秒了.
第二题判断两个二叉树是不是相同. O(1) space. 递归不算O(1), 我不会.就要hint. 面试官说, 如果TreeNode里面储存了 Node* parent,你有没有办法. 我就试图O(1) space Inorder遍历. 被卡住了.在提示下磕磕绊绊的最终写了出来.
第4轮 输入一个6位ip地址的表示形式,输出一个对应的128位整型. 输入可以是这样的“1:a:abcd:23:0:0”, 也可以出现::表示省略. 比如“1::2”, 等价于 “1:0:0:0:0:2”. 输入字符串里最多出现一次省略符::
第5轮 输入是一堆各自形状的二维俄罗斯方块. 问他们能不能组成一个正方形. 我用的dfs+回溯.面试官顺便考察interface设计. 比如怎样用数据结构表示俄罗斯方块, 怎样表示旋转. 怎样增加可读性,之类的.
几个题都不难, 比我准备过的hard题简单很多. 都做出来了, 除了判断二叉树相同那个. 今天hr告诉我被hc拒了. 没说理由. 我问我能不能知道面试官的feedback, hr说那是保密的. 但是我看地里很多人发面经都是会有feedback的呀… 然后hr说虽然SRE组不要我了, 但是会把我“大力推荐”到普通SDE组. 不知道这是真的呢..还是为了让我开心一些.
刚刚面试完我感觉还是挺不错的. 毕竟题都做出来了嘛, 沟通也很顺畅. 唉, 继续努力!
41.4 393. UTF-8 Validation
https://leetcode.com/problems/utf-8-validation
2017(1-3月) 码农类 博士 全职 Google - 网上海投 - |Other其他 五轮 1. 求区间的常见运算,并集,交集之类的 2.类似lc utf-8的变种 3. jotto word guess game (跪了) 4. leetcode 类似英雄救公主一题的变种 5. class design calculator
http://www.1point3acres.com/bbs/thread-228589-1-1.html
struct Solution {
bool validUtf8(vector<int>& data) {
int c = 0; // the number of valid octet after the first valid octect
for (int v : data) {
if (c == 0) {
if ((v >> 5) == 0b110) c = 1;
else if ((v >> 4) == 0b1110) c = 2;
else if ((v >> 3) == 0b11110) c = 3;
else if ((v >> 7) != 0) return false;// the first octect cannot be 10xxx...
} else {
if ((v >> 6) != 0b10) return false;
--c;
}
}
return c == 0;
}
};41.5 Hashmap with TTL
2017(1-3月) 码农类 硕士 全职Google - 内推 - Onsite |Pass在职跳槽
onsite 一共5轮
第一轮:实现auto-complete,也就是trie,支持搜索单词和包含wildcard的单词例如ab*cd
第二轮:1)给一个int类型的二维矩阵,寻找最长严格递增的path长度,path可以上下左右走(dfs+memorization)
2) 一个boolean类型的二维矩阵,问是否存在一个矩形区域,它的4个顶点都是True
第三轮:实现一个hashmap,其中的每个元素包含一个duration,超出duration的元素需要expire掉,写出get和put方法
午餐
第四轮:lc permutation II,follow up,如何实现一个类似iterator的东西使得可以每次get任意数量的结果(我没答上来)
第五轮:1)complete binary tree,计算node总数
2)和第二轮第二题很相似,一个只有1或0的矩阵,求4个顶点都是1的矩形区域的数量
可以有不同的做法,一种是每次get时判断元素是否expire了,做相应处理,也可以用类似queue的数据结构,每次get时从queue的头部pop掉所有过期的元素
41.7 Find Shortest Non-substring With Give Alphabet
// 1. string to integer with base 2
// 2. int to binary conversion
string shortest(string s) {
for (int i = 1; i <= s.size(); ++i) {// i is the length
set<string> st;
int h = 0;
while (h + i <= s.size()) {
if (st.size() == (1 << i)) break;
st.insert(s.substr(h, i)), h++;
}
if (st.size() != (1 << i)) {
auto it = st.begin();
for (int g = 0; g < (1 << i); ++g) {
if (it == st.end() || stoi(*it, 0, 2) != g) {
string r(i, '0');
while (g) r[i-- - 1] = (g & 1) ? '1' : '0', g >>= 1;
return r;
}
++it;
}
}
}
return "";
}