📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 27
跳转到指定楼层
上一主题 下一主题
收起左侧

SNAPCHAT电面挂经

全局:

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

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
题大概是这样,一个INPUT STRING ARRAY1 比如CAT, DOG,一个INPUT STRING ARRAY 2, 比如GAT, D
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
先搜索,但是做来做去都写的不太对,然后果然电面就挂了
求大牛给完整思路和代码

谢了

评分

参与人数 4大米 +41 收起 理由
coldrainy + 5 感谢分享!
fantasiasango + 3 感谢分享!
alucardzhou + 3 感谢分享!
夏虫不知雪花 + 30

查看全部评分


上一篇:coursera OA1面经
下一篇:微软面试是越早越好吗
推荐
xietao0221 2016-9-25 12:01:03 | 只看该作者
全局:
如果不用trie的写了这么一个。用trie的还没想,一会儿想想。
  1. public class Solution {
  2.     private List<List<String>> res = new ArrayList<>();
  3.     private List<String> tmpRes = new ArrayList<>();
  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
  8.         for(String word: input1) {
  9.             for(char c: word.toCharArray()) {
  10.                 charSet[c - 'A']++;
  11.                 charSum++;
  12.             }
  13.         }

  14.         wordSearchHelper(input2, 0, 0);
  15.         return res;
  16.     }

  17.     private void wordSearchHelper(String[] input2, int pos, int count) {
  18.         if(count > charSum) return;

  19.         if(count == charSum) {
  20.             int[] tmpCharSum = Arrays.copyOf(charSet, 26);
  21.             for(String word: tmpRes) {
  22.                 for(char c: word.toCharArray()) {
  23.                     if (--tmpCharSum[c - 'A'] < 0) return;
  24.                 }
  25.             }
  26.             res.add(new ArrayList<>(tmpRes));
  27.             return;
  28.         }

  29.         for(int i = pos; i < input2.length; i++) {
  30.             tmpRes.add(input2[i]);
  31.             wordSearchHelper(input2, i + 1, count + input2[i].length());
  32.             tmpRes.remove(tmpRes.size() - 1);
  33.         }
  34.     }
  35. }
复制代码

评分

参与人数 2大米 +15 收起 理由
高渐离击筑高歌 + 5 给你点个赞!
忆梦前尘 + 10 回答的很好!

查看全部评分

回复

使用道具 举报

全局:
大概写了一个。 要backtrack input2 而不是input1
  1. public List<List<String>> wordSearch (String[] input1, String[] input2) {
  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.                 }
  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) {
  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.         }
复制代码
回复

使用道具 举报

推荐
cicean 2016-9-8 11:53:58 | 只看该作者
全局:
这不是word search two 么?
回复

使用道具 举报

🔗
zmyvszk 2016-9-8 10:59:08 | 只看该作者
全局:
这个题目用Backtracking可以做
回复

使用道具 举报

🔗
hxtang 2016-9-8 11:07:33 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
 楼主| ariesxiao 2016-9-8 11:50:13 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
hxtang 2016-9-8 11:58:16 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
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) {
  7.                                 count[c - 'A']++;
  8.                                 total++;
  9.                         }
  10.                 }
  11.                 vector<string> curr;
  12.                 dfs(input2, 0, 0, curr);
  13.                 return result;
  14.         }

  15.         void dfs(vector<string>& words, int pos, int occ, vector<string>& curr) {
  16.                 if (occ == total) {
  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.                         }
  28.                         if (flag) {
  29.                                 curr.push_back(word);
  30.                                 dfs(words, i + 1, occ, curr);
  31.                                 curr.pop_back();
  32.                         }
  33.                         for (auto c : word) {
  34.                                 count[c - 'A']++;
  35.                                 occ--;
  36.                         }
  37.                 }
  38.         }

  39. private:
  40.         unordered_map<char, int> count;
  41.         vector<vector<string>> result;
  42.         int total;
  43. }
复制代码
回复

使用道具 举报

🔗
maktf 2016-9-8 22:43:40 | 只看该作者
全局:
求问楼主从面完到有消息用了多久啊?而且他家的店面到底是45分钟还是一个小时?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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