一亩三分地论坛

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

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

Google电面

[复制链接] |试试Instant~ |关注本帖
caigaa 发表于 2015-9-3 01:50:32 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Google - Other - 技术电面 |Passfresh grad应届毕业生

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

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

x
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
上个星期面的,前两天拿到了onsite.

面试官听声音像是老美, 对我phd期间的project挺感兴趣, 聊project花了接近20分钟,最后只做了一题.

1. 题目: word abbreviation, 版上之前也有人发过. 一个string只保留首尾字母, 中间字母数用数字表示, 比如 "abcde" = "a3e", "ab" = "ab", "abc" = "a1c" . 给一组string, 输出相同abbreviation的所有string, 但重复的string不算.
直接用的hashmap, 存储string的时候脑子没转过来,用的array,面试官问是不是有更好的,果断换hashset.
coding完时间剩的不多了,面试官说看code没多大问题,不用测试了... 唉,写代码的速度太慢了啊.

2. 接着是分析下复杂度, O(n). 需要一步步给面试官分析为什么是O(n).

3. 最后面试官问了下, OOP的好处. 这个没怎么准备,只能凭印象瞎掰.


评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| caigaa 发表于 2015-9-3 02:14:39 | 显示全部楼层
我当时的代码没有保存下来.. more info on 1point3acres.com
只能说下我怎么写的:. 1point3acres.com/bbs

1. 一个函数计算abbreviation, 长度小于3的直接返回输入,否则取首尾字母,中间插上to_string(s.size()-2)
2. 用unordered_map<string, unordered_set<string>> 存不同abbreviation的string, 遍历所有输入
3. 遍历hash map, 输出set.length() > 1 的set里面的所有string

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

discoveryi 发表于 2015-9-3 01:55:46 | 显示全部楼层
LZ能贴一下word abbreviation的代码吗?谢谢了!
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-3 02:34:39 | 显示全部楼层
caigaa 发表于 2015-9-3 02:14
我当时的代码没有保存下来.
只能说下我怎么写的:
. Waral 鍗氬鏈夋洿澶氭枃绔,
所以只有去头去尾后中间的字母可以简写成数字?
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-9-3 02:53:35 | 显示全部楼层
对,缩写的规则就是首尾字母保留,中间的字母用长度代替
比如: "abc" -> "a1c", "abbc" ->"a2c", "abdc" ->"a2c"
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-3 03:07:53 | 显示全部楼层
caigaa 发表于 2015-9-3 02:53
对,缩写的规则就是首尾字母保留,中间的字母用长度代替
比如: "abc" -> "a1c", "abbc" ->"a2c", "abdc" ->" ...

多谢!祝LZ好运!
回复 支持 反对

使用道具 举报

discoveryi 发表于 2015-9-3 04:09:55 | 显示全部楼层
caigaa 发表于 2015-9-3 02:14
我当时的代码没有保存下来.
只能说下我怎么写的:

看了LZ的解释还是写不出来,不知道是不是因为自己没理解。
LZ能花个5分钟敲个代码吗? 谢谢。
回复 支持 反对

使用道具 举报

hello2pig 发表于 2015-9-3 05:02:08 | 显示全部楼层
discoveryi 发表于 2015-9-3 04:09
看了LZ的解释还是写不出来,不知道是不是因为自己没理解。
LZ能花个5分钟敲个代码吗? 谢谢。

你可以把代码贴上来 大家帮你改 感觉楼主解释的还是挺明白的 最开始也没想到用set
回复 支持 反对

使用道具 举报

discoveryi 发表于 2015-9-3 11:58:50 | 显示全部楼层
hello2pig 发表于 2015-9-3 05:02
你可以把代码贴上来 大家帮你改 感觉楼主解释的还是挺明白的 最开始也没想到用set

好吧,我说我智商低,压根就没想出O(n), 所以认为自己题目理解错了。. From 1point 3acres bbs
题目介绍的好模糊,我没办法推理了。
回复 支持 反对

使用道具 举报

zzwzhong698800 发表于 2015-9-8 15:24:21 | 显示全部楼层
大家看看这个对么?不知道有没有理解错题意,遍历一遍就是O(n)了
  1. class Solution
  2. {
  3. public:
  4.         vector<string> wordAbbreviation(vector<string> &words). 鍥磋鎴戜滑@1point 3 acres
  5.         {
  6.                 vector<string> res;
  7.                 if(words.size() < 1). from: 1point3acres.com/bbs
  8.                         return res;

  9.                 unordered_map<string, unordered_set<string> > mp;
  10.                 for(int i = 0; i < words.size(); i++)
  11.                 {
  12.                         if(words.size() < 3)
  13.                                 continue;

  14.                         string abbr = abbreviation(words[i]);
  15.                         mp[abbr].insert(words[i]);
  16.                 }
  17. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  18.                 unordered_map<string, unordered_set<string> >::iterator mapItr = mp.begin();
  19.                 for(; mapItr != mp.end(); mapItr++)
  20.                 {
  21.                         unordered_set<string> &st = (*mapItr).second;
  22.                         if(st.size() > 1)
  23.                         {. Waral 鍗氬鏈夋洿澶氭枃绔,
  24.                                 unordered_set<string>::iterator setItr = st.begin();
  25.                                 for(; setItr != st.end(); setItr++)
  26.                                 {
  27.                                         res.push_back(*setItr);
  28.                                 }
  29.                         }
  30.                 }
  31.                 return res;
  32.         }. From 1point 3acres bbs
  33.         string abbreviation(string str)
  34.         {
  35.                 if(str.size() < 3)
  36.                         return str;
  37.                 string res;
  38.                 res = str[0] + to_string(long long(str.size() - 2)) + str[str.size() - 1];
  39.                 return res;
  40.         }
  41. };

  42. int main()
  43. {
  44.         vector<string> words;
  45.         words.push_back("aerb");;
  46.         words.push_back("ab");
  47.         words.push_back("adfb");
  48.         words.push_back("ergb");
  49.         Solution ss;
  50.         vector<string> res = ss.wordAbbreviation(words);
  51.         int i = 0;
  52. }
复制代码

补充内容 (2015-9-9 11:49):
13行哪里错了,多谢楼下的指出,写错了,if(words.size() < 3),应该改为if(words.size() < 3)
那个主要是因为,如果长度小于3,那就是长为1或2,如“ab”,“cd"这种,这个的abbreivation就是自己本身,所以...
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-9-8 22:33:20 | 显示全部楼层
caigaa 发表于 2015-9-3 02:14
我当时的代码没有保存下来.
只能说下我怎么写的:

为什么是O(n)? 不用考虑string的长度吗
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-9-9 00:16:20 | 显示全部楼层
blactangeri 发表于 2015-9-8 22:33
为什么是O(n)? 不用考虑string的长度吗

string 长度不影响算法时间.
abbreviation(string str)时间是定长的,只用了str.size().
其他hashmap,hashset操作时间也是定长的,都不受string长度影响.
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-9-9 00:18:32 | 显示全部楼层
zzwzhong698800 发表于 2015-9-8 15:24. visit 1point3acres.com for more.
大家看看这个对么?不知道有没有理解错题意,遍历一遍就是O(n)了

我面试时候实现和这个差不多.
不过代码13,14行是干嘛的?
回复 支持 反对

使用道具 举报

luzhuzeng 发表于 2015-9-9 01:27:57 | 显示全部楼层
caigaa 发表于 2015-9-8 10:16
string 长度不影响算法时间.
abbreviation(string str)时间是定长的,只用了str.size().
其他hashmap,h ...

其实我一直在想,对string做hash的时候难道不需要获取全部的string的信息吗?那这样的话其实计算string的hash的时候理论上是跟string长度成正比的?
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-9-9 01:58:21 | 显示全部楼层
luzhuzeng 发表于 2015-9-9 01:27
其实我一直在想,对string做hash的时候难道不需要获取全部的string的信息吗?那这样的话其实计算string的 ...

这个我确实没有考虑到.如果一个一个字符算hash的话,确实要考虑string的长度.

我面试的时候是说的O(n), 面试官也没说有问题. 估计是他只考虑输入array的长度
回复 支持 反对

使用道具 举报

zzwzhong698800 发表于 2015-9-9 11:25:07 | 显示全部楼层
caigaa 发表于 2015-9-9 00:18
我面试时候实现和这个差不多.
不过代码13,14行是干嘛的?

那个主要是因为,如果长度小于3,那就是长为1或2,如“ab”,“cd"这种,这个的abbreivation就是自己本身,所以要长度小于3的,又要abbrivation相同的,那肯定就只有自己本身了,但是按你的题意,不是不能加入重复字符串么?所以,长度小于3的字符串是肯定不会出现在最后结果集里的,所以直接continue不处理。我是这么想的。你认为呢?
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-9-9 11:30:40 | 显示全部楼层
zzwzhong698800 发表于 2015-9-9 11:25
那个主要是因为,如果长度小于3,那就是长为1或2,如“ab”,“cd"这种,这个的abbreivation就是自己本身 ...

哦,那13行应该是:
     if(words.size() < 3)
回复 支持 反对

使用道具 举报

zzwzhong698800 发表于 2015-9-9 11:50:01 | 显示全部楼层
caigaa 发表于 2015-9-9 11:30
哦,那13行应该是:
     if(words.size() < 3)

对的,写错了,应该是
if(words.size() < 3)
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2015-9-9 11:50):
为嘛又打错了呢?应该是if(words.size() < 3)
. more info on 1point3acres.com
补充内容 (2015-9-9 11:52):
我放弃了,貌似是编辑器的问题还是怎么了,words后面的【i】打不出来,就是取string的长度,而不是words本身这个vector的长度,你说的应该是这个意思吧?
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-9-9 22:01:35 | 显示全部楼层
zzwzhong698800 发表于 2015-9-9 11:50. 1point 3acres 璁哄潧
对的,写错了,应该是. from: 1point3acres.com/bbs

补充内容 (2015-9-9 11:50):

我这边也是一样,写的时候有,最后又显示不了,真是神奇
回复 支持 反对

使用道具 举报

douya 发表于 2015-9-22 07:51:15 | 显示全部楼层
楼主是那个Tom面的吗?我也问了abbrevation的题。但是follow up是有returns the shortest unique abbreviation. 没时间写完。
楼主有拿到onsite吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 04:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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