G家onsite面经02/05

感觉排队那一题是不是可以用counting sort? 总共n个人，有m个人比他高，那他的位置不就是n-m吗？这样只应该O(n)就可以了吧

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

比他矮的人也有可能在他前面， 所以他的位置不一定是n-m哈我觉得

我觉得最后一题可以用tree吗，楼主拿到offer了吗

samantha_kr 发表于 2015-2-27 02:41
lz最后一题，如果是分段存最大值的话，如果start或者end落在分段的中间不是边界怎么办？

那就要依次比较start到自己那隔边界, end到自己那隔边界，和中间的分段最大值，跟他也讨论了这个的

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

前提是没有相同高度的人，还没有到那一步时间就没了。。所以估计是挂在这道题上面了

L纪翔L 发表于 2015-2-27 08:06
那就要依次比较start到自己那隔边界, end到自己那隔边界，和中间的分段最大值，跟他也讨论了这个的

谢谢楼主~~我觉得你答得很好呀。。感觉会有offer！

L纪翔L 发表于 2015-2-27 08:06
那就要依次比较start到自己那隔边界, end到自己那隔边界，和中间的分段最大值，跟他也讨论了这个的

再请问一下，德普那个题输入是怎么给的呢~谢谢！！

补充内容 (2015-2-27 09:34):
如果能大概讲一下思路就最好啦。。本来觉得不难，最后发现还是挺麻烦！

补充内容 (2015-2-27 09:34):
谢谢楼主...

L纪翔L 发表于 2015-2-27 08:09
前提是没有相同高度的人，还没有到那一步时间就没了。。所以估计是挂在这道题上面了

楼主没问题的，他们主要看解题思路和能力，不要求最优解？楼主是在Mountain View面的？

排队题，先按身高和比自己比自己高的人数升序排序（即首先考虑身高，身高相同的情况下考虑比自己高的人数），nlogn，然后从队尾开始一个个往前看“前面有几个比自己高”的数据（假设是n），把那个人（假设排在i）移到i+n和i+n+1中间去。只要把“移动和插入”这一步做到logn时间（链表+索引），就可以把整个题在nlongn完成。

最后一题，lz给出的解法在（start，end）的长度小于k的时候基本就是要重算……如果start和end在相邻的两段里也得重算吧。
我的方法是，用自平衡BST存储所有极大值的坐标。每次查询的时候遍历区间内的极大值，取最大的，和区间端点比较后返回。这个方法如果不优化的话最坏情况也基本上和重新算一样。但是可以在建立bst的时候，在各个节点存储子树所有极大值的最大值。这样几乎每次查询就是查bst的复杂度了。

排队那道题  是不可以这么做 每个 人的位置 初始化 都是0  那么那么他的位置就是 0 ＋ 多少个人在前面。 这如果 每个人身高不同 就可以 O（n） 时间排好序了  ， 还有一种情况 就是有人身高相等 那么 需要用一个 hashmap 来存   是否出现过 这身高的人 key 是身高， value 是  上一个这个身高的人出现的位置 那个只要 ＋1 就是当前的位置。 这样遍历一遍 范今数组里就好了！！