j*****s
发帖数: 189 | 1 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
。还让我take care of myself。
整理一下心情，把onsite的面筋发出来，攒一下人品吧。
我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
叔，不过我感觉他应该是对我印象最好的一个了。
第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
作以维护这个iterator的数据结构。当然，hash table本身的操作是O(1)的，所以要求
维护这个数据结构的时间也是O(1)。压根没想过……乱七八糟说了一堆，他大概满意了
之后，开始写代码，写了一半时间到了，他说就这样吧。
第二个是个看起来三十多岁的美国人，比较严肃，从头到尾都没有露出过笑容。他问我
知道chrome么，我说知道。他说chrome地址栏有个功能，就是输入一个词的时候，会跳
出以输入的字符为前缀的suggestion，这些suggestion是从历史记录和书签来的。问我
对这个实现的数据结构有什么看法。我说了一下需要记录每个书签的content以及最近
访问的次数，然后根据访问次数排序。他又问那假如有连个书签，一个是在一个月之前
访问了500次，而另一个是在昨天访问了100次，哪个应该在前面呢？我说我觉得那应该
记录每次访问的时间，然后给分配一个权重，然后每天将已有的记录的权重降低。他差
不多满意了，有问我那这个根据输入内容给出suggestion的实现应该怎么做呢？我说应
该用个后缀树类似的数据结构。他让我描述一下，我就画图描述了一下，他问我能不能
优化一下，我说可以把节点压缩一下。他又问那压缩之后再插入新节点怎么办呢？我说
必要的时候split一下。他貌似还比较满意，就让我写代码实现一下……我日，彻底没
写过后缀树啊，只是知道而已，硬着头皮瞎写了。写的差不多了之后，他看到我每个节
点申请了一个固定大小的数组来维护子节点，说有些浪费空间，能不能优化一下，想了
半天说可以用BST。他貌似对这个答案比较满意。然后时间就差不多到了。
接下来就是lunch了。吃的东西还是很不错的。只是不知道为什么，google LA里面中国
人好少啊，烙印也没几个。然后逛了一圈就不说了。
lunch过后，第三个面试，就是那个俄罗斯大叔，刚一见面把我吓坏了，操着一口卷舌
音，不过几句交流之后慢慢适应了。我是C++的，大叔就问我现在是个什么等级，我说
应该是beginner，大叔咋舌，然后又问我那最熟悉的是哪种语言，我不好意思的说是C+
+，我说我知道怎么用，只是对C++ STL等底层的实现不是特别了解。大叔说好吧，那你
告诉我explicit是干嘛的，擦了，这个当初实习的时候见过，可是没用过啊，一时半会
儿还真想不起来，就说不知道。大叔又问我voltile是干嘛的，我说这个我知道，是告
诉编译器每次读取这个变量的时候要直接读原始数据，不读缓存里的。大叔说差不多是
这个意思。然后问我知道template么。就让我用template写了个斐波那契的实现。我当
时直接写了递归的那种，现在回想起来其实应该写iterative的比较好，当时紧张了。
大叔看了说还行，然后说下一个问题，就是有一个DoubleLinkedList，但是不知道头和
尾在哪里，然后有一个vector记录了其中的一些节点，让我找出所给输入中islands的
个数。我一看还是比较简单的，哗哗就开始写，基本也没什么bug，就写完了。大叔一
看说写的还行，应该没啥问题，只是有个小地方可以优化一下。我看了半天不知道说的
是哪里，大叔说函数的参数那里，我说对，可以改成引用，那样要快一些。大叔说还可
以优化，我就不知道了，最后大叔说应该加个const就更完美了。然后大叔说还剩点儿
时间，就给我介绍了一下google，说如何如何好，还说google里有好多人和我一样也适
用python的，我当时听了觉得有戏啊，心里乐滋滋的。可惜还是挂了。
大叔走了之后，来了另一个美国小伙，问了我一个DP问题，大概是这样的，有一个长为
L的木料需要割开，割的位置在一个数组里A[1...N]，从一个地方切开的cost是当前所
切木料的长度，按不同的顺序切割，得到的total cost是不一样的，问我怎么切cost最
小。这个题真冤，我一看就会，然后给他写了个递归式，写了base case，又画了个二
维数组给他简单解释了一下，就开始写代码了。结果可能是用脑过度，脑子在写第三层
循环的时候不好使了，看都没看自己写的递归式，直接瞎写了一个……后来他说貌似有
点儿问题，我一看还真是，又来回改了半天，最后改好之后还给了我一个test case，
让我一步一步的给他跑一遍……跑差不多了，时间到了，小伙儿说答案应该是对的。哎
，假如当时努把力，一次写对，估计就不用浪费时间跑test case了。说不定还可以再
写一道题。
完了之后是另一个美国大叔。问我假如有个系统，要记录访问的次数，然后有个
increase的操作，问我应该怎么实现，才能返回最近一分钟的访问次数和最近一个小时
的访问次数。这个题在版上见过，之前也想过，所以还是比较淡定的说出了想法。他觉
得还不错，又问我要是increase的操作不是很频繁怎么办，我想了想说可以用个queue
，每次将最近的访问push进去，然后将front端超过一分钟的pop出来。他也很满意。然
后说，那咱们来说个iterator的故事吧，然后就开始说next()和hasNext()，我赶紧制
止，说第一个面试官已经问过了。他显得略慌，拿出了自己的题库开始看，貌似没有什
么比较合适的问题。就说，那你把刚才说的那个solution实现一下吧……好吧，我就无
奈的开始写。写的还比较顺利。没有什么bug。写完了，时间也差不多到了。他就walk
me out了，然后让前台给了我个mark杯留念。
哎，感觉自己好水啊……希望这碗面筋对各位大大们有用。 |
h*******e
发帖数: 1377 | |
b***e
发帖数: 383 | |
l*****a
发帖数: 14598 | 4 thanks for sharing
nice
【在 j*****s 的大作中提到】
: 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
: ，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
: 。还让我take care of myself。
: 整理一下心情，把onsite的面筋发出来，攒一下人品吧。
: 我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
: 叔，不过我感觉他应该是对我印象最好的一个了。
: 第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
: project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
: address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
: iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
|
h****n
发帖数: 1093 | 5 感觉楼主答的还可以吧。看来进google不光得有实力还得有运气
nice
【在 j*****s 的大作中提到】
: 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
: ，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
: 。还让我take care of myself。
: 整理一下心情，把onsite的面筋发出来，攒一下人品吧。
: 我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
: 叔，不过我感觉他应该是对我印象最好的一个了。
: 第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
: project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
: address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
: iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
|
d*s
发帖数: 699 | |
j*****s
发帖数: 189 | 7 可能吧，不过这是我们算法课里DP那章的一个作业。
【在 h*******e 的大作中提到】
: 切數組問題好像是haffman tree.
|
j*****s
发帖数: 189 | 8 DP那个不该写错，iterator那个也有点儿乱。哎，总之再接再厉吧。
【在 d*s 的大作中提到】
: 看起来面的不错，为什么就挂了呢？
|
p*****2
发帖数: 21240 | |
j*****s
发帖数: 189 | 10 哦？是这样么？除了MV都算local？
【在 p*****2 的大作中提到】
: local office比mv都更难吧。
|
|
|
c********t
发帖数: 5706 | 11 pat pat, 感觉面得不错，可能local招的人少，hiring bar更高。
第一题如何解？我觉得删除是不是就类似删除linkedlist里面一个节点，很容易。但插
入怎么办？难道不要搜索找插入的位置吗？
假如有一个iterator，可以对chain的hash table进行iterate，它有两个函数,next(),
hasNext().问我如何修改hash table的插入和删除操作以维护这个iterator的数据结
构。当然，hash table本身的操作是O(1)的，所以要求
维护这个数据结构的时间也是O(1)。
第二题前缀搜寻，为什么不用trie, 而用后缀树呢？你最后给的结构是节点是BST的
suffix tree,然后叶子节点有权重值？
他说chrome地址栏有个功能，就是输入一个词的时候，会跳出以输入的字符为前缀的
suggestion，这些suggestion是从历史记录和书签来的。问我对这个实现的数据结构有
什么看法。我说了一下需要记录每个书签的content以及最近
访问的次数，然后根据访问次数排序。他又问那假如有连个书签，一个是在一个月之前
访问了500次，而另一个是在昨天访问了100次，哪个应该在前面呢？我说我觉得那应该
记录每次访问的时间，然后给分配一个权重，然后每天将已有的记录的权重降低。他差
不多满意了，有问我那这个根据输入内容给出suggestion的实现应该怎么做呢？我说应
该用个后缀树类似的数据结构。他让我描述一下，我就画图描述了一下，他问我能不能
优化一下，我说可以把节点压缩一下。他又问那压缩之后再插入新节点怎么办呢？我说
必要的时候split一下。他貌似还比较满意，就让我写代码实现一下……我日，彻底没
写过后缀树啊，只是知道而已，硬着头皮瞎写了。写的差不多了之后，他看到我每个节
点申请了一个固定大小的数组来维护子节点，说有些浪费空间，能不能优化一下，想了
半天说可以用BST。他貌似对这个答案比较满意。然后时间就差不多到了
nice
【在 j*****s 的大作中提到】
: 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
: ，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
: 。还让我take care of myself。
: 整理一下心情，把onsite的面筋发出来，攒一下人品吧。
: 我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
: 叔，不过我感觉他应该是对我印象最好的一个了。
: 第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
: project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
: address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
: iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
|
l*****a
发帖数: 14598 | 12 hashtable是unsorted的
不知道他怎么定义这个顺序的
nice
【在 j*****s 的大作中提到】
: 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
: ，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
: 。还让我take care of myself。
: 整理一下心情，把onsite的面筋发出来，攒一下人品吧。
: 我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
: 叔，不过我感觉他应该是对我印象最好的一个了。
: 第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
: project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
: address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
: iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
|
j*****s
发帖数: 189 | 13 嗯，第一题其实需要主要维护两个东西，因为是chain式的，要维护slot不为空的index
的数组A，还要有一个当前slot里面所遍历到的Node的指针。另外还需要一个辅助数组B
来记录每个slot在数组A中的位置。插入的时候直接在A后面添一个就行，然后在B中进
行记录。删除的时候，从B中找到相应slot在A中的位置，假设是i，然后把A中i和最后
一个换一下就行，然后在B里也修改一下。
第二题其实就是trie，只是我当时没想起来，给了个后缀树，然后把多余的没用的节点
删了。节点结构我用的string，BST是完了之后他问可以怎么优化一下，我又说的，他
没往深了问。
),
【在 c********t 的大作中提到】
: pat pat, 感觉面得不错，可能local招的人少，hiring bar更高。
: 第一题如何解？我觉得删除是不是就类似删除linkedlist里面一个节点，很容易。但插
: 入怎么办？难道不要搜索找插入的位置吗？
: 假如有一个iterator，可以对chain的hash table进行iterate，它有两个函数,next(),
: hasNext().问我如何修改hash table的插入和删除操作以维护这个iterator的数据结
: 构。当然，hash table本身的操作是O(1)的，所以要求
: 维护这个数据结构的时间也是O(1)。
: 第二题前缀搜寻，为什么不用trie, 而用后缀树呢？你最后给的结构是节点是BST的
: suffix tree,然后叶子节点有权重值？
: 他说chrome地址栏有个功能，就是输入一个词的时候，会跳出以输入的字符为前缀的
|
j*****s
发帖数: 189 | 14 嗯，我也是在这里绊了好久，其实hash table的遍历是不讲究顺序的，只要能把所有元
素遍历一遍就行了。
【在 l*****a 的大作中提到】
: hashtable是unsorted的
: 不知道他怎么定义这个顺序的
:
: nice
|
j*****s
发帖数: 189 | |
l*****a
发帖数: 14598 | 16 不是A数组中的每个item就是一个你所说的slot吗？
为什么需要B?
另外你数组怎么控制动态追加删除？
index
组B
【在 j*****s 的大作中提到】
: 嗯，第一题其实需要主要维护两个东西，因为是chain式的，要维护slot不为空的index
: 的数组A，还要有一个当前slot里面所遍历到的Node的指针。另外还需要一个辅助数组B
: 来记录每个slot在数组A中的位置。插入的时候直接在A后面添一个就行，然后在B中进
: 行记录。删除的时候，从B中找到相应slot在A中的位置，假设是i，然后把A中i和最后
: 一个换一下就行，然后在B里也修改一下。
: 第二题其实就是trie，只是我当时没想起来，给了个后缀树，然后把多余的没用的节点
: 删了。节点结构我用的string，BST是完了之后他问可以怎么优化一下，我又说的，他
: 没往深了问。
:
: ),
|
f*****e
发帖数: 2992 | 17 其实就是CLRS上的矩阵相乘的顺序问题。
【在 h*******e 的大作中提到】
: 切數組問題好像是haffman tree.
|
h*******e
发帖数: 1377 | 18
【在 f*****e 的大作中提到】
: 其实就是CLRS上的矩阵相乘的顺序问题。
|
j*****s
发帖数: 189 | 19 是啊，就是为了能再O(n)的时间内追加删除，才需要数组B啊。
比如A是{1,3,4,5,7}，hash table 长度为10.
那B就是{-1,0，-1,1,2,3，-1,4，-1，-1，-1}， 其中-1代表在A中没有，其他是代表
这个slot在A中的index。假如要在A中加入一个8的话，先在B中看B[8]是不是等于-1，
等于的话就在A最后加上8，然后标记B[8]为5.
然后如果要在A中删除5的话，把A中5和7换一下，然后A的size - 1.然后B[7] = B[5],
B[5] = -1.大概是这么个意思。
【在 l*****a 的大作中提到】
: 不是A数组中的每个item就是一个你所说的slot吗？
: 为什么需要B?
: 另外你数组怎么控制动态追加删除？
:
: index
: 组B
|
j*****s
发帖数: 189 | 20 是呀，那哈夫曼可以做么。
【在 f*****e 的大作中提到】
: 其实就是CLRS上的矩阵相乘的顺序问题。
|
|
|
j*****y
发帖数: 1071 | 21 hoffman 好像不行
这个切割是有顺序的。
【在 j*****s 的大作中提到】
: 是呀，那哈夫曼可以做么。
|
f*****e
发帖数: 2992 | 22 楼主在UCLA？答得很好了，也挂了？
【在 j*****s 的大作中提到】
: 是呀，那哈夫曼可以做么。
|
j*****s
发帖数: 189 | 23 嗯，好吧。
【在 j*****y 的大作中提到】
: hoffman 好像不行
: 这个切割是有顺序的。
|
h*******e
发帖数: 1377 | 24 哦如果dp做是那个思路哦，谢谢：）
【在 f*****e 的大作中提到】
: 其实就是CLRS上的矩阵相乘的顺序问题。
|
h*******e
发帖数: 1377 | 25 哦，确实。有道很像的题目，切木板是哈夫曼。。我想错了。。
【在 j*****y 的大作中提到】
: hoffman 好像不行
: 这个切割是有顺序的。
|
s****t
发帖数: 467 | 26 是啊，我也觉得lz答得很好啊
据说google是有个hiring committee，不见面试的人，只看feedback决定招不招？难道
是feedback写的太隐晦，committee没看明白应该招？pat lz。。
【在 f*****e 的大作中提到】
: 楼主在UCLA？答得很好了，也挂了？
|
l**b
发帖数: 457 | 27 iterator没有一定要求是sorted吧？只要能loop所有的elements就可以了。
还有，LZ能不能把切木头的题意讲清楚一点。L和N是什么关系？
【在 l*****a 的大作中提到】
: hashtable是unsorted的
: 不知道他怎么定义这个顺序的
:
: nice
|
h*******e
发帖数: 1377 | 28 又想了一下，
如果切的木板必须按照数组 顺序从左到右a[0] a[1] [2] a[3] a[4] a[5] 应该就是dp
啦 如果切的木板要求最后切剩下的木板 有a[0] a[1] a[2] a[3] a[4] a[5] 的值就
行了就是哈夫曼最小堆实现。
【在 h*******e 的大作中提到】
: 哦，确实。有道很像的题目，切木板是哈夫曼。。我想错了。。
|
j*****s
发帖数: 189 | 29 我在U Chicago，可能其他地方还有不足吧
【在 f*****e 的大作中提到】
: 楼主在UCLA？答得很好了，也挂了？
|
j*****y
发帖数: 1071 | 30 切木头和矩阵相乘还真的是一样的
M[i, j] = min_{i < k < j}(M[i, k] + M[k, j]) + (j - i)
【在 l**b 的大作中提到】
: iterator没有一定要求是sorted吧？只要能loop所有的elements就可以了。
: 还有，LZ能不能把切木头的题意讲清楚一点。L和N是什么关系？
|
|
|
j*****s
发帖数: 189 | 31 L是木板的长度，N是切的位置。
比如L为100.
A = {20,50},表示在离左端20，和50的地方需要切开。
【在 l**b 的大作中提到】
: iterator没有一定要求是sorted吧？只要能loop所有的elements就可以了。
: 还有，LZ能不能把切木头的题意讲清楚一点。L和N是什么关系？
|
h*******e
发帖数: 1377 | 32 那就是矩阵相乘了：）
【在 j*****s 的大作中提到】
: L是木板的长度，N是切的位置。
: 比如L为100.
: A = {20,50},表示在离左端20，和50的地方需要切开。
|
j*****s
发帖数: 189 | 33 嗯，我只是给楼上的兄弟解释清楚题意。
【在 h*******e 的大作中提到】
: 那就是矩阵相乘了：）
|
l**b
发帖数: 457 | 34 所以先切20，再切50的total cost就是20 + 30 （50 - 20）= 50
然后先切50再切20的total cost就是50 + 20 = 70
这样理解对吗？
【在 j*****s 的大作中提到】
: L是木板的长度，N是切的位置。
: 比如L为100.
: A = {20,50},表示在离左端20，和50的地方需要切开。
|
l*****a
发帖数: 14598 | 35 你这样的好处是什么呢？真的没看懂
我的理解就是一个数组，每个数组保存一个chain
List> [] array= new LinkedList>[size];
hashtableIterator中hold一个 array, index(for the array),Iterator
,V>> (for the list in each slot)
应该就可以了吧？
插入删除都是先找slot,然后对相应的list操作就可以了
hasNext(),next()的话都是先找current iterator.hasNext(), iterator.next()
如果没有的话，再去找下一个slot对应list的iterator
,
【在 j*****s 的大作中提到】
: 是啊，就是为了能再O(n)的时间内追加删除，才需要数组B啊。
: 比如A是{1,3,4,5,7}，hash table 长度为10.
: 那B就是{-1,0，-1,1,2,3，-1,4，-1，-1，-1}， 其中-1代表在A中没有，其他是代表
: 这个slot在A中的index。假如要在A中加入一个8的话，先在B中看B[8]是不是等于-1，
: 等于的话就在A最后加上8，然后标记B[8]为5.
: 然后如果要在A中删除5的话，把A中5和7换一下，然后A的size - 1.然后B[7] = B[5],
: B[5] = -1.大概是这么个意思。
|
p*****2
发帖数: 21240 | 36
问我如何修改hash table的插入和删除操
作以维护这个iterator的数据结构。
感觉主要是如果插入和删除跟你的纪录有冲突需要一些code来做处理。比如你本来next
是一个元素，结果你调用next之前它被删除了。
【在 l*****a 的大作中提到】
: 你这样的好处是什么呢？真的没看懂
: 我的理解就是一个数组，每个数组保存一个chain
: List> [] array= new LinkedList>[size];
: hashtableIterator中hold一个 array, index(for the array),Iterator: ,V>> (for the list in each slot)
: 应该就可以了吧？
: 插入删除都是先找slot,然后对相应的list操作就可以了
: hasNext(),next()的话都是先找current iterator.hasNext(), iterator.next()
: 如果没有的话，再去找下一个slot对应list的iterator
:
|
j*****s
发帖数: 189 | 37 我不懂你的，我是用c++的，可能java可以你这么做吧。
【在 l*****a 的大作中提到】
: 你这样的好处是什么呢？真的没看懂
: 我的理解就是一个数组，每个数组保存一个chain
: List> [] array= new LinkedList>[size];
: hashtableIterator中hold一个 array, index(for the array),Iterator: ,V>> (for the list in each slot)
: 应该就可以了吧？
: 插入删除都是先找slot,然后对相应的list操作就可以了
: hasNext(),next()的话都是先找current iterator.hasNext(), iterator.next()
: 如果没有的话，再去找下一个slot对应list的iterator
:
|
p*****2
发帖数: 21240 | 38 就是有一个DoubleLinkedList，但是不知道头和
尾在哪里，然后有一个vector记录了其中的一些节点，让我找出所给输入中islands的
个数。
这题什么意思？能不能给个例子？貌似不是什么难题吗？ |
j*****s
发帖数: 189 | 39 哦，我懂了，他其实就是让实现java里的iterator，你直接就用了。
【在 l*****a 的大作中提到】
: 你这样的好处是什么呢？真的没看懂
: 我的理解就是一个数组，每个数组保存一个chain
: List> [] array= new LinkedList>[size];
: hashtableIterator中hold一个 array, index(for the array),Iterator: ,V>> (for the list in each slot)
: 应该就可以了吧？
: 插入删除都是先找slot,然后对相应的list操作就可以了
: hasNext(),next()的话都是先找current iterator.hasNext(), iterator.next()
: 如果没有的话，再去找下一个slot对应list的iterator
:
|
p*****2
发帖数: 21240 | 40
也不是。他是通过java iterator来实现总的iterator。但是添加，删除的时候可能会
有问题。
【在 j*****s 的大作中提到】
: 哦，我懂了，他其实就是让实现java里的iterator，你直接就用了。
:
:
|
|
|
p*****2
发帖数: 21240 | 41
就是这个意思。
【在 j*****y 的大作中提到】
: 切木头和矩阵相乘还真的是一样的
: M[i, j] = min_{i < k < j}(M[i, k] + M[k, j]) + (j - i)
|
j*****s
发帖数: 189 | 42 好吧……对java不熟……
【在 p*****2 的大作中提到】
:
: 就是这个意思。
|
l*****a
发帖数: 14598 | 43 这个是个问题，
但是现有的iterator能避免这个问题？
【在 p*****2 的大作中提到】
:
: 就是这个意思。
|
g**e
发帖数: 6127 | 44 实现fail fast iterator, 抛出ConcurrentModificationException? 那就直接把
HashMap的
代码看看
Entry
next
【在 p*****2 的大作中提到】
:
: 就是这个意思。
|
j******2
发帖数: 362 | |
j*****s
发帖数: 189 | 46 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
。还让我take care of myself。
整理一下心情，把onsite的面筋发出来，攒一下人品吧。
我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
叔，不过我感觉他应该是对我印象最好的一个了。
第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
作以维护这个iterator的数据结构。当然，hash table本身的操作是O(1)的，所以要求
维护这个数据结构的时间也是O(1)。压根没想过……乱七八糟说了一堆，他大概满意了
之后，开始写代码，写了一半时间到了，他说就这样吧。
第二个是个看起来三十多岁的美国人，比较严肃，从头到尾都没有露出过笑容。他问我
知道chrome么，我说知道。他说chrome地址栏有个功能，就是输入一个词的时候，会跳
出以输入的字符为前缀的suggestion，这些suggestion是从历史记录和书签来的。问我
对这个实现的数据结构有什么看法。我说了一下需要记录每个书签的content以及最近
访问的次数，然后根据访问次数排序。他又问那假如有连个书签，一个是在一个月之前
访问了500次，而另一个是在昨天访问了100次，哪个应该在前面呢？我说我觉得那应该
记录每次访问的时间，然后给分配一个权重，然后每天将已有的记录的权重降低。他差
不多满意了，有问我那这个根据输入内容给出suggestion的实现应该怎么做呢？我说应
该用个后缀树类似的数据结构。他让我描述一下，我就画图描述了一下，他问我能不能
优化一下，我说可以把节点压缩一下。他又问那压缩之后再插入新节点怎么办呢？我说
必要的时候split一下。他貌似还比较满意，就让我写代码实现一下……我日，彻底没
写过后缀树啊，只是知道而已，硬着头皮瞎写了。写的差不多了之后，他看到我每个节
点申请了一个固定大小的数组来维护子节点，说有些浪费空间，能不能优化一下，想了
半天说可以用BST。他貌似对这个答案比较满意。然后时间就差不多到了。
接下来就是lunch了。吃的东西还是很不错的。只是不知道为什么，google LA里面中国
人好少啊，烙印也没几个。然后逛了一圈就不说了。
lunch过后，第三个面试，就是那个俄罗斯大叔，刚一见面把我吓坏了，操着一口卷舌
音，不过几句交流之后慢慢适应了。我是C++的，大叔就问我现在是个什么等级，我说
应该是beginner，大叔咋舌，然后又问我那最熟悉的是哪种语言，我不好意思的说是C+
+，我说我知道怎么用，只是对C++ STL等底层的实现不是特别了解。大叔说好吧，那你
告诉我explicit是干嘛的，擦了，这个当初实习的时候见过，可是没用过啊，一时半会
儿还真想不起来，就说不知道。大叔又问我voltile是干嘛的，我说这个我知道，是告
诉编译器每次读取这个变量的时候要直接读原始数据，不读缓存里的。大叔说差不多是
这个意思。然后问我知道template么。就让我用template写了个斐波那契的实现。我当
时直接写了递归的那种，现在回想起来其实应该写iterative的比较好，当时紧张了。
大叔看了说还行，然后说下一个问题，就是有一个DoubleLinkedList，但是不知道头和
尾在哪里，然后有一个vector记录了其中的一些节点，让我找出所给输入中islands的
个数。我一看还是比较简单的，哗哗就开始写，基本也没什么bug，就写完了。大叔一
看说写的还行，应该没啥问题，只是有个小地方可以优化一下。我看了半天不知道说的
是哪里，大叔说函数的参数那里，我说对，可以改成引用，那样要快一些。大叔说还可
以优化，我就不知道了，最后大叔说应该加个const就更完美了。然后大叔说还剩点儿
时间，就给我介绍了一下google，说如何如何好，还说google里有好多人和我一样也适
用python的，我当时听了觉得有戏啊，心里乐滋滋的。可惜还是挂了。
大叔走了之后，来了另一个美国小伙，问了我一个DP问题，大概是这样的，有一个长为
L的木料需要割开，割的位置在一个数组里A[1...N]，从一个地方切开的cost是当前所
切木料的长度，按不同的顺序切割，得到的total cost是不一样的，问我怎么切cost最
小。这个题真冤，我一看就会，然后给他写了个递归式，写了base case，又画了个二
维数组给他简单解释了一下，就开始写代码了。结果可能是用脑过度，脑子在写第三层
循环的时候不好使了，看都没看自己写的递归式，直接瞎写了一个……后来他说貌似有
点儿问题，我一看还真是，又来回改了半天，最后改好之后还给了我一个test case，
让我一步一步的给他跑一遍……跑差不多了，时间到了，小伙儿说答案应该是对的。哎
，假如当时努把力，一次写对，估计就不用浪费时间跑test case了。说不定还可以再
写一道题。
完了之后是另一个美国大叔。问我假如有个系统，要记录访问的次数，然后有个
increase的操作，问我应该怎么实现，才能返回最近一分钟的访问次数和最近一个小时
的访问次数。这个题在版上见过，之前也想过，所以还是比较淡定的说出了想法。他觉
得还不错，又问我要是increase的操作不是很频繁怎么办，我想了想说可以用个queue
，每次将最近的访问push进去，然后将front端超过一分钟的pop出来。他也很满意。然
后说，那咱们来说个iterator的故事吧，然后就开始说next()和hasNext()，我赶紧制
止，说第一个面试官已经问过了。他显得略慌，拿出了自己的题库开始看，貌似没有什
么比较合适的问题。就说，那你把刚才说的那个solution实现一下吧……好吧，我就无
奈的开始写。写的还比较顺利。没有什么bug。写完了，时间也差不多到了。他就walk
me out了，然后让前台给了我个mark杯留念。
哎，感觉自己好水啊……希望这碗面筋对各位大大们有用。 |
h*******e
发帖数: 1377 | |
b***e
发帖数: 383 | |
l*****a
发帖数: 14598 | 49 thanks for sharing
nice
【在 j*****s 的大作中提到】
: 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
: ，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
: 。还让我take care of myself。
: 整理一下心情，把onsite的面筋发出来，攒一下人品吧。
: 我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
: 叔，不过我感觉他应该是对我印象最好的一个了。
: 第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
: project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
: address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
: iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
|
h****n
发帖数: 1093 | 50 感觉楼主答的还可以吧。看来进google不光得有实力还得有运气
nice
【在 j*****s 的大作中提到】
: 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
: ，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
: 。还让我take care of myself。
: 整理一下心情，把onsite的面筋发出来，攒一下人品吧。
: 我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
: 叔，不过我感觉他应该是对我印象最好的一个了。
: 第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
: project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
: address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
: iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
|
|
|
d*s
发帖数: 699 | |
j*****s
发帖数: 189 | 52 可能吧，不过这是我们算法课里DP那章的一个作业。
【在 h*******e 的大作中提到】
: 切數組問題好像是haffman tree.
|
j*****s
发帖数: 189 | 53 DP那个不该写错，iterator那个也有点儿乱。哎，总之再接再厉吧。
【在 d*s 的大作中提到】
: 看起来面的不错，为什么就挂了呢？
|
p*****2
发帖数: 21240 | |
j*****s
发帖数: 189 | 55 哦？是这样么？除了MV都算local？
【在 p*****2 的大作中提到】
: local office比mv都更难吧。
|
c********t
发帖数: 5706 | 56 pat pat, 感觉面得不错，可能local招的人少，hiring bar更高。
第一题如何解？我觉得删除是不是就类似删除linkedlist里面一个节点，很容易。但插
入怎么办？难道不要搜索找插入的位置吗？
假如有一个iterator，可以对chain的hash table进行iterate，它有两个函数,next(),
hasNext().问我如何修改hash table的插入和删除操作以维护这个iterator的数据结
构。当然，hash table本身的操作是O(1)的，所以要求
维护这个数据结构的时间也是O(1)。
第二题前缀搜寻，为什么不用trie, 而用后缀树呢？你最后给的结构是节点是BST的
suffix tree,然后叶子节点有权重值？
他说chrome地址栏有个功能，就是输入一个词的时候，会跳出以输入的字符为前缀的
suggestion，这些suggestion是从历史记录和书签来的。问我对这个实现的数据结构有
什么看法。我说了一下需要记录每个书签的content以及最近
访问的次数，然后根据访问次数排序。他又问那假如有连个书签，一个是在一个月之前
访问了500次，而另一个是在昨天访问了100次，哪个应该在前面呢？我说我觉得那应该
记录每次访问的时间，然后给分配一个权重，然后每天将已有的记录的权重降低。他差
不多满意了，有问我那这个根据输入内容给出suggestion的实现应该怎么做呢？我说应
该用个后缀树类似的数据结构。他让我描述一下，我就画图描述了一下，他问我能不能
优化一下，我说可以把节点压缩一下。他又问那压缩之后再插入新节点怎么办呢？我说
必要的时候split一下。他貌似还比较满意，就让我写代码实现一下……我日，彻底没
写过后缀树啊，只是知道而已，硬着头皮瞎写了。写的差不多了之后，他看到我每个节
点申请了一个固定大小的数组来维护子节点，说有些浪费空间，能不能优化一下，想了
半天说可以用BST。他貌似对这个答案比较满意。然后时间就差不多到了
nice
【在 j*****s 的大作中提到】
: 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
: ，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
: 。还让我take care of myself。
: 整理一下心情，把onsite的面筋发出来，攒一下人品吧。
: 我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
: 叔，不过我感觉他应该是对我印象最好的一个了。
: 第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
: project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
: address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
: iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
|
l*****a
发帖数: 14598 | 57 hashtable是unsorted的
不知道他怎么定义这个顺序的
nice
【在 j*****s 的大作中提到】
: 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
: ，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
: 。还让我take care of myself。
: 整理一下心情，把onsite的面筋发出来，攒一下人品吧。
: 我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
: 叔，不过我感觉他应该是对我印象最好的一个了。
: 第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
: project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
: address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
: iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
|
j*****s
发帖数: 189 | 58 嗯，第一题其实需要主要维护两个东西，因为是chain式的，要维护slot不为空的index
的数组A，还要有一个当前slot里面所遍历到的Node的指针。另外还需要一个辅助数组B
来记录每个slot在数组A中的位置。插入的时候直接在A后面添一个就行，然后在B中进
行记录。删除的时候，从B中找到相应slot在A中的位置，假设是i，然后把A中i和最后
一个换一下就行，然后在B里也修改一下。
第二题其实就是trie，只是我当时没想起来，给了个后缀树，然后把多余的没用的节点
删了。节点结构我用的string，BST是完了之后他问可以怎么优化一下，我又说的，他
没往深了问。
),
【在 c********t 的大作中提到】
: pat pat, 感觉面得不错，可能local招的人少，hiring bar更高。
: 第一题如何解？我觉得删除是不是就类似删除linkedlist里面一个节点，很容易。但插
: 入怎么办？难道不要搜索找插入的位置吗？
: 假如有一个iterator，可以对chain的hash table进行iterate，它有两个函数,next(),
: hasNext().问我如何修改hash table的插入和删除操作以维护这个iterator的数据结
: 构。当然，hash table本身的操作是O(1)的，所以要求
: 维护这个数据结构的时间也是O(1)。
: 第二题前缀搜寻，为什么不用trie, 而用后缀树呢？你最后给的结构是节点是BST的
: suffix tree,然后叶子节点有权重值？
: 他说chrome地址栏有个功能，就是输入一个词的时候，会跳出以输入的字符为前缀的
|
j*****s
发帖数: 189 | 59 嗯，我也是在这里绊了好久，其实hash table的遍历是不讲究顺序的，只要能把所有元
素遍历一遍就行了。
【在 l*****a 的大作中提到】
: hashtable是unsorted的
: 不知道他怎么定义这个顺序的
:
: nice
|
j*****s
发帖数: 189 | |
|
|
l*****a
发帖数: 14598 | 61 不是A数组中的每个item就是一个你所说的slot吗？
为什么需要B?
另外你数组怎么控制动态追加删除？
index
组B
【在 j*****s 的大作中提到】
: 嗯，第一题其实需要主要维护两个东西，因为是chain式的，要维护slot不为空的index
: 的数组A，还要有一个当前slot里面所遍历到的Node的指针。另外还需要一个辅助数组B
: 来记录每个slot在数组A中的位置。插入的时候直接在A后面添一个就行，然后在B中进
: 行记录。删除的时候，从B中找到相应slot在A中的位置，假设是i，然后把A中i和最后
: 一个换一下就行，然后在B里也修改一下。
: 第二题其实就是trie，只是我当时没想起来，给了个后缀树，然后把多余的没用的节点
: 删了。节点结构我用的string，BST是完了之后他问可以怎么优化一下，我又说的，他
: 没往深了问。
:
: ),
|
f*****e
发帖数: 2992 | 62 其实就是CLRS上的矩阵相乘的顺序问题。
【在 h*******e 的大作中提到】
: 切數組問題好像是haffman tree.
|
h*******e
发帖数: 1377 | 63
【在 f*****e 的大作中提到】
: 其实就是CLRS上的矩阵相乘的顺序问题。
|
j*****s
发帖数: 189 | 64 是啊，就是为了能再O(n)的时间内追加删除，才需要数组B啊。
比如A是{1,3,4,5,7}，hash table 长度为10.
那B就是{-1,0，-1,1,2,3，-1,4，-1，-1，-1}， 其中-1代表在A中没有，其他是代表
这个slot在A中的index。假如要在A中加入一个8的话，先在B中看B[8]是不是等于-1，
等于的话就在A最后加上8，然后标记B[8]为5.
然后如果要在A中删除5的话，把A中5和7换一下，然后A的size - 1.然后B[7] = B[5],
B[5] = -1.大概是这么个意思。
【在 l*****a 的大作中提到】
: 不是A数组中的每个item就是一个你所说的slot吗？
: 为什么需要B?
: 另外你数组怎么控制动态追加删除？
:
: index
: 组B
|
j*****s
发帖数: 189 | 65 是呀，那哈夫曼可以做么。
【在 f*****e 的大作中提到】
: 其实就是CLRS上的矩阵相乘的顺序问题。
|
j*****y
发帖数: 1071 | 66 hoffman 好像不行
这个切割是有顺序的。
【在 j*****s 的大作中提到】
: 是呀，那哈夫曼可以做么。
|
f*****e
发帖数: 2992 | 67 楼主在UCLA？答得很好了，也挂了？
【在 j*****s 的大作中提到】
: 是呀，那哈夫曼可以做么。
|
j*****s
发帖数: 189 | 68 嗯，好吧。
【在 j*****y 的大作中提到】
: hoffman 好像不行
: 这个切割是有顺序的。
|
h*******e
发帖数: 1377 | 69 哦如果dp做是那个思路哦，谢谢：）
【在 f*****e 的大作中提到】
: 其实就是CLRS上的矩阵相乘的顺序问题。
|
h*******e
发帖数: 1377 | 70 哦，确实。有道很像的题目，切木板是哈夫曼。。我想错了。。
【在 j*****y 的大作中提到】
: hoffman 好像不行
: 这个切割是有顺序的。
|
|
|
s****t
发帖数: 467 | 71 是啊，我也觉得lz答得很好啊
据说google是有个hiring committee，不见面试的人，只看feedback决定招不招？难道
是feedback写的太隐晦，committee没看明白应该招？pat lz。。
【在 f*****e 的大作中提到】
: 楼主在UCLA？答得很好了，也挂了？
|
l**b
发帖数: 457 | 72 iterator没有一定要求是sorted吧？只要能loop所有的elements就可以了。
还有，LZ能不能把切木头的题意讲清楚一点。L和N是什么关系？
【在 l*****a 的大作中提到】
: hashtable是unsorted的
: 不知道他怎么定义这个顺序的
:
: nice
|
h*******e
发帖数: 1377 | 73 又想了一下，
如果切的木板必须按照数组 顺序从左到右a[0] a[1] [2] a[3] a[4] a[5] 应该就是dp
啦 如果切的木板要求最后切剩下的木板 有a[0] a[1] a[2] a[3] a[4] a[5] 的值就
行了就是哈夫曼最小堆实现。
【在 h*******e 的大作中提到】
: 哦，确实。有道很像的题目，切木板是哈夫曼。。我想错了。。
|
j*****s
发帖数: 189 | 74 我在U Chicago，可能其他地方还有不足吧
【在 f*****e 的大作中提到】
: 楼主在UCLA？答得很好了，也挂了？
|
j*****y
发帖数: 1071 | 75 切木头和矩阵相乘还真的是一样的
M[i, j] = min_{i < k < j}(M[i, k] + M[k, j]) + (j - i)
【在 l**b 的大作中提到】
: iterator没有一定要求是sorted吧？只要能loop所有的elements就可以了。
: 还有，LZ能不能把切木头的题意讲清楚一点。L和N是什么关系？
|
j*****s
发帖数: 189 | 76 L是木板的长度，N是切的位置。
比如L为100.
A = {20,50},表示在离左端20，和50的地方需要切开。
【在 l**b 的大作中提到】
: iterator没有一定要求是sorted吧？只要能loop所有的elements就可以了。
: 还有，LZ能不能把切木头的题意讲清楚一点。L和N是什么关系？
|
h*******e
发帖数: 1377 | 77 那就是矩阵相乘了：）
【在 j*****s 的大作中提到】
: L是木板的长度，N是切的位置。
: 比如L为100.
: A = {20,50},表示在离左端20，和50的地方需要切开。
|
j*****s
发帖数: 189 | 78 嗯，我只是给楼上的兄弟解释清楚题意。
【在 h*******e 的大作中提到】
: 那就是矩阵相乘了：）
|
l**b
发帖数: 457 | 79 所以先切20，再切50的total cost就是20 + 30 （50 - 20）= 50
然后先切50再切20的total cost就是50 + 20 = 70
这样理解对吗？
【在 j*****s 的大作中提到】
: L是木板的长度，N是切的位置。
: 比如L为100.
: A = {20,50},表示在离左端20，和50的地方需要切开。
|
l*****a
发帖数: 14598 | 80 你这样的好处是什么呢？真的没看懂
我的理解就是一个数组，每个数组保存一个chain
List> [] array= new LinkedList>[size];
hashtableIterator中hold一个 array, index(for the array),Iterator
,V>> (for the list in each slot)
应该就可以了吧？
插入删除都是先找slot,然后对相应的list操作就可以了
hasNext(),next()的话都是先找current iterator.hasNext(), iterator.next()
如果没有的话，再去找下一个slot对应list的iterator
,
【在 j*****s 的大作中提到】
: 是啊，就是为了能再O(n)的时间内追加删除，才需要数组B啊。
: 比如A是{1,3,4,5,7}，hash table 长度为10.
: 那B就是{-1,0，-1,1,2,3，-1,4，-1，-1，-1}， 其中-1代表在A中没有，其他是代表
: 这个slot在A中的index。假如要在A中加入一个8的话，先在B中看B[8]是不是等于-1，
: 等于的话就在A最后加上8，然后标记B[8]为5.
: 然后如果要在A中删除5的话，把A中5和7换一下，然后A的size - 1.然后B[7] = B[5],
: B[5] = -1.大概是这么个意思。
|
|
|
p*****2
发帖数: 21240 | 81
问我如何修改hash table的插入和删除操
作以维护这个iterator的数据结构。
感觉主要是如果插入和删除跟你的纪录有冲突需要一些code来做处理。比如你本来next
是一个元素，结果你调用next之前它被删除了。
【在 l*****a 的大作中提到】
: 你这样的好处是什么呢？真的没看懂
: 我的理解就是一个数组，每个数组保存一个chain
: List> [] array= new LinkedList>[size];
: hashtableIterator中hold一个 array, index(for the array),Iterator: ,V>> (for the list in each slot)
: 应该就可以了吧？
: 插入删除都是先找slot,然后对相应的list操作就可以了
: hasNext(),next()的话都是先找current iterator.hasNext(), iterator.next()
: 如果没有的话，再去找下一个slot对应list的iterator
:
|
j*****s
发帖数: 189 | 82 我不懂你的，我是用c++的，可能java可以你这么做吧。
【在 l*****a 的大作中提到】
: 你这样的好处是什么呢？真的没看懂
: 我的理解就是一个数组，每个数组保存一个chain
: List> [] array= new LinkedList>[size];
: hashtableIterator中hold一个 array, index(for the array),Iterator: ,V>> (for the list in each slot)
: 应该就可以了吧？
: 插入删除都是先找slot,然后对相应的list操作就可以了
: hasNext(),next()的话都是先找current iterator.hasNext(), iterator.next()
: 如果没有的话，再去找下一个slot对应list的iterator
:
|
p*****2
发帖数: 21240 | 83 就是有一个DoubleLinkedList，但是不知道头和
尾在哪里，然后有一个vector记录了其中的一些节点，让我找出所给输入中islands的
个数。
这题什么意思？能不能给个例子？貌似不是什么难题吗？ |
j*****s
发帖数: 189 | 84 哦，我懂了，他其实就是让实现java里的iterator，你直接就用了。
【在 l*****a 的大作中提到】
: 你这样的好处是什么呢？真的没看懂
: 我的理解就是一个数组，每个数组保存一个chain
: List> [] array= new LinkedList>[size];
: hashtableIterator中hold一个 array, index(for the array),Iterator: ,V>> (for the list in each slot)
: 应该就可以了吧？
: 插入删除都是先找slot,然后对相应的list操作就可以了
: hasNext(),next()的话都是先找current iterator.hasNext(), iterator.next()
: 如果没有的话，再去找下一个slot对应list的iterator
:
|
p*****2
发帖数: 21240 | 85
也不是。他是通过java iterator来实现总的iterator。但是添加，删除的时候可能会
有问题。
【在 j*****s 的大作中提到】
: 哦，我懂了，他其实就是让实现java里的iterator，你直接就用了。
:
:
|
p*****2
发帖数: 21240 | 86
就是这个意思。
【在 j*****y 的大作中提到】
: 切木头和矩阵相乘还真的是一样的
: M[i, j] = min_{i < k < j}(M[i, k] + M[k, j]) + (j - i)
|
j*****s
发帖数: 189 | 87 好吧……对java不熟……
【在 p*****2 的大作中提到】
:
: 就是这个意思。
|
l*****a
发帖数: 14598 | 88 这个是个问题，
但是现有的iterator能避免这个问题？
【在 p*****2 的大作中提到】
:
: 就是这个意思。
|
g**e
发帖数: 6127 | 89 实现fail fast iterator, 抛出ConcurrentModificationException? 那就直接把
HashMap的
代码看看
Entry
next
【在 p*****2 的大作中提到】
:
: 就是这个意思。
|
j******2
发帖数: 362 | |
|
|
P****d
发帖数: 137 | 91 请问这道题第四问怎么返回一小时或者一分钟的访问量？没找到本版原题，谢啦 |
l*n
发帖数: 529 | 92 第一题怎么感觉像是要你搞LinkedHashMap啊？
nice
【在 j*****s 的大作中提到】
: 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
: ，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
: 。还让我take care of myself。
: 整理一下心情，把onsite的面筋发出来，攒一下人品吧。
: 我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
: 叔，不过我感觉他应该是对我印象最好的一个了。
: 第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
: project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
: address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
: iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
|
v***n
发帖数: 562 | |
p*u
发帖数: 136 | |
s********u
发帖数: 1109 | 95 应该就是吧，感觉问这个好多。或者问设计个lru cache，其实就是问这个
【在 l*n 的大作中提到】
: 第一题怎么感觉像是要你搞LinkedHashMap啊？
:
: nice
|
h***i
发帖数: 1970 | 96 Chicago也有office的，可以再试试
我在U Chicago，可能其他地方还有不足吧
【在 j*****s 的大作中提到】
: 我在U Chicago，可能其他地方还有不足吧
|
P****d
发帖数: 137 | 97 请问这道题第四问怎么返回一小时或者一分钟的访问量？没找到本版原题，谢啦 |
l*n
发帖数: 529 | 98 第一题怎么感觉像是要你搞LinkedHashMap啊？
nice
【在 j*****s 的大作中提到】
: 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
: ，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
: 。还让我take care of myself。
: 整理一下心情，把onsite的面筋发出来，攒一下人品吧。
: 我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
: 叔，不过我感觉他应该是对我印象最好的一个了。
: 第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
: project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
: address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
: iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
|
v***n
发帖数: 562 | |
p*u
发帖数: 136 | |
|
|
s********u
发帖数: 1109 | 101 应该就是吧，感觉问这个好多。或者问设计个lru cache，其实就是问这个
【在 l*n 的大作中提到】
: 第一题怎么感觉像是要你搞LinkedHashMap啊？
:
: nice
|
h***i
发帖数: 1970 | 102 Chicago也有office的，可以再试试
我在U Chicago，可能其他地方还有不足吧
【在 j*****s 的大作中提到】
: 我在U Chicago，可能其他地方还有不足吧
|
s*****y
发帖数: 32 | |
H******7
发帖数: 1728 | 104 c++ template 看来还得准备以下
写一个typelist估计就可以了 |
c******t
发帖数: 391 | 105 “ 有个系统，要记录访问的次数，然后有个increase的操作，问我应该怎么实现，才
能返回最近一分钟的访问次数和最近一个小时的访问次数。”
这个题正确的思路应该是啥？ 我的想法是分别用一个keep rotate的数组，size是60，
然后每次timestamp round to minute再用mod运算放到一个数组的一个bucket里，
sliding window过了就清零。求访问次数就扫一遍这个数组
这个思路对吗？ |
n******n
发帖数: 12088 | 106 女生吧。
nice
【在 j*****s 的大作中提到】
: 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
: ，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
: 。还让我take care of myself。
: 整理一下心情，把onsite的面筋发出来，攒一下人品吧。
: 我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
: 叔，不过我感觉他应该是对我印象最好的一个了。
: 第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
: project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
: address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
: iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
|
c***r
发帖数: 280 | 107 想问下，俄罗斯大叔出的第二题，islands个数，是啥意思？
nice
【在 j*****s 的大作中提到】
: 这周一google LA onsite的，结果周三晚上就通知我说挂了。HR还安慰我说我人很nice
: ，大家都很喜欢和我交流，只是我可能还缺乏一些经验，让我再等一段时间再申请试试
: 。还让我take care of myself。
: 整理一下心情，把onsite的面筋发出来，攒一下人品吧。
: 我这次onsite其实算是很幸运的了，没有遇到三哥，全是白人，虽然有一个是俄罗斯大
: 叔，不过我感觉他应该是对我印象最好的一个了。
: 第一个是个美国小伙儿，先让我放送下，介绍一下自己，以及最近做的比较大的
: project。然后让我描述了一下如何实现hash table。我描述了chain实现的，和open
: address实现的，然后他说假如有一个iterator，可以对chain的hash table进行
: iterate，它有两个函数,next(), hasNext().问我如何修改hash table的插入和删除操
|
w****x
发帖数: 14 | 108 好象是DGIM算法吧
【在 c******t 的大作中提到】
: “ 有个系统，要记录访问的次数，然后有个increase的操作，问我应该怎么实现，才
: 能返回最近一分钟的访问次数和最近一个小时的访问次数。”
: 这个题正确的思路应该是啥？ 我的想法是分别用一个keep rotate的数组，size是60，
: 然后每次timestamp round to minute再用mod运算放到一个数组的一个bucket里，
: sliding window过了就清零。求访问次数就扫一遍这个数组
: 这个思路对吗？
|
m*****n
发帖数: 2152 | 109 切木料那道题的递归式是什么？我怎么想不清楚阿。
如果我做估计就DFS了。 |
