Snapchat OA

You have solved 20/ 24 problems.

Show problem tags

Problem 1: word abbreviation

题意:

我们通常压缩的时候会把 interval 压缩成 i8l, 即首尾字母加这个word的长度。

1. 但是研究人员发现，internal 和 interval 如果按上面那种方法就会模糊不清，因为都会压缩成 i8l. 于是研究人员就想到一个办法，就是加长它们的prefix, 直到遇到它们第一个不同的字母， 比如：internal 和 interval 会压缩成： intern8l, interv8l. intension 和 intrusion 会变成： inte9n, intr9n
2. 当 压缩完后， 发现压缩后的长度 大于等于 原始长度时， 保留原始长度。比如 intern8l 长度也是 8， 那么就 保留原始： internal.

(例子我自己举的， 大概这意思)

• input: like god internal me internet interval intension face intrusion
• output: l4e god internal me i8t interval inte9n f4e intr9n

(注意： 输出的时候要按照 输入string 的顺序， 顺序不能变)。

version: cpp

#include <map>
#include <string>
#include <vector>
#include <iostream>
using namespace std;

class TrieNode {
public:
    int count;
    TrieNode* children[26];
    TrieNode(): count(0) {
        for (auto &a:children) a = NULL;
    }
};


class Solution {
private:
    void insert(TrieNode *p, string word) {
        for (auto &c:word) {
            int i = c-'a';
            if (!p->children[i]) p->children[i] = new TrieNode();
            ++p->children[i]->count;
            p = p->children[i];
        }
    }
    string search(TrieNode *p, string word) {
        string prefix;
        for (auto c:word) {
            int i = c-'a';
            p = p->children[i];
            prefix += c;
            if (p->count == 1) {
                return prefix;
            }
        }
        return prefix;
    }
public:

    vector<string> EncodeStr(vector<string> words){
        map<int, TrieNode*> m;
        for (auto &word:words) {
            word = word.back()+word;
            int len = word.size();
            if (m.count(len) == 0) m[len] = new TrieNode();
            insert(m[len], word);
        }
        vector<string> res(words.size());
        int i = 0;
        for (auto word:words) {
            int len = word.size();
            string prefix = search(m[len], word);
            string abbr;
            if (prefix.size() > 1) {
                abbr = prefix.substr(1);
            } else {
                abbr = word[1];
            }

            abbr += to_string(len-1) + word[len-1];
            res[i++] = (abbr.size() < len-1) ? abbr:word.substr(1);
        }
        return res;
    }

};

int main () {
    vector<string> ipt = {"like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"};
    Solution test;
    vector<string> rst = test.EncodeStr(ipt);
    for (auto &abbr:rst) {
        cout << abbr << " ";
    }
    cout << "\nDone!\n";
    return 0;
}

version: java

import java.util.*;

public class WordAbbr {
    public class TriNode {
        TriNode[] children;
        boolean isWord;
        int wordsCnt;
        public TriNode(){
            this.children = new TriNode[26];
            this.isWord = false;
            this.wordsCnt = 0;
        }
    }

    public String[] EncodeStr(String[] ipt){
        Map<String, TriNode> map = new HashMap<>();

        //build trie for input string
        for(String ea : ipt){
            int len = ea.length();
            String ptn = ""+ea.charAt(0)+len+ea.charAt(len-1);
            if(!map.containsKey(ptn)){
                TriNode crt = new TriNode();
                map.put(ptn,crt);
            }
            addToTrie(ea,map.get(ptn));
        }

        String[] rst = new String[ipt.length];
        //check for validation and start encoding
        for(int i=0;i<ipt.length;i++){
            int len = ipt[i].length();
            String ptn = ""+ipt[i].charAt(0)+len+ipt[i].charAt(len-1);
            TriNode root = map.get(ptn);
            String prefix = findPrefix(ipt[i],root);
            rst[i] = prefix.length()+2<len ? ""+prefix+len+ipt[i].charAt(len-1) : ipt[i];
        }
        return rst;
    }

    private void addToTrie(String s, TriNode root){
        TriNode idx = root;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(idx.children[c-'a']==null)
                idx.children[c-'a'] = new TriNode();
            idx = idx.children[c-'a'];
            idx.wordsCnt++;
        }
        idx.isWord = true;
    }

    private String findPrefix(String s, TriNode root){
        StringBuilder prefix = new StringBuilder();
        TriNode idx = root;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            idx = idx.children[c-'a'];
            prefix.append(c);
            if(idx.wordsCnt==1) return prefix.toString();
        }
        return prefix.toString();
    }
    public static void main(String[] args) {
        String[] ipt = {"like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"};
        WordAbbr test = new WordAbbr();
        String[] rst = test.EncodeStr(ipt);
        System.out.println(Arrays.toString(rst));
    }

}

Problem 2: Valid Sudoku

Problem 3: Simple Words

#include <string>
#include <vector>
#include <unordered_set>
#include <iostream>
using namespace std;

class Solution {
    bool isCompound(string word, unordered_set<string> &dict) {
        if (word.size() == 0) return false;
        vector<bool> dp(word.size()+1, false);
        dp[0] = true;
        for (int i = 1; i <= word.size(); ++i) { // word length
            for (int j = 0; j < i; ++j) {
                if (dp[j] && dict.count(word.substr(j,i-j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[word.size()];
    }
public:
    vector<string> simpleWords(vector<string>& words) {
        vector<string> res;
        unordered_set<string> dict;
        for (auto &word: words) {
            dict.insert(word);
        }
        for (auto &word: words) {
            dict.erase(word);
            if (!isCompound(word, dict)) res.push_back(word);
            dict.insert(word);
        }
        return res;
    }
};

int main() {
    vector<string> input = {"chat", "ever",  "snapchat" ,"snap", "salesperson" ,"per", "person", "sales" ,"son" ,"whatsoever" ,"what", "so", ""};
    Solution test;
    vector<string> result = test.simpleWords(input);
    for (auto &s : result) {
        cout << "result: " << s << endl;
    }
    return 0;
}