Google onsite七月面经

lookbackinanger 发表于 2016-9-28 08:34
求问第二问的时间复杂度要求是啥? 都要O(lgn)么?

不用segment tree，考官说考查重点是程序要对

hyj143 发表于 2016-9-28 08:30
楼主再接再厉！！

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

hr说欢迎六个月后再投

第四题lz怎么做的呢? 感觉很tricky啊

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

如果是用Java，String都是Immutable类型，返回的string必然占用新的内存空间啊...

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 01:48
首先在Java里，String是immutable的。如果你要manipulate一个String，一旦产生了一点变化，你都需要生成 ...

StringBuilder的toSting调用的就是new String()所以应该是不行。按照你的思路，貌似只能用"" + char1 + char2之类的...

说实话，不知道这个题的考点是什么。

virpro 发表于 2016-10-3 02:09
StringBuilder的toSting调用的就是new String()所以应该是不行。按照你的思路，貌似只能用"" + char1 + c ...

不不不，你误会了。你不能用toString，也不能用char[]来生成String。
这个题目的考点是你自己实现一个instance的management system
Trie tree在这里是用来搜索，储存和删除String instance的。


补充内容 (2016-10-3 02:32):
这里不管你用StringBuffer还是char[]，这只是临时的一个可以重用的内存空间。除非是第一次生成这个String instance，否则你永远都不用生成任何instance。如果该instance被删除了，把它从trie tree里“删除”

补充内容 (2016-10-3 02:34):
“”+ char1 + char2 + ... 更是不可取。会生成一堆短命的instance。造成young gc, full gc。完蛋。。。

LynKang 发表于 2016-10-3 02:30
不不不，你误会了。你不能用toString，也不能用char[]来生成String。
这个题目的考点是你自己实现一个in ...

所以ultimately，你的目标是避免造成full gc。这题java基本概念考的很多。建议去读一读effective java和java performance这两本书。

第一问是不是其实就是LC 的EXCEL的字母列和数字列转换的问题？

第三题也是LEETCODE原题吧，就是BFS加DP？