Google 店面

面试官感觉是个美国人，上来让我自己介绍了一个project，大概5分钟，然后直接开始做题
1. 给一个

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

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

" smilieid="104" border="0" alt="" />

我觉得可以把数字和index当做一个pair ,然后对pair按照数字的大小进行排序，（O(nlogn)）
然后对pairs从头开始扫描（O(n)），不断更新最小的index，然后对每对pair的index 减去最小的index，记录下最大的差值，应该就可以了

followup是不是可以类似最长上升子序列那样做?

一个线性表作栈,每当当前元素 a 比栈顶小时压入. 比栈顶大时对栈二分查找到小于 a 的最大值 b,比较二者位置ai - bi和已知最大差.

owenqyzhang 发表于 2017-11-2 07:09
第一题我也是用hash map做的，我先以为不能有负的，写完以后他问我有没有edge case，我想了半天说也许没 ...

原来这样，那你加两行就对了。nlog(n)是sort nums的index让后scan array解。
比如 【0,1,0,2,1】 index = {0,1,2,3,4} (需要o(n) memory)
sort index according to nums, 就有 {0,2,1,4,3} 代表 【0,0,1,1,2】
max j - i = 4

像这样？？ j - i 尽量大，如果不能为负数的 所以要 j > i

1. int maxDiff(vector<int>& nums) {
   
2.     unordered_map<int, int> m;
   
3.     int maxdiff = -1;
   
4.     for (int i = 0; i < nums.size(); i++) {
   
5.         if (m.count(nums[i]) == 0) m[nums[i]] = i;
   
6.         if (m.count(nums[i] - 1)) maxdiff = max(maxdiff, i - m[nums[i] - 1]);
   
7.     }
   
8.     return maxdiff;
   
9. }

复制代码

A[j] > A[i]的时候只能for (int i = 0; i < nums.size(); i++ ) while (nums[i] < nums[i + 1]) i++这样找了??

美国人就爱自己出题，然后让你分析，不一定像国人面馆那样bug free.楼主等等消息吧。。。。

edyyy 发表于 2017-11-2 07:03
像这样？？ j - i 尽量大，如果不能为负数的 所以要 j > i

A[j] > A的时候只能for (int i = 0; i < nums ...

第一题我也是用hash map做的，我先以为不能有负的，写完以后他问我有没有edge case，我想了半天说也许没有这种对，或者j-i是负的，然后他就让我加上了这两种情况。第二个他说有个nlogn的解法，先preprocess一下，我也没想出来

楼主能写个例子吗

rickliang 发表于 2017-11-2 07:10
楼主能写个例子吗

比如A=[5, 2, 4, 5, 3, 1], 就返回(1, 4)

edyyy 发表于 2017-11-2 07:16
原来这样，那你加两行就对了。nlog(n)是sort nums的index让后scan array解。
比如 【0,1,0,2,1】 index  ...

能具体说说如何scan解吗?

shuidiaogetou 发表于 2017-11-2 23:05
能具体说说如何scan解吗?

sort完以后就在index list里面找最大的差，而且保证大数在后面，参考 http://www.geeksforgeeks.org/max ... tween-two-elements/