求问两道fb面经题

求问fb的面经题 给定两个压缩表示的vector 比如[(3,2),(4,1),(2,3)] 就是[2, 2, 2, 1, 1, 1, 1, 3, 3]的缩写 现在给你两个这样压缩好的vetcor 让你求和 当两个长度不同的时候 按最小一个的长度算

trie的搜索, 和李口儿妖妖有些不同。搜索返回所有符合wildcard的词
比如
add(“car”)
add(“caw”)
add(“cauw”)
search(“c*w”) 返回 “caw” 和 “cauw”.

还有一道给定 一个字符串和一个切分长度k 比如:
“This is a good day” k=10
切分为:
“This (1/4)”
“is a (2/4)”
“good (3/4)”
“day (4/4)”
也就是说每个切分后面还要带上一个后缀 而且这个后缀还是算长度的 最后返回的切分最小需要多少下

补充内容 (2017-11-12 08:39):
修正一下 第一个不是求和 是求vector点乘

跟原提想法很像 加一些改編

void Main()
{
        var wordDict = new WordDictionary();
        wordDict.AddWord("car");
        wordDict.AddWord("caaw");
        wordDict.AddWord("cauw");
        wordDict.AddWord("cw");
        Console.WriteLine(wordDict.Search("c*w"));
}

public class WordDictionary {
    private TrieNode root;
    
    /** Initialize your data structure here. */
    public WordDictionary() {
        this.root = new TrieNode();
    }
    
    /** Adds a word into the data structure. */
    public void AddWord(string word) {
        TrieNode node = this.root;
        foreach(char c in word) {
            if(!node.ContainsChild(c)) {
                node.SetChild(c, new TrieNode());
            }
            node = node.GetChild(c);
        }
        node.MarkWord();
    }
    
    public HashSet<string> Search(string word) {
                var result = new HashSet<string>();
        Search(word, this.root, "", result);
                return result;
    }
    
    private void Search(string word, TrieNode node, string soFar, HashSet<string> result) {
        if(node == null &amp;&amp; string.IsNullOrEmpty(word)) {
            result.Add(soFar);
                        return;
        }
        
        TrieNode current = node;
        
        for(int i = 0; i < word.Length; i++) {
            char c = word[i];
            if(c != ''*'') {
                // If c != ''*'', regular search
                if(current.ContainsChild(c)){
                                        soFar += c;
                    current = current.GetChild(c);
                } else {
                    return;
                }    
            } else {
                                // Skip the * to check the scenario where * matches nothing
                                Search(word.Substring(i + 1), current, soFar, result);
                        
                // Search for all children
                foreach(var key in current.GetChildrenKeys()) {
                                        //Check if * matches any current char
                    Search(word.Substring(i + 1), current.GetChild(key), soFar + key, result);
                                        
                                        //Check if * matches any current char, and possibly more char later
                                        Search(word.Substring(i), current.GetChild(key), soFar + key, result);
                }
                return;
            }
            
        }
        
                // All chars match, make sure this is a word
         if(current != null &amp;&amp; current.IsWord) {
                         result.Add(soFar);
                 }
    }
}

class TrieNode
{
    private IDictionary<char, TrieNode> children;
    public bool IsWord { get; private set; }
    // Initialize your data structure here.
    public TrieNode()
    {
        this.children = new Dictionary<char, TrieNode>();
    }
    
    public ICollection<char> GetChildrenKeys() {
        return children.Keys;
    }
    
    public bool ContainsChild(char c) {
        return children.ContainsKey(c);
    }
    
    public TrieNode GetChild(char c) {
        return children[c];
    }
    
    public TrieNode SetChild(char c, TrieNode node) {
        return children[c] = node;
    }
    
    public void MarkWord() {
        this.IsWord = true;
    }
}

这是实习题目吗,感觉路子很野啊,第一题可以顺序比较两个vector内的每个tuple的第一位,比如两个(a1, b1), (a2, b2),可以算Min(a1, a2)b1b2,较小的a所在的tuple过掉,较大的a所在的tuple更新a值为Math.abs(a1-a2),然后每一次都这么比较,直到某一个vector到达最后

不确定是不是实习面的 但是说这道题的人是在实习群说的 打印倒是不是主要难点

sorry 理解错题了。这样的话,因为leaf存在才算找到了,那string从后向前,树从下往上,同时开始。如果遇到string里的star,直接从trie的当前层找star前面的字母直到找到为止。search成功的条件就是同时到达最前面。有些corner case需要注意。也不知道对不对,错了的话还请谅解。

听面试人说 考官说这种不够smart…

嗯 我知道这个 我现在是想不通*号匹配任意长度该怎么处理

就是每行的长度除了最后一行 都是k 然后不足的长度用空格补齐 具体规则和text justification 差不多 但是现在后面加了一个(i/n)的后缀 而且这个后缀还要占字符

别人的 别人被面倒了

没有明白 你的意思是在节点额外存单词的后缀?

后两道确实有点野

第二题跟莉蔻add and search解法一样 只不过把在leaf存的boolean换成字符串

"字符串和一个切分长度k "没看懂啊

同没看明白。。关注一下。。这是楼主看的面经还是楼主被面倒的题目?

你看下trie tree的建造就知道了 我说的莉蔻那道题只用search存在与否 所以当add到最后一个字母的时候 将boolean改为true即可…如果你要返回字符串的话 那么当add到最后一个字母的时候 将字符串存在leaf里…