San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3629|回复: 22
收起左侧

补一个狗家店面跪经

[复制链接] |试试Instant~ |关注本帖
uranus23 发表于 2016-9-18 08:36:16 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类General 硕士 全职@Google - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x

周二面的,估计跪了,发上来攒点人品吧。.留学论坛-一亩-三分地
电话迟了5分多钟,上来就做题,没任何介绍。

“用过Eclipse吗?”
“用过”
“实现下Eclipse里的Camel-Case Search吧”

. from: 1point3acres
比如有一个Set里面有如下单词:FooBar, FootBall, FooToo, FiBa
Input a pattern, return all the words that match the pattern, e.g.
"F" should return "FooBar", "FootBall", "FooToo", "FiBa"
"FB" should return "FooBar", "FootBall", "FiBa"
"FT" should return "FooToo"
"FoBa" should return "FooBar", "FootBall"
"FBa" should renturn "FooBar", "FootBall", "FiBa" 来源一亩.三分地论坛.
"FiB" should return "FiBa"
. more info on 1point3acres

大概是要用Trie做,然而并没写出来,只写了个优化版的brute force

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 459, 订阅: 123
hxtang 发表于 2016-9-18 11:30:46 | 显示全部楼层
uranus23 发表于 2016-9-18 11:13
写错了,不用全出现,但出现的必须按顺序match前几个,不能跳

感觉就是和LC211类似办法,碰到小写字母就是往下走一层,碰到大写字母的时候在子树下面递归search。.1point3acres网
回复 支持 1 反对 0

使用道具 举报

domofeng 发表于 2016-9-18 09:06:58 | 显示全部楼层
感觉是分两情况:

1. Trie build 所有的word, 然后根据 search for prefix, 穷举这一条路径上的所有单词。
2. 把UPCASE 单独处理, 放到一个Map<String, List<String>> 里面。 .本文原创自1point3acres论坛

其实我感觉都应该放到Map<String, List<String>> 中去, 这样子查询速度更快。
回复 支持 反对

使用道具 举报

pinkdatura 发表于 2016-9-18 09:24:27 | 显示全部楼层
谢谢楼主~bless
请问关于建立trie树的话,是不是一般的trie树呢还是有些改造呢, 大写和小写字母在carmel case的区别
比如FO可以match FoG类似这类吗 那Fo可以match FO吗,我的理解是大写必须都出现并且match上,小写可以match大写和小写,谢谢指教~. 牛人云集,一亩三分地
                    F
                  /  \
                o   
               /       i
              o      
            /   \      /. visit 1point3acres for more.
           T    B
           /    |
来源一亩.三分地论坛.           o      a
          /      /  \. From 1point 3acres bbs
        o      r      l. 留学申请论坛-一亩三分地
                       \.留学论坛-一亩-三分地
                       l
回复 支持 反对

使用道具 举报

 楼主| uranus23 发表于 2016-9-18 10:47:57 | 显示全部楼层
pinkdatura 发表于 2016-9-17 20:24
谢谢楼主~bless
请问关于建立trie树的话,是不是一般的trie树呢还是有些改造呢, 大写和小写字母在carmel  ...
. 留学申请论坛-一亩三分地
“FO可以match FoG类似这类吗” 不可以
“Fo可以match FO吗” 不可以
“我的理解是大写必须都出现并且match上” Yes
“小写可以match大写和小写” 只能match小写

补充内容 (2016-9-17 22:12):
“我的理解是大写必须都出现并且match上” No..不必全出现,但出现过的要按顺序match
回复 支持 反对

使用道具 举报

 楼主| uranus23 发表于 2016-9-18 10:52:46 | 显示全部楼层
domofeng 发表于 2016-9-17 20:06
感觉是分两情况:

1. Trie build 所有的word, 然后根据 search for prefix, 穷举这一条路径上的所有单 ...

能给个第二种情况的例子吗?没太看懂
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-18 11:02:59 | 显示全部楼层
uranus23 发表于 2016-9-18 10:47. From 1point 3acres bbs
“FO可以match FoG类似这类吗” 不可以
“Fo可以match FO吗” 不可以
“我的理解是大写必须都出现并且m ...

大写是必须都出现都match上吗?
第一个query是“F”的例子似乎并不符合这个原则啊..
或者说大写如果是部分必须是前几个,不能跳?
回复 支持 反对

使用道具 举报

 楼主| uranus23 发表于 2016-9-18 11:13:59 | 显示全部楼层
hxtang 发表于 2016-9-17 22:02. 留学申请论坛-一亩三分地
大写是必须都出现都match上吗?
第一个query是“F”的例子似乎并不符合这个原则啊..
或者说大写如果是 ...

写错了,不用全出现,但出现的必须按顺序match前几个,不能跳
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| uranus23 发表于 2016-9-18 12:55:24 | 显示全部楼层
hxtang 发表于 2016-9-17 22:30
感觉就是和LC211类似办法,碰到小写字母就是往下走一层,碰到大写字母的时候在子树下面递归search。

对,我想到了但没来得及写。。
回复 支持 反对

使用道具 举报

xytan123 发表于 2016-9-18 14:13:32 | 显示全部楼层
http://www.geeksforgeeks.org/print-words-matching-pattern-camelcase-notation-dictonary/
回复 支持 反对

使用道具 举报

xytan123 发表于 2016-9-18 14:59:51 | 显示全部楼层
按照上面的思路,可以做一下改变
FooBar, FootBall, FooToo, FiBa 形成的trie 是这样的
             root
         F /
        (Foo, Fi)
    B /         T\   
   (FooBar     (FooToo)  
    FootBall
    FiBa)
search的时候,先把input 按照camel case 分成 “Fo” "Ba", 在每一层遍历startWith, 一直到找到。
其实就是把普通Trie一个字母一个字母匹配,变成一个单词一个单词匹配(startWith)。
话说电面就问这种难度,真是强人所难
-google 1point3acres
补充内容 (2016-9-18 15:07):
不对,我说错了。如果是FoB,在叶子层没法扫描。。。可以每一层存成分开的单词组unordered_set,然后挨个遍历startWith
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-18 20:56:47 | 显示全部楼层
xytan123 发表于 2016-9-18 14:13
http://www.geeksforgeeks.org/print-words-matching-pattern-camelcase-notation-dictonary/
来源一亩.三分地论坛.
geeksforgeeks的这个要容易很多,就是把单词压缩成大写,然后对大写表示建trie就好了
但是这个题因为会出现部分小写所以会很麻烦,比如你11楼给的例子,如果query是FiT,那么应该什么都搜不到,所以不能把Foo和Fi放在一个结点里。
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-18 20:58:44 | 显示全部楼层
uranus23 发表于 2016-9-18 12:55
对,我想到了但没来得及写。。

如果是三四十分钟里要想还要从头到底写,不太可能写完。
不过如果来得及说思路的话,也许不一定会跪。G好像比较在乎思路,不太在乎code写完了没
回复 支持 反对

使用道具 举报

dydcfg 发表于 2016-9-18 22:24:46 | 显示全部楼层
给每个TrieNode加一条指向下一个可能的大写字母的指针就可以了.本文原创自1point3acres论坛

class TrieNode{
unordered_map<char,TrieNode*> nextChar;
unordered_map<char,TrieNode*> nextUpperChar;
string words;
};
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-9-19 01:31:35 | 显示全部楼层
有点疑惑这题为什么要分大小写呢?不是字符都要match吗
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-19 03:42:30 | 显示全部楼层
hxtang 发表于 2016-9-18 20:58
如果是三四十分钟里要想还要从头到底写,不太可能写完。
不过如果来得及说思路的话,也许不一定会跪。G ...

贴一个我写的实现。其实不难,核心就是两个*_recur函数,但是确实觉得电面那点时间连写带讲太不现实了,哪怕做过。. from: 1point3acres

#include <iostream>
#include <cctype>
#include <vector>
#include <string>
using namespace std;. 1point3acres

class CamelSearchEng {

    struct Node { //trie node
        //lazy impl. for children, ideally would only allocate space for alphabetical chars
        Node* children[256] = { nullptr }; 来源一亩.三分地论坛.
        bool is_word = false; 来源一亩.三分地论坛.

        ~Node() { . 留学申请论坛-一亩三分地
            for (int k = 0; k < 256; ++k) delete children[k];
        }
    };
. 围观我们@1point 3 acres
    Node* root;

public:
    //allocate trie
    CamelSearchEng(vector<string> words) {
        root = new Node;
        for (const string& word : words) {
            Node* t = root; 来源一亩.三分地论坛.
            for (char c : word) {
                if (t->children[c] == nullptr) t->children[c] = new Node;
                t = t->children[c];
            }
            t->is_word = true;
        }
    };
. Waral 博客有更多文章,
    // deallocate trie
    ~CamelSearchEng() {
        delete root;
    };
. 牛人云集,一亩三分地
    // search CamelPattern
    vector<string> search(const string& pattern) const {
        vector<string> result;.留学论坛-一亩-三分地
        string word;
        search_recur(pattern, 0, root, word, result);. more info on 1point3acres
        return result;
    }

    void append_words_recur(Node* t, string& word, vector<string>& result) const {
        if (t->is_word) result.push_back(word);
        for (char c = 'a'; c <= 'z'; ++c) {
            if (t->children[c]) {. 牛人云集,一亩三分地
                word.push_back(c);
                append_words_recur(t->children[c], word, result);
                word.pop_back();. 牛人云集,一亩三分地
            }
        }
        for (char c = 'A'; c <= 'Z'; ++c) {
            if (t->children[c]) {
                word.push_back(c);
                append_words_recur(t->children[c], word, result);
                word.pop_back();
            }.留学论坛-一亩-三分地
        }
    }.留学论坛-一亩-三分地

    void search_recur(const string& pattern, int first, Node* t, string& word, vector<string>& result) const {
. 牛人云集,一亩三分地        size_t word_len = word.size();
        while (first < pattern.size() && islower(pattern[first]) && t) {. Waral 博客有更多文章,
            t = t->children[pattern[first]];
            word.push_back(pattern[first]);. more info on 1point3acres
            ++first;
        }
        if (t == nullptr) {//no match
            ; //stop searching
        }
        else if (first == pattern.size()) { //found a matched prefix
            append_words_recur(t, word, result); //append all words under t
        }
        else { //pattern[first] is upper. visit 1point3acres for more.
            char c = pattern[first];
            for (int ch = 'a'; ch <= 'z'; ++ch) {
                if (t->children[ch]) search_recur(pattern, first, t->children[ch], word, result);.1point3acres网
            }
            if (t->children[c]) {
                word.push_back(c);
                search_recur(pattern, first+1, t->children[c], word, result);
            }
        }

        //restore word for back tracing
        word.resize(word_len);
    }-google 1point3acres
};.1point3acres网

void test(const CamelSearchEng& eng, const string& query) {
    cout << "query: " << query << endl;
    vector<string> result = eng.search(query);
    for (const string& str: result) cout << str << " ";
    cout << endl << endl;
}

int main() {
    vector<string> dictionary{"FooBar", "FootBall", "FooToo", "FiBa"};
    CamelSearchEng eng(dictionary);. 围观我们@1point 3 acres
    test(eng, "F");. From 1point 3acres bbs
    test(eng, "FB");. 一亩-三分-地,独家发布
    test(eng, "FT");
    test(eng, "FoBa");
    test(eng, "FBa");
    test(eng, "FiB");
    return 0;   
}
. more info on 1point3acres



.留学论坛-一亩-三分地
补充内容 (2016-9-19 03:45):
写构造函数API的时候脑残了传了vector<string>,应该传const vector<string>&的
不过不影响正确性
回复 支持 反对

使用道具 举报

omega094 发表于 2016-9-19 04:18:41 | 显示全部楼层
感谢楼主分享。。。
电面给这个题感觉有点重口啊。。。。。
回复 支持 反对

使用道具 举报

xytan123 发表于 2016-9-19 04:48:53 | 显示全部楼层
hxtang 发表于 2016-9-19 03:42
贴一个我写的实现。其实不难,核心就是两个*_recur函数,但是确实觉得电面那点时间连写带讲太不现实了, ...

挺难的。你的代码我读了好几遍...
难点在于,Trie是普通一个字母一个字母的结构,如果不完全match 了一段,就迎来下一个大写,怎样找到下一个大写的在trie里的位置。你的方法是遍历所有当前Trie Node 小写孩子,强迫前进。这样的话,如果是完全match了一段,比如,query('FooBaC') -->'FooBarCar',  其中'Foo'可以完全match , 我依旧要遍历所有第二个'o'下面的所有小写孩子 before starting to match 'B'。这个太难转过弯...
. from: 1point3acres
我想可不可以一个node包含一个group starting with the same Uppercase character, 然后这个group里面的成员再分别指向下一个camel case

补充内容 (2016-9-19 04:53):
class TrieNode {
    string word;. 1point3acres
    unordered_map<char, vetor<TrieNode>>children;
}

补充内容 (2016-9-19 04:57):
                     root. 围观我们@1point 3 acres
                   /      
       (Foo,     Foot ,     Fi)   
        /                \       \
(Bar, Ball) (Too)   (Ball)   (Bar)
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-19 05:58:02 | 显示全部楼层
xytan123 发表于 2016-9-19 04:48
挺难的。你的代码我读了好几遍...
难点在于,Trie是普通一个字母一个字母的结构,如果不完全match 了一 ...

你说的这个想法我想过,我的主要顾虑是空间开销。vector<TrieNode>可能会非常大。. 一亩-三分-地,独家发布
. 留学申请论坛-一亩三分地
另外一个原因我没有信心在二三十分钟里写完这个数据结构。虽然search部分的实现逻辑变简单了(其实就差几行code),但构造部分很麻烦,如果TrieNode设计得不好,析构部分也会变复杂,容易出bug(例如你写的数据结构trie children和到下一个大写的shortcut没分开,delete会产生dangling pointer)。标准trie树如果状态好,还是有希望的。
. from: 1point3acres
如果面试官要求优化并且说有的是memory,我可能会提你说的这个idea。因为你指出的优化点是有意义的。
回复 支持 反对

使用道具 举报

pinkdatura 发表于 2016-9-19 10:18:18 | 显示全部楼层
uranus23 发表于 2016-9-18 10:47
“FO可以match FoG类似这类吗” 不可以
“Fo可以match FO吗” 不可以
“我的理解是大写必须都出现并且m ...

谢谢楼主细心解答 关于小写,比如FiB能match FioBoo吗?还有FioB可以match FiiioooBoo, 但是肯定不能match FoiBoo或者FoBoo, FiBoo对吗?
就是比较像regular matching

大写*(0到n次)小写+(1到n次)是吗?这道题关键在于改造trie树,好难啊,狗家最近怎么啦~
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-26 14:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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