《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 13107|回复: 78
收起左侧

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

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

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

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

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

x
年前内推snapchat后, 昨天收到oa, 随即看面经,以为还是 数独那题。 兴奋的打开oa,发现变了。于是妥妥的跪了!. Waral 鍗氬鏈夋洿澶氭枃绔,

下面还原题目:

word abbreviation

题意:  我们通常压缩的时候会把  interval 压缩成 i8l, 即首尾字母加这个word的长度。 . from: 1point3acres.com/bbs
1. 但是研究人员发现,
游客,本帖隐藏的内容需要积分高于 155 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

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

output: l2e god internal me i8t interval inte9n f2e intr9n

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

评分

12

查看全部评分

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

使用道具 举报

gjxwin 发表于 2016-1-13 16:21:01 | 显示全部楼层
根据21楼的思路,lz写了下代码,欢迎大家讨论指正:基本思路:
定义hashmap,key是原先的compressed string,比如 interval, internal, intaaaal 都是 i8l,value是每个string对应的tries
1. 遍历string数组,构造对应的tries
2. 再次遍历数组,对于每个string,在tries里查找,返回对应的compressed string,具体步骤为:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
(1)找出分叉节点数(这里用变量numOfChildren表示)大于1的最后一个trie node
(2)根据(1)中找出的node获取compressed string,并和原来的长度进行比较,返回最终结果


代码输出结果:


l4e god internal me i8t interval inte9n f4e intr9n . Waral 鍗氬鏈夋洿澶氭枃绔,
interval internal inta8l
aaa



import java.util.*;

class TrieNode {
    public int numOfChildren;
    public TrieNode[] children = new TrieNode[26];
    public TrieNode() {}
}


public class test { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    private HashMap<String, TrieNode> h = new HashMap<String, TrieNode>();

    public void insert(String word, TrieNode root) {. 1point 3acres 璁哄潧
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(root.children[c - 'a'] == null) {. visit 1point3acres.com for more.
                root.numOfChildren++;
                root.children[c - 'a'] = new TrieNode();
            }
            root = root.children[c - 'a'];
        }
    }
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    public String search(String word, TrieNode root) {
        TrieNode tmp = root;
        TrieNode node = tmp;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (tmp.numOfChildren > 1) node = tmp;
            if (i == word.length() - 1 && node == root) {
                String compressed = "" + word.charAt(0) + word.length() + word.charAt(word.length() - 1);
                if (compressed.length() >= word.length()) return word;
                else return compressed;. more info on 1point3acres.com
            }
            tmp = tmp.children[c - 'a'];
        }


        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);.鐣欏璁哄潧-涓浜-涓夊垎鍦
            if (root != node) {
                sb.append(c);
                root = root.children[c - 'a'];
            }
            else {
                sb.append(c);
                break;
            }
        }
        String compressed = sb.toString() + word.length() + word.charAt(word.length() - 1);

        return compressed.length() >= word.length() ? word : compressed;
    }

    public void abbreviation(String[] strs) {
        for (String word: strs) {
            String compressed = "" + word.charAt(0) + word.length() + word.charAt(word.length() - 1);
            if (!h.containsKey(compressed)) h.put(compressed, new TrieNode());
            insert(word, h.get(compressed));. visit 1point3acres.com for more.
        }

        for (String word: strs) {
            String compressed = "" + word.charAt(0) + word.length() + word.charAt(word.length() - 1);
            System.out.print(search(word, h.get(compressed)) + " ");
        }
    }
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

    public static void main(String[] args) {
        test t = new test();

        String[] arr = new String[]{"like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"};
        t.abbreviation(arr);
        System.out.println(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
.1point3acres缃
        arr = new String[]{"interval", "internal", "intaaaal"};
        t.abbreviation(arr);
        System.out.println();. From 1point 3acres bbs

        arr = new String[]{"aaa"};
        t.abbreviation(arr);
        System.out.println();

    }
}
. Waral 鍗氬鏈夋洿澶氭枃绔,


补充内容 (2016-1-14 04:44):
刚刚做完他家OA,我投的intern,还是数独那道题
回复 支持 1 反对 0

使用道具 举报

celestial 发表于 2016-1-10 11:01:27 | 显示全部楼层
迪克斯特拉 发表于 2016-1-10 10:50
对,这里确实有问题,还想问问大神,如果这三个输入的话怎么找到压缩后的前缀啊?还是用trie么?

刚刚发现我之前也弄错了题意。。
你可以这样考虑 interval, internal, intaaaal 都是 i8l。
你就先建立一个 map,map 的 key 是 i8l,value 是 i8l 所对应的 trie 树,树的建立方法我之前的代码可以参考~
这样先遍历一下数组,把 map 建立起来。再遍历一下数组,求出对应的 compressString
回复 支持 1 反对 0

使用道具 举报

 楼主| 269644943 发表于 2016-2-4 05:12:44 | 显示全部楼层
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 | 显示全部楼层
我是没做出来,
首先一个问题,就是输出的时候顺序不知道如何保持。.鏈枃鍘熷垱鑷1point3acres璁哄潧
再一个问题就是: 当遇到第一个时,先压缩。 然后遇到个压缩相同的,那么原来那个压缩的就得变。 如果继续遇到第三个相同的,又继续得变

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

使用道具 举报

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的时候,说明只有自己现在这个前缀是唯一的. visit 1point3acres.com for more.
写了一个 DEMO,比较粗糙,大家借鉴一下-google 1point3acres
class TrieTree {
    class TrieNode {
        boolean isWord;
        TrieNode[] children;
        int wordsCount;. 鍥磋鎴戜滑@1point 3 acres

        public TrieNode() {. 1point3acres.com/bbs
            isWord = false;.鐣欏璁哄潧-涓浜-涓夊垎鍦
            children = new TrieNode[26];
            wordsCount = 0;
        }
    }

    TrieNode root;

    public TrieTree() {
        root = new TrieNode();
    }
. 1point3acres.com/bbs
    public void addWord(String _word) {. more info on 1point3acres.com
        char[] word = _word.toCharArray();
        TrieNode curNode = root;. From 1point 3acres bbs
        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;. 鍥磋鎴戜滑@1point 3 acres
    }-google 1point3acres

    public String compressWord(String _word) {
        TrieNode curNode = root;
        char[] word = _word.toCharArray();
        StringBuilder result = new StringBuilder();. 鍥磋鎴戜滑@1point 3 acres
        
        for (int i = 0; i < word.length; ++i) {
            curNode = curNode.children[word-'a'];
            result.append(word);. 1point3acres.com/bbs
            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"));
    }.鏈枃鍘熷垱鑷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 树里。. 1point 3acres 璁哄潧

再遍历一次,每个单词都找到它对应的 Trie 树,然后求出缩写。

  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <string>. 1point3acres.com/bbs

  5. using namespace std;

  6. class TrieNode{. more info on 1point3acres.com
  7. public:
  8.         int count;
  9.         unordered_map<char,TrieNode*> children;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  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.                 }
  18.                 char ch = str[pos];. Waral 鍗氬鏈夋洿澶氭枃绔,
  19.                 if(root->children.find(ch)==root->children.end()){
  20.                         root->children[ch] = new TrieNode(1);
  21.                 } else {
  22.                         root->children[ch]->count++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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];
  35.                 } else {
  36.                         path += ch;
  37.                         findAbbrev(root->children[ch],str,path,pos+1);
  38.                 }
  39.         }

  40. . 1point3acres.com/bbs
  41.         vector<string> compressWord(vector<string>& strs){
  42.                 unordered_map<string,TrieNode*> mapTrie;
  43.                 for(auto str : strs){
  44.                         if(str.length()<=3){
  45.                                 continue;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  46.                         }
  47.                         string index = str[0] + to_string(str.length()) + str.back();
  48.                         if(mapTrie.find(index)==mapTrie.end()){
  49.                                 TrieNode *newNode = new TrieNode(0);
  50.                                 mapTrie[index] = newNode;
  51.                         }
  52.                         addWord(mapTrie[index],str,0);
  53.                 }

  54.                 vector<string> result;
  55.                 for(auto str : strs){
  56.                         if(str.length()>3){
  57.                                 string index = str[0] + to_string(str.length()) + str.back();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  58.                                 string path;
  59.                                 findAbbrev(mapTrie[index],str,path,0);
  60.                                 result.push_back(path);
  61.                         } else {
  62.                                 result.push_back(str);
  63.                         }
  64.                 }
  65.                 return result;
  66.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  67. };

  68. int main(int argc, char** argv) {. 鍥磋鎴戜滑@1point 3 acres
  69.     .鏈枃鍘熷垱鑷1point3acres璁哄潧
  70.     Solution su;-google 1point3acres
  71.     vector<string> words{"like", "god"  ,"internal", "me", "internet" ,"interval" ,"intension", "face", "intrusion"};
  72.     vector<string> res = su.compressWord(words);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  73. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  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.1point3acres缃
- - 题是我加面g家实习的原题...好多陷阱...
.1point3acres缃
可以多说些 corner case 吗?
回复 支持 反对

使用道具 举报

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

使用道具 举报

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
当时被问的是要设计一个数据结构, 而不是算法.

数据结构里要有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的 ...

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

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-24 22:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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