《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 5867|回复: 30
收起左侧

Google 电面 * 2

[复制链接] |试试Instant~ |关注本帖
surezero 发表于 2015-10-20 07:10:16 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Failfresh grad应届毕业生

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

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

x
Google:
电面#1:. From 1point 3acres bbs
一个没有口音的三哥. Leetcode plus one. int数组变成了char. 需要自己实现intToChar和charToInt. 好久没面试了超级紧张, bug百出. hr说再来一轮吧.
电面#2:.鐣欏璁哄潧-涓浜-涓夊垎鍦
<235, Obama> 代表在第235秒时, obama得到了一个选票. 你现在有一个list的这种数据, 求在第x秒时谁的票数最多.
follow up: 你这个函数会被调用多次, 如何优化?
自认为答的不错 一周后hr打电话说跪了 建议10个月之后再申.. more info on 1point3acres.com

大米. 顺便问问有没有一月想在bellevue找房子的?. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

4

查看全部评分

本帖被以下淘专辑推荐:

头像被屏蔽
lll_2013 发表于 2015-10-21 06:07:12 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 1 反对 0

使用道具 举报

liyanjia92 发表于 2015-10-20 09:03:06 | 显示全部楼层
char to int 啥意思啊? char - '0'??

补充内容 (2015-10-20 09:04):
还有请问楼主第二面是怎么回答的呢?
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-10-20 09:07:18 | 显示全部楼层
第二题 Map<time, List<WraperClass>>?
WraperClass { key: name, value: count}
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-10-20 09:07:24 | 显示全部楼层
第二题 Map<time, List<WraperClass>>?
WraperClass { key: name, value: count}
回复 支持 反对

使用道具 举报

 楼主| surezero 发表于 2015-10-20 09:08:01 | 显示全部楼层
yjfox 发表于 2015-10-20 09:07
第二题 Map? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
WraperClass { key: name, value: count}
. 1point3acres.com/bbs
yep + yep
回复 支持 反对

使用道具 举报

 楼主| surezero 发表于 2015-10-20 09:10:24 | 显示全部楼层
liyanjia92 发表于 2015-10-20 09:03
char to int 啥意思啊? char - '0'??
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2015-10-20 09:04):

第二面 先一个Map存人名和次数. visit 1point3acres.com for more.
follow up 外面再加一个map当cache
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-20 09:13:19 | 显示全部楼层
第一题怎么做啊。。。调用很多次是全扫完list后调用,还是边加list边调用?如果是前者,预处理完就好了吧,如果是后者用个堆?
-google 1point3acres
补充内容 (2015-10-20 09:25):
第二题
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-20 13:08:21 | 显示全部楼层
surezero 发表于 2015-10-20 09:10
第二面 先一个Map存人名和次数
follow up 外面再加一个map当cache

hashMap<TimeStamp, HashMap<People, count>> 这样update 是o(1) search是o(n) 想不到search是o(logn) 的方法?
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-10-20 13:38:22 | 显示全部楼层
say543 发表于 2015-10-20 13:08
hashMap 这样update 是o(1) search是o(n) 想不到search是o(logn) 的方法?

这里题目求最大,额外用其它容器在更新的同时记录该时间点最大值即可
还有你说的search是search on what?
回复 支持 反对

使用道具 举报

liyanjia92 发表于 2015-10-20 23:02:08 | 显示全部楼层
Map<Time, Name>
Map<Name, Count>
先把输入List按时间排序,然后从头遍历,维护一个最大的Count和Name组合,每到新的一秒写入Map<Time, Name>
这样怎么样?
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-10-21 02:09:37 | 显示全部楼层
liyanjia92 发表于 2015-10-20 23:02
Map
Map. from: 1point3acres.com/bbs
先把输入List按时间排序,然后从头遍历,维护一个最大的Count和Name组合,每到新的一秒写入Map

time会重复把。。  
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2015-10-21 02:37:17 | 显示全部楼层
liyanjia92 发表于 2015-10-20 10:02
Map
Map
先把输入List按时间排序,然后从头遍历,维护一个最大的Count和Name组合,每到新的一秒写入Map

我也是这么想的,至少没上面那么复杂,还节省空间一点。。。
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-10-21 02:38:56 | 显示全部楼层
yjfox 发表于 2015-10-20 09:07
第二题 Map?-google 1point3acres
WraperClass { key: name, value: count}

如果参选的人很多的话怎么办?

这样会不会更好些? List sort的前提下.鏈枃鍘熷垱鑷1point3acres璁哄潧

Map<name, count> m1
Map<time, CurrentWinner> m2
CurrentWinner{
   int count;.1point3acres缃
   string name
}
public void load(List<vote> l){.鐣欏璁哄潧-涓浜-涓夊垎鍦
    for(vote v: l){
       update m1;
       update m2; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
   }
}. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

public String get(int second){
    m2.get(second).name
}
回复 支持 反对

使用道具 举报

liyanjia92 发表于 2015-10-21 05:11:40 | 显示全部楼层
hyliu0000 发表于 2015-10-21 02:38
如果参选的人很多的话怎么办?
. 1point3acres.com/bbs
这样会不会更好些? List sort的前提下
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
在原来的输入中会有重复Time,但排序后,是整理完1秒的数据后,才往Map<Time, Name>里写新的
比如<3, Cathy><1, Alice><1, Bob><2, Bob><1, Bob><3, Bob>
排序后变为
<1, Alice><1, Bob><1, Bob><2, Bob><3, Bob><3, Cathy>
然后先一个一个看
1: Alice: 1 最大是Alice: 1
2: Bob: 1 最大是Alice: 1
3: Bob: 2 最大是Bob: 2

这个选票过后第一秒结束了,所以在Map<Time, Name>中写入<1, Bob>
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
4: Bob: 3 最大是Bob: 3

这个选票过后第二秒结束了,所以在Map<Time, Name>中写入<2, Bob>

5: Bob: 4 最大是Bob: 4
6: Cathy: 1 最大是Bob: 4
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这个选票过后第三秒结束了,所以在Map<Time, Name>中写入<3, Bob>. 1point 3acres 璁哄潧

这样Map<Time, Name>就建好了,有三个值:
<1, Bob><2, Bob><3, Bob>. Waral 鍗氬鏈夋洿澶氭枃绔,
然后再取任意秒的时候就是O(1).1point3acres缃

但是如果原题是这样:输入List是一个Stream,要求在有一个接口可以返回在当前时刻之前任意时刻的最多票数者,就不能这么做了吧,因为无法对Stream排序
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-22 03:55:58 | 显示全部楼层
yjfox 发表于 2015-10-20 13:38.鏈枃鍘熷垱鑷1point3acres璁哄潧
这里题目求最大,额外用其它容器在更新的同时记录该时间点最大值即可. visit 1point3acres.com for more.
还有你说的search是search on what ...

sea​​rch指的是找最多vote的candidate in a given timestamp
回复 支持 反对

使用道具 举报

tangvictor 发表于 2015-10-22 23:54:33 | 显示全部楼层
liyanjia92 发表于 2015-10-20 17:11
在原来的输入中会有重复Time,但排序后,是整理完1秒的数据后,才往Map里写新的
比如-google 1point3acres
排序后变为
.鐣欏璁哄潧-涓浜-涓夊垎鍦
跟你思路差不多,写了下代码。第一个function是普通做法扫一遍,第二个是为了call many times的。

如果是stream,只用一个hashmap存每个人对应票数,用一个变量维护最多票数人,每次用hashmap的value和这个变量比较更新返回它。
  1. class Vote:
  2.         def __init__(self, name, time):
  3.                 self.name = name
  4.                 self.time = time-google 1point3acres


  5. def maxVote(A, timestamp):. from: 1point3acres.com/bbs
  6.         dic = collections.defaultdict(int).鐣欏璁哄潧-涓浜-涓夊垎鍦

  7.         res = None
  8.         for i in A:
  9.                 if i.time <= timestamp:
  10.                         dic[i.name] += 1
  11.                         if res == None or dic[i.name] > dic[res]:
  12.                                 res = i.name

  13.         return res


  14. # call many times
  15. class System:. Waral 鍗氬鏈夋洿澶氭枃绔,
  16.         def __init__(self, A):
  17.                 self.sort_A = sorted(A, key=lambda x: x.time)
  18.                 self.time_dic = self.preprocess(self.sort_A)

  19.         def preprocess(self, sort_A):
  20.                 vote_dic = collections.defaultdict(int)
  21.                 time_dic = dict()

  22.                 maxVote = None
  23.                 for i in sort_A:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.                         vote_dic[i.name] += 1. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  25.                         if maxVote == None or vote_dic[i.name] > vote_dic[maxVote]:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  26.                                 maxVote = i.name

  27.                         time_dic[i.time] = maxVote

  28.                 return time_dic

  29.         def query(self, timestamp):
  30.                 return self.time_dic[timestamp]
复制代码
回复 支持 反对

使用道具 举报

luofeidream 发表于 2015-10-23 01:05:19 | 显示全部楼层
如果是python的话怎么自己实现intTochar呢,求指教
回复 支持 反对

使用道具 举报

tangvictor 发表于 2015-10-23 01:19:43 | 显示全部楼层
luofeidream 发表于 2015-10-22 13:05. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
如果是python的话怎么自己实现intTochar呢,求指教

直接int('1')->1, str(1)->'1'就行了吧
回复 支持 反对

使用道具 举报

luofeidream 发表于 2015-10-23 13:12:01 | 显示全部楼层
tangvictor 发表于 2015-10-23 01:19. visit 1point3acres.com for more.
直接int('1')->1, str(1)->'1'就行了吧

意思是手动给映射过去?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-20 05:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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