谷歌 Intern OA

刚做完谷歌19 Summer Intern OA，题目和地理说的一样还没有变。数组加storeandhouse

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

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

顺便求一波大米，积分太低了什么都干不了。

980329498 发表于 2018-9-29 22:54
抱歉我刚才想错了，第一次我用的是最小堆所以错了，最大堆应该没问题。你的方法确实应该是时间最好的解法 ...

大家说的对。我之前给的解法确实是错的。抱歉，没有仔细思考就发了出来。这题不能用 heap。正确的解法应该是这样：开一个 list，这个 list 还是保存每个子数组最后一个元素。然后保持这个 list 是强递增的。刚开始 list 只有 nums[0] 一个元素。然后来新值 nums[i] 时，先看它是不是>= list 中最后一个（即最大值），如果是，说明必须开一个新子数组，这样把它 append 到 list 上边；如果不是，那就二叉搜索 list 中最小的大于 nums[i] 的那个值，然后用 nums[i] 更新该值，也就是更新该子数组的队尾。最后返回值是 list 中元素个数。
这样做法时间复杂度还是 O(n logn)，空间复杂度 O(n)。

Unous 发表于 2018-9-30 00:57
7,9,6,5,1,8 这个也不行啊。 8进来的时候堆中仅有5和1 这样的话由于8>5需要新开
然而8可以跟在9后边

大家说的对。我之前给的解法确实是错的。抱歉，没有仔细思考就发了出来。这题不能用 heap。正确的解法应该是这样：开一个 list，这个 list 还是保存每个子数组最后一个元素。然后保持这个 list 是强递增的。刚开始 list 只有 nums[0] 一个元素。然后来新值 nums[i] 时，先看它是不是>= list 中最后一个（即最大值），如果是，说明必须开一个新子数组，这样把它 append 到 list 上边；如果不是，那就二叉搜索 list 中最小的大于 nums[i] 的那个值，然后用 nums[i] 更新该值，也就是更新该子数组的队尾。最后返回值是 list 中元素个数。
这样做法时间复杂度还是 O(n logn)，空间复杂度 O(n)。

Wuwei8372 发表于 2018-9-30 00:26
这个test case貌似不能过啊：7,8,4,9,1,6,5,7

大家说的对。我之前给的解法确实是错的。抱歉，没有仔细思考就发了出来。这题不能用 heap。正确的解法应该是这样：开一个 list，这个 list 还是保存每个子数组最后一个元素。然后保持这个 list 是强递增的。刚开始 list 只有 nums[0] 一个元素。然后来新值 nums[i] 时，先看它是不是>= list 中最后一个（即最大值），如果是，说明必须开一个新子数组，这样把它 append 到 list 上边；如果不是，那就二叉搜索 list 中最小的大于 nums[i] 的那个值，然后用 nums[i] 更新该值，也就是更新该子数组的队尾。最后返回值是 list 中元素个数。
这样做法时间复杂度还是 O(n logn)，空间复杂度 O(n)。

谢谢楼主，很详细的题解~~~~ 只是第一题的例子是不是有问题哈：[5,2,1], [4,3], [6] 还是[5,2], [4,3,1], [6]

yiminglu22 发表于 2018-9-29 11:17
谢谢楼主，很详细的题解~~~~ 只是第一题的例子是不是有问题哈：[5,2,1], [4,3], [6] 还是[5,2], [4,3,1], [ ...

看解法吧，如果直接遍历每个子数组的最后数值的话那就是只要比1大就插入到该数组后面，就应该是[5,2,1], [4,3], [6]

请问交了之后大概多久能看到summary啊？

wzy602867832 发表于 2018-9-29 13:29
请问交了之后大概多久能看到summary啊？

你指的什么summary？做完之后立刻可以看到提交的情况，写了多少行，用的什么语言，其他信息我还没看到

980329498 发表于 2018-9-29 13:35
你指的什么summary？做完之后立刻可以看到提交的情况，写了多少行，用的什么语言，其他信息我还没看到

我是想看看对不对什么的，虽然我觉得应该没问题，不过没看到还是不放心

赞楼主！祝接下来好运！

第一题比较好的解法应该是用一个 max heap 保留所有字数组的最后一个数字。刚开始 heap 里只有 nums[0]，之后每来一个新数时，跟堆顶的最大值比较，如果严格小于最大值，则 pop 掉堆顶，把新值 push 入堆。如果新值大于或等于堆顶，则表示不能把打它 append 到之前的任何一个子数组，必须新开一个子数组来存它。此时只需要把新值 push 入堆，而不用 pop 堆顶。最后返回值是堆中元素个数，也就是开了几个子数组（有几个尾巴就是开了几个子数组）。
这样可以实现O(n logn) time，比楼主的 O(n^2) 解法要好些。

wofaint 发表于 2018-9-29 15:54
第一题比较好的解法应该是用一个 max heap 保留所有字数组的最后一个数字。刚开始 heap 里只有 nums[0]，之 ...

不错的解法

wofaint 发表于 2018-9-29 15:54
第一题比较好的解法应该是用一个 max heap 保留所有字数组的最后一个数字。刚开始 heap 里只有 nums[0]，之 ...

我第一遍做的时候也是想用堆排序，但是你考虑下这种情况：输入为【5，1，4，3】，如果用堆排序的话先push5，然后5被更新成1，然后push4，再来一个3，这时候3不会跟4比较而是因为大于1就直接被push进堆导致最后堆中有1，4，3三个数是错误的