一亩三分地论坛

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

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

Google 电面

[复制链接] |试试Instant~ |关注本帖
zhlsh 发表于 2016-5-10 06:52:12 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 博士 全职@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
5/6 google 电面
首先给一个字典,比如:{apple, people,...}
再给一个misspelling word,比如:adple,返回它的正确拼写,即 apple
还知道一个限制条件,misspelling word只跟原单词有一个字母的区别。如果输入是addle,返回null。如果字数不同,也返回null. visit 1point3acres.com for more.


还是比较简单的一个题,一开始以为是warm up。结果发现这种简单题也是能扯出很多东西的,主要在问题的理解和交流上。比如:是不是需要返回所有的correction,如何降低一些时间复杂度。写完代码,又问了下我怎么测试。一共用了30分钟在这道题上。剩下的15分钟就是聊我过去的项目和她现在的team。45分钟准时挂电话。。
. 鍥磋鎴戜滑@1point 3 acres

上周五电面,今天就给了onsite通知,还是很有效率的。.鐣欏璁哄潧-涓浜-涓夊垎鍦

评分

1

查看全部评分

blackrose 发表于 2016-5-10 13:17:54 | 显示全部楼层
same as one edit distance.
回复 支持 0 反对 2

使用道具 举报

Littles 发表于 2016-5-15 05:23:19 | 显示全部楼层
赞楼主的方法。
  1. public static String findMissSpelling(Set<String> dict, String str) {.1point3acres缃
  2.                 if (dict == null || dict.size() == 0 || str == null || str.length() == 0) {
  3.                         return null;
  4.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  5.                 int n = str.length();
  6.                 char[] cs = str.toCharArray();
  7.                 for (int i = 0; i < cs.length; i++) {
  8.                         char ori = cs[i];
  9.                         for (char tmp = 'a'; tmp <= 'z'; tmp++) {
  10.                                 if (ori == tmp) {
  11.                                         continue;-google 1point3acres
  12.                                 }
  13.                                 cs[i] = tmp;
  14.                                 String tmpString = new String(cs);
  15.                                 if (dict.contains(tmpString)) {
  16.                                         return tmpString;
  17.                                 }
  18.                         }
  19.                         cs[i] = ori;
  20.                 }
  21.                 return null;. Waral 鍗氬鏈夋洿澶氭枃绔,
  22.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

veryflying 发表于 2016-5-10 14:44:58 | 显示全部楼层
HighWayT0HeLL 发表于 2016-5-10 08:24
楼主能讲讲这道题你怎么做的吗,我想到的是用trie tree做

为什么我觉得应该从a-z,0-单词长度遍历一遍,在wordlist里面找。。
回复 支持 1 反对 0

使用道具 举报

HighWayT0HeLL 发表于 2016-5-10 08:24:49 | 显示全部楼层
楼主能讲讲这道题你怎么做的吗,我想到的是用trie tree做
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-5-10 13:08:29 | 显示全部楼层
恭喜lz。 请问 只有一个字母区别, 是可以多一个少一个,还是长度是一样的,只是一个字母拼错了?
回复 支持 反对

使用道具 举报

dimi 发表于 2016-5-10 14:38:58 | 显示全部楼层
好簡單阿 恭喜!
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-5-10 15:44:46 | 显示全部楼层
写了个brute force
void recoverMispellingWord(vector<string> dict, string misSpellingWord)
{
        if (dict.size() == 0)return;
        for (int i = 0; i < dict.size(); i++). 1point3acres.com/bbs
        {
                if (dict[i].size() != misSpellingWord.size())continue;
                int cnt = 0;
                int j = 0;
                while (j < dict[i].size() && cnt < 2)
                {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        if (dict[i][j] != misSpellingWord[j])
                        {
                                cnt++;
                        }
                        j++;
                }
                if (j == dict[i].size() && cnt == 1). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                {
                        cout << dict[i] << endl;
. visit 1point3acres.com for more.                }
        }
}
回复 支持 反对

使用道具 举报

cyqiii 发表于 2016-5-10 23:18:12 | 显示全部楼层
我面的问题一模一样,就一道题,follow up 也一样
回复 支持 反对

使用道具 举报

HighWayT0HeLL 发表于 2016-5-10 23:42:12 | 显示全部楼层
cyqiii 发表于 2016-5-10 23:18
我面的问题一模一样,就一道题,follow up 也一样

请问能讲讲你的思路吗
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-10 23:46:31 | 显示全部楼层
mingzhou1987 发表于 2016-5-10 15:44
写了个brute force. From 1point 3acres bbs
void recoverMispellingWord(vector dict, string misSpellingWord). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
{

不对吧,misSpellWord 有可能少写了一个字母或者多写一个字母,或者拼错一个字母。
回复 支持 反对

使用道具 举报

menderr 发表于 2016-5-11 00:20:54 | 显示全部楼层
这个题最优解是2维 dp 吗?
回复 支持 反对

使用道具 举报

 楼主| zhlsh 发表于 2016-5-11 01:14:25 | 显示全部楼层
这题还是有点小技巧。因为已知misspelling word和正确的单词之间只有一个字母的区别(再次说明,长度一样的),所以给定一个misspelling word,它只有25K(K是单词长度)种可能的正确单词。假设词典是用hashset存的,只要遍历这25K种可能性就好了,而不用遍历整个词典。遍历词典的方法复杂度是O(NK)。楼下那个bruteforce的方法没问题,那也是我和面试官说的第一个方法,不过并没有做实现。再讨论完这个更好的解法之后做地实现。我一开始也没想到,被提醒了一下。
回复 支持 反对

使用道具 举报

cyqiii 发表于 2016-5-11 23:56:53 | 显示全部楼层
zhlsh 发表于 2016-5-11 01:14
这题还是有点小技巧。因为已知misspelling word和正确的单词之间只有一个字母的区别(再次说明,长度一样的 ...

可能的拼法不是pow(26, K)吗?我面的时候是这么说的。然后我说这种方法不可取。。.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2016-5-12 00:07):
Edit:
pow(25, K)
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-5-12 00:07:30 | 显示全部楼层
cyqiii 发表于 2016-5-11 23:56. Waral 鍗氬鏈夋洿澶氭枃绔,
可能的拼法不是pow(26, K)吗?我面的时候是这么说的。然后我说这种方法不可取。。

应该是 25K吧。 因为可能的拼法是
假如第1个字符错了就有25种正确的 || 假如第2个字符错了就有25种正确的 || 假如第3个字符错了就有25种正确的 ......|| 假如第n个字符错了就有25种正确的

所有的或加起来,应该是 (25 + 25 + ... + 25) = 25K。是这样吧?
回复 支持 反对

使用道具 举报

cyqiii 发表于 2016-5-12 00:11:35 | 显示全部楼层
zhlsh 发表于 2016-5-11 01:14
这题还是有点小技巧。因为已知misspelling word和正确的单词之间只有一个字母的区别(再次说明,长度一样的 ...

我用trie做的,把字典建成trie, 写一个search(string misspell, int K), K 表示可以容忍的不匹配数,这样可以做到匹配的early termination
回复 支持 反对

使用道具 举报

cyqiii 发表于 2016-5-13 00:00:03 | 显示全部楼层
yueliu2366 发表于 2016-5-12 00:07
应该是 25K吧。 因为可能的拼法是 . 1point 3acres 璁哄潧
假如第1个字符错了就有25种正确的 || 假如第2个字符错了就有25种正确 ...
-google 1point3acres
对的,my bad
回复 支持 反对

使用道具 举报

ptbrxlphx 发表于 2016-5-13 00:29:27 | 显示全部楼层
用trie,第一次找不到记录一下,第二次找不到返回null,感觉没有其他更加好的方法了
回复 支持 反对

使用道具 举报

JermaineDing 发表于 2016-5-14 02:04:58 | 显示全部楼层
这题用one edit distance那种做法可以吗?
回复 支持 反对

使用道具 举报

tianf 发表于 2016-5-17 05:38:28 | 显示全部楼层
想问一下楼主写完代码怎么测试,是让你写一些unit testing的test cases吗?要写多少呢?还是说说就可以了?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 08:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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