G家onsite面经02/05

tanis 发表于 2015-2-26 16:07
有点问题，你新建的ArrayList空间不足会报IndexOutOfBoundsException。还有点求教楼主，如果是相同高度怎 ...

因为是按照身高由高到低排序，当一个Person p被插入的时候，所有比p高的人都已经在list中了，不会出现 outOfBound 错误

最后一题是经典的RMQ问题，简单一点的话可以在O(nlogn)的时间preprocess，然后每次query都是常数。
使用复杂的复合方法的话可以在O(n)的时间内preprocess完，然后每次query也是常数

samantha_kr 发表于 2015-2-27 09:16
再请问一下，德普那个题输入是怎么给的呢~谢谢！！

补充内容 (2015-2-27 09:34):

输入就是给力 n 张牌，但是n不等于52，我就是按花色sort一下，再按大小sort一下，然后走一遍，用HashMap存个数，走一遍的时候再看有没有连续的同花色的，如果找到最大的那个就立马停止了，但是code比较繁琐，应该不是最优解

tanis 发表于 2015-2-27 09:18
楼主没问题的，他们主要看解题思路和能力，不要求最优解？楼主是在Mountain View面的？

对呀，不过看面试官的表情，貌似这道题答得不好。。

L纪翔L 发表于 2015-2-28 03:01
输入就是给力 n 张牌，但是n不等于52，我就是按花色sort一下，再按大小sort一下，然后走一遍，用HashMap ...

LZ的想法跟我差不多。。先查花色，再查数字。。对的，code特别麻烦。。。没想到更好的方法

rlzth2013 发表于 2015-2-26 12:33
感觉排队那一题是不是可以用counting sort? 总共n个人，有m个人比他高，那他的位置不就是n-m吗？这样只应该 ...

是队伍里面前面比自己高的人数，不是总共有多少人比他高吧。

最后一道题能不能用矩阵，n*n的矩阵，计算所有start到end的最大值。时间复杂度O(n^2)
在Query的时候直接从矩阵里面取值

请问大神想明白people排队的问题了么

mattsun 发表于 2015-3-8 08:36
最后一道题能不能用矩阵，n*n的矩阵，计算所有start到end的最大值。时间复杂度O(n^2)
在Query的时候直接从 ...

我也这么想 利用dp建立矩阵