一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 3648|回复: 26
收起左侧

SNAPCHAT电面挂经

[复制链接] |试试Instant~ |关注本帖
ariesxiao 发表于 2016-9-8 10:15:27 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Fail在职跳槽

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

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

x
题大概是这样,一个INPUT STRING ARRAY1 比如CAT, DOG,一个INPUT STRING ARRAY 2, 比如GAT, DOC, CD, GOAT, BAD, COOL
要求第一个INPUT ARRAY的字母必须全部用,而且每个字母只能用一次,求其能组合成的INPUT STRING ARRAY2里的单词组合
比如上面这个例子,返回值会是{{GAT, DOC},{CD, GOAT}}

我的做法是建了一个TRIE,然后统计INPUT ARRAY 1中的每个字母的COUNT,想做一个深度优先搜索,但是做来做去都写的不太对,然后果然电面就挂了
求大牛给完整思路和代码
. more info on 1point3acres.com
谢了

评分

4

查看全部评分

xietao0221 发表于 2016-9-25 12:01:03 | 显示全部楼层
如果不用trie的写了这么一个。用trie的还没想,一会儿想想。
  1. public class Solution {
  2.     private List<List<String>> res = new ArrayList<>();. more info on 1point3acres.com
  3.     private List<String> tmpRes = new ArrayList<>();. From 1point 3acres bbs
  4.     private int charSum = 0;
  5.     private int[] charSet = new int[26];
    .鐣欏璁哄潧-涓浜-涓夊垎鍦

  6.     public List<List<String>> wordSearch(String[] input1, String[] input2) {
  7.         // build charSet. visit 1point3acres.com for more.
  8.         for(String word: input1) {
  9.             for(char c: word.toCharArray()) {. 鍥磋鎴戜滑@1point 3 acres
  10.                 charSet[c - 'A']++;
  11.                 charSum++;
  12.             }
  13.         }
  14. . more info on 1point3acres.com
  15.         wordSearchHelper(input2, 0, 0);. 1point 3acres 璁哄潧
  16.         return res;
  17.     }

  18.     private void wordSearchHelper(String[] input2, int pos, int count) {
  19.         if(count > charSum) return;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  20. . 鍥磋鎴戜滑@1point 3 acres
  21.         if(count == charSum) {
  22.             int[] tmpCharSum = Arrays.copyOf(charSet, 26);
  23.             for(String word: tmpRes) {
  24.                 for(char c: word.toCharArray()) {
  25.                     if (--tmpCharSum[c - 'A'] < 0) return;
  26.                 }
  27.             }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  28.             res.add(new ArrayList<>(tmpRes));
  29.             return;
  30.         }

  31.         for(int i = pos; i < input2.length; i++) {
  32.             tmpRes.add(input2[i]);. Waral 鍗氬鏈夋洿澶氭枃绔,
  33.             wordSearchHelper(input2, i + 1, count + input2[i].length());
  34.             tmpRes.remove(tmpRes.size() - 1);
  35.         }. 鍥磋鎴戜滑@1point 3 acres
  36.     }
  37. }
复制代码

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

zmyvszk 发表于 2016-9-8 10:59:08 | 显示全部楼层
这个题目用Backtracking可以做
回复 支持 1 反对 0

使用道具 举报

hxtang 发表于 2016-9-8 11:07:33 | 显示全部楼层
第一个array只有total count是有用信息,数一遍就好了。
第二个array那里可以预处理一下把count先数好,把有字母occurrence大于array 1的total count的那些单词直接扔掉。
然后就类似没有重复的combination sum做个DFS就行了,只是DFS是26个target,combination sum是一个target。

不知道你为什么要建trie,这个问题里完全没有前缀结构啊...
回复 支持 1 反对 0

使用道具 举报

cicean 发表于 2016-9-8 11:53:58 | 显示全部楼层
这不是word search two 么?
回复 支持 0 反对 1

使用道具 举报

 楼主| ariesxiao 发表于 2016-9-8 11:50:13 | 显示全部楼层
hxtang 发表于 2016-9-8 11:07
第一个array只有total count是有用信息,数一遍就好了。
第二个array那里可以预处理一下把count先数好,把 ...

我建立TRIE是因为面试官一直在引导我建TRIE。。他之前跟我说如果INPUT ARRAY 2是不变的,用户CALL我们的API只是不断的给我们INPUT ARRAY 1,然后返回结果
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-8 11:58:16 | 显示全部楼层
ariesxiao 发表于 2016-9-8 11:50
我建立TRIE是因为面试官一直在引导我建TRIE。。他之前跟我说如果INPUT ARRAY 2是不变的,用户CALL我们的A ...

我觉得他的意思是说input array 2因为可能被用多次,所以尽量多做点预处理....预处理不一定是建trie...
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-8 12:20:28 | 显示全部楼层
好题,preprocessing array2得到List<Map<Character, Integer>>,  相当于coins; array1得到Map<Character, Integer> 相当于target; 然后dfs求coins组合
回复 支持 反对

使用道具 举报

droidgps 发表于 2016-9-8 12:46:16 | 显示全部楼层
我的理解是建个HashMap<Character, Integer> map, 先记录string1每个字母出现个数,然后再遍历string2的每个单词,if(map.get(s2.charAt(i))<1)则表示这个单词不符合。我不是很理解为什么要用trie树做,trie树如果是prefix问题还可以,可是这个。。
回复 支持 反对

使用道具 举报

kebugcheck 发表于 2016-9-8 14:04:32 | 显示全部楼层
随手写了一段代码,楼主给出的测试数据是能通过的,其他的没有测过。如果有bug请通知我。
  1. class Solution {
  2. public:
  3.         vector<vector<string>> snapchat(vector<string> input1, vector<string> input2) {
  4.                 total = 0;
  5.                 for (auto s : input1) {
  6.                         for (auto c : s) {. From 1point 3acres bbs
  7.                                 count[c - 'A']++;
  8.                                 total++;
  9.                         }
  10.                 }
  11.                 vector<string> curr;
  12.                 dfs(input2, 0, 0, curr);
  13.                 return result;
  14.         }. visit 1point3acres.com for more.

  15.         void dfs(vector<string>& words, int pos, int occ, vector<string>& curr) {
  16.                 if (occ == total) {-google 1point3acres
  17.                         result.push_back(curr);
  18.                         return;
  19.                 }
  20.                 for (int i = pos; i < words.size(); i++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  21.                         string word = words[i];
  22.                         bool flag = true;
  23.                         for (auto c : word) {
  24.                                 count[c - 'A']--;
  25.                                 if (count[c - 'A'] < 0) flag = false;
  26.                                 occ++;
  27.                         }. From 1point 3acres bbs
  28.                         if (flag) {
  29.                                 curr.push_back(word);
  30.                                 dfs(words, i + 1, occ, curr);.1point3acres缃
  31.                                 curr.pop_back();
  32.                         }
  33.                         for (auto c : word) {
  34.                                 count[c - 'A']++;
  35.                                 occ--;
  36.                         }-google 1point3acres
  37.                 }
  38.         }

  39. private:. 1point3acres.com/bbs
  40.         unordered_map<char, int> count;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  41.         vector<vector<string>> result;
  42.         int total;. visit 1point3acres.com for more.
  43. }
复制代码
回复 支持 反对

使用道具 举报

maktf 发表于 2016-9-8 22:43:40 | 显示全部楼层
求问楼主从面完到有消息用了多久啊?而且他家的店面到底是45分钟还是一个小时?
回复 支持 反对

使用道具 举报

 楼主| ariesxiao 发表于 2016-9-9 05:24:01 | 显示全部楼层
maktf 发表于 2016-9-8 22:43
求问楼主从面完到有消息用了多久啊?而且他家的店面到底是45分钟还是一个小时?

早上面的,下午就有消息了,问了一下内部的朋友,说最近SNAPCHAT在谈IPO,为了防止有人进去混股票,BAR高了很多,ANYWAY,MOVE FORWARD了
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-14 12:33:40 | 显示全部楼层
请问需要考虑顺序吗?输出是list吗?{GAT, DOC} 和 {DOC, GAT} 算几个?
回复 支持 反对

使用道具 举报

todayand 发表于 2016-9-20 08:41:07 | 显示全部楼层
因为顺序不重要,所以可以将INPUT STRING ARRAY 2里的string先sort,建个hashmap存sorted string对应原string
对sorted string建Trie,这样可以方便之后搜索

然后对INPUT STRING ARRAY 1, count each char in it,然后就是dfs找出所有可能组合啦
回复 支持 反对

使用道具 举报

myangelasuka 发表于 2016-9-20 18:45:43 | 显示全部楼层
大概写了一个。 要backtrack input2 而不是input1
  1. public List<List<String>> wordSearch (String[] input1, String[] input2) {. 1point 3acres 璁哄潧
  2.                 /*
  3.                  * 题大概是这样,一个INPUT STRING ARRAY1 比如CAT, DOG,一个INPUT STRING ARRAY 2, 比如GAT, DOC, CD, GOAT, BAD, COOL. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  4.                  * 要求第一个INPUT ARRAY的字母必须全部用,而且每个字母只能用一次,求其能组合成的INPUT STRING ARRAY2里的单词组
  5.                  * 比如上面这个例子,返回值会是{{GAT, DOC},{CD, GOAT}}
  6.                  */
  7.                 //edge cases
  8.                 List<List<String>> ret = new ArrayList<>();
  9.                 StringBuilder input1B = new StringBuilder();
  10.                 for (String s : input1) {
  11.                         char[] arr = s.toCharArray();
  12.                         for (char ch : arr) {
  13.                                 input1B.append(ch);
  14.                         }
  15.                 }-google 1point3acres
  16.                 backtracking (ret, new ArrayList<String>(), 0 ,input1B.toString().toCharArray(), input2);
  17.                 return ret;
  18.         }
  19.        
  20.         private void backtracking (List<List<String>> ret, List<String> temp, int start, char[] input1, String[] input2) {. more info on 1point3acres.com
  21.                 if (isAnagram(input1, temp)) {
  22.                         ret.add(new ArrayList<>(temp));
  23.                 } else {
  24.                         for (int i = start; i < input2.length; i++) {
  25.                                 temp.add(input2[i]);
  26.                                 backtracking (ret, temp, i+1, input1, input2);
  27.                                 temp.remove(temp.size()-1);
  28.                         }
  29.                 }
  30.         }
  31.        
  32.         private boolean isAnagram (char[] str1, List<String> temp) {
  33.                 int[] trie = new int[26];
  34.                 for (char c : str1) {
  35.                         trie[c-'A']++;
  36.                 }
  37.                 for (String s : temp) {
  38.                         for (int i = 0; i < s.length(); i++) {
  39.                                 trie[s.charAt(i)-'A']--;
  40.                         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  41.                 }
  42.                 for (int i : trie) {
  43.                         if (i != 0) return false;
  44.                 }
  45.                 return true;
  46.         }
复制代码
回复 支持 反对

使用道具 举报

白丁117 发表于 2016-9-25 11:00:29 | 显示全部楼层
感觉没必要用trie...dfs + 剪枝可以把 hashmap<char, int> map l取array1 word总长度, 每次l-- int=0时 map.remove(char), l<array2 中word length时,return
想不出啥优化,等大牛>.
回复 支持 反对

使用道具 举报

todayand 发表于 2016-9-25 11:17:38 | 显示全部楼层
白丁117 发表于 2016-9-25 11:00
感觉没必要用trie...dfs + 剪枝可以把 hashmap map l取array1 word总长度, 每次l-- int=0时 map.remove(ch ...

lz说了用trie是因为被要求的,因为input2会被query很多次,trie是个比较合理的数据结构
回复 支持 反对

使用道具 举报

xiaoyehhuang23 发表于 2016-10-9 14:03:14 | 显示全部楼层
如果是给定了input2,并且反复调用API给新的input1,我觉得可以先对input2做各种排列组合,得到一个key value pair,key是组合之后所有出现的字母sort之后的string,value是这个key对应的各种组合。然后每次给一个新的input1,先把input1里所有的字母sort后并成一个string(比如例子里的变成ACDGOT),然后直接去key value pair里找对应的组合就好啦。思想类似于anagram吧
回复 支持 反对

使用道具 举报

freemail165 发表于 2016-10-10 06:13:34 | 显示全部楼层
ariesxiao 发表于 2016-9-8 11:50
我建立TRIE是因为面试官一直在引导我建TRIE。。他之前跟我说如果INPUT ARRAY 2是不变的,用户CALL我们的A ...

我觉得你被误导了,那如果input2也是变化的,怎么做?. Waral 鍗氬鏈夋洿澶氭枃绔,
而且trie不应该用在这个场景,trie的话,字母顺序就固定了,现在这个问题不需要固定
回复 支持 反对

使用道具 举报

freemail165 发表于 2016-10-10 06:18:59 | 显示全部楼层
xiaoyehhuang23 发表于 2016-10-9 14:03
如果是给定了input2,并且反复调用API给新的input1,我觉得可以先对input2做各种排列组合,得到一个key val ...

你说的很简单,但是第二部你怎么做?
你得找到所有可能的key组合,能生成第一个输入的string.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2016-10-10 06:28):. From 1point 3acres bbs
其实就是找第二个数组中所有单词组合,他们包含的字符恰好是第一个数组的全部字符
最直接的办法就是求组合了。 为了提高效率可以提前删掉必要的结果.鏈枃鍘熷垱鑷1point3acres璁哄潧
collections.sort(arr2, ***);  //sort 2nd array by string length
// assuming for each loop, we still need targetLen chars and they are in targetArr
for(int i=start;i<arr.length;i++) {
    if(arr2.length()>targetLen) break; // no need for longer string.鐣欏璁哄潧-涓浜-涓夊垎鍦
    // if arr2 contains sth not in targetArr, continue...
   Helper(i++,arr2,targetLen-arr2.length(), ......
}.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 23:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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