推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 5665|回复: 30
收起左侧

Google 电面 * 2

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

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

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

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

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

大米. 顺便问问有没有一月想在bellevue找房子的?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

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>>?. 鍥磋鎴戜滑@1point 3 acres
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
char to int 啥意思啊? char - '0'??

补充内容 (2015-10-20 09:04):
. visit 1point3acres.com for more.
第二面 先一个Map存人名和次数
follow up 外面再加一个map当cache
回复 支持 反对

使用道具 举报

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

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

这里题目求最大,额外用其它容器在更新的同时记录该时间点最大值即可.1point3acres缃
还有你说的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. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
先把输入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?. from: 1point3acres.com/bbs
WraperClass { key: name, value: count}

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

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

Map<name, count> m1
Map<time, CurrentWinner> m2
CurrentWinner{
   int count;
   string name. Waral 鍗氬鏈夋洿澶氭枃绔,
}.1point3acres缃
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
如果参选的人很多的话怎么办?

这样会不会更好些? 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 3acres 璁哄潧
这个选票过后第一秒结束了,所以在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>

这样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里写新的
比如. visit 1point3acres.com for more.
排序后变为
.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

  5. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6. def maxVote(A, timestamp):
  7.         dic = collections.defaultdict(int)

  8.         res = None
  9.         for i in A:
  10.                 if i.time <= timestamp:. 鍥磋鎴戜滑@1point 3 acres
  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):
  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. Waral 鍗氬鏈夋洿澶氭枃绔,
  26.                         if maxVote == None or vote_dic[i.name] > vote_dic[maxVote]:. 1point3acres.com/bbs
  27.                                 maxVote = i.name

  28.                         time_dic[i.time] = maxVote

  29.                 return time_dic

  30.         def query(self, timestamp):
  31.                 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. 鍥磋鎴戜滑@1point 3 acres
直接int('1')->1, str(1)->'1'就行了吧

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-19 02:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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