一亩三分地论坛

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

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

Google电面

[复制链接] |试试Instant~ |关注本帖
herotrue 发表于 2015-1-1 17:00:39 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Pass

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

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

x
报一个Google电面面经。
面试官是印度人,开始给了一组map,问有没有发现什么pattern。
apple -> a3e
teacher -> t5r
Pattern就是首尾字母加中间的长度。题目要求:给一个txt文件,里面有很多word,写一个function,input是类似于“a3e”,需要输出所有满足这个pattern的word。
楼主说的是先pre-process一下文件,生成一个HashTable,”a3e"是key, value就是同一个pattern的word list。-google 1point3acres
面试官基本满意,开始我说对读文件的API不太熟悉,他建议还是要掌握一下。
两天后收到第二轮电面,估计第一轮面试官不是很满意,需要再面一轮看看。。。。. from: 1point3acres.com/bbs

评分

2

查看全部评分

massagecream 发表于 2015-1-2 05:22:27 | 显示全部楼层
谢谢楼主分享。
不过我没太明白题意,是说只找符合“Pattern就是首尾字母加中间的长度”这个pattern的word么?
回复 支持 反对

使用道具 举报

 楼主| herotrue 发表于 2015-1-2 10:37:30 | 显示全部楼层
所有的word都有一个对应的缩略形式,题目是给一个缩略形式,找出文件里面所有满足这个缩率形式的word。
例如文件有四个词:apple, peach, orange, pitch
输入是“a3e”,输出就是“apple”;输入是“p3h”, 输出就是“peach”和“pitch”
回复 支持 反对

使用道具 举报

legendava 发表于 2015-1-2 12:17:38 | 显示全部楼层
建个trie比较好吧,返回depth满足条件,首尾字符match的单词
回复 支持 反对

使用道具 举报

 楼主| herotrue 发表于 2015-1-2 12:24:23 | 显示全部楼层
legendava 发表于 2015-1-2 12:17. 鍥磋鎴戜滑@1point 3 acres
建个trie比较好吧,返回depth满足条件,首尾字符match的单词

恩恩,我当时也提到trie,但是跟面试官承认自己对trie不太熟悉。他就说还是用自己熟悉的数据结构比较好。
回复 支持 反对

使用道具 举报

haiken 发表于 2015-1-25 11:34:41 | 显示全部楼层
herotrue 发表于 2015-1-2 12:24.1point3acres缃
恩恩,我当时也提到trie,但是跟面试官承认自己对trie不太熟悉。他就说还是用自己熟悉的数据结构比较好。

如果不用trie, 用个编码简单的DFS,遍历所有的combination 应该也可以把?

void findWords(string &p, vector<string> &res, string &str, set<string> &S){
        if(str.size() == p[1] - '0'){
                string word = p[0] + str + p[2];
                if(S.count(word) > 0)
                        res.push_back(word);
                return;       
        }
        for(char c='a'; c<='z'; ++c){
                str += c;
                findWords(p, res, str, S);
                str.pop_back();
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}

vector<string> samePatternWords(string &p, set<string> &S){
        vector<string> res;
        string str;
        findWords(p, res, str, S);
        return res;. from: 1point3acres.com/bbs
}
回复 支持 反对

使用道具 举报

m4reiiy 发表于 2015-1-25 11:40:15 | 显示全部楼层
trie和DFS不如hashmap快。。查找O(1)啊。。

其实LZ还可以用多层hashmap,一般可以省点内存什么的。。
回复 支持 反对

使用道具 举报

tekmark 发表于 2015-1-30 00:21:04 | 显示全部楼层
我跟楼主是同一道题,最后又follow up了一下把abbr升级了一下,比如localise  -》 l2al1s1如何去找。面我的是一个印度姐姐,态度及其不耐烦,而且觉得特别赶时间, 搞得我还挺紧张,我虽然都写出来个差不多,但是估计没戏,给人的感觉是一开始就没打算让你过似得,哎!!!
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-1-30 00:26:30 | 显示全部楼层
这题看起来不错
回复 支持 反对

使用道具 举报

csstudyup234 发表于 2015-2-7 08:08:40 | 显示全部楼层
haiken 发表于 2015-1-25 11:34
如果不用trie, 用个编码简单的DFS,遍历所有的combination 应该也可以把?

void findWords(string &p ...

你这方法不对吧,这题不是让输出所有可能组合。
回复 支持 反对

使用道具 举报

pulpfree009 发表于 2015-2-8 09:29:27 | 显示全部楼层
不就是两个字母吗?需要用trie吗?
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-4-10 05:49:01 | 显示全部楼层
m4reiiy 发表于 2015-1-25 11:40
trie和DFS不如hashmap快。。查找O(1)啊。。

其实LZ还可以用多层hashmap,一般可以省点内存什么的。。

怎么使用多层hashmap?
回复 支持 反对

使用道具 举报

memememe 发表于 2015-4-10 06:30:37 | 显示全部楼层
多谢分享~
回复 支持 反对

使用道具 举报

m4reiiy 发表于 2015-4-11 03:39:01 | 显示全部楼层
mm豆 发表于 2015-4-9 13:49
怎么使用多层hashmap?

比如第一层是首字母,第二层是尾字母,第三层是单词长度-2这样。根据hash function效果不同,通常这样能省更多的内存,不过也更容易写出bug就是了
回复 支持 反对

使用道具 举报

dwl1222 发表于 2015-4-11 04:57:21 | 显示全部楼层
我有点看不懂你们想怎么写。这题不是很简单。
List<String> find(String s, String[] L) {. 鍥磋鎴戜滑@1point 3 acres
        List<String> res = new ArrayList<>();
        for ( String l : L) {
                if (isValid(s, l)) {
                        res.add(l);
                }
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
       
        return res;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}. visit 1point3acres.com for more.
boolean isValid (String s, String l) {
    if (l.length() < 2) {
            return false;.1point3acres缃
        }
        String convert = s.charAt(0) + String.valueOf(s.length() - 2) + s.charAt(s.length() - 1);. Waral 鍗氬鏈夋洿澶氭枃绔,
        return s.equals(convert); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}
回复 支持 反对

使用道具 举报

swx1031 发表于 2015-4-11 05:49:29 | 显示全部楼层
请问lz这题用tree的思路是什么呀。没想明白
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-4-11 06:52:35 | 显示全部楼层
m4reiiy 发表于 2015-4-11 03:39
比如第一层是首字母,第二层是尾字母,第三层是单词长度-2这样。根据hash function效果不同,通常这样能 ...

好厉害!这个方法很聪明。有人说他follow up了一下把abbr升级了一下,比如localise  -》 l2al1s1如何去找。这样出了trie 还有其他办法么?
回复 支持 反对

使用道具 举报

m4reiiy 发表于 2015-4-12 03:47:53 | 显示全部楼层
mm豆 发表于 2015-4-10 14:52-google 1point3acres
好厉害!这个方法很聪明。有人说他follow up了一下把abbr升级了一下,比如localise  -》 l2al1s1如何去找 ...

如果目标是解决这个扩展问题的话应该trie比较万能,直接在trie上BFS+pruning应该就够快了。
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-4-13 00:33:20 | 显示全部楼层
m4reiiy 发表于 2015-4-12 03:47.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果目标是解决这个扩展问题的话应该trie比较万能,直接在trie上BFS+pruning应该就够快了。

明白了,谢谢~~~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 06:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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