要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 6249|回复: 30
收起左侧

Google 电面 * 2

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

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

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

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

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

大米. 顺便问问有没有一月想在bellevue找房子的?

评分

4

查看全部评分




上一篇:Bloomberg 全职校面 第一轮
下一篇:Linkeidn + Uber 电面一面

本帖被以下淘专辑推荐:

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

使用道具 举报

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

补充内容 (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.本文原创自1point3acres论坛
第二题 Map?. 1point 3acres 论坛
WraperClass { key: name, value: count}

yep + yep
回复 支持 反对

使用道具 举报

 楼主| surezero 发表于 2015-10-20 09:10:24 | 显示全部楼层
liyanjia92 发表于 2015-10-20 09:03
char to int 啥意思啊? char - '0'??
. more info on 1point3acres
补充内容 (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):
第二题
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-20 13:08:21 | 显示全部楼层
surezero 发表于 2015-10-20 09:10. 围观我们@1point 3 acres
第二面 先一个Map存人名和次数
follow up 外面再加一个map当cache
.本文原创自1point3acres论坛
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?. 围观我们@1point 3 acres
回复 支持 反对

使用道具 举报

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.本文原创自1point3acres论坛
先把输入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.1point3acres网
第二题 Map?. more info on 1point3acres
WraperClass { key: name, value: count}

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

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

Map<name, count> m1
Map<time, CurrentWinner> m2
CurrentWinner{. 留学申请论坛-一亩三分地
   int count;
   string name. From 1point 3acres bbs
}
public void load(List<vote> l){
    for(vote v: l){.留学论坛-一亩-三分地
       update m1;
       update m2; . from: 1point3acres
   }. 围观我们@1point 3 acres
}

public String get(int second){
    m2.get(second).name. 牛人云集,一亩三分地
}
回复 支持 反对

使用道具 举报

liyanjia92 发表于 2015-10-21 05:11:40 | 显示全部楼层
hyliu0000 发表于 2015-10-21 02:38.1point3acres网
如果参选的人很多的话怎么办?
. 牛人云集,一亩三分地
这样会不会更好些? 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>. visit 1point3acres for more.
然后先一个一个看
1: Alice: 1 最大是Alice: 1. 1point 3acres 论坛
2: Bob: 1 最大是Alice: 1. 1point 3acres 论坛
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. more info on 1point3acres

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

这样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-google 1point3acres
在原来的输入中会有重复Time,但排序后,是整理完1秒的数据后,才往Map里写新的
比如
排序后变为

跟你思路差不多,写了下代码。第一个function是普通做法扫一遍,第二个是为了call many times的。. Waral 博客有更多文章,
. more info on 1point3acres
如果是stream,只用一个hashmap存每个人对应票数,用一个变量维护最多票数人,每次用hashmap的value和这个变量比较更新返回它。
  1. class Vote:
  2.         def __init__(self, name, time):
  3.                 self.name = name
  4.                 self.time = time


  5. def maxVote(A, timestamp):
  6.         dic = collections.defaultdict(int)
  7. . 围观我们@1point 3 acres
  8.         res = None
  9.         for i in A:
  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


  15. # call many times
  16. class System:
  17.         def __init__(self, A):. 1point 3acres 论坛
  18.                 self.sort_A = sorted(A, key=lambda x: x.time)
  19.                 self.time_dic = self.preprocess(self.sort_A). 一亩-三分-地,独家发布

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

  23.                 maxVote = None
  24.                 for i in sort_A:
  25.                         vote_dic[i.name] += 1
  26.                         if maxVote == None or vote_dic[i.name] > vote_dic[maxVote]:
  27.                                 maxVote = i.name 来源一亩.三分地论坛.

  28.                         time_dic[i.time] = maxVote

  29.                 return time_dic
  30. . 1point3acres
  31.         def query(self, timestamp):
  32.                 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. 围观我们@1point 3 acres
如果是python的话怎么自己实现intTochar呢,求指教

直接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'就行了吧
. more info on 1point3acres
意思是手动给映射过去?
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-27 08:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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