Google onsite七月面经

八月份Google的onsite，一直没有机会写，现在基本尘埃落定了，有时间写一些面经，希望对大家有帮助。

一共五轮面试，四轮coding加一轮PhD。

coding 1：编码解码。比如A是1，B是2。。。Z是26，第一问是一串字母（e.g.,ABACCC

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

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

计数据结构，写代码，我感觉是挂在这一面了

Ph.D：就是随便聊聊Ph.D的工作

各位大神多给些金币啊，接下来还会有Facebook，Amazon，Uber，Cisco等面经，敬请期待

keluotete 发表于 2016-9-29 05:07
关键是设计数据结构，减少内存操作，比如一个string str是abcdefgh，然后调用del(str, 1, 2)，返回adffgh ...

首先在Java里，String是immutable的。如果你要manipulate一个String，一旦产生了一点变化，你都需要生成一个新的instance。所以in-place是不可能的。
而且Java里，literal的String建立，生成的instance是存在于jvm heap里的一个constant string pool里的，而用constructor创立的instance是存在于heap里的。前者始终返回同一个instance，后者每次建立一个新的instance。可以借鉴前者。
可以想到的一个方法是：
1. manipulate的时候用StringBuffer和StringBuilder。或者自己写数据结构用char[]。
2. 自己管理一个constant String pool，每次有新的String instance需要生成的时候检查是不是存在于这个pool里了。可以想到建立一个trie tree字典，然后用char[]去匹配。如果存在直接返回那个instance。
这个方法可以保证一个字符串永远只有一个或者零个instance存在于内存里。

LynKang 发表于 2016-10-3 06:41
你难道要返回StringBuffer吗？这不能解决任何问题。
如果题目要求尽量不要生成额外的instance，占用内存 ...

在Java的API层面上思考问题是不够的，我们需要看到这个API背后的东西。毕竟Java也不是一个完美的语言，后来有很多设计都是为了弥补过去的不足，但是为了backward compatibility，有很多坏东西被保存了下来。官方的API文档还有很多有误的地方。这就是为什么有Apache的commons的库和Google Guava。但是Java整体的走向是好的，马上Java9要出了，又是很多惊喜。

LynKang 发表于 2016-10-3 01:48
首先在Java里，String是immutable的。如果你要manipulate一个String，一旦产生了一点变化，你都需要生成 ...

用TRIE每次加入TRING，比如OFFSET是20，那还要跑到ROOT的第二十层CHILD那去，速度很慢啊，我觉得是不是就用STRING BUFFER就好了，如果OFFSET超过STRING BUFFER现长度，就用空格补齐，删除的话就把OFFSET那一部分设置成空格。。。

怎么改进performance  LZ怎么答的

hanabeast 发表于 2016-9-28 07:03
怎么改进performance  LZ怎么答的

用hashtable存已经访问的路径吧

楼主好人，请问有follow up的问题吗？

4 感觉两个操作已经都是O(1)的了，还有什么其它限制么？

楼主再接再厉！！

这几道题感觉难度都不是特别变态那种， hr 是什么 feedback？

求问第二问的时间复杂度要求是啥? 都要O(lgn)么?

真的考的都特别难…他们都随笔想题，偶尔重复也是因为…懒得想别的了。

xiaoling99 发表于 2016-9-28 07:56
楼主好人，请问有follow up的问题吗？

follow up一般就是怎么改进time和space，rtadeoff之类的

tigercode 发表于 2016-9-28 08:02
4 感觉两个操作已经都是O(1)的了，还有什么其它限制么？

关键是设计数据结构，减少内存操作，比如一个string str是abcdefgh，然后调用del(str, 1, 2)，返回adffgh，怎么不重新申请内存空间做到这点