GOOGLE 1116新鲜电面－－实习第三轮

刚刚结束的第三轮实习加面，听上去是白人小哥，新鲜出炉两道题：
1. Find number of reciprocated edges in directed graph
第一道题灰常简单，给你一个set 的edges， 比如[[0,1],[1,2],[2,1]]，[1,2]跟[2,1]就是eciprocated edges，return 2


2. Given a double array, find x such that [x,x+1] contains most numbers

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

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

nnected，最基础的

补充内容 (2015-12-3 03:41):
进入team match了，祈祷早日被捞走

补充内容 (2016-1-23 23:53):
马克下，把offer签了今天，一块大石落了地了

我也写了下第二题代码 边界条件没考虑 nums的个数小于2的情况我没考虑 因为不知道该返回什么。。其他情况应该都是对的了。。。吧？？大家用作参考咯~

1. <blockquote><pre>public double MostElements(double[] nums){
   
2.     Arrays.sort(nums);
   
3.     int start = 0;
   
4.     int end = 0;
   
5.     int max = 0;
   
6.     int index = 0;
   
7.     while(start<=end&&end<nums.length){
   
8.         while(end<nums.length&&nums[start]+1>nums[end]) end++;
   
9.         if(end-start>max){
   
10.             max = end-start;
    
11.             index = start;
    
12.         }
    
13.         start++;
    
14.     }
    
15.     return nums[index];
    
16. }</pre>

复制代码

写了下第二题的代码，欢迎指教

1. public class MostElementBetweenXAndXPlusOne {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 double[] array = {1.2, 2.4, 2.6, 2.9, 3.2, 5.3, 6.9};
   
5.                 double res = getTheStartOfMostElement(array);
   
6.                 System.out.println(res);
   
7.         }
   
8. 
   
9.         private static double getTheStartOfMostElement(double[] array) {
   
10.                 if (array == null || array.length == 1) {
    
11.                         return -1;
    
12.                 }
    
13.                 Arrays.sort(array);
    
14.                 int start = 0;
    
15.                 double diff = 0;
    
16.                 int max = 0;
    
17.                 double res = 0.0;
    
18.                 for (int i = 0; i < array.length; i++) {
    
19.                         diff = array[i] - array[start];
    
20.                         while (diff > 1) {
    
21.                                 start++;
    
22.                                 diff = array[i] - array[start];
    
23.                         }
    
24.                         if (i - start + 1 > max) {
    
25.                                 res = array[start];
    
26.                                 max = i - start + 1;
    
27.                         }
    
28.                 }
    
29.                 return res;
    
30.         }
    
31. }
    

复制代码

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

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

请问第二题的array是sorted吗？

宝贝忆彼岸 发表于 2015-11-17 06:39
请问第二题的array是sorted吗？

可能不是，但是只要用Arrays.sort就行了，不太要求这个

楼主能举例说一下算法吗？

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

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

第二题可以这样么
sort, 然后两个指针 start和end, 开始都指向0, x = A[start], 然后移动end,直到 A[end]>=x+1, 这时候计算这个window中的数字个数end-start+1, 如果比当前已经知道的最优还好，更新，然后start=end, end继续向前移动

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

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

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

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

樓主可以分享一下你第一題的思路嘛？我今天也被問這題

同问第一题，如果有[0,1],[1,2],[2,3],[3,0]这种算有几条reciprocated edges啊?
谢谢