May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

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

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
年前内推snapchat后, 昨天收到oa, 随即看面经,以为还是 数独那题。 兴奋的打开oa,发现变了。于是妥妥的跪了!
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
下面还原题目:

word abbreviation

题意:  我们通常压缩的时候会把  interval 压缩成 i8l, 即首尾字母加这个word的长度。
1. 但是研究人员发现, internal 和 interval  如果按上面那种方法就会模糊不清,因为都会压缩成 i8l. 于是研究人员就想到一个办法,就是加长它们的prefix, 直到遇到它们第一个不同的字母,-google 1point3acres
比如:internal 和 interval 会压缩成: intern8l, interv8l.
          intension 和 intrusion  会变成: inte9n, intr9n

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

(例子我自己举的, 大概这意思)
鏉ユ簮涓浜.涓夊垎鍦拌鍧. input: 是一个 string.鏈枃鍘熷垱鑷1point3acres璁哄潧
like god  internal me internet interval intension face intrusion

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面经里看见过
回复 支持 反对

使用道具 举报

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

使用道具 举报

celestial 发表于 2016-1-8 02:51:51 | 显示全部楼层
还是应该用 trie 吧,就是 trie 节点增加一个int 来记录单词以当前前缀作为自己前缀的个数,如果计数器为1的时候,说明只有自己现在这个前缀是唯一的
写了一个 DEMO,比较粗糙,大家借鉴一下. 鍥磋鎴戜滑@1point 3 acres
class TrieTree {
    class TrieNode {
        boolean isWord;
        TrieNode[] children;
        int wordsCount;

        public TrieNode() {
            isWord = false;
            children = new TrieNode[26];. from: 1point3acres.com/bbs
            wordsCount = 0;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        }. 1point3acres.com/bbs
    }.1point3acres缃

    TrieNode root;
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    public TrieTree() {.鐣欏璁哄潧-涓浜-涓夊垎鍦
        root = new TrieNode();
    }

    public void addWord(String _word) {
        char[] word = _word.toCharArray();
        TrieNode curNode = root; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        for (int i = 0; i < word.length; ++i) {.1point3acres缃
            curNode.wordsCount ++;
            if (curNode.children[word-'a'] == null) {
                TrieNode newNode = new TrieNode();
.1point3acres缃                curNode.children[word-'a'] = newNode;
                curNode = newNode;
            } else curNode = curNode.children[word-'a'];
        }
        curNode.isWord = true;
    }. 1point3acres.com/bbs

    public String compressWord(String _word) {
        TrieNode curNode = root;
        char[] word = _word.toCharArray();
        StringBuilder result = new StringBuilder();.1point3acres缃
        .鏈枃鍘熷垱鑷1point3acres璁哄潧
        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);. from: 1point3acres.com/bbs
        } else result.append(word[word.length-2]);
-google 1point3acres        result.append(word[word.length-1]);. 鍥磋鎴戜滑@1point 3 acres
        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"));
    }
}-google 1point3acres

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

使用道具 举报

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

思路是每一个单词都属于一个组,比如 interval 和 interbal 都属于 "i8l" 组。建立一个 组名-> Trie 树根的 unordered_map,然后遍历 dict,把对应的单词加到对应的 Trie 树里。

再遍历一次,每个单词都找到它对应的 Trie 树,然后求出缩写。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>. 鍥磋鎴戜滑@1point 3 acres
  4. #include <string>

  5. using namespace std;
  6. . visit 1point3acres.com for more.
  7. class TrieNode{
  8. public:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.         int count;
  10.         unordered_map<char,TrieNode*> children;. From 1point 3acres bbs
  11.         TrieNode(int cnt):count(cnt){};
  12. };

  13. class Solution {
  14. public:
  15.         void addWord(TrieNode *root, string& str, int pos){
  16.                 if(pos==str.length()){
  17.                         return;
  18.                 }
  19.                 char ch = str[pos];
  20.                 if(root->children.find(ch)==root->children.end()){
  21.                         root->children[ch] = new TrieNode(1);
  22.                 } else {
  23.                         root->children[ch]->count++;
  24.                 }. from: 1point3acres.com/bbs
  25.                 addWord(root->children[ch],str,pos+1);
  26.         }

  27.         void findAbbrev(TrieNode *root, string& str, string& path, int pos){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  28.                 int n = str.length();
  29.                 if(pos>=n-3){
  30.                         path += str.substr(pos);
  31.                         return;
  32.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  33.                 char ch = str[pos];
  34.                 if(root->children[ch]->count == 1){
  35.                         path += ch + to_string(n) + str[n-1];
  36.                 } else {
  37.                         path += ch;
  38.                         findAbbrev(root->children[ch],str,path,pos+1);
  39.                 }
  40.         }. more info on 1point3acres.com
  41. . 1point 3acres 璁哄潧
  42.         vector<string> compressWord(vector<string>& strs){
  43.                 unordered_map<string,TrieNode*> mapTrie;-google 1point3acres
  44.                 for(auto str : strs){
  45.                         if(str.length()<=3){
  46.                                 continue;
  47.                         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  48.                         string index = str[0] + to_string(str.length()) + str.back();
  49.                         if(mapTrie.find(index)==mapTrie.end()){
  50.                                 TrieNode *newNode = new TrieNode(0);
  51.                                 mapTrie[index] = newNode; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  52.                         }
  53.                         addWord(mapTrie[index],str,0);.1point3acres缃
  54.                 }

  55.                 vector<string> result;
  56.                 for(auto str : strs){
  57.                         if(str.length()>3){
  58.                                 string index = str[0] + to_string(str.length()) + str.back();
  59.                                 string path;
  60.                                 findAbbrev(mapTrie[index],str,path,0);
  61.                                 result.push_back(path);
  62.                         } else {
  63.                                 result.push_back(str);
  64.                         }
  65.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  66.                 return result;
  67.         }

  68. };

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

  74.     for(auto s : res){
  75.             cout<<s<<" ";
  76.     }
  77.     cout<<endl;

  78. }
复制代码

回复 支持 反对

使用道具 举报

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 吗?
. from: 1point3acres.com/bbs
当时被问的是要设计一个数据结构, 而不是算法.

数据结构里要有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
当时被问的是要设计一个数据结构, 而不是算法.. 鍥磋鎴戜滑@1point 3 acres

数据结构里要有add和remove两个, 然后你会发现, 同一个 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
弱弱的问问同样的word 不一样是因为add() remove() 会交错这样吗?
回复 支持 反对

使用道具 举报

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

思路是每一个单词都属于一个组,比如 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的 ...

按我的理解如果输入是这几个单词: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. From 1point 3acres bbs
按我的理解如果输入是这几个单词:interval, internal, intaaaal,那压缩结果应该是 interval, internal, ...

对,这里确实有问题,还想问问大神,如果这三个输入的话怎么找到压缩后的前缀啊?还是用trie么?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-26 04:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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