贡献一个Facebook题目

Facebook电面，应该是阿三面试官，碰到了一个题目貌似版上没有看到过所以来贡献一下。

Q1：first bad version 以

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

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

但是有的帖子里面的附件权限不够下载，烦请各位觉得题目有帮助的打赏点积分多谢啦！

jimmyzzxhlh 发表于 2016-6-23 06:46
Min Queue似乎要比Min Stack难
http://stackoverflow.com/questions/12054415/get-min-max-in-o1-time-fro ...

1.         class MinQueue {
   
2.                
   
3.                 Queue<Integer> queue;
   
4.                 Deque<Integer> deque;
   
5.                
   
6.                 public MinQueue() {
   
7.                         queue = new LinkedList<Integer>();
   
8.                         deque = new ArrayDeque<Integer>();
   
9.                 }
   
10.                
    
11.                 public void offer(int x) {
    
12.                         if (queue.size() == 0) {
    
13.                                 queue.offer(x);
    
14.                                
    
15.                                 deque.offer(x);
    
16.                         }
    
17.                         else {
    
18.                                 queue.offer(x);
    
19.                                 for (Iterator<Integer> it = deque.descendingIterator(); it.hasNext();) {
    
20.                                         if (it.next() > x) {
    
21.                                                 it.remove();
    
22.                                         }
    
23.                                 }
    
24.                                 deque.offer(x);
    
25.                         }
    
26.                 }
    
27.                
    
28.                 public int remove() {
    
29.                         if (queue.size() == 0) return -1;
    
30.                         int val = 0;
    
31.                         if (queue.peek() == deque.peek()) {
    
32.                                 val = queue.remove();
    
33.                                 deque.remove();
    
34.                         }
    
35.                         else {
    
36.                                 val = queue.remove();
    
37.                         }
    
38.                         return val;
    
39.                 }
    
40.                
    
41.                 public int getMin() {
    
42.                         return deque.getFirst();
    
43.                 }
    
44.                
    
45.         }

复制代码

不知道end在哪就指数找end呗...2^n找.. 比如某个n能找到了, 就知道start在[2^n-1, 2^n]了

239. Sliding Window Maximum

first bad version 变种怎么搞。。。。之前好像看过一个比那容易

补充内容 (2016-6-22 03:00):
binary search in unlmited input的。忘记了。。。。

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

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

没boundary么不是....有boundary就二分了....

readman 发表于 2016-6-22 03:19
没boundary么不是....有boundary就二分了....

是不知道boundry在哪里吧。。。

blackrose 发表于 2016-6-22 03:21
是不知道boundry在哪里吧。。。

我的解法跟3楼说的类似，比如就是每次1000个数这样子跳，然后找到之后就用二分法在那个区间里找就行了。

https://www.quora.com/Given-an-array-of-unknown-size-n-how-do-you-find-the-exact-value-of-n-in-O-log-n-time

感觉和3楼说的一样，把二分反过来用。
1. 找2^n直到越界，然后在 [2^(n-1), 2^n] 范围内二分来找边界。
2. 返回正常二分。
一共就是 3*logn

Min Queue似乎要比Min Stack难
http://stackoverflow.com/questions/12054415/get-min-max-in-o1-time-from-a-queue
stack overflow上有一个用queue和deque的解释，不知道lz是不是这样实现的？