Google电面

报一个Google电面面经。
面试官是印度人，开始给了一组map，问有没有发现什么pattern。
apple -> a3e
teacher -> t5r
Patter

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

建议还是要掌握一下。
两天后收到第二轮电面，估计第一轮面试官不是很满意，需要再面一轮看看。。。。

herotrue 发表于 2015-1-2 12:24
恩恩，我当时也提到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;
}

我有点看不懂你们想怎么写。这题不是很简单。
List<String> find(String s, String[] L) {
        List<String> res = new ArrayList<>();
        for ( String l : L) {
                if (isValid(s, l)) {
                        res.add(l);
                }
        }
       
        return res;
}
boolean isValid (String s, String l) {
    if (l.length() < 2) {
            return false;
        }
        String convert = s.charAt(0) + String.valueOf(s.length() - 2) + s.charAt(s.length() - 1);
        return s.equals(convert);
}

m4reiiy 发表于 2015-4-11 03:39
比如第一层是首字母，第二层是尾字母，第三层是单词长度-2这样。根据hash function效果不同，通常这样能 ...

好厉害！这个方法很聪明。有人说他follow up了一下把abbr升级了一下，比如localise  -》 l2al1s1如何去找。这样出了trie 还有其他办法么？

谢谢楼主分享。
不过我没太明白题意，是说只找符合“Pattern就是首尾字母加中间的长度”这个pattern的word么？

所有的word都有一个对应的缩略形式，题目是给一个缩略形式，找出文件里面所有满足这个缩率形式的word。
例如文件有四个词：apple, peach, orange, pitch
输入是“a3e”，输出就是“apple”；输入是“p3h”, 输出就是“peach”和“pitch”

建个trie比较好吧，返回depth满足条件，首尾字符match的单词

legendava 发表于 2015-1-2 12:17
建个trie比较好吧，返回depth满足条件，首尾字符match的单词

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

trie和DFS不如hashmap快。。查找O(1)啊。。

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

我跟楼主是同一道题，最后又follow up了一下把abbr升级了一下，比如localise  -》 l2al1s1如何去找。面我的是一个印度姐姐，态度及其不耐烦，而且觉得特别赶时间， 搞得我还挺紧张，我虽然都写出来个差不多，但是估计没戏，给人的感觉是一开始就没打算让你过似得，哎！！！

这题看起来不错

haiken 发表于 2015-1-25 11:34
如果不用trie， 用个编码简单的DFS，遍历所有的combination 应该也可以把？

void findWords(string &p ...

你这方法不对吧，这题不是让输出所有可能组合。