t****m
发帖数: 140 | 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 |
c******n
发帖数: 4965 | 2 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?
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，拍了照片
|
b**********5
发帖数: 7881 | 3 其他都是什么题啊？ 这题， 你是按照一个挨着一个看？ |
b**********5
发帖数: 7881 | 4 好像应该有个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?
:
|
n******n
发帖数: 12088 | 5 不就是第二和倒数第二之间每个元素扫一遍吗？
多一点优化：如果一个元素是局部最大，下一个只能是局部最小。
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******7
发帖数: 1758 | 6 这个题很莫名呀，O（n）很简单
lgn貌似不可能呀，任何一个都有可能是，怎么排除 |
t****m
发帖数: 140 | 7 印度小哥出的题哪能那么简单。。。
这题可以检查array的第一个元素和最后一个元素，判断array是不是单调递增，递减
如果是单调递增、递减，则这个区间内没有local max、min
然后就是类似binary search |
l*********8
发帖数: 4642 | 8 You're right
【在 b**********5 的大作中提到】
: 好像应该有个lgn的解法。。。
|
l*********8
发帖数: 4642 | 9 You're right
【在 b**********5 的大作中提到】
: 好像应该有个lgn的解法。。。
|
b******i
发帖数: 914 | 10 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******7
发帖数: 1758 | 11 高, 可惜这样都fail
【在 t****m 的大作中提到】
: 印度小哥出的题哪能那么简单。。。
: 这题可以检查array的第一个元素和最后一个元素，判断array是不是单调递增，递减
: 如果是单调递增、递减，则这个区间内没有local max、min
: 然后就是类似binary search
|
t****m
发帖数: 140 | 12 大牛请看我楼上的答案
就是有个小trick检查数组是不是单调递增递减
然后类似binary search的做法可以print出所有的local max、min
【在 b******i 的大作中提到】
: pat pat
: 求问这个新题，如果求出所有的，有logN的算法吗，你是怎么做的？
:
: local
|
y*****e
发帖数: 712 | 13 只看第一个和最后一个就能判断monotonically increasing/decreasing吗？好像不能
吧？
【在 t****m 的大作中提到】
: 印度小哥出的题哪能那么简单。。。
: 这题可以检查array的第一个元素和最后一个元素，判断array是不是单调递增，递减
: 如果是单调递增、递减，则这个区间内没有local max、min
: 然后就是类似binary search
|
t****m
发帖数: 140 | 14 是不是我题目没写清楚？
你再仔细看看
【在 y*****e 的大作中提到】
: 只看第一个和最后一个就能判断monotonically increasing/decreasing吗？好像不能
: 吧？
|
y*****e
发帖数: 712 | 15 哦忘了+1 -1这个条件了，但logN能求出所有的吗？
【在 t****m 的大作中提到】
: 是不是我题目没写清楚？
: 你再仔细看看
|
t****m
发帖数: 140 | 16 如果一个数组是：
[1， 2， 3， 4， 5]
你知道这个数组的长度是5
然后第一个数和第最后一个数的差是4
那么这个数组只能是单调递增的，对吗？
【在 y*****e 的大作中提到】
: 哦忘了+1 -1这个条件了，但logN能求出所有的吗？
|
t****m
发帖数: 140 | 17 Bestcase 数组单调 O（1）
worstcase 整个数组一全部都是local max、min，列入[1，2，1，2，1。。。]， O(n)
【在 y*****e 的大作中提到】
: 哦忘了+1 -1这个条件了，但logN能求出所有的吗？
|
P******r
发帖数: 1342 | 18 那道题应该用divide and conquer 做吧。
+1 -1那个条件告诉你，在区间[i, j]里，如果A[j] -A[i] = +- ( j - i ), 那么这个
区间里就不可能有local min or max. 条件告诉你这样的区间非常多，所以可以用类似
二分的算法 |
P******r
发帖数: 1342 | 19 考官说了考虑local min max极少的情况。就不要考虑这种worst case了
：Bestcase 数组单调 O（1）
：worstcase 整个数组一全部都是local max、min，列入[1，2，1，2，1。。。]， O(
n) |
y*****e
发帖数: 712 | 20 明白了，果真条件每一句都很有用啊
【在 P******r 的大作中提到】
: 那道题应该用divide and conquer 做吧。
: +1 -1那个条件告诉你，在区间[i, j]里，如果A[j] -A[i] = +- ( j - i ), 那么这个
: 区间里就不可能有local min or max. 条件告诉你这样的区间非常多，所以可以用类似
: 二分的算法
|
|
|
l******9
发帖数: 26 | 21 我的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******r
发帖数: 1342 | 22 差不多。。不过漏考虑数列整体递减的情况了。。
：我的two cents
： |
h*********n
发帖数: 11319 | 23 应该是正解了
【在 P******r 的大作中提到】
: 那道题应该用divide and conquer 做吧。
: +1 -1那个条件告诉你，在区间[i, j]里，如果A[j] -A[i] = +- ( j - i ), 那么这个
: 区间里就不可能有local min or max. 条件告诉你这样的区间非常多，所以可以用类似
: 二分的算法
|
n******n
发帖数: 12088 | 24 哈哈，同忘记
【在 y*****e 的大作中提到】
: 哦忘了+1 -1这个条件了，但logN能求出所有的吗？
|
e********2
发帖数: 495 | 25 clog(N)，c是local min/max个数。
【在 h*********n 的大作中提到】
: 应该是正解了
|
c******n
发帖数: 4965 | 26 谢了， 很有趣。 我当年第一次被拒是一个类似的题，
100000个士兵， 里面有几个有感染什么病毒。 然后可以把血样放一起化验， 问怎么
能最快找出来这几个士兵
【在 t****m 的大作中提到】
: 印度小哥出的题哪能那么简单。。。
: 这题可以检查array的第一个元素和最后一个元素，判断array是不是单调递增，递减
: 如果是单调递增、递减，则这个区间内没有local max、min
: 然后就是类似binary search
|
h****3
发帖数: 89 | 27 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*****e
发帖数: 712 | 28 还需要另外考虑递减的情况吗？层主用的math.abs()，应该递增减都包括了吧
【在 P******r 的大作中提到】
: 差不多。。不过漏考虑数列整体递减的情况了。。
:
: ：我的two cents
: ：
|
b**********5
发帖数: 7881 | 29 那个code，好像修改过。。 我的观察能力强吧， 仔细吧。。。 可惜， 这种能力，
面试都不考虑。。。
【在 y*****e 的大作中提到】
: 还需要另外考虑递减的情况吗？层主用的math.abs()，应该递增减都包括了吧
|
l*k
发帖数: 10 | 30 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*********5
发帖数: 576 | 31 如果输入是21212121212121212121212121212121212121
你这个还不如O(n)吧?
【在 e********2 的大作中提到】
: clog(N)，c是local min/max个数。
|
c*******e
发帖数: 621 | 32 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****3
发帖数: 89 | 33 在楼主原文中有这么一句话：
已知数组的长度远大于local Max/local min的数量
所以对这种情况还是二分法更优
【在 f*********5 的大作中提到】
: 如果输入是21212121212121212121212121212121212121
: 你这个还不如O(n)吧?
|
a*********0
发帖数: 2727 | |
b**********5
发帖数: 7881 | 35 有的面试官， 看你不顺眼， 就给你一道题， 你怎么办？
【在 a*********0 的大作中提到】
: 全是老题为什么一轮只能做一题呢？
|
t****m
发帖数: 140 | 36 面试官一开始义正言辞的对我说：
我们反对背题，你背题我们能看出来！
我就说，那我一边说一边给你详细的解释行吗？
就不敢写两道了
【在 a*********0 的大作中提到】
: 全是老题为什么一轮只能做一题呢？
|
b**********5
发帖数: 7881 | 37 能上个全一点的面经么？ design什么题啊？
【在 t****m 的大作中提到】
: 面试官一开始义正言辞的对我说：
: 我们反对背题，你背题我们能看出来！
: 我就说，那我一边说一边给你详细的解释行吗？
: 就不敢写两道了
|
s***m
发帖数: 336 | 38 wow, 简洁明快的解法。多谢！
【在 h****3 的大作中提到】
: 在楼主原文中有这么一句话：
: 已知数组的长度远大于local Max/local min的数量
: 所以对这种情况还是二分法更优
|
s********l
发帖数: 998 | 39 可以啊~
看差值是不是距离~
【在 y*****e 的大作中提到】
: 只看第一个和最后一个就能判断monotonically increasing/decreasing吗？好像不能
: 吧？
|
l*****a
发帖数: 180 | 40 楼主挂的原因是什么？ 说有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*******n
发帖数: 47 | 41 #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<<"found local max/min at "<
}
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;
} |
