李冰冰2月捞金8000万登顶内地“吸金王 zt - 未名空间MITBBS历史存档

李冰冰2月捞金8000万登顶内地“吸金王 zt# Joke - 肚皮舞运动

t*m2014-07-13 07:07

1 楼

上周面的F家，今天收到邮件悲剧
题目说实话都不难，也都做出来了，但是每轮只写了一题，有一轮还写了个bug
culture fit那轮也老老实实按照知道的准备
只有一道新题：
有一个数组，这个数组里的数总是比前一个大一或者小一，如果一个数比它相邻的两边
的数都大，这个数叫local max，如果一个数比它相邻的两个数都小，这个数叫local
min（数组里的第一个和最后一个数都不能叫local max 和 local min）。
已知数组的长度远大于local Max/local min的数量，要求print出来这个数组里所有的
local max和local min（可以不按顺序）
我这题愣了下，然后当场写出答案，印度小哥看了看说looks good，拍了照片
顺便求个referral！leetcode、lintcode各两边，自学frontend、system design

Y*o2014-07-13 07:07

2 楼

想撸张卡出去玩，又受5/24限制。。。

g*12014-07-13 07:07

3 楼

李冰冰与某集团董事长共同完成代言合作签约仪式。

c*n2014-07-13 07:07

4 楼

for(int i=1;iif (data[i-1] < data[i] && data [i] > data[i+1]) {
// print local max
}
if (data[i-1]>data[i] && data[i] < data[i+1]) {
// print local min
}
}
looks too simple, or am I missing something?

local

【在 t****m 的大作中提到】

: 上周面的F家，今天收到邮件悲剧
: 题目说实话都不难，也都做出来了，但是每轮只写了一题，有一轮还写了个bug
: culture fit那轮也老老实实按照知道的准备
: 只有一道新题：
: 有一个数组，这个数组里的数总是比前一个大一或者小一，如果一个数比它相邻的两边
: 的数都大，这个数叫local max，如果一个数比它相邻的两个数都小，这个数叫local
: min（数组里的第一个和最后一个数都不能叫local max 和 local min）。
: 已知数组的长度远大于local Max/local min的数量，要求print出来这个数组里所有的
: local max和local min（可以不按顺序）
: 我这题愣了下，然后当场写出答案，印度小哥看了看说looks good，拍了照片

m*o2014-07-13 07:07

5 楼

店里的卡更容易申请吗？

【在 Y*******o 的大作中提到】

: 想撸张卡出去玩，又受5/24限制。。。

n*g2014-07-13 07:07

6 楼

厉害。是哪个集团啊

【在 g**1 的大作中提到】

: 李冰冰与某集团董事长共同完成代言合作签约仪式。

b*52014-07-13 07:07

7 楼

其他都是什么题啊？这题，你是按照一个挨着一个看？

Y*o2014-07-13 07:07

8 楼

是branch里面会有pre approval，有了这个就可以绕过5/24了

【在 m****o 的大作中提到】

: 店里的卡更容易申请吗？

g*r2014-07-13 07:07

9 楼

吸金

【在 g**1 的大作中提到】

: 李冰冰与某集团董事长共同完成代言合作签约仪式。

b*52014-07-13 07:07

10 楼

好像应该有个lgn的解法。。。

【在 c******n 的大作中提到】

: for(int i=1;i: if (data[i-1] < data[i] && data [i] > data[i+1]) {
: // print local max
: }
: if (data[i-1]>data[i] && data[i] < data[i+1]) {
: // print local min
: }
: }
: looks too simple, or am I missing something?
:

m*o2014-07-13 07:07

11 楼

Preapproval怎么查？

【在 Y*******o 的大作中提到】

: 是branch里面会有pre approval，有了这个就可以绕过5/24了

w*p2014-07-13 07:07

12 楼

签完了陪睡？

n*n2014-07-13 07:07

13 楼

不就是第二和倒数第二之间每个元素扫一遍吗？
多一点优化：如果一个元素是局部最大，下一个只能是局部最小。

local

【在 t****m 的大作中提到】

: 上周面的F家，今天收到邮件悲剧
: 题目说实话都不难，也都做出来了，但是每轮只写了一题，有一轮还写了个bug
: culture fit那轮也老老实实按照知道的准备
: 只有一道新题：
: 有一个数组，这个数组里的数总是比前一个大一或者小一，如果一个数比它相邻的两边
: 的数都大，这个数叫local max，如果一个数比它相邻的两个数都小，这个数叫local
: min（数组里的第一个和最后一个数都不能叫local max 和 local min）。
: 已知数组的长度远大于local Max/local min的数量，要求print出来这个数组里所有的
: local max和local min（可以不按顺序）
: 我这题愣了下，然后当场写出答案，印度小哥看了看说looks good，拍了照片

d*o2014-07-13 07:07

14 楼

都四十多了
再过几年就是吸土王了

【在 g**1 的大作中提到】

: 李冰冰与某集团董事长共同完成代言合作签约仪式。

s*72014-07-13 07:07

15 楼

这个题很莫名呀，O（n）很简单
lgn貌似不可能呀，任何一个都有可能是，怎么排除

l*p2014-07-13 07:07

16 楼

这几年分别是吸木王，吸水王，熄火王
最后神功大成，稀土王

【在 d****o 的大作中提到】

: 都四十多了
: 再过几年就是吸土王了

t*m2014-07-13 07:07

17 楼

印度小哥出的题哪能那么简单。。。
这题可以检查array的第一个元素和最后一个元素，判断array是不是单调递增，递减
如果是单调递增、递减，则这个区间内没有local max、min
然后就是类似binary search

l*82014-07-13 07:07

18 楼

You're right

【在 b**********5 的大作中提到】

: 好像应该有个lgn的解法。。。

l*82014-07-13 07:07

19 楼

You're right

【在 b**********5 的大作中提到】

: 好像应该有个lgn的解法。。。

b*i2014-07-13 07:07

20 楼

pat pat
求问这个新题，如果求出所有的，有logN的算法吗，你是怎么做的？

local

【在 t****m 的大作中提到】

: 上周面的F家，今天收到邮件悲剧
: 题目说实话都不难，也都做出来了，但是每轮只写了一题，有一轮还写了个bug
: culture fit那轮也老老实实按照知道的准备
: 只有一道新题：
: 有一个数组，这个数组里的数总是比前一个大一或者小一，如果一个数比它相邻的两边
: 的数都大，这个数叫local max，如果一个数比它相邻的两个数都小，这个数叫local
: min（数组里的第一个和最后一个数都不能叫local max 和 local min）。
: 已知数组的长度远大于local Max/local min的数量，要求print出来这个数组里所有的
: local max和local min（可以不按顺序）
: 我这题愣了下，然后当场写出答案，印度小哥看了看说looks good，拍了照片

s*72014-07-13 07:07

21 楼

高, 可惜这样都fail

【在 t****m 的大作中提到】

: 印度小哥出的题哪能那么简单。。。
: 这题可以检查array的第一个元素和最后一个元素，判断array是不是单调递增，递减
: 如果是单调递增、递减，则这个区间内没有local max、min
: 然后就是类似binary search

t*m2014-07-13 07:07

22 楼

大牛请看我楼上的答案
就是有个小trick检查数组是不是单调递增递减
然后类似binary search的做法可以print出所有的local max、min

【在 b******i 的大作中提到】

: pat pat
: 求问这个新题，如果求出所有的，有logN的算法吗，你是怎么做的？
:
: local

y*e2014-07-13 07:07

23 楼

只看第一个和最后一个就能判断monotonically increasing/decreasing吗？好像不能
吧？

【在 t****m 的大作中提到】

: 印度小哥出的题哪能那么简单。。。
: 这题可以检查array的第一个元素和最后一个元素，判断array是不是单调递增，递减
: 如果是单调递增、递减，则这个区间内没有local max、min
: 然后就是类似binary search

t*m2014-07-13 07:07

24 楼

是不是我题目没写清楚？
你再仔细看看

【在 y*****e 的大作中提到】

: 只看第一个和最后一个就能判断monotonically increasing/decreasing吗？好像不能
: 吧？

y*e2014-07-13 07:07

25 楼

哦忘了+1 -1这个条件了，但logN能求出所有的吗？

【在 t****m 的大作中提到】

: 是不是我题目没写清楚？
: 你再仔细看看

t*m2014-07-13 07:07

26 楼

如果一个数组是：
[1， 2， 3， 4， 5]
你知道这个数组的长度是5
然后第一个数和第最后一个数的差是4
那么这个数组只能是单调递增的，对吗？

【在 y*****e 的大作中提到】

: 哦忘了+1 -1这个条件了，但logN能求出所有的吗？

t*m2014-07-13 07:07

27 楼

Bestcase 数组单调 O（1）
worstcase 整个数组一全部都是local max、min，列入[1，2，1，2，1。。。]， O(n)

【在 y*****e 的大作中提到】

: 哦忘了+1 -1这个条件了，但logN能求出所有的吗？

P*r2014-07-13 07:07

28 楼

那道题应该用divide and conquer 做吧。
+1 -1那个条件告诉你，在区间[i, j]里，如果A[j] -A[i] = +- ( j - i ), 那么这个
区间里就不可能有local min or max. 条件告诉你这样的区间非常多，所以可以用类似
二分的算法

P*r2014-07-13 07:07

29 楼

考官说了考虑local min max极少的情况。就不要考虑这种worst case了

：Bestcase 数组单调 O（1）
：worstcase 整个数组一全部都是local max、min，列入[1，2，1，2，1。。。]， O(
n)

y*e2014-07-13 07:07

30 楼

明白了，果真条件每一句都很有用啊

【在 P******r 的大作中提到】

: 那道题应该用divide and conquer 做吧。
: +1 -1那个条件告诉你，在区间[i, j]里，如果A[j] -A[i] = +- ( j - i ), 那么这个
: 区间里就不可能有local min or max. 条件告诉你这样的区间非常多，所以可以用类似
: 二分的算法

l*92014-07-13 07:07

31 楼

我的two cents
public void print(int[] a) {
helper(a, 0, a.length - 1);
}

public void print(int[] a) {
helper(a, 0, a.length - 1);
}
public void helper(int[] a, int left, int right) {
if (right - left < 2) {
return;
}
int mid = left + (right - left) / 2;
if (a[mid] > a[mid-1] && a[mid] > a[mid+1]) {
System.out.println(a[mid]);
} else if (a[mid] < a[mid-1] && a[mid] < a[mid+1]) {
System.out.println(a[mid]);
}
if (Math.abs(a[mid] - a[left]) < mid - left) {
helper(a, left, mid);
}
if (Math.abs(a[right] - a[mid]) < right - mid) {
helper(a, mid, right);
}
}

P*r2014-07-13 07:07

32 楼

差不多。。不过漏考虑数列整体递减的情况了。。

：我的two cents
：

h*n2014-07-13 07:07

33 楼

应该是正解了

【在 P******r 的大作中提到】

: 那道题应该用divide and conquer 做吧。
: +1 -1那个条件告诉你，在区间[i, j]里，如果A[j] -A[i] = +- ( j - i ), 那么这个
: 区间里就不可能有local min or max. 条件告诉你这样的区间非常多，所以可以用类似
: 二分的算法

n*n2014-07-13 07:07

34 楼

哈哈，同忘记

【在 y*****e 的大作中提到】

: 哦忘了+1 -1这个条件了，但logN能求出所有的吗？

e*22014-07-13 07:07

35 楼

clog(N)，c是local min/max个数。

【在 h*********n 的大作中提到】

: 应该是正解了

c*n2014-07-13 07:07

36 楼

谢了，很有趣。我当年第一次被拒是一个类似的题，
100000个士兵，里面有几个有感染什么病毒。然后可以把血样放一起化验，问怎么
能最快找出来这几个士兵

【在 t****m 的大作中提到】

: 印度小哥出的题哪能那么简单。。。
: 这题可以检查array的第一个元素和最后一个元素，判断array是不是单调递增，递减
: 如果是单调递增、递减，则这个区间内没有local max、min
: 然后就是类似binary search

h*32014-07-13 07:07

37 楼

public static void printLocalHelper(int[] arr, int left, int right){
/* return condition */
if(right-left<2) return;
int mid = left+(right-left)/2;
if(right-left == Math.abs(arr[right]-arr[left])){
return;
}
if((arr[mid](arr[mid]>arr[mid-1] && arr[mid]>arr[mid+1]) ){
System.out.print(arr[mid]+" ");
}
printLocalHelper(arr,left,mid);
printLocalHelper(arr,mid,right);
}
感谢分享

y*e2014-07-13 07:07

38 楼

还需要另外考虑递减的情况吗？层主用的math.abs()，应该递增减都包括了吧

【在 P******r 的大作中提到】

: 差不多。。不过漏考虑数列整体递减的情况了。。
:
: ：我的two cents
: ：

b*52014-07-13 07:07

39 楼

那个code，好像修改过。。我的观察能力强吧，仔细吧。。。可惜，这种能力，
面试都不考虑。。。

【在 y*****e 的大作中提到】

: 还需要另外考虑递减的情况吗？层主用的math.abs()，应该递增减都包括了吧

l*k2014-07-13 07:07

40 楼

My solution in Python:
def findLocal(A, i, j):
if abs(A[i]-A[j]) == j-i:
return
else:
if j-i == 2:
print(A[i+1])
return
m = (i+j)/2
if A[m]>A[m-1] and A[m]>A[m+1]:
print(A[m])
if A[m]print(A[m])
findLocal(A, i, m)
findLocal(A, m, j)

f*52014-07-13 07:07

41 楼

如果输入是21212121212121212121212121212121212121
你这个还不如O(n)吧?

【在 e********2 的大作中提到】

: clog(N)，c是local min/max个数。

c*e2014-07-13 07:07

42 楼

patpat
简单题要两道才行的

local

【在 t****m 的大作中提到】

: 上周面的F家，今天收到邮件悲剧
: 题目说实话都不难，也都做出来了，但是每轮只写了一题，有一轮还写了个bug
: culture fit那轮也老老实实按照知道的准备
: 只有一道新题：
: 有一个数组，这个数组里的数总是比前一个大一或者小一，如果一个数比它相邻的两边
: 的数都大，这个数叫local max，如果一个数比它相邻的两个数都小，这个数叫local
: min（数组里的第一个和最后一个数都不能叫local max 和 local min）。
: 已知数组的长度远大于local Max/local min的数量，要求print出来这个数组里所有的
: local max和local min（可以不按顺序）
: 我这题愣了下，然后当场写出答案，印度小哥看了看说looks good，拍了照片

h*32014-07-13 07:07

43 楼

在楼主原文中有这么一句话：
已知数组的长度远大于local Max/local min的数量
所以对这种情况还是二分法更优

【在 f*********5 的大作中提到】

: 如果输入是21212121212121212121212121212121212121
: 你这个还不如O(n)吧?

a*02014-07-13 07:07

44 楼

全是老题为什么一轮只能做一题呢？

b*52014-07-13 07:07

45 楼

有的面试官，看你不顺眼，就给你一道题，你怎么办？

【在 a*********0 的大作中提到】

: 全是老题为什么一轮只能做一题呢？

t*m2014-07-13 07:07

46 楼

面试官一开始义正言辞的对我说：
我们反对背题，你背题我们能看出来！
我就说，那我一边说一边给你详细的解释行吗？
就不敢写两道了

【在 a*********0 的大作中提到】

: 全是老题为什么一轮只能做一题呢？

b*52014-07-13 07:07

47 楼

能上个全一点的面经么？ design什么题啊？

【在 t****m 的大作中提到】

: 面试官一开始义正言辞的对我说：
: 我们反对背题，你背题我们能看出来！
: 我就说，那我一边说一边给你详细的解释行吗？
: 就不敢写两道了

s*m2014-07-13 07:07

48 楼

wow, 简洁明快的解法。多谢！

【在 h****3 的大作中提到】

: 在楼主原文中有这么一句话：
: 已知数组的长度远大于local Max/local min的数量
: 所以对这种情况还是二分法更优

s*l2014-07-13 07:07

49 楼

可以啊~
看差值是不是距离~

【在 y*****e 的大作中提到】

: 只看第一个和最后一个就能判断monotonically increasing/decreasing吗？好像不能
: 吧？

l*a2014-07-13 07:07

50 楼

楼主挂的原因是什么？说有bug我不信，有的人写code有bug也进了。说只每轮做了一
道我也不太信，我听说也有人每轮只做了一道进了。

local

【在 t****m 的大作中提到】

: 上周面的F家，今天收到邮件悲剧
: 题目说实话都不难，也都做出来了，但是每轮只写了一题，有一轮还写了个bug
: culture fit那轮也老老实实按照知道的准备
: 只有一道新题：
: 有一个数组，这个数组里的数总是比前一个大一或者小一，如果一个数比它相邻的两边
: 的数都大，这个数叫local max，如果一个数比它相邻的两个数都小，这个数叫local
: min（数组里的第一个和最后一个数都不能叫local max 和 local min）。
: 已知数组的长度远大于local Max/local min的数量，要求print出来这个数组里所有的
: local max和local min（可以不按顺序）
: 我这题愣了下，然后当场写出答案，印度小哥看了看说looks good，拍了照片

m*n2014-07-13 07:07

51 楼

#include
#include
#include
using namespace std;
void solve(vector list, int l, int r) {
if(l>r) return;
int m = (l+r)/2;
if (list[m-1]==list[m+1]&&(list[m]==list[m-1]+1||list[m]==list[m-1]-1)) {
cout<}
if(abs(list[l]-list[r])>=r-l) return;
solve(list, m+1,r);
solve(list, l,m-1);
}
void solve(vector list) {
if(list.size()<3)return;
solve(list, 1, list.size()-2);
}
int main() {
solve(vector({1,2,3,2,3,4,5,6,7}));
return 0;
}