一亩三分地论坛

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

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

Google 电面 * 2

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

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

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

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

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

大米. 顺便问问有没有一月想在bellevue找房子的?
. 1point 3acres 璁哄潧

评分

4

查看全部评分

本帖被以下淘专辑推荐:

lll_2013 发表于 2015-10-21 06:07:12 | 显示全部楼层
可以unordered_map<time, vector<map<name, cnt>>> 嘛?
vector 内部全部降序排列

补充内容 (2015-10-20 17:23):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
改一下map<time, map<cnt, vector<name>>>
回复 支持 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}

yep + yep
回复 支持 反对

使用道具 举报

 楼主| surezero 发表于 2015-10-20 09:10:24 | 显示全部楼层
liyanjia92 发表于 2015-10-20 09:03. 1point3acres.com/bbs
char to int 啥意思啊? char - '0'??
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2015-10-20 09:04):

第二面 先一个Map存人名和次数
follow up 外面再加一个map当cache
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-20 09:13:19 | 显示全部楼层
第一题怎么做啊。。。调用很多次是全扫完list后调用,还是边加list边调用?如果是前者,预处理完就好了吧,如果是后者用个堆?

补充内容 (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) 的方法?

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

使用道具 举报

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. 鍥磋鎴戜滑@1point 3 acres
先把输入List按时间排序,然后从头遍历,维护一个最大的Count和Name组合,每到新的一秒写入Map

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

使用道具 举报

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

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

使用道具 举报

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

如果参选的人很多的话怎么办?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

这样会不会更好些? List sort的前提下

Map<name, count> m1
Map<time, CurrentWinner> m2
CurrentWinner{
   int count;
   string name
}
public void load(List<vote> l){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    for(vote v: l){. from: 1point3acres.com/bbs
       update m1;
       update m2; . visit 1point3acres.com for more.
   }
}

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

使用道具 举报

liyanjia92 发表于 2015-10-21 05:11:40 | 显示全部楼层
hyliu0000 发表于 2015-10-21 02:38
如果参选的人很多的话怎么办?
. Waral 鍗氬鏈夋洿澶氭枃绔,
这样会不会更好些? 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. 鍥磋鎴戜滑@1point 3 acres
. Waral 鍗氬鏈夋洿澶氭枃绔,
这个选票过后第一秒结束了,所以在Map<Time, Name>中写入<1, Bob>. 鍥磋鎴戜滑@1point 3 acres

4: Bob: 3 最大是Bob: 3. From 1point 3acres bbs

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

5: Bob: 4 最大是Bob: 4
6: Cathy: 1 最大是Bob: 4

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

这样Map<Time, Name>就建好了,有三个值:
<1, Bob><2, Bob><3, Bob>
然后再取任意秒的时候就是O(1)

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

使用道具 举报

say543 发表于 2015-10-22 03:55:58 | 显示全部楼层
yjfox 发表于 2015-10-20 13:38
这里题目求最大,额外用其它容器在更新的同时记录该时间点最大值即可
还有你说的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里写新的
比如
排序后变为

跟你思路差不多,写了下代码。第一个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

  5. . From 1point 3acres bbs
  6. def maxVote(A, timestamp):
  7.         dic = collections.defaultdict(int). from: 1point3acres.com/bbs

  8.         res = None
  9.         for i in A:. Waral 鍗氬鏈夋洿澶氭枃绔,
  10.                 if i.time <= timestamp:
  11.                         dic[i.name] += 1
  12.                         if res == None or dic[i.name] > dic[res]:
  13.                                 res = i.name

  14.         return res. 1point3acres.com/bbs
  15. . more info on 1point3acres.com

  16. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  17. # call many times
  18. class System:
  19.         def __init__(self, A):
  20.                 self.sort_A = sorted(A, key=lambda x: x.time)
  21.                 self.time_dic = self.preprocess(self.sort_A)

  22.         def preprocess(self, sort_A):
  23.                 vote_dic = collections.defaultdict(int)
  24.                 time_dic = dict()

  25.                 maxVote = None.1point3acres缃
  26.                 for i in sort_A:
  27.                         vote_dic[i.name] += 1
  28.                         if maxVote == None or vote_dic[i.name] > vote_dic[maxVote]:
  29.                                 maxVote = i.name

  30.                         time_dic[i.time] = maxVote

  31.                 return time_dic-google 1point3acres

  32.         def query(self, timestamp):
  33.                 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呢,求指教
. visit 1point3acres.com for more.
直接int('1')->1, str(1)->'1'就行了吧
回复 支持 反对

使用道具 举报

luofeidream 发表于 2015-10-23 13:12:01 | 显示全部楼层
tangvictor 发表于 2015-10-23 01:19
直接int('1')->1, str(1)->'1'就行了吧
. 鍥磋鎴戜滑@1point 3 acres
意思是手动给映射过去?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 11:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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