推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

Snapchat 电面.10分钟以前

[复制链接] |试试Instant~ |关注本帖
弱视个体 发表于 2016-11-3 05:34:55 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 全职@Snapchat - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
本来很有信心,后来刷面经才觉得snapchat bar很高.后悔投早了.幸好面试官是个华人大哥,特别nice.感激~~~~~~~~~~.鐣欏璁哄潧-涓浜-涓夊垎鍦
刚开始聊了挺久的,why snapchat and personal experience.
码码的时候有点紧张,出了一些小bug,好在最后都跑出来了.

上题:
. more info on 1point3acres.com
public List<String> solution (char[] array, List<String> dic) {}

输出任意字符组合成的在字典里的所有String.

我一开始说用一个set + dfs, 他说输入很多怎么办,比如说100,0000...

然后就是用Trie + dfs.磕磕碰碰最后跑完. 希望有onsite...


.鐣欏璁哄潧-涓浜-涓夊垎鍦补充内容 (2016-11-3 05:36):
char[] 里面有重复字符,但不能重复利用. 比如说'A', 'A' ...  可以输出"A", "AA"

补充内容 (2016-11-3 08:25):
举个例子: char[] array = {'A', 'B', 'C', 'A'}, List<String> = {"A","AA","BA"};  正确的输出: "A", "AA","BA";   非法输出:"AAA","BB","AB"........

评分

2

查看全部评分

本帖被以下淘专辑推荐:

shoppinglee 发表于 2016-12-21 15:23:48 | 显示全部楼层
贴个代码。

  1. public class WordSearch {
  2.     public List<String> findWord(char[] array, List<String> dict) {
  3.         int[] table = new int[256];
  4.         for (char c : array) {
  5.             table[c]++;
  6.         }
  7. . 1point3acres.com/bbs
  8.         List<String> result = new ArrayList<>();
  9.         for (String s : dict) {
  10.             Map<Character, Integer> map = new HashMap<>();. more info on 1point3acres.com
  11.             boolean found = true;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.             for (int i = 0; i < s.length(); ++i) {
    . 1point 3acres 璁哄潧
  13.                 char c = s.charAt(i);
  14.                 map.put(c, map.getOrDefault(c, 0) + 1);
  15.                 if (map.get(c) > table[c]) {
  16.                     found = false;
  17.                     break;. from: 1point3acres.com/bbs
  18.                 }
  19.             }
  20.             if (found) result.add(s);
  21.         }

  22.         return result;
  23.     }

  24.     public static void main(String[] args) {
  25.         char[] array = {'A', 'B', 'C', 'A'};
  26.         List<String> dict = Arrays.asList("AA", "BB", "A", "BA");
  27.         WordSearch wordSearch = new WordSearch();
  28.         List<String> result = wordSearch.findWord(array, dict);. from: 1point3acres.com/bbs
  29.         for (String s : result) {
  30.             System.out.println(s);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  31.         }
  32.     }
  33. }
复制代码
回复 支持 1 反对 0

使用道具 举报

glad2mu 发表于 2016-12-14 02:58:11 | 显示全部楼层
是不是用trie 来存储词典然后用dfs 搜索这个trie. 碰到isend to true 加到结果里 然后继续向下找。 用hashset记录字母count和使用次数。
回复 支持 1 反对 0

使用道具 举报

 楼主| 弱视个体 发表于 2016-11-3 05:36:16 | 显示全部楼层
char[] 里面有重复字符,但不能重复利用. 比如说'A', 'A' ...  可以输出"A", "AA"
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-11-3 05:45:42 | 显示全部楼层
是dict里的字符很多还是array里的字符很多?
回复 支持 反对

使用道具 举报

 楼主| 弱视个体 发表于 2016-11-3 05:58:55 | 显示全部楼层
csushin1992 发表于 2016-11-3 05:45
是dict里的字符很多还是array里的字符很多?

dic吧
字符字符字符
回复 支持 反对

使用道具 举报

31415926 发表于 2016-11-3 07:05:22 | 显示全部楼层
求解答。。
题目是这样吗? 每个字符用一次,用完所有字符,看字典里面有多少个string 匹配,并输出? -> 这样的输出结果应该不唯一吧
还是其他啥意思?  
回复 支持 反对

使用道具 举报

Liuology 发表于 2016-11-3 07:11:33 | 显示全部楼层
不太明白题目意思啊,楼主举个例子说明以下
回复 支持 反对

使用道具 举报

nycowboy 发表于 2016-11-3 07:17:46 | 显示全部楼层
这题好像之前看到过的一个谷歌的onsite题,那题是给出lists of words,然后一个字符stream,求当前能找到的words。
回复 支持 反对

使用道具 举报

Toby 发表于 2016-11-3 07:32:28 | 显示全部楼层
求问字符组合中字符的顺序是否要和array中一样?
回复 支持 反对

使用道具 举报

vesalius 发表于 2016-11-3 07:35:36 | 显示全部楼层
word search II?
回复 支持 反对

使用道具 举报

 楼主| 弱视个体 发表于 2016-11-3 08:21:08 | 显示全部楼层
vesalius 发表于 2016-11-3 07:35 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
word search II?

不一样的.这个是一位字符串,可以任意顺序.
回复 支持 反对

使用道具 举报

 楼主| 弱视个体 发表于 2016-11-3 08:22:00 | 显示全部楼层
31415926 发表于 2016-11-3 07:05
求解答。。
题目是这样吗? 每个字符用一次,用完所有字符,看字典里面有多少个string 匹配,并输出? ->  ...

dfs + backTracking + Trie 可以输出所有结果
回复 支持 反对

使用道具 举报

 楼主| 弱视个体 发表于 2016-11-3 08:23:08 | 显示全部楼层
举个例子: char[] array = {'A', 'B', 'C', 'A'}, List<String> = {"A","AA","BA"};
回复 支持 反对

使用道具 举报

 楼主| 弱视个体 发表于 2016-11-3 08:24:52 | 显示全部楼层

举个例子: char[] array = {'A', 'B', 'A'}, List<String> = {"A","AA","BA","CA"};
正确的输出: "A", "AA","BA". 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
非法输出:"AAA","BB","AB"........
回复 支持 反对

使用道具 举报

31415926 发表于 2016-11-3 08:33:21 | 显示全部楼层
弱视个体 发表于 2016-11-3 08:22
dfs + backTracking + Trie 可以输出所有结果

那倒是。。 每个解是一个 字典子集,是可以把所有这样的子集输出。
但是,怎么用trie 做,感觉这题就像一个背包。。. visit 1point3acres.com for more.
. 鍥磋鎴戜滑@1point 3 acres
比如,字母集合 [5*a, 3*b, 55*c] , 字典儿 [ [a*2 b*2], [a*1 b*1 c*1], [c*5], [a*5] ]
求教 trie 咋做。。。
回复 支持 反对

使用道具 举报

flashpacker 发表于 2016-11-3 08:35:30 | 显示全部楼层
这题DFS+TRIE是可以解的吧。。?就算很大tire也可以handle的
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-11-3 08:38:48 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

31415926 发表于 2016-11-3 08:57:57 | 显示全部楼层
弱视个体 发表于 2016-11-3 08:24
举个例子: char[] array = {'A', 'B', 'A'}, List = {"A","AA","BA","CA"};
正确的输出: "A", "AA","BA" ...

... 为啥感觉,字母集大于单词。。 就可以输出了。。.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主能再帮我理解下吗,感觉一直没上道。。
回复 支持 反对

使用道具 举报

 楼主| 弱视个体 发表于 2016-11-3 10:18:20 | 显示全部楼层
31415926 发表于 2016-11-3 08:57
... 为啥感觉,字母集大于单词。。 就可以输出了。。
楼主能再帮我理解下吗,感觉一直没上道。。

你这种解法也可以的.
回复 支持 反对

使用道具 举报

Camel_Yan 发表于 2016-11-3 13:16:42 | 显示全部楼层
lz 是用set去重的吗,backtracking的时候可能得到重复的"AA"(第一个char和第四个char,顺序相反)
回复 支持 反对

使用道具 举报

 楼主| 弱视个体 发表于 2016-11-3 22:09:51 | 显示全部楼层
Camel_Yan 发表于 2016-11-3 13:16
lz 是用set去重的吗,backtracking的时候可能得到重复的"AA"(第一个char和第四个char,顺序相反)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
可以用个set,也可以backtracking路上,把trieNode 里的boolean 取反
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-20 12:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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