一亩三分地论坛

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

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

google 电面

[复制链接] |试试Instant~ |关注本帖
Newneo 发表于 2016-4-23 02:39:59 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Other在职跳槽

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

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

x
1. maxDepth of a tree:recursion. visit 1point3acres.com for more.
2.Design a interface for find the running mode in a stream of values:
   随时返回most frequent word 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
   先写函数get();add(String input);
   再问怎么实现这个两个函数:先说了Heap, get()-->O(1),add()--O(n) 然后她说优化add(),我说用HashMap+ counter,这样get()-->O(1),add()--->O(1)
   然后开始写代码。。
   写完了问你觉得这个代码有什么问题,我说multi-threading可能有错,一个在get(), 一个在add(),她说 是的,如果这是single thread 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
         我说可能space太大了,因为有些hot词频会被频繁输入,但是冷门的词语也会一直保存,她说对的 怎么优化?
         1.我说用Tritree,减少HashMap key的存放空间,她说这个key不一定是string,可能是object,
         2.我说group input searching,比如 google, google.inc 表示的可能是一样的意思,只用一个key保存,这样插入时判断similarity,小于一个threshold就认定match,把当前位置+1;
         3.我说用cache。大概说了说,时间就到了,她说you are in the right track,但是我们没时间了。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
杰西Jesse 发表于 2016-5-4 02:53:44 | 显示全部楼层
HashMap + counter是用两个HashMap(key = string, value = time),一个String,一个counter记录最大次数,然后add的时候update string么?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2016-5-4 02:54):
一个hashmap
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-7 14:41:37 | 显示全部楼层
应该是Map + maxHeap吧, map<string, HeapNode>, HeapNode includes count and word. get() -> O(1), add() -> O(lgn)
回复 支持 反对

使用道具 举报

大古1234 发表于 2016-10-8 02:04:26 | 显示全部楼层
tigercode 发表于 2016-9-7 14:41
应该是Map + maxHeap吧, map, HeapNode includes count and word. get() -> O(1), add() -> O(lgn)

我觉得加Map没有用啊,还是得把之前的那个node从heap里删掉,node.count++后再加进去
回复 支持 反对

使用道具 举报

virpro 发表于 2016-10-8 02:24:18 | 显示全部楼层
能说一下你cache的思路吗?
回复 支持 反对

使用道具 举报

BruceLee 发表于 2016-10-14 00:01:56 | 显示全部楼层
大古1234 发表于 2016-10-8 02:04. From 1point 3acres bbs
我觉得加Map没有用啊,还是得把之前的那个node从heap里删掉,node.count++后再加进去

你维护一个string和一个freq,里面存着当前最高频的词,和其频率。每次add的时候,先把对应hashmap中的value++,再查看,如果value > freq,就更新string = key, freq = value。如果要top k的话,就建立多个这样的string,freq的node,放在heap里就好了,一个的话,不用heap也没问题。。. 1point3acres.com/bbs

个人看法.......
回复 支持 反对

使用道具 举报

wopani007 发表于 2016-10-14 07:28:15 | 显示全部楼层
BruceLee 发表于 2016-10-14 00:01
你维护一个string和一个freq,里面存着当前最高频的词,和其频率。每次add的时候,先把对应hashmap中的va ...

感觉挺对的,类似于那个closest k point的做法,用minheap,如果超过heap最小频率的,就把新的node加进去。。
回复 支持 反对

使用道具 举报

intaglio 发表于 2016-10-14 08:55:27 | 显示全部楼层
请问可以详细说下cache吗
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 20:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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