狗家onsite面经

感谢楼主 T T 这几题真的太硬核了

匿名者 发表于 2021-4-7 23:49
请问线段那题有什么技巧吗

可以用TreeSet做, 内部存一个线段

分享一个简单的encode的办法replace(#,##) 用_#_来当delimiter 这样原本的_#_变成了_##_ 不会和delimiter冲突 split的时候就用_#_ 还原的时候replace(##,#)

hjldtc 发表于 2021-4-12 04:10
分享一个简单的encode的办法replace(#,##) 用_#_来当delimiter 这样原本的_#_变成了_##_ 不会和delimiter冲 ...

点赞, 有道理. 这题还有几个Corner case需要注意一下, node.val = null, node.val = "" 还有node = null 这三个得能区分出来

匿名者 发表于 2021-4-8 12:45
是的Trie 存字典, 然后dfs下去, 和 word 一起算dp, 因为下一层dp只和上一层dp有关, 所以可以传一个dp arr ...

我的基本思路就是用“\” 做escape。 你说的转义符，是不是就是找一些不需要escape的sign， 用这些sign加escape去表示这几个特殊的？
比如 ：
“” -> \s
value null -> \n

大概这样

p1

1. def kclose(lst, wd, k):
   
2. #build dict
   
3. dit = collections.defaultdict(set)
   
4. for w in last:
   
5.    for i in range(len(w)):
      
   
6.       k = w[0:i]+’*’+w[i+1:]
   
7.       dit[k].add(w)
   
8. 
   
9. stk = [wd]
   
10. res = set()
    
11. res.add(wd)
    
12. while stk and k:
    
13.         k -=1
    
14.         l = len(stk)
    
15.         for i in range(l):
            
    
16.             p = stk.pop(0)
    
17.              # find all one hop neighbors     
    
18.             for j in range(len(p)):
               
    
19.                t= w[0:j]+’*’+w[j+1:]
    
20.                for w in dit[t]:
    
21.                   if w not in res:                                                stk.append(w)
    
22.                     res.add(w)      
    
23.                   
    
24. return list(res)
    

复制代码

麻烦问一下楼主，第一题里的edit distance是什么意思，只能修改字符吗 还是说增删改都可以。所以的单词长度都是一样的吗

Gligfdyjfrtfds 发表于 2021-4-24 01:33
麻烦问一下楼主，第一题里的edit distance是什么意思，只能修改字符吗 还是说增删改都可以。所以的单词长度 ...

估计就是leetcode上的编辑距离那道题吧。。。

楼主这些题有点吓人啊

是真的难。。。



1. Design一个 auto spell-correction: 讨论下来, 面试官想给我一个Collection<String> dictionary 表示字典, 让我设计一个数据结构, 实现一个API :  List<String> findKClosest(String word, int k) : 返回字典里所有的距离 word 的 edit distance <= k 的单词, 单词按照edit distance排序, 如果edit distance相同, 按照alphabetical排序
可以Trie + DFS + DP + TreeSet 实现  
priority_queue<pair<int,string>, vector<pair<int,string>>, greater<pair<int,string>>> pq = {};
vector<string> findKClosest(string word, int k, vector<string> words){
        TrieNode* root;
        for(string s:words)
                insert(root,s);

        TrieNode* p = root;
        dfs(word,0,p,0,k);

        vector<string> res = {};
        while(!pq.empty()){
                res.push_back(pq.top().second);
                pq.pop();
        }
        return res;
}

void dfs(string word, int idx, Trie* p, int ED, int k){
        if(idx == word.size()){
                pq.push({ED,word});
                return;
        }

        // not change
        if(p->next[word[idx]-'a'])
                dfs(word,idx+1,p->next[word[idx]-'a'],ED,k);

        // if change
        string tmp = word;
        for(int i=0; i<26; ++i){
                if(p->next[i] && word[idx]!= (char)('a'+i) && ED+1<=k){
                        tmp[idx] = (char)('a'+i);
                        dfs(tmp,idx+1,p->next[tmp[idx]],ED+1,k);
                        tmp = word;
                }
        }

}


2. LC 57 + LC 1272 推广: design 一个数据结构, 支持三个api: add(int start, int end), remove(int start, int end), isExist(int start, int end):  能往这个数据结构里add 线段, remove 线段, 可以query某个线段是不是被现在数据结构里include 比如: add(1, 3)  add (2, 5)  add(7, 9) add(15, 20) 这时候内部有这样的线段 [1, 5] [7, 9] [15, 20], isExist(2,3): true  isExist(4, 6) false. 如果remove(4, 8) 内部的线段 [1,3] [9, 9] [15, 20]
        715

3. Serialize/Deserialize Binary Tree: 但是面试官说 TreeNode 的 field是String, 可以是任意String. 我本来想用"," 间隔, 但面试官说val就可以是逗号, 并且可以任意Unicode组成的String, 任何我想拿来当分隔符的符号, 都可以是val

TreeNode {
     String val;
     TreeNode left, right;
}  
我想到的可以用转义符解决, "," 表示逗号  "\," 表示分隔符,   "\\" 才表示 \

class Codec {
public:
    string serialize(TreeNode* root) {
        ostringstream out;
        serialize(root, out);
        return out.str();
    }

    TreeNode* deserialize(string data) {
        istringstream in(data);
        return deserialize(in);
    }

private:
    void serialize(TreeNode* root, ostringstream& out) {
        if (root) {
            string tmp = root->val;
            if(!tmp) out << "_*_" << "_#_";
            else if(tmp == "") out << "_%_" << "_#_";
            else{
                int i = 0;
                while(i<tmp.size() && (tmp.find("#") || tmp.find("$") || tmp.find("*") || tmp.find("%") )){
                    if(tmp[i] == "#") {tmp.replace(i,1,"# #");i+=2;}
                    else if(tmp[i] == "$") {tmp.replace(i,1,"$ $");i+=2;}
                    else if(tmp[i] == "*") {tmp.replace(i,1,"* *");i+=2;}
                    else if(tmp[i] == "%") {tmp.replace(i,1,"% %");i+=2;}
                    i++;
                }
                out << tmp << "_#_";
            }
            serialize(root->left, out);
            serialize(root->right, out);
        } else {
            out << "_$_" << "_#_";
        }
    }

    TreeNode* deserialize(istringstream& in) {
        string tmp;
        getline(in,tmp,"_#_");
        TreeNode* root = nullptr;
        if (tmp != "_$_"){
            string val = NULL;
            if(tmp == "_%_") val = "";
            else {
                int i = 0;
                while(i<tmp.size()-2 && (tmp.find("# #") || tmp.find("$ $") || tmp.find("* *") || tmp.find("% %") )){
                    if(tmp.substr(i,3) == "# #") tmp.replace(i,3,"#");
                    else if(tmp.substr(i,3) == "$ $") tmp.replace(i,3,"$");
                    else if(tmp.substr(i,3) == "* *") tmp.replace(i,3,"*");
                    else if(tmp.substr(i,3) == "% %") tmp.replace(i,3,"%");
                    i++;
                }
                val = tmp;
            }
            root = new TreeNode(val);
            root->left = deserialize(in);
            root->right = deserialize(in);
        }
        return root;
    }
};
       

有一轮面试: 问了一个House Robber(LC 198)的二维推广版, 就是给一个 n x m 2d array, 每个位置代表房子的金额 >= 0, 如果偷了一个房子, 则周围八个房子都不能偷, 问能偷到的最大金额是多少?  
        X 1349