一亩三分地论坛

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

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

google onsite

[复制链接] |试试Instant~ |关注本帖
cszeus 发表于 2015-12-6 02:01:36 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 猎头 - Onsite |Otherfresh grad应届毕业生

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

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

x
1. longest substring with at most m distinct characters。问了一堆怎么优化。最后面试官问我是不是见过这题,我说见过类似的,他似乎很不开心,说你应该一开始就提出来。
2. travelling sales man。暴力解。问了很多特殊条件下的优化,比如怎么存图,如果每个城市连接5个城市,复杂度
3. 中国姐姐问的问题,比较2个DOM tree,设计数据结构。注意tag当中有可能包含text。dfs解。姐姐又问怎么节省空间,python的yield关键字会不会。我说不会。她就找了个网页,给我看了些yield的例子,让我写。最后没写出来,她说写得比较接近了。这么短时间学会,可以了。
4. 计算 + 7 (* 8 19) (* 12 (+ 1 2))这样的表达式,就是 7 +(8*9)+(12* (1+2))
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
都在面经里看过,感觉大家已经快把题库都穷尽了

评分

7

查看全部评分

randomusername 发表于 2015-12-22 14:26:06 | 显示全部楼层
cszeus 发表于 2015-12-22 14:23. 鍥磋鎴戜滑@1point 3 acres
悲剧了,让我参加一个ITRP的项目。应该不会去。

ITRP是什么  IT界的RP收集program吗
回复 支持 1 反对 0

使用道具 举报

ssross 发表于 2015-12-6 02:29:19 | 显示全部楼层
楼主能不能说下具体第三题?能不能说下设计的数据结构长啥样?
非常感谢!bless LZ!
回复 支持 反对

使用道具 举报

 楼主| cszeus 发表于 2015-12-6 02:34:22 | 显示全部楼层
ssross 发表于 2015-12-6 02:29
楼主能不能说下具体第三题?能不能说下设计的数据结构长啥样?
非常感谢!bless LZ!

就是树的结构啊,DOM就是个树啊。每个node有个children list,表示子节点。因为有可能有text的,我用的方法是把text也放到一个特殊的node里。

比如<html>hello <p>world<p></html> 就是:
   <html>
      <text> hello </text>
      <p>world </p>
   </html>
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-12-6 05:17:17 | 显示全部楼层
LZ在哪里面的 只有4轮吗
回复 支持 反对

使用道具 举报

ssross 发表于 2015-12-6 05:28:30 | 显示全部楼层
cszeus 发表于 2015-12-6 02:34. 鍥磋鎴戜滑@1point 3 acres
就是树的结构啊,DOM就是个树啊。每个node有个children list,表示子节点。因为有可能有text的,我用的方 ...
.1point3acres缃
什么叫把test放到一个特殊的node里?

我design的是这样的不知道有没有问题:. 鍥磋鎴戜滑@1point 3 acres
class Node {
List<Node> children;.鐣欏璁哄潧-涓浜-涓夊垎鍦
String text;. more info on 1point3acres.com
boolean inTag; // means if the node is in a tag
}
楼主设计的跟我有什么不一样嘛?

还想问下第一题我看到别人的面经里也有过。有个followup是如果给的input是stream怎么办?不知道LZ有没有问到。
回复 支持 反对

使用道具 举报

 楼主| cszeus 发表于 2015-12-6 05:44:15 | 显示全部楼层
queeniejing 发表于 2015-12-6 05:17
LZ在哪里面的 只有4轮吗
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
mountain view, 4轮
回复 支持 反对

使用道具 举报

 楼主| cszeus 发表于 2015-12-6 05:46:33 | 显示全部楼层
ssross 发表于 2015-12-6 05:28
什么叫把test放到一个特殊的node里?

我design的是这样的不知道有没有问题:

因为可能是. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
hello <p>world</p>,也有可能是 <p>hello</p> world

text出现的位置不一定,所以把他也当做node处理。你那个结构,你知道text是在哪里么?
回复 支持 反对

使用道具 举报

 楼主| cszeus 发表于 2015-12-6 05:48:13 | 显示全部楼层
ssross 发表于 2015-12-6 05:28. Waral 鍗氬鏈夋洿澶氭枃绔,
什么叫把test放到一个特殊的node里?
. Waral 鍗氬鏈夋洿澶氭枃绔,
我design的是这样的不知道有没有问题:

并没有问stream的follow up。我不知道你怎么做,反正我会记录字母出现的位置。是不是stream,我觉得没有什么不同
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-12-6 07:56:01 | 显示全部楼层
楼主,第一题需要怎么优化啊? 是不是就是两个指针 + hashmap? 第二轮需要给出dp的解吗? 最后一题是不是就用一个stack就ok了啊? 遇到+-* /就放倒stack里面,遇到)或者结尾了就pop,然后计算。楼主你是怎么做的?
回复 支持 反对

使用道具 举报

 楼主| cszeus 发表于 2015-12-6 14:36:54 | 显示全部楼层
hyliu0000 发表于 2015-12-6 07:56
楼主,第一题需要怎么优化啊? 是不是就是两个指针 + hashmap? 第二轮需要给出dp的解吗? 最后一题是不是 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
第一题主要了优化数据结构,讨论了用堆,BST,python里的OrderedDict的可行性。第二轮NP-hard,我不觉得有dp,就是要你暴力解,然后根据他给的特殊条件,优化下。最后一题我用的stack
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-12-7 05:54:18 | 显示全部楼层
cszeus 发表于 2015-12-6 14:36. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一题主要了优化数据结构,讨论了用堆,BST,python里的OrderedDict的可行性。第二轮NP-hard,我不觉得 ...

longest substring with at most m distinct characters如何用堆和bst? 另外,tsp是有dp解法的。
回复 支持 反对

使用道具 举报

 楼主| cszeus 发表于 2015-12-7 09:39:06 | 显示全部楼层
hyliu0000 发表于 2015-12-7 05:54
longest substring with at most m distinct characters如何用堆和bst? 另外,tsp是有dp解法的。

我存了每个字母出现的位置,我要删最早出现的那个。他就希望我讨论,用什么结构,找这个最早出现的,比较快
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-12-7 11:24:55 | 显示全部楼层
cszeus 发表于 2015-12-7 09:39
我存了每个字母出现的位置,我要删最早出现的那个。他就希望我讨论,用什么结构,找这个最早出现的,比较 ...

这样会不会太费内存了? 最好的方法是不是用hashmap存 char -》 count , 然后用两个指针从前往后扫久行了?
回复 支持 反对

使用道具 举报

 楼主| cszeus 发表于 2015-12-9 01:00:01 | 显示全部楼层
hyliu0000 发表于 2015-12-7 11:24. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这样会不会太费内存了? 最好的方法是不是用hashmap存 char -》 count , 然后用两个指针从前往后扫久行 ...

只要存m个字母,每个字母最后出现的位置。然后找删除哪个的时候,扫一遍这个table,cost O(m)。 但是如果有比较好的数据结构,像是python里的OrderedDict, 连找删除哪一个都是 O(1),所以会很快
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-12-9 02:09:44 | 显示全部楼层
cszeus 发表于 2015-12-9 01:00
只要存m个字母,每个字母最后出现的位置。然后找删除哪个的时候,扫一遍这个table,cost O(m)。 但是如果 ...

楼主啊, 能不能详细说说你是怎么做的?. visit 1point3acres.com for more.
我先说下我的:
定义两个pointer left ,right 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
定义hashmap<char, int> map. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
int maxLength = Integer.MAX_VALUE;
while(right < n)
   map[char] ++
   if(map.size() > m)
     left ++;
     map[char at left] -- ;
     maxLength = max(maxLength, right - left);
   right ++;
maxLength = max(maxLength, right - left);
return maxLength
  
  
回复 支持 反对

使用道具 举报

 楼主| cszeus 发表于 2015-12-9 02:50:12 | 显示全部楼层
hyliu0000 发表于 2015-12-9 02:09. 1point 3acres 璁哄潧
楼主啊, 能不能详细说说你是怎么做的?-google 1point3acres
我先说下我的:
定义两个pointer left ,right

maxLen = 0
dic = {}
end = start = 0
while end < len(s):
    if ch in dic or len(dic) < m:
        dic[ch] = end
    else:
        maxLen = max(maxLen,end-start)
        # find minimum index in dic and its ch, O(m)
        start = index+1
        dic.pop(ch)
    end += 1. from: 1point3acres.com/bbs
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

大致是这样,当你有m个字母,并且出现m+1个字母的时候,你要试图删掉某个字母吧?我就找m个字母里面,出现最早的那个。

比如, ababac, m = 2
当出现c时,字典里面有{"b":3,"a":4}. 我只记录某个字母最后一次出现的位置。现在我可以知道,最后一个b出现在位置3,从位置4开始,只有m-1个字母。

然后这个地方,找到b,要扫一遍这个table。但是如果用OrderDict结合LRU cache的思想,每次更新一个字母的位置时,把它放到字典的最后,你就知道,字典中第一个,永远是我要找的那个。


补充内容 (2015-12-9 02:53):
这个字典会变成: {"a":0}, {"a":0,"b":1}, {"b":1,"a":2},{"a":2,"b":3}......m很大,你就看看出这个好处了
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-12-9 05:13:12 | 显示全部楼层
cszeus 发表于 2015-12-9 02:50
maxLen = 0
dic = {}
end = start = 0

不错的方法。 不过其实我的方法也很简单。 思路和你的差不多。 不过start是 ++ 而不是 start = index + 1. 另外,直接用hashmap, 所以time complexity is O(n)
回复 支持 反对

使用道具 举报

 楼主| cszeus 发表于 2015-12-10 00:35:06 | 显示全部楼层
hyliu0000 发表于 2015-12-9 05:13
不错的方法。 不过其实我的方法也很简单。 思路和你的差不多。 不过start是 ++ 而不是 start = index + 1 ...

面试官说了,一般人都会用你那种方法做。我用了我那个方法,他很奇怪,问我是不是见过类似的。我说有,他很不开心,说我应该提出来。
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-22 03:06:46 | 显示全部楼层
楼主送进hc审核了嘛...我面试时间跟你很近噢
回复 支持 反对

使用道具 举报

 楼主| cszeus 发表于 2015-12-22 14:23:34 | 显示全部楼层
randomusername 发表于 2015-12-22 03:06
楼主送进hc审核了嘛...我面试时间跟你很近噢

悲剧了,让我参加一个ITRP的项目。应该不会去。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 03:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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