Chapter 42 Google 2017 05
2017(4-6月) 码农类 硕士 全职 Google - Other - Onsite |Other在职跳槽
这周1才面的,回来回报一下大家~
一共5轮:
1. 印度人但口音不重
Warm up: 输入是一个字符串,写一个function判断这个字符串有没有任意的permutation
能够组成一个palindrome.很简单,统计一个每个字符的个数就行了. 第2题: 基本跟course
schedule一样,有n个event,还有一些这n个event发生的关系,比如{1, 2}表示2要在1之前发
生,输出任意的event发生的顺序.拓扑排序,应该是很常见的题目
2. 白人+白人shadow
有一个二叉树,有一个节点有2个父亲节点指向了它,删除其中的一条指向它的边,再返回这个
二叉树
Follow up: 如果有很多个这样的节点怎么办,需要返回一个valid的二叉树
再Follow up: 如果是BST怎么做,要返回valid的BST
最后再问问怎么unit test,再想一些corner case
3. 印度人印度口音
有一个class是用来写log的,大概是这样:
class Logger {
void start(int requestID, int timestamp);
void finish(int requestID, int timestamp);
}
每一个requestID都会start和finish,当一个request finish的时候就可以写入log了,但是
log的request必须按照时间顺序排好,意思就是先start的要写在前面. 我开始想的是start
需要排好序,想用hashmap + treemap,但三哥说start的timestamp一直都是递增的,写了一个
hashmap + queue
Lunch: 白人妹子陪吃饭陪聊天
4. 白人妹子
没记错的话应该是一道面经题,输入是一个矩阵,只有0和1,路径只能上下左右包含1,判断这
个矩阵是否有一条路径从这个矩阵的第一行到这个矩阵的最后一行
Follow up: 返回任意一条这样的路径
我还特意问了一下是不是返回最短的路径,妹子看了看题说就返回任意的一条..dfs或者bfs,
分析了一下矩阵会长什么样子和tradeoff,哪种情况下用哪种方法更好
5. ABC.
上来先问我用什么语言写,我说Java,他说好,那就假设输入是Java的source file,需要
remove source file里面所有的comment,再输出这个文件. 对于各种各样的情况讨论了一
会,有哪些corner case,然后时间复杂度和空间复杂度,最后才开始写code 最后一轮我有
点不太清醒了,code有些小错误没发现,不过总体应该还行.. 面完感觉就是...略简单..其
实这次面试我准备了很长时间,看了地里的各种面经,然后我准备的什么KMP, BIT, Segment
tree,Union find,trie,值二分,区间DP等等这些面经里常见的都没考.. 但是没出结果之前
还是很虚,一直在想面试时还有哪些地方应该做得更好.http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=282734
42.1 Binary Search _last_equal_or_less
2017(7-9月) 码农类 博士 实习 Google - 内推 - 技术电面 |Otherfresh grad应届毕业生
2 min 前刚面完...加面先聊了一通research相关的.
要求实现一个计时的 map 和其两个功能,set和get:
- set(key, val, time)插入val和time for key.
- get(key,time) return val if not found return None
每个key可以有好几个val和time.我选了dict来实现.因为我用的python,用了
defaultdict(list),面试官一开 始没反应过来.
tricky部分是,set调用多次,不一定time递增调用,然后get,如果time＝1,3,4 for
key1, get(key1, 2), 要求返回time＝1的val.我一开始忽略了,结果直接返回none,因
为2不在1,3,4里面...面试官(安慰我?)说好多人也犯过这个错误.连连道歉然后猛
改...越改越紧张,磕磕绊绊.问get的复杂度,O(N).面试官全程很nice很照顾,就是
自己太紧张了!!!
follow up如何优化get,我说keep a sorted list based on time,这样get是logN,不过
set也是logN了. 然后就聊天,聊google的开放文化 希望能有好结果吧...也祝福各位http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=286100
- STL
set::upper_bound
Check Patience Sort for LIS
可以用set来存储时间,其本质是red black tree.
如果upper_bound返回值等于s.begin(),那么说明没有time值,返回NULL. 否则返回upper_bound()-1那个时间点上面的值.
- How to understand up/lower bound in STL?
lower_bound and upper_bound are designed for insertion. lower mean the first place you can insert, and upper means the last place you can insert.
- Write a balance binary search tree yourself
set -> LogN
get -> Find last less or equal
42.2 Longest Ridge
2017(1-3月) 码农类 博士 全职 Google - 内推 - 技术电面 |Otherfresh grad应届毕业生 1. 给一个数组,找最长山脉.山脉的定义是先升后降. 比如,假设[2, 6, 1, 8, 9, 2, 7, 3, 10], 那么[1, 8, 9, 2]就是最长山脉.
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=268861
