狗狗11/2店面

sqrl 发表于 2016-11-5 17:14
那我也得做好心理准备了……你是几号面的？

1号面的

sqrl 发表于 2016-11-5 17:22
第二题跟284差不多，唉，就感觉做过，好久以前做的都忘了

摸摸楼主，没事，继续加油！另外想问一下狗家的questionnaire是不是要写得很细？那个是用来在pool里面匹配的吗？我之前不知道，写得很简单，能不能重新提交呀？

jpeng7 发表于 2016-11-5 08:05
摸摸楼主，没事，继续加油！另外想问一下狗家的questionnaire是不是要写得很细？那个是用来在pool里面匹 ...

我也没写很细，就写了prefer西海岸之类的

zhan1612 发表于 2016-11-5 11:30
第一题是lc原题， 条件是无重复数， 然后两边无限小。
思路是：
if(mid < mid+1)

多谢！我说怎么能O(logN)时间解决呢，原来Leetcode 162原题里还有两个限制条件。。。


PS（纯娱乐）：我想了想为什么加上那两个条件就可以O(logN)时间解决（即使不是sorted），这其实就是一个微积分关于连续函数局部极大值证明题的离散版本啊！
根据离散条件，我可以对等的出这么一道题：（这个题就是用闭区间套定理证明的，相当于binary search）
给定一个定义在闭区间[a, b]上的连续函数f(x), 满足：
1. f(x) > f(a), f(x) > f(b), 对任意 x in (a, b);
2. 对任意 x in [a, b], 存在小邻域(x-d, x+d) 使得f(x)在(x-d, x]和[x, x+d)上分别严格单调 （若x=a or b的话只需满足一边）。
求建立一个[a, b]中的一个序列{x_n}使其收敛到一个严格局部极大值。

zzgzzm 发表于 2016-11-6 06:30
多谢！我说怎么能O(logN)时间解决呢，原来Leetcode 162原题里还有两个限制条件。。。

我觉得这个题的考点肯定就是binary search，不然没任何意义。
”两边无限小“这个并不算关键，甚至算是隐含在题目描述里的（当然要和面试官确认）。
问题的关键是他只需要你随便找一个peak element，而不是所有peak element。随便找就是O(logn)，所有就是O(n)

zzgzzm 发表于 2016-11-6 06:30
多谢！我说怎么能O(logN)时间解决呢，原来Leetcode 162原题里还有两个限制条件。。。

就是loule定理啊，如果函数f(x）满足：
在闭区间[a,b]上连续；
在开区间（a,b）内可导；
在区间端点处的函数值相等，即f(a)=f(b），
那么在（a,b）内至少有一点ξ（a<ξ<b），使得 f'（ξ）=0.

Owenli20 发表于 2016-11-6 09:27
我觉得这个题的考点肯定就是binary search，不然没任何意义。
”两边无限小“这个并不算关键，甚至算是 ...

两边无限小这个条件很关键，这样会保证element一定有先递增再递减的过程。否则binary search用不了，最简单的例子[1,3,2,4,5,6,7]二分查找是找不出来3的

你给f(x)的假设条件太强了，因为可能它就不是可导的。而且为什么要求f(a)=f(b)呢？而且即使找到f'(x)=0的点也不能说明它就一定是严格局部极大值点。
这个关键是要把a[i]!=a[i+1]翻译成等价的连续形式。在离散系统中1就是最小的delta, 而在连续系统中就只能用存在邻域的形式表述了。而这个题是要构造找出严格极大值点，光证明存在性还是不够的。我在Leetcode 162的discussion 中写了证明离散（就是本题）和连续两个版本的证明。得用到实数域的比区间套定理。