一亩三分地论坛

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

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

补一个狗家店面跪经

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

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

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

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

x
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
周二面的,估计跪了,发上来攒点人品吧。
电话迟了5分多钟,上来就做题,没任何介绍。

游客,本帖隐藏的内容需要积分高于 150 才可浏览,您当前积分为 0。 查看如何攒积分

. 1point3acres.com/bbs

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

评分

1

查看全部评分

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

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

使用道具 举报

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

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

其实我感觉都应该放到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      
            /   \      /
           T    B
           /    |
          o      a
          /      /  \
        o      r      l
                       \.鐣欏璁哄潧-涓浜-涓夊垎鍦
                       l
回复 支持 反对

使用道具 举报

 楼主| uranus23 发表于 2016-9-18 10:47:57 | 显示全部楼层
pinkdatura 发表于 2016-9-17 20:24
谢谢楼主~bless
请问关于建立trie树的话,是不是一般的trie树呢还是有些改造呢, 大写和小写字母在carmel  ...
. from: 1point3acres.com/bbs
“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. Waral 鍗氬鏈夋洿澶氭枃绔,
感觉是分两情况: . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

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

使用道具 举报

hxtang 发表于 2016-9-18 11:02:59 | 显示全部楼层
uranus23 发表于 2016-9-18 10:47
. Waral 鍗氬鏈夋洿澶氭枃绔,“FO可以match FoG类似这类吗” 不可以
“Fo可以match FO吗” 不可以
“我的理解是大写必须都出现并且m ...

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

使用道具 举报

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

写错了,不用全出现,但出现的必须按顺序match前几个,不能跳
回复 支持 反对

使用道具 举报

 楼主| uranus23 发表于 2016-9-18 12:55:24 | 显示全部楼层
hxtang 发表于 2016-9-17 22:30.鏈枃鍘熷垱鑷1point3acres璁哄潧
感觉就是和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 | 显示全部楼层
按照上面的思路,可以做一下改变-google 1point3acres
FooBar, FootBall, FooToo, FiBa 形成的trie 是这样的
             root 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
         F /
        (Foo, Fi).鐣欏璁哄潧-涓浜-涓夊垎鍦
    B /         T\   
   (FooBar     (FooToo)  .1point3acres缃
    FootBall.鏈枃鍘熷垱鑷1point3acres璁哄潧
    FiBa)
search的时候,先把input 按照camel case 分成 “Fo” "Ba", 在每一层遍历startWith, 一直到找到。
其实就是把普通Trie一个字母一个字母匹配,变成一个单词一个单词匹配(startWith)。
话说电面就问这种难度,真是强人所难. more info on 1point3acres.com

补充内容 (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. 鍥磋鎴戜滑@1point 3 acres
对,我想到了但没来得及写。。
. more info on 1point3acres.com
如果是三四十分钟里要想还要从头到底写,不太可能写完。
不过如果来得及说思路的话,也许不一定会跪。G好像比较在乎思路,不太在乎code写完了没
回复 支持 反对

使用道具 举报

dydcfg 发表于 2016-9-18 22:24:46 | 显示全部楼层
给每个TrieNode加一条指向下一个可能的大写字母的指针就可以了
. 1point 3acres 璁哄潧
class TrieNode{
unordered_map<char,TrieNode*> nextChar;. From 1point 3acres bbs
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. more info on 1point3acres.com
如果是三四十分钟里要想还要从头到底写,不太可能写完。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
不过如果来得及说思路的话,也许不一定会跪。G ...

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

#include <iostream>
#include <cctype>
#include <vector>
#include <string>. 鍥磋鎴戜滑@1point 3 acres
using namespace std;

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;
. visit 1point3acres.com for more.
        ~Node() {
            for (int k = 0; k < 256; ++k) delete children[k];
        }
    };

    Node* root;

public:. 1point 3acres 璁哄潧
    //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;
        }
    };

    // deallocate trie
    ~CamelSearchEng() {. 1point 3acres 璁哄潧
        delete root;
    };

    // search CamelPattern
    vector<string> search(const string& pattern) const {
        vector<string> result;
        string word;. visit 1point3acres.com for more.
        search_recur(pattern, 0, root, word, result);
        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);. visit 1point3acres.com for more.
                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);. From 1point 3acres bbs
                word.pop_back();. 1point 3acres 璁哄潧
            }
        }
    }

    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) {
            t = t->children[pattern[first]];
            word.push_back(pattern[first]);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            ++first;. 鍥磋鎴戜滑@1point 3 acres
        }
        if (t == nullptr) {//no match. 鍥磋鎴戜滑@1point 3 acres
            ; //stop searching
        }
        else if (first == pattern.size()) { //found a matched prefix
            append_words_recur(t, word, result); //append all words under t. 鍥磋鎴戜滑@1point 3 acres
        }
        else { //pattern[first] is upper
            char c = pattern[first];
            for (int ch = 'a'; ch <= 'z'; ++ch) {
                if (t->children[ch]) search_recur(pattern, first, t->children[ch], word, result);
            }
            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);
    }
};
. from: 1point3acres.com/bbs
void test(const CamelSearchEng& eng, const string& query) {. from: 1point3acres.com/bbs
    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);
    test(eng, "F");
    test(eng, "FB");
    test(eng, "FT");.鐣欏璁哄潧-涓浜-涓夊垎鍦
    test(eng, "FoBa"); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    test(eng, "FBa");
    test(eng, "FiB");
    return 0;   
}. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


.鏈枃鍘熷垱鑷1point3acres璁哄潧


补充内容 (2016-9-19 03:45):
写构造函数API的时候脑残了传了vector<string>,应该传const vector<string>&的-google 1point3acres
不过不影响正确性
回复 支持 反对

使用道具 举报

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'。这个太难转过弯.... Waral 鍗氬鏈夋洿澶氭枃绔,

我想可不可以一个node包含一个group starting with the same Uppercase character, 然后这个group里面的成员再分别指向下一个camel case-google 1point3acres

补充内容 (2016-9-19 04:53):
class TrieNode {
    string word;
    unordered_map<char, vetor<TrieNode>>children;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
}

补充内容 (2016-9-19 04:57):
                     root. from: 1point3acres.com/bbs
                   /      
       (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>可能会非常大。.鏈枃鍘熷垱鑷1point3acres璁哄潧

另外一个原因我没有信心在二三十分钟里写完这个数据结构。虽然search部分的实现逻辑变简单了(其实就差几行code),但构造部分很麻烦,如果TrieNode设计得不好,析构部分也会变复杂,容易出bug(例如你写的数据结构trie children和到下一个大写的shortcut没分开,delete会产生dangling pointer)。标准trie树如果状态好,还是有希望的。

如果面试官要求优化并且说有的是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树,好难啊,狗家最近怎么啦~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-16 21:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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