Google onsite 4轮

请问楼主第一题为什么input是List<String> 不是string呢，还有请问应该怎么算结果呀。。lc的那些calculator题好像没有包含+-*/和括号所有的，谢谢。。！

第三题在16年的面经上就出现过，一开始觉得是lcs，但是仔细一想貌似行不通。

请问第二题怎么做的。

cengjing 发表于 2018-12-9 05:21
求楼主讲讲第三题

一点想法：假设s=ABCDE, p=CBAED。那么在p中A之前的两个字符B和C，必须从s里面取出放在A之前。因为s中取出B和C的顺序没有限制，所以可以形成p中的任何顺序。只要我们能匹配s'=ADE, p'=AED，不论此时B和C在A之后的什么地方，两步一定可以完成最后的匹配。如果此时s'==p'，返回0；不然，例如s'=ADE, p'=AED，结果是子串DE匹配子串ED的步数加一，（因为A在最后一步需要提到第一个位置上）。不断递归下去。只是如果有重复的元素就不知道怎么办了。
     

xil12008 发表于 2018-12-23 04:17
一点想法：假设s=ABCDE, p=CBAED。那么在p中A之前的两个字符B和C，必须从s里面取出放在A之前。因为s中取 ...

我想可以这样：

显然在最佳移动方案中，每个字母最多只需被移动一次。因为假设如果有个方案中会出现某字母（比如A）被移动了2次的情况(先移动A，再移动其他t个字母，然后再移动一次这个A），那这个方案得到的效果等价于（先移动那t个字母，再移动一次A），但是后者比前者少一次操作。

所以，对于某个s->p，如果最佳移动步数是k的话，那就是说只有k个字母被移动过。剩下的n-k个字母一定没有被移动过。这没有移动过的n-k个字母在目标字符串p中一定会连起来并出现在p的最后（即后缀）。因此，只要在p中找到最长的满足“该后缀是s的一个子序列”这一条件的后缀（find the longest suffix of p that is a subsequence of s），即可得到最佳步数k。

stellari 发表于 2018-12-23 05:29
我想可以这样：

显然在最佳移动方案中，每个字母最多只需被移动一次。因为假设如果有个方案中会出现某 ...

感觉是正解呀。这题好像还有一个follow up，一次可以移动一个字串到头部，而非字符。大神有什么想法吗？
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=465437&extra=&page=1

xil12008 发表于 2018-12-24 01:09
感觉是正解呀。这题好像还有一个follow up，一次可以移动一个字串到头部，而非字符。大神有什么想法吗？
...

链接里的题和你的描述不是一个意思吧。那个面经里的题是说用B的subsequence（可重复使用字母）去组成A，也就是说A和B的长度很可能不相等，且A中的每个字母可能在B中没有出现，也可能出现多次。比如A="abcabcabc", B="bacd"

MacJordan 发表于 2018-12-9 06:08
请问第二题有比O(pos+len)更好的思路嘛

第二题可以O(log10(pos) + len)

首先定义：
f(1) = 个位数的数字总量 = |{0 ~ 9}| = 9
f(2) = 二位数的数字总量 = |{10 ~ 99}| * 2 = 90 * 2
...
f(k) = k位数的数字总量 = 9 * 10^(k-1) * k

给定一个pos，首先用O(log10(n))的时间找到最大的k，使得f(1) + ... + f(k) <= pos

然后我们只需要用O(1)时间（做除法）就可以在一组全是(k+1)位数的序列中定位pos（非整除情况下要处理一下corner case）

第四题的关键词是 snapshot isolation 和 multi-version concurrency control (MVCC)

handler本质上是一个逻辑时间戳，一般用64位长整型（Java里可以用long）

存储布局如果只是回答面试题的话可以选
--
ArrayList<TreeMap<long, int>>
--
但是实际系统中是不太可能用这种数据结构的，因为空间overhead大，version数量没有很大的情况下性能也不快，所以
--
ArrayList<LinkedList<Pair<long, int>>
--
反而更好一些

然后SnapshotArray中维护一个 long currentSnapshotId; 计数器，takeSnapshot()时只需要 return currentSnapshotId++;

set()的时候将currentSnapshotId和value一起append到index的位置
get()的时候在index位置寻找小于等于handler的最大snapshot id，返回对应value即可


关于现实中MVCC的实现可以看看这篇小文章，介绍得还不错：
https://thenewstack.io/multi-version-concurrency-control-mvcc-design-decisions/

stellari 发表于 2018-12-24 03:01
链接里的题和你的描述不是一个意思吧。那个面经里的题是说用B的subsequence（可重复使用字母）去组成A， ...

哦哦，这样面经上的题似乎也是每次匹配最长的A的suffix和B的子串了。