Facebook intern 一面

电话一响，三哥，我就听听，不说话。

1.在一个sorted array找target出现的次数，logn:
follow up,

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

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

15-4-4 09:39):
效率真高，过了，ONSITE求好运

1. 两遍Binary Search，注意判断条件的区别
2. floodfill，用BFS实现，如果用DFS实现可能会爆栈

贴个solution 麻烦看下对不对

1. public static int numOfAppearence(int[] arr, int target) {
   
2.                 int l = 0, r = arr.length - 1;
   
3.                 int start = -1, end = -1;
   
4.                 while (l <= r) {
   
5.                         int m = (l + r) / 2;
   
6.                         if (target <= arr[m])
   
7.                                 r = m - 1;
   
8.                         else
   
9.                                 l = m + 1;
   
10.                 }
    
11.                 start = l;
    
12.                 l = 0;
    
13.                 r = arr.length - 1;
    
14.                 while (l <= r) {
    
15.                         int m = (l + r) / 2;
    
16.                         if (target < arr[m])
    
17.                                 r = m - 1;
    
18.                         else
    
19.                                 l = m + 1;
    
20.                 }
    
21.                 end = l;
    
22.                 return end - start;
    
23.         }

复制代码

likenisha 发表于 2015-4-4 12:06
对角线这个就是dfs的时候多4种情况么

其实是吧，也没什么，就是我做的时候用的recursive 后来用Eclipse跑很容易就Overflow了 不知道怎么还让我过了，应该分配个栈比较好吧

刚面的吗？

有多少岛? 数多少个1?

请问楼主 第一题找到target以后是继续binary search呢 还是linear scan找到target左右的index 然后求出结果 谢谢

readman 发表于 2015-4-4 03:03
有多少岛? 数多少个1?

相邻的1组成一个岛屿  0是海水  所以就是问有多少组连在一起的1

是用染色的方法吗？
写code用软件吗？还是口头说的？谢谢啦~~

jianixie 发表于 2015-4-4 04:34
是用染色的方法吗？
写code用软件吗？还是口头说的？谢谢啦~~

本来HR发了邮件给了stypi的link，结果三哥让我用collabit。。。。。新开了一个然后给他号登进去用的，差不多就染色，类型都一样

wilsonwang1119 发表于 2015-4-4 04:36
本来HR发了邮件给了stypi的link，结果三哥让我用collabit。。。。。新开了一个然后给他号登进去用的，差 ...

好的，谢谢啦~~

ppips 发表于 2015-4-4 07:08
贴个solution 麻烦看下对不对

你可以看看这个：
http://www.geeksforgeeks.org/cou ... -in-a-sorted-array/