b*******h
发帖数: 53 | 1 g面了两轮：1. 给一个bst，给一个值，找到这个bst中与这个值最接近的数； 在月球
上放了一排host，怎么构架这些host，让他们不用人为操作。
2. 经典题：给一个数组，找出一个local minima的值。（local minima 即这个数比左
右两边的数小，假设没有重复。）
明天面试另一家公司的onsite，求bless啊！！ |
B*******1
发帖数: 2454 | 2 onsite就2轮？
【在 b*******h 的大作中提到】
: g面了两轮：1. 给一个bst，给一个值，找到这个bst中与这个值最接近的数； 在月球
: 上放了一排host，怎么构架这些host，让他们不用人为操作。
: 2. 经典题：给一个数组，找出一个local minima的值。（local minima 即这个数比左
: 右两边的数小，假设没有重复。）
: 明天面试另一家公司的onsite，求bless啊！！
|
j*****y
发帖数: 1071 | 3 bless.
月球上 host这个题目啥意思阿？
local minima用 线性时间 吧？
【在 b*******h 的大作中提到】
: g面了两轮：1. 给一个bst，给一个值，找到这个bst中与这个值最接近的数； 在月球
: 上放了一排host，怎么构架这些host，让他们不用人为操作。
: 2. 经典题：给一个数组，找出一个local minima的值。（local minima 即这个数比左
: 右两边的数小，假设没有重复。）
: 明天面试另一家公司的onsite，求bless啊！！
|
l****i
发帖数: 396 | |
b*******h
发帖数: 53 | 5 相当于电面，因为我在的地方有google office，他们让我过去面试。
【在 B*******1 的大作中提到】
: onsite就2轮？
|
b*******h
发帖数: 53 | 6 local minima 是logn的时间
月球上的host我的理解是考怎么架构，设计。我说了这些点：用一个master host管理
所有的hosts，master host 也是普通的host，如果它down了，其它host 通过ping，
ping不到这个service时，可以选择另一个host做master host。 如何选择另一个host
，就用token， 谁拿到了token谁是host。 还有就是数据重复，防止一个host down了
数据的丢失。
【在 j*****y 的大作中提到】
: bless.
: 月球上 host这个题目啥意思阿？
: local minima用 线性时间 吧？
|
b*******h
发帖数: 53 | 7 我是平时看到了这道题，就扫了一眼，没理解逻辑就放过了，教训啊。 硬生生的在面
试的时候被面试官教会的。是个数学题，画图会比较好理解。明天面试回来我来update
我的理解，或者坐等高人。
先求bless～ |
a***o
发帖数: 1182 | 8 bless~
update
【在 b*******h 的大作中提到】
: 我是平时看到了这道题，就扫了一眼，没理解逻辑就放过了，教训啊。 硬生生的在面
: 试的时候被面试官教会的。是个数学题，画图会比较好理解。明天面试回来我来update
: 我的理解，或者坐等高人。
: 先求bless～
|
B********t
发帖数: 147 | 9 local min那题好像对原数组有要求吧？a[0] >= a[1] && a[n-2] <= a[n-1]. 然后二
分就行了
没这限制 logn做不到。。 |
s********l
发帖数: 998 | 10 只有数组 2个end有限制
怎么就可以log(n)了？
【在 B********t 的大作中提到】
: local min那题好像对原数组有要求吧？a[0] >= a[1] && a[n-2] <= a[n-1]. 然后二
: 分就行了
: 没这限制 logn做不到。。
|
|
|
P******r
发帖数: 842 | 11 http://www.careercup.com/question?id=8223978
第一个答案好像不完整。还有一个情况没考虑，就是a[mid]比两边大。
思路是这样的吧
There are three kinds of arrays that have no local min: monotonically
increasing, monotonically decreasing, and monotonically increasing then
monotonically decreasing. Any array that satisfied the given condition (a[0]
>= a[1] && a[n-2] <= a[n-1]) must have at least one local min. We just need
to divide our problem into smaller ones that satisfy this condition. For
log(n) solution, it’s natural to look at the mid element and divide from
there.
1. suppose function signature is f(a, p, q)
2. let mid = (p+q)/2
3. if (a[mid-1] >= a[mid] && a[mid+1] >= a[mid]), return mid
4. otherwise if (a[mid-1] >= a[mid] && mid-1-p >= 2) return f(a,p,mid-1)
5. otherwise return f(a, mid+1, q)
6. need to consider when array has only two elements
大家帮我看看对不对？自己test了几个cases
int findLocalMin(int a[], int p, int q) {
if (q-p < 2) return -1;
int mid = (p+q)/2;
if (a[mid-1] >= a[mid] && a[mid+1] >= a[mid])
return mid;
if (a[mid-1] <= a[mid] && mid-p >= 2) // 9 9 8 10
return findLocalMin(a,p,mid);
return findLocalMin(a,mid,q);
} |
l**b
发帖数: 457 | 12 斗胆问一下，local min这道题，如果平时没见过，面试给45分钟，有多少大牛能保证
一定想得出来？ |
l*******b
发帖数: 2586 | 13 端点可以是local min，然后写code 。 或者面试官想让你先问他端点可不可以是local
min.
前两天板上讨论过
【在 b*******h 的大作中提到】
: g面了两轮：1. 给一个bst，给一个值，找到这个bst中与这个值最接近的数； 在月球
: 上放了一排host，怎么构架这些host，让他们不用人为操作。
: 2. 经典题：给一个数组，找出一个local minima的值。（local minima 即这个数比左
: 右两边的数小，假设没有重复。）
: 明天面试另一家公司的onsite，求bless啊！！
|
l***i
发帖数: 1309 | 14 local min的题,如果告诉你是divide and conquer, O(log n) time可能还能想想,要不
然就是老师上课讲过了.比如我是听说过的,人说是MIT algorithm课上讲的.不太明白这
种题考什么,coding太容易,是不是说要不你就是MIT的,要不你就得想出一个MIT
professor交给他学生的一个algorithm |
P******r
发帖数: 842 | 15 这个linear解法简单，所以下一步应该是log，除非像那个同时找min和max的能从2n个
比较降到1.5n comparison。如果这么分析下来，就是devide and conquer了。即使这
样，答案也不好想。
【在 l***i 的大作中提到】
: local min的题,如果告诉你是divide and conquer, O(log n) time可能还能想想,要不
: 然就是老师上课讲过了.比如我是听说过的,人说是MIT algorithm课上讲的.不太明白这
: 种题考什么,coding太容易,是不是说要不你就是MIT的,要不你就得想出一个MIT
: professor交给他学生的一个algorithm
|
c********t
发帖数: 5706 | 16 多谢讲解。基本思路应该就是这样。
但这道题我觉得本身限定很多。
第一,就是要given condition (a[0] >= a[1] && a[n-2] <= a[n-1]) 或者允许两头作
为local min
第二，就是不应该有duplicate (至少duplicate不相邻，否则遇到 a[mid-1] == a[mid
]==a[mid+1] 就不知道往哪里搜了。你的程序这种情况往前搜应该不对。
5,4,2,2,2,2,1,3
5,1,2,2,2,2,3,4
0]
need
【在 P******r 的大作中提到】
: http://www.careercup.com/question?id=8223978
: 第一个答案好像不完整。还有一个情况没考虑，就是a[mid]比两边大。
: 思路是这样的吧
: There are three kinds of arrays that have no local min: monotonically
: increasing, monotonically decreasing, and monotonically increasing then
: monotonically decreasing. Any array that satisfied the given condition (a[0]
: >= a[1] && a[n-2] <= a[n-1]) must have at least one local min. We just need
: to divide our problem into smaller ones that satisfy this condition. For
: log(n) solution, it’s natural to look at the mid element and divide from
: there.
|
B********t
发帖数: 147 | 17 如果有这个限制 你可以想像成从a[0]开始一直是单调递减的，如果发现a[mid-1] < a
[mid] 说明一定有一个凹点在0-mid之间。所以二分了。
【在 s********l 的大作中提到】
: 只有数组 2个end有限制
: 怎么就可以log(n)了？
|
B********t
发帖数: 147 | 18 这个只要允许凹点允许等于左右就行了
mid
【在 c********t 的大作中提到】
: 多谢讲解。基本思路应该就是这样。
: 但这道题我觉得本身限定很多。
: 第一,就是要given condition (a[0] >= a[1] && a[n-2] <= a[n-1]) 或者允许两头作
: 为local min
: 第二，就是不应该有duplicate (至少duplicate不相邻，否则遇到 a[mid-1] == a[mid
: ]==a[mid+1] 就不知道往哪里搜了。你的程序这种情况往前搜应该不对。
: 5,4,2,2,2,2,1,3
: 5,1,2,2,2,2,3,4
:
: 0]
|
B********t
发帖数: 147 | 19 比两边大没关系啊，因为比两边大可以往两边走
0]
need
【在 P******r 的大作中提到】
: http://www.careercup.com/question?id=8223978
: 第一个答案好像不完整。还有一个情况没考虑，就是a[mid]比两边大。
: 思路是这样的吧
: There are three kinds of arrays that have no local min: monotonically
: increasing, monotonically decreasing, and monotonically increasing then
: monotonically decreasing. Any array that satisfied the given condition (a[0]
: >= a[1] && a[n-2] <= a[n-1]) must have at least one local min. We just need
: to divide our problem into smaller ones that satisfy this condition. For
: log(n) solution, it’s natural to look at the mid element and divide from
: there.
|
P******r
发帖数: 842 | 20
mid
是的，条件限制比较多。careercup上是有duplicate的，我写程序时时把local min定
义为小于等于而不是小于的。不然程序要改成strictly less or greater than.
【在 c********t 的大作中提到】
: 多谢讲解。基本思路应该就是这样。
: 但这道题我觉得本身限定很多。
: 第一,就是要given condition (a[0] >= a[1] && a[n-2] <= a[n-1]) 或者允许两头作
: 为local min
: 第二，就是不应该有duplicate (至少duplicate不相邻，否则遇到 a[mid-1] == a[mid
: ]==a[mid+1] 就不知道往哪里搜了。你的程序这种情况往前搜应该不对。
: 5,4,2,2,2,2,1,3
: 5,1,2,2,2,2,3,4
:
: 0]
|
|
|
P******r
发帖数: 842 | 21 是的，是走那边都行。我说的是careercup link那的第一个答案没有包括这个case的处
理。
【在 B********t 的大作中提到】
: 比两边大没关系啊，因为比两边大可以往两边走
:
: 0]
: need
|
c********t
发帖数: 5706 | 22 明白了，多谢！
【在 P******r 的大作中提到】
: 是的，是走那边都行。我说的是careercup link那的第一个答案没有包括这个case的处
: 理。
|
l**b
发帖数: 457 | 23 那不就是明显意思让老中都去做民工？NND，题海战术，谁怕谁啊？ |
s********k
发帖数: 6180 | 24 这题我电面第二道题遇到过，当时想到了二分法做，不过时间不多有点紧张没搞定挂了
。我觉得这个given condition (a[0] >= a[1] && a[n-2] <= a[n-1])也不一定需要。
可以自己问这个local的定义
mid
【在 c********t 的大作中提到】
: 多谢讲解。基本思路应该就是这样。
: 但这道题我觉得本身限定很多。
: 第一,就是要given condition (a[0] >= a[1] && a[n-2] <= a[n-1]) 或者允许两头作
: 为local min
: 第二，就是不应该有duplicate (至少duplicate不相邻，否则遇到 a[mid-1] == a[mid
: ]==a[mid+1] 就不知道往哪里搜了。你的程序这种情况往前搜应该不对。
: 5,4,2,2,2,2,1,3
: 5,1,2,2,2,2,3,4
:
: 0]
|
m******s
发帖数: 1469 | 25 Bless
【在 b*******h 的大作中提到】
: g面了两轮：1. 给一个bst，给一个值，找到这个bst中与这个值最接近的数； 在月球
: 上放了一排host，怎么构架这些host，让他们不用人为操作。
: 2. 经典题：给一个数组，找出一个local minima的值。（local minima 即这个数比左
: 右两边的数小，假设没有重复。）
: 明天面试另一家公司的onsite，求bless啊！！
|
l**b
发帖数: 457 | |
l*********u
发帖数: 19053 | 27 bless
【在 b*******h 的大作中提到】
: g面了两轮：1. 给一个bst，给一个值，找到这个bst中与这个值最接近的数； 在月球
: 上放了一排host，怎么构架这些host，让他们不用人为操作。
: 2. 经典题：给一个数组，找出一个local minima的值。（local minima 即这个数比左
: 右两边的数小，假设没有重复。）
: 明天面试另一家公司的onsite，求bless啊！！
|
p**p
发帖数: 2493 | |
b*******h
发帖数: 53 | 29 谢谢大家，回来更新 攒人品
这道题有前提的：1. 没有重复，2. a［0］《a［1］的话a［0］就是local minima， a
［n－1］ 《 a［n－2］的话，a［n－1］是local minima。
通过画图，如果左右两个端点的某一个端点比中点小，意味着这边都有local minima，
找这一边。
如果两个端点都比中点大，意味着左边或右边有一个local minima，画图的时候可一看
到。看中点的左右相邻两点，如果是递增，local minima在左侧一定有一个， 如果递
减， 在右侧一定有一个。如果相邻点都比中点大，中点就是local minima，都比中点
小，两边都有local minima。 |
i*******s
发帖数: 558 | 30 zan & bless
a
【在 b*******h 的大作中提到】
: 谢谢大家，回来更新 攒人品
: 这道题有前提的：1. 没有重复，2. a［0］《a［1］的话a［0］就是local minima， a
: ［n－1］ 《 a［n－2］的话，a［n－1］是local minima。
: 通过画图，如果左右两个端点的某一个端点比中点小，意味着这边都有local minima，
: 找这一边。
: 如果两个端点都比中点大，意味着左边或右边有一个local minima，画图的时候可一看
: 到。看中点的左右相邻两点，如果是递增，local minima在左侧一定有一个， 如果递
: 减， 在右侧一定有一个。如果相邻点都比中点大，中点就是local minima，都比中点
: 小，两边都有local minima。
|
|
|
j*****y
发帖数: 1071 | 31 不怕做不到，就怕想不到阿。
如果面试官说有 log N 的话，还是不难想到的。
a
【在 b*******h 的大作中提到】
: 谢谢大家，回来更新 攒人品
: 这道题有前提的：1. 没有重复，2. a［0］《a［1］的话a［0］就是local minima， a
: ［n－1］ 《 a［n－2］的话，a［n－1］是local minima。
: 通过画图，如果左右两个端点的某一个端点比中点小，意味着这边都有local minima，
: 找这一边。
: 如果两个端点都比中点大，意味着左边或右边有一个local minima，画图的时候可一看
: 到。看中点的左右相邻两点，如果是递增，local minima在左侧一定有一个， 如果递
: 减， 在右侧一定有一个。如果相邻点都比中点大，中点就是local minima，都比中点
: 小，两边都有local minima。
|
J******e
发帖数: 225 | 32 when a[mid-1] == a[mid]==a[mid+1], a[mid] is considered as a local minimum.
mid
【在 c********t 的大作中提到】
: 多谢讲解。基本思路应该就是这样。
: 但这道题我觉得本身限定很多。
: 第一,就是要given condition (a[0] >= a[1] && a[n-2] <= a[n-1]) 或者允许两头作
: 为local min
: 第二，就是不应该有duplicate (至少duplicate不相邻，否则遇到 a[mid-1] == a[mid
: ]==a[mid+1] 就不知道往哪里搜了。你的程序这种情况往前搜应该不对。
: 5,4,2,2,2,2,1,3
: 5,1,2,2,2,2,3,4
:
: 0]
|
A****e
发帖数: 310 | |
