[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 13716|回复: 78
收起左侧

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

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

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

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

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

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

下面还原题目:

word abbreviation

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

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

output: l2e god internal me i8t interval inte9n f2e intr9n. visit 1point3acres for more.

(注意: 输出的时候要按照 输入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. visit 1point3acres for more.
2. 再次遍历数组,对于每个string,在tries里查找,返回对应的compressed string,具体步骤为:
(1)找出分叉节点数(这里用变量numOfChildren表示)大于1的最后一个trie node
(2)根据(1)中找出的node获取compressed string,并和原来的长度进行比较,返回最终结果

. from: 1point3acres
代码输出结果:


l4e god internal me i8t interval inte9n f4e intr9n
interval internal inta8l . 围观我们@1point 3 acres
aaa



import java.util.*;
. From 1point 3acres bbs
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) {
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);. from: 1point3acres
            if(root.children[c - 'a'] == null) {
                root.numOfChildren++;
                root.children[c - 'a'] = new TrieNode();
            }. 1point3acres
            root = root.children[c - 'a'];
        }
    }

    public String search(String word, TrieNode root) {
-google 1point3acres        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;. visit 1point3acres for more.
            if (i == word.length() - 1 && node == root) {.1point3acres网
                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
            }
. Waral 博客有更多文章,            tmp = tmp.children[c - 'a'];
        }. From 1point 3acres bbs


        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (root != node) {
                sb.append(c);
. 围观我们@1point 3 acres
                root = root.children[c - 'a'];.1point3acres网
            }
            else {
                sb.append(c);.本文原创自1point3acres论坛
                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));
        }

        for (String word: strs) {. visit 1point3acres for more.
            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();
. 围观我们@1point 3 acres
        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();. 留学申请论坛-一亩三分地
. 1point 3acres 论坛
        arr = new String[]{"aaa"};.1point3acres网
        t.abbreviation(arr);
        System.out.println();

    }
}
. From 1point 3acres bbs
来源一亩.三分地论坛.

补充内容 (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
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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

        public TrieNode() {. 1point3acres
            isWord = false;
            children = new TrieNode[26];
            wordsCount = 0;
        }
    }

    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) {
            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'];.本文原创自1point3acres论坛
        }
        curNode.isWord = true;
    }. 一亩-三分-地,独家发布

    public String compressWord(String _word) {
        TrieNode curNode = root;
        char[] word = _word.toCharArray();
        StringBuilder result = new StringBuilder();
        
        for (int i = 0; i < word.length; ++i) {. more info on 1point3acres
            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) {.本文原创自1point3acres论坛
        TrieTree t = new TrieTree();.本文原创自1point3acres论坛
        t.addWord("intension");
        t.addWord("intrusion");
        System.out.println(t.compressWord("intension"));
    }. Waral 博客有更多文章,
}
.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>
  4. #include <string>

  5. .1point3acres网
  6. using namespace std;
  7. . more info on 1point3acres
  8. class TrieNode{
  9. public:
  10.         int count;
  11.         unordered_map<char,TrieNode*> children;
  12.         TrieNode(int cnt):count(cnt){};
  13. };

  14. class Solution {
  15. public:
  16.         void addWord(TrieNode *root, string& str, int pos){
  17.                 if(pos==str.length()){. from: 1point3acres
  18.                         return;.1point3acres网
  19.                 }
  20.                 char ch = str[pos];
  21.                 if(root->children.find(ch)==root->children.end()){
    . 牛人云集,一亩三分地
  22.                         root->children[ch] = new TrieNode(1);
  23.                 } else {
  24.                         root->children[ch]->count++;
  25.                 }
  26.                 addWord(root->children[ch],str,pos+1);
  27.         }

  28.         void findAbbrev(TrieNode *root, string& str, string& path, int pos){. 1point3acres
  29.                 int n = str.length();
  30.                 if(pos>=n-3){
  31.                         path += str.substr(pos);
  32.                         return;
  33.                 }
  34.                 char ch = str[pos];
  35.                 if(root->children[ch]->count == 1){-google 1point3acres
  36.                         path += ch + to_string(n) + str[n-1];
  37.                 } else {. 留学申请论坛-一亩三分地
  38.                         path += ch;
  39.                         findAbbrev(root->children[ch],str,path,pos+1);
  40.                 }.留学论坛-一亩-三分地
  41.         }

  42.         vector<string> compressWord(vector<string>& strs){
  43.                 unordered_map<string,TrieNode*> mapTrie;
  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()){. Waral 博客有更多文章,
  50.                                 TrieNode *newNode = new TrieNode(0);
  51.                                 mapTrie[index] = newNode;. 1point3acres
  52.                         }
  53.                         addWord(mapTrie[index],str,0);
  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 {. visit 1point3acres for more.
  63.                                 result.push_back(str);
  64.                         }
  65.                 }
  66.                 return result;
  67.         }

  68. };
  69. . 留学申请论坛-一亩三分地
  70. int main(int argc, char** argv) {
  71.     . visit 1point3acres for more.
  72.     Solution su;
  73.     vector<string> words{"like", "god"  ,"internal", "me", "internet" ,"interval" ,"intension", "face", "intrusion"};
  74.     vector<string> res = su.compressWord(words);

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

  79. }
复制代码

回复 支持 反对

使用道具 举报

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.本文原创自1point3acres论坛
可以多说些 corner case 吗?
. visit 1point3acres for more.
当时被问的是要设计一个数据结构, 而不是算法.. 1point 3acres 论坛

数据结构里要有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. Waral 博客有更多文章,
当时被问的是要设计一个数据结构, 而不是算法.

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

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-25 15:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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