google 面经 - proudmore的专栏 - 博客频道 - CSDN.NET
input string："+++–++-+"
游戏规则：每人每次可以 flip "++" to "–"（必须是相邻的）
第一问：generate all possible moves
第二问：determine if this player can will. 下一步没有连续的++
2.
1.先写反转链表，然后第二题把链表变成a1->an->a2->an-1
2.第一题是path sum难度一样的dp水果。 第二题给画布上的几个线段，问怎么画最快（移动画笔会浪费时间)
solution: 线段作为vertex，端点之间的连线是edge，转化成tsp问题
3.给一个字符串，问可否组成一个新串使得每两个相邻字符不重复
**solution：**O(n!)
4.先问简历，然后又是一个path sum难度一样的dp水果
5.扫雷
solution:
set mines,其他counter=0, 然后对每个mine周围的counter++.
click: if mine, lose. if empty, show counters and run dfs 打开连通分支
mark a flag: nothing happens
2 layers: UI + matrix
3.设计一个电话本系统，实现三个功能：查找号码 boolean isTaken()，添加号码 void takeNumber()，返回一个不在电话本里的没人用的号码 number giveMeANumber()。我一开始说用HashMap，这样前两个函数的复杂度都是O(1)，第三个是O(n)。面试官说能不能优化第三个函数，我说用BST，每个节点多存一个value记录这个节点下还有几个available的号码，giveMeANumber()的实现只要沿着value>0的node往下找就行了。这样三个函数的复杂度都是O(lgn).
- 要从server A 到 server B 备份很大的文件，网速很慢，文件改动很小, 用rsync: delta更新
5.
1.Word abbreviation,
e.g. Between=>b5n, friend=>f4d
Follow-up: implement
Bool checkduplicate(string [] dict, string word).1point3acres缃�
E.g. {feed }, feed => false; {door }, deer =>true; {dare}, deer => false
如果dict里有word 和input word的abbreviation 一样，则return true
follow up：如果调用很多次。 用hashmap<abbreviation, list<string>>
2.Given a list of words, find two strings S & T such that:
a. S & T have no common character. From 1point 3acres bbs
b. S.length() * T.length() is maximized
Follow up: how to optimize and speed up your algorithm
6.
onsite面了四轮，
设计random queue（面经题！！），follow-up，设计支持权重的random queue， 这一轮对复杂度的计算很多
第二轮，面经题，返回一个整数的平方和表示，使得个数最小。
第三轮，三道leetcode变种。返回二叉树的最小深度；抢银行的新题，一个数组不能连续访问两个相邻的数字，求和的最大值；求rotated sorted数组的最小值。这一轮比较开心。。
第四轮，我靠题目就是设计一个RMQ(http://en.wikipedia.org/wiki/Range_minimum_query) (我也是后来才知道这是RMQ的)。
solution：http://dongxicheng.org/structure/lca-rmq/
预处理空间+时间 O(nlgn), 查询O(1)
第一轮，给一个字符串数组，找出这样的字符串对（str1,str2），使得1，两个字符串不包含一样的字符，2. 长度乘积最大。我一开始对面试官说O(n^2)比较intuitive，然后写完了之后让我改进，后来想了一个按长度先排序，然后设置两个指针慢慢移动，估计会好很多。.
第二轮，偏向c++功底跟concurrency。实现memcopy，还有就是实现一个银行的类里面的几个算法，都很简单，但是对多线程调用的加锁需要有了解。最后又问了一个实现每次调用，运行5秒，期间不停循环自增的简单算法，follow-up是如何应对系统管理员尴尬地恰巧在这段时间内改了系统时间。
7.
1. 2个string排序，加special case 比如 'ch' 在'k'之前'j'之后.
2. 电话本。 用trie+count, 新号码沿着count>0的路走就行
3. string[]. 找2个没有common letter的string ，length乘积最大。
solution: new BitSet(26). 然后set(digit-'0'). 比较用 bitset1.and(bitset2)==0.
维护hashmap<bitset, list<string>>, 和top1, top2.每次更新hashmap的时候，如果有list size超过了top2, 更新top1,top2.
或者直接用a2b3c4d1…
Read full article from google 面经 - proudmore的专栏 - 博客频道 - CSDN.NET
No comments:
Post a Comment