一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 10568|回复: 78
收起左侧

人肉试验题! snapchat 最新 oa 题,写跪了。

  [复制链接] |试试Instant~ |关注本帖
269644943 发表于 2016-1-7 16:53:52 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Snapchat - 内推 - 在线笔试 |Failfresh grad应届毕业生

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

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

x
年前内推snapchat后, 昨天收到oa, 随即看面经,以为还是 数独那题。 兴奋的打开oa,发现变了。于是妥妥的跪了!

下面还原题目:
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
word abbreviation
. 1point3acres.com/bbs
题意:  我们通常压缩的时候会把  interval 压缩成 i8l, 即首尾字母加这个word的长度。
1. 但是研究人员发现, internal 和 interval  如果按上面那种方法就会模糊不清,因为都会压缩成 i8l. 于是研究人员就想到一个办法,就是加长它们的prefix, 直到遇到它们第一个不同的字母,
比如:internal 和 interval 会压缩成: intern8l, interv8l.
          intension 和 intrusion  会变成: inte9n, intr9n

2. 当 压缩完后, 发现压缩后的长度 大于等于 原始长度时, 保留原始长度。比如 intern8l  长度也是 8, 那么就 保留原始: internal.

(例子我自己举的, 大概这意思)
input: 是一个 string
like god  internal me internet interval intension face intrusion-google 1point3acres

output: l2e god internal me i8t interval inte9n f2e intr9n

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

评分

12

查看全部评分

flyaway25 发表于 2016-1-8 01:45:53 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
我也遇到了,妥妥的跪了。一开始理解错踢了,不应该对所有的都建trie,感觉应该只是对所有首字母和尾字母相同的单词去建trie,得到每一个string的prefix然后再压缩后半部分,其他直接按照正常压缩然后比较长度就可以了。
回复 支持 2 反对 0

使用道具 举报

 楼主| 269644943 发表于 2016-2-4 05:12:44 | 显示全部楼层
关注一亩三分地微博:
Warald
yang2640 发表于 2016-2-4 04:00
为什么internet能被压缩成i8t ?  internet 和 internal 不是有common prefix吗,为什么还能被压缩,求解答 ...

因为internal 和 interval 压缩后是 i8l,  internet压缩后是 i8t,   i8l 和 i8t 不一样,所以可以压缩。但是internal 和 interval都压缩成i8l,这就出问题了,所以要考虑他们的prefix.
回复 支持 1 反对 0

使用道具 举报

 楼主| 269644943 发表于 2016-1-7 16:57:24 | 显示全部楼层
我是没做出来,
首先一个问题,就是输出的时候顺序不知道如何保持。
再一个问题就是: 当遇到第一个时,先压缩。 然后遇到个压缩相同的,那么原来那个压缩的就得变。 如果继续遇到第三个相同的,又继续得变

实在是不知道怎么做
回复 支持 反对

使用道具 举报

vesalius 发表于 2016-1-7 20:10:58 | 显示全部楼层
这题是leetcode上那个不,我好像在一个google面经里看见过
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

haifengc 发表于 2016-1-8 01:25:06 | 显示全部楼层
感觉应该先对所有的string建一个tire
回复 支持 反对

使用道具 举报

celestial 发表于 2016-1-8 02:51:51 | 显示全部楼层
还是应该用 trie 吧,就是 trie 节点增加一个int 来记录单词以当前前缀作为自己前缀的个数,如果计数器为1的时候,说明只有自己现在这个前缀是唯一的
写了一个 DEMO,比较粗糙,大家借鉴一下
class TrieTree {. 1point3acres.com/bbs
    class TrieNode {
        boolean isWord;
        TrieNode[] children;
        int wordsCount;
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        public TrieNode() {
            isWord = false;
            children = new TrieNode[26];
            wordsCount = 0;
        }
    }

    TrieNode root;
. more info on 1point3acres.com
    public TrieTree() {
        root = new TrieNode();
    }

    public void addWord(String _word) {
        char[] word = _word.toCharArray();
        TrieNode curNode = root;. more info on 1point3acres.com
        for (int i = 0; i < word.length; ++i) {
            curNode.wordsCount ++;
            if (curNode.children[word-'a'] == null) {
                TrieNode newNode = new TrieNode();
                curNode.children[word-'a'] = newNode;
                curNode = newNode;
            } else curNode = curNode.children[word-'a'];
        }
        curNode.isWord = true;
    }

    public String compressWord(String _word) {
. 鍥磋鎴戜滑@1point 3 acres        TrieNode curNode = root;
        char[] word = _word.toCharArray();
        StringBuilder result = new StringBuilder();
        
        for (int i = 0; i < word.length; ++i) {
            curNode = curNode.children[word-'a'];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            result.append(word);
            if (curNode.wordsCount < 2) break;
        }
        if (result.length() < word.length - 2) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            result.append(word.length);
        } else result.append(word[word.length-2]);
        result.append(word[word.length-1]);
        return result.toString();
    }
.鐣欏璁哄潧-涓浜-涓夊垎鍦
    public static void main(String[] args) {
        TrieTree t = new TrieTree();
        t.addWord("intension");
        t.addWord("intrusion");. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        System.out.println(t.compressWord("intension"));
    }
}

补充内容 (2016-1-8 03:07):
上面的代码还有 bug,大家就当是一个思路就好
回复 支持 反对

使用道具 举报

Gianluigi 发表于 2016-1-8 10:11:45 | 显示全部楼层
感谢 lz 分享新 OA。我大概写了一下,如果有 bug 请大家指出。.1point3acres缃
. visit 1point3acres.com for more.
思路是每一个单词都属于一个组,比如 interval 和 interbal 都属于 "i8l" 组。建立一个 组名-> Trie 树根的 unordered_map,然后遍历 dict,把对应的单词加到对应的 Trie 树里。

再遍历一次,每个单词都找到它对应的 Trie 树,然后求出缩写。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  4. #include <string>

  5. using namespace std;

  6. class TrieNode{
  7. public:. from: 1point3acres.com/bbs
  8.         int count;
  9.         unordered_map<char,TrieNode*> children;. Waral 鍗氬鏈夋洿澶氭枃绔,
  10.         TrieNode(int cnt):count(cnt){};
  11. };

  12. class Solution {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13. public:
  14.         void addWord(TrieNode *root, string& str, int pos){
  15.                 if(pos==str.length()){
  16.                         return;
  17.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  18.                 char ch = str[pos];
  19.                 if(root->children.find(ch)==root->children.end()){
  20.                         root->children[ch] = new TrieNode(1);
  21.                 } else {
  22.                         root->children[ch]->count++;
  23.                 }
  24.                 addWord(root->children[ch],str,pos+1);
  25.         }

  26.         void findAbbrev(TrieNode *root, string& str, string& path, int pos){
  27.                 int n = str.length();
  28.                 if(pos>=n-3){
  29.                         path += str.substr(pos);
  30.                         return;
  31.                 }
  32.                 char ch = str[pos];
  33.                 if(root->children[ch]->count == 1){
  34.                         path += ch + to_string(n) + str[n-1];. 鍥磋鎴戜滑@1point 3 acres
  35.                 } else {
  36.                         path += ch;
  37.                         findAbbrev(root->children[ch],str,path,pos+1);
  38.                 }
  39.         }

  40.         vector<string> compressWord(vector<string>& strs){
  41.                 unordered_map<string,TrieNode*> mapTrie;
  42.                 for(auto str : strs){. 1point 3acres 璁哄潧
  43.                         if(str.length()<=3){
  44.                                 continue;
  45.                         }
  46.                         string index = str[0] + to_string(str.length()) + str.back();
  47.                         if(mapTrie.find(index)==mapTrie.end()){
  48.                                 TrieNode *newNode = new TrieNode(0);
  49.                                 mapTrie[index] = newNode;. 鍥磋鎴戜滑@1point 3 acres
  50.                         }. 鍥磋鎴戜滑@1point 3 acres
  51.                         addWord(mapTrie[index],str,0);
  52.                 }

  53.                 vector<string> result;. 1point3acres.com/bbs
  54.                 for(auto str : strs){
  55.                         if(str.length()>3){
  56.                                 string index = str[0] + to_string(str.length()) + str.back();
  57.                                 string path;
  58.                                 findAbbrev(mapTrie[index],str,path,0);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  59.                                 result.push_back(path);
  60.                         } else {
  61.                                 result.push_back(str);
  62.                         }
  63.                 }
  64.                 return result;
  65.         }

  66. };

  67. int main(int argc, char** argv) {
  68.    
  69.     Solution su;.1point3acres缃
  70.     vector<string> words{"like", "god"  ,"internal", "me", "internet" ,"interval" ,"intension", "face", "intrusion"};
  71.     vector<string> res = su.compressWord(words);

  72.     for(auto s : res){
  73.             cout<<s<<" ";.鐣欏璁哄潧-涓浜-涓夊垎鍦
  74.     }-google 1point3acres
  75.     cout<<endl;

  76. }
复制代码

回复 支持 反对

使用道具 举报

readman 发表于 2016-1-8 10:17:15 | 显示全部楼层
- - 题是我加面g家实习的原题...好多陷阱...
回复 支持 反对

使用道具 举报

Gianluigi 发表于 2016-1-8 10:18:44 | 显示全部楼层
readman 发表于 2016-1-8 10:17
- - 题是我加面g家实习的原题...好多陷阱...

可以多说些 corner case 吗?
回复 支持 反对

使用道具 举报

 楼主| 269644943 发表于 2016-1-8 16:29:32 | 显示全部楼层
flyaway25 发表于 2016-1-8 01:45
我也遇到了,妥妥的跪了。一开始理解错踢了,不应该对所有的都建trie,感觉应该只是对所有首字母和尾字母相 ...

你也没做出来吗?
回复 支持 反对

使用道具 举报

wcyz666 发表于 2016-1-8 16:45:06 | 显示全部楼层
怎么Snapchat OA变这么难了。。。?从easy突然变成了hard
回复 支持 反对

使用道具 举报

readman 发表于 2016-1-8 22:33:39 | 显示全部楼层
Gianluigi 发表于 2016-1-8 10:18
可以多说些 corner case 吗?

当时被问的是要设计一个数据结构, 而不是算法.

数据结构里要有add和remove两个, 然后你会发现, 同一个word在添加顺序不同的时候, 会被压缩成不同的结果..最后好像是一个HashMap<word,ab> + Trie 做的 但是没调出来
回复 支持 反对

使用道具 举报

Gianluigi 发表于 2016-1-9 00:12:46 | 显示全部楼层
readman 发表于 2016-1-8 22:33
当时被问的是要设计一个数据结构, 而不是算法.

数据结构里要有add和remove两个, 然后你会发现, 同一个 ...

多谢!

如果要有 remove,还要写一个函数把一个单词从 Trie 里删掉。

这样的题如果第一次在面试里遇到,真是妥妥的跪啊。
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-9 06:57:45 | 显示全部楼层
readman 发表于 2016-1-8 22:33. visit 1point3acres.com for more.
当时被问的是要设计一个数据结构, 而不是算法.. From 1point 3acres bbs

数据结构里要有add和remove两个, 然后你会发现, 同一个 ...

弱弱的问问同样的word 不一样是因为add() remove() 会交错这样吗?
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-9 07:04:20 | 显示全部楼层
Gianluigi 发表于 2016-1-8 10:11
感谢 lz 分享新 OA。我大概写了一下,如果有 bug 请大家指出。

思路是每一个单词都属于一个组,比如 int ...

想讨论这个case string order is[internal, interval] internal 因压缩后没有帮助所以用原本的string , 假设dictionary 只有两个word 为什么interval 不能压成i8l 呢? 坐等大神...
回复 支持 反对

使用道具 举报

迪克斯特拉 发表于 2016-1-10 08:47:48 | 显示全部楼层
有一个想法,感觉不用trie也行。建一个map,key是正常的首尾加长度的压缩,value是拥有同样的key的string的longest common prefix。这样先遍历一遍输入的所有单词建立map,然后再遍历一遍输入的所有单词,现在已经有longest common prefix了,所以再对每个单词进行一遍针对prefix的压缩就行了。我觉得这道题是一次输入所有的单词,然后一起压缩,得到输出。而不是像提供api那样,要写add(), compress()这样。不知道理解的对不对。。。
回复 支持 反对

使用道具 举报

majiamajia 发表于 2016-1-10 10:07:07 | 显示全部楼层
我去。。。这题就是我ONSITE题目。。。
回复 支持 反对

使用道具 举报

地里小马甲 发表于 2016-1-10 10:27:26 | 显示全部楼层
majiamajia 发表于 2016-1-10 10:07
我去。。。这题就是我ONSITE题目。。。

(⊙﹏⊙)b
回复 支持 反对

使用道具 举报

celestial 发表于 2016-1-10 10:44:09 | 显示全部楼层
迪克斯特拉 发表于 2016-1-10 08:47
有一个想法,感觉不用trie也行。建一个map,key是正常的首尾加长度的压缩,value是拥有同样的key的string的 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
按我的理解如果输入是这几个单词:interval, internal, intaaaal,那压缩结果应该是 interval, internal, inta8l 吧。
如果按你的方法,这三个单词在 map 里面是同一个 key (i8l), longest common prefix 应该是 int。那压缩结果就变成了 inte8l, inte8l, inta8l?
回复 支持 反对

使用道具 举报

迪克斯特拉 发表于 2016-1-10 10:50:08 | 显示全部楼层
celestial 发表于 2016-1-10 10:44
. 1point 3acres 璁哄潧按我的理解如果输入是这几个单词:interval, internal, intaaaal,那压缩结果应该是 interval, internal, ...
. 1point3acres.com/bbs
对,这里确实有问题,还想问问大神,如果这三个输入的话怎么找到压缩后的前缀啊?还是用trie么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-29 11:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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