Google onsite 4轮

四轮onsite

1. 计算器

(1+2)*3+4  

输入List<String> 算结果

2. 输入String 的格式确定  “123456789101112.....”  数字叠加

实现getSubStr(int pos, int len)  

e.g.  getSubStr(10,2)---->“01”

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

>int takeSnapshot()

int getSnampshot(handler h, int index)

第4题好像不全是算法题   面试官说我对reference理解不够

求大米～

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。

第四题的关键词是 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/

wangyuesong2 发表于 2018-11-29 07:57
问下楼主第二题是什么意思？没有看懂，第四题的handler是给了一个class么？

第四题的handler应该是一个class吧  只给了class名字，内容不知

第二题getSubStr(int pos, int len) 可以看到input没有传入String，因为String格式固定，可以看作是长度无限的由数字拼接的字符串

new grad为什么会面ood

楼主在哪里面的啊？

什么时候面的，感觉都不是面经，除了第一题

laCampanella 发表于 2018/11/29 05:03:14
new grad为什么会面ood

new grad才会ood 要不然系统设计？

问下楼主第二题是什么意思？没有看懂，第四题的handler是给了一个class么？

求楼主讲讲第三题

请问第二题有比O(pos+len)更好的思路嘛

第三题莫不是lcs

补充内容 (2018-12-9 08:24):
nvm, i am wrong