1105/1119google实习三轮电面面经

之前潜水太久 现回报地里！

1105两轮电面
第一轮（白人姐姐1）：
1.一个排序好的数组，问存不存在一个popular value，其个数超过n/4，可用二分 log(n)时间
2.n个字符串的最长公共前缀
3.一个数组找一个local minimal(两边的数比中间大)，面试官提出用random search，与brute force比较优劣
每个题都要写test case，且要simulate怎么运行
这一轮情况应该不错，白人姐姐态度挺好

第二轮（白人姐姐2）：

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

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

找出来
如4，5，6，7，9，10 输出8
二分解决

第二天通知进host了～

希望对大家有帮助～～
求大米

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

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

zsycn 发表于 2015-11-25 07:42
沙发～求问楼主第一题popular value 思路！

如果popular value存在， 则n/4、n/2、3n/4位置处的数字至少有一个是popular value，只要对这三个位置上的数用二分找边界即可

interval intersection这道题，就是拿一个start, end，看是不是在另一个interval的范围之内？

1. public class IntervalIntersection {
   
2. 
   
3.         static class Interval {
   
4.                 int start;
   
5.                 int end;
   
6.                 public Interval(int start, int end) {
   
7.                         this.start = start;
   
8.                         this.end = end;
   
9.                 }
   
10.         }
    
11.        
    
12.         public static int isIntervalIntersect(Interval i1, Interval i2) {
    
13.                 if ((i2.start >= i1.start && i2.start <= i1.end) || ((i2.end >= i1.start && i2.end <= i1.end))) {
    
14.                         return 0;
    
15.                 } else {
    
16.                         int start = Math.max(i1.start, i2.start);
    
17.                         int end = Math.min(i1.end, i2.end);
    
18.                         return Math.abs(start - end);
    
19.                 }
    
20.         }
    
21.        
    
22.         public static void main(String[] args) {
    
23.                 Interval i1 = new Interval(3, 4);
    
24.                 Interval i2 = new Interval(1, 2);
    
25.                 int res = isIntervalIntersect(i1, i2);
    
26.                 System.out.println(res);
    
27.         }
    
28. }
    

复制代码

沙发～求问楼主第一题popular value 思路！

楼主是有machine learning的project在简历上吗？

bobzhang2004 发表于 2015-11-25 08:54
楼主是有machine learning的project在简历上吗？

有一小段 水水的文本分类的

chaozc 发表于 2015-11-25 11:06
如果popular value存在， 则n/4、n/2、3n/4位置处的数字至少有一个是popular value，只要对这三个位置上 ...

那就是用3次二分查找吗？

lzheng8 发表于 2015-11-26 03:44
那就是用3次二分查找吗？

对的 对三个点找其边界

chaozc 发表于 2015-12-1 13:26
对的 对三个点找其边界

upperbound-lowerbound > n/4 是不是两次就够了

是不是两次就够了