一亩三分地论坛

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

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

Snapchat 电面.10分钟以前

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

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

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

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

x
本来很有信心,后来刷面经才觉得snapchat bar很高.后悔投早了.幸好面试官是个华人大哥,特别nice.感激~~~~~~~~~~
刚开始聊了挺久的,why snapchat and personal experience..鏈枃鍘熷垱鑷1point3acres璁哄潧
码码的时候有点紧张,出了一些小bug,好在最后都跑出来了.

上题:

public List<String> solution (char[] array, List<String> dic) {}

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

我一开始说用一个set + dfs, 他说输入很多怎么办,比如说100,0000...
. more info on 1point3acres.com
然后就是用Trie + dfs.磕磕碰碰最后跑完. 希望有onsite...

. From 1point 3acres bbs
补充内容 (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

查看全部评分

 楼主| 弱视个体 发表于 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。. visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

 楼主| 弱视个体 发表于 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 做,感觉这题就像一个背包。。. 1point 3acres 璁哄潧

比如,字母集合 [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" ...

... 为啥感觉,字母集大于单词。。 就可以输出了。。. more info on 1point3acres.com
楼主能再帮我理解下吗,感觉一直没上道。。
回复 支持 反对

使用道具 举报

 楼主| 弱视个体 发表于 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,顺序相反)

可以用个set,也可以backtracking路上,把trieNode 里的boolean 取反
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 03:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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