一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1760|回复: 16
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
chaozc 发表于 2015-11-25 05:53:45 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
之前潜水太久 现回报地里!
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1105两轮电面. visit 1point3acres.com for more.
第一轮(白人姐姐1):
1.一个排序好的数组,问存不存在一个popular value,其个数超过n/4,可用二分 log(n)时间
2.n个字符串的最长公共前缀
3.一个数组找一个local minimal(两边的数比中间大),面试官提出用random search,与brute force比较优劣
每个题都要写test case,且要simulate怎么运行. more info on 1point3acres.com
这一轮情况应该不错,白人姐姐态度挺好

第二轮(白人姐姐2):
1. warm up 比较两个interval是否相交,不相交求距离
2. lc 281 zigzag iterator,输入就是iterator的iterator而不是vector或者list,而iterator的个数也不定,开始有点晕没搞清题目,所以这题干了三十五分钟,跪在这里

由于第二轮面的不好三个工作日之后通知加面第三轮
第三面1119. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
白人大叔,人挺nice的,上来先问简历,一段做微博文本分类的
1.然后要写一个文本分类器。。。
由于没见过这种问法。。硬着头皮说要有training、predict两个部分,要提取feature vector然后投到svm里面去之类的,写了一个调库的版本
然后大叔说不要调库,直接写一个,效果差也没关系。。。
然后当时也没有想到写naive bayes啥的,于是写了个最裸的拿term frequency做feature vector,训练的时候求平均,预测的时候找最近。。。类似于supervised的kmeans。。。
然后大叔高兴的说了句this is what I want!
然后心里有点底了
之后又问了一下数据量大怎么搞,答在distributed system训练.1point3acres缃
. 1point3acres.com/bbs
2.搞完还有10分钟,问了道水题missing number
一个连续数列,中间缺了一项,找出来
如4,5,6,7,9,10 输出8
二分解决-google 1point3acres

第二天通知进host了~. 1point 3acres 璁哄潧
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
希望对大家有帮助~~.鐣欏璁哄潧-涓浜-涓夊垎鍦
大米
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

4

查看全部评分

 楼主| chaozc 发表于 2015-12-3 07:14:45 | 显示全部楼层
bobzhang2004 发表于 2015-12-1 23:44
interval intersection这道题,就是拿一个start, end,看是不是在另一个interval的范围之内?
. 鍥磋鎴戜滑@1point 3 acres
对。。很水。。不重合的条件是 s1>e2||s2>e1 反之重合 求差就是max(s1,s2)-min(e1,e2)

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| chaozc 发表于 2015-11-25 11:06:17 | 显示全部楼层
zsycn 发表于 2015-11-25 07:42
沙发~求问楼主第一题popular value 思路!

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

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

zsycn 发表于 2015-11-25 07:42:08 | 显示全部楼层
沙发~求问楼主第一题popular value 思路!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-11-25 08:54:24 来自手机 | 显示全部楼层
楼主是有machine learning的project在简历上吗?
回复 支持 反对

使用道具 举报

 楼主| chaozc 发表于 2015-11-25 11:04:13 | 显示全部楼层
bobzhang2004 发表于 2015-11-25 08:54.1point3acres缃
楼主是有machine learning的project在简历上吗?
. From 1point 3acres bbs
有一小段 水水的文本分类的
回复 支持 反对

使用道具 举报

lzheng8 发表于 2015-11-26 03:44:57 | 显示全部楼层
chaozc 发表于 2015-11-25 11:06
如果popular value存在, 则n/4、n/2、3n/4位置处的数字至少有一个是popular value,只要对这三个位置上 ...

那就是用3次二分查找吗?
回复 支持 反对

使用道具 举报

 楼主| chaozc 发表于 2015-12-1 13:26:53 | 显示全部楼层
lzheng8 发表于 2015-11-26 03:44
那就是用3次二分查找吗?

对的 对三个点找其边界
回复 支持 反对

使用道具 举报

mynn2003 发表于 2015-12-1 13:44:10 | 显示全部楼层
chaozc 发表于 2015-12-1 13:26
对的 对三个点找其边界
-google 1point3acres
upperbound-lowerbound > n/4 是不是两次就够了
回复 支持 反对

使用道具 举报

tyingoey 发表于 2015-12-1 14:39:11 | 显示全部楼层
是不是两次就够了
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-1 23:44:42 | 显示全部楼层
interval intersection这道题,就是拿一个start, end,看是不是在另一个interval的范围之内?
  1. public class IntervalIntersection {

  2.         static class Interval {
  3.                 int start;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4.                 int end;
  5.                 public Interval(int start, int end) {
  6.                         this.start = start;
  7.                         this.end = end;
  8.                 }
  9.         }
  10.        
  11.         public static int isIntervalIntersect(Interval i1, Interval i2) {. from: 1point3acres.com/bbs
  12.                 if ((i2.start >= i1.start && i2.start <= i1.end) || ((i2.end >= i1.start && i2.end <= i1.end))) {
  13.                         return 0;
  14.                 } else {. from: 1point3acres.com/bbs
  15.                         int start = Math.max(i1.start, i2.start);
  16.                         int end = Math.min(i1.end, i2.end);
  17.                         return Math.abs(start - end);
  18.                 }
  19.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  20.        
  21.         public static void main(String[] args) {
  22.                 Interval i1 = new Interval(3, 4);
  23.                 Interval i2 = new Interval(1, 2);
  24.                 int res = isIntervalIntersect(i1, i2);. From 1point 3acres bbs
  25.                 System.out.println(res);
  26.         }
  27. }-google 1point3acres
复制代码
回复 支持 反对

使用道具 举报

 楼主| chaozc 发表于 2015-12-3 07:11:22 | 显示全部楼层
mynn2003 发表于 2015-12-1 13:44
upperbound-lowerbound > n/4 是不是两次就够了

两次请问是哪两次?
回复 支持 反对

使用道具 举报

mynn2003 发表于 2015-12-3 10:44:09 | 显示全部楼层
chaozc 发表于 2015-12-3 07:11
两次请问是哪两次?

假设n是要check的数,就是找一次n最找出现的位置,找一次最晚出现的位置 就够了吧
回复 支持 反对

使用道具 举报

 楼主| chaozc 发表于 2015-12-3 23:29:18 | 显示全部楼层
mynn2003 发表于 2015-12-3 10:44
假设n是要check的数,就是找一次n最找出现的位置,找一次最晚出现的位置 就够了吧

我们说的意思好像不一样。。我说的三次是要对三个位置上的点找最早最晚边界,用二分实现,总的时间是3*logn
回复 支持 反对

使用道具 举报

mynn2003 发表于 2015-12-4 01:13:08 | 显示全部楼层
chaozc 发表于 2015-12-3 23:29-google 1point3acres
我们说的意思好像不一样。。我说的三次是要对三个位置上的点找最早最晚边界,用二分实现,总的时间是3*lo ...

噢,对不起 我可能理解成检测某个数是否数量大于n/4了
回复 支持 反对

使用道具 举报

albee_fighting 发表于 2015-12-18 08:33:21 | 显示全部楼层
楼主,能帮忙具体讲一下Random Search吗?
回复 支持 反对

使用道具 举报

draculaxx 发表于 2015-12-23 06:37:20 | 显示全部楼层
楼主做的project是属于个人的研究方向么?还是属于课程内的proecjt?
我把machine learning写在了take过的课里,不知道会不会也被问道。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 15:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表