《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4270|回复: 19
收起左侧

Google 电面

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

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

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

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

x
5/6 google 电面. 1point 3acres 璁哄潧
首先给一个字典,比如:{apple, people,...}. 1point 3acres 璁哄潧
再给一个misspelling word,比如:adple,返回它的正确拼写,即 apple. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
还知道一个限制条件,misspelling word只跟原单词有一个字母的区别。如果输入是addle,返回null。如果字数不同,也返回null
. 1point 3acres 璁哄潧

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

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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

Littles 发表于 2016-5-15 05:23:19 | 显示全部楼层
赞楼主的方法。. 鍥磋鎴戜滑@1point 3 acres
  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.                 }
  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;
  12.                                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  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;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  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)
                {. 1point3acres.com/bbs
                        if (dict[i][j] != misSpellingWord[j]). 1point 3acres 璁哄潧
                        {
                                cnt++;
                        }. 鍥磋鎴戜滑@1point 3 acres
                        j++;
                }
                if (j == dict[i].size() && cnt == 1)
                {
                        cout << dict[i] << endl;
                }. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
}
回复 支持 反对

使用道具 举报

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

使用道具 举报

HighWayT0HeLL 发表于 2016-5-10 23:42:12 | 显示全部楼层
cyqiii 发表于 2016-5-10 23:18
我面的问题一模一样,就一道题,follow up 也一样
. 1point 3acres 璁哄潧
请问能讲讲你的思路吗
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-10 23:46:31 | 显示全部楼层
mingzhou1987 发表于 2016-5-10 15:44
写了个brute force
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
可能的拼法不是pow(26, K)吗?我面的时候是这么说的。然后我说这种方法不可取。。

应该是 25K吧。 因为可能的拼法是 .鏈枃鍘熷垱鑷1point3acres璁哄潧
假如第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. 鍥磋鎴戜滑@1point 3 acres
这题还是有点小技巧。因为已知misspelling word和正确的单词之间只有一个字母的区别(再次说明,长度一样的 ...
. 鍥磋鎴戜滑@1point 3 acres
我用trie做的,把字典建成trie, 写一个search(string misspell, int K), K 表示可以容忍的不匹配数,这样可以做到匹配的early termination
回复 支持 反对

使用道具 举报

cyqiii 发表于 2016-5-13 00:00:03 | 显示全部楼层
yueliu2366 发表于 2016-5-12 00:07
应该是 25K吧。 因为可能的拼法是
假如第1个字符错了就有25种正确的 || 假如第2个字符错了就有25种正确 ...

对的,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吗?要写多少呢?还是说说就可以了?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-20 00:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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