一亩三分地论坛

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

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

SnapChat OA passed 9/10 test cases

[复制链接] |试试Instant~ |关注本帖
user123456 发表于 2016-3-30 13:51:42 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 博士 全职@Snapchat - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
题目还是Easy / Compound单词那个。
  1. given an array of words. output array of simple words. compound word are made of multiple simple words in the array.

  2. Example input:
  3. String[] = {chat ever snapchat snap salesperson per person sales son whatsoever what so}
  4. 其中simple word是: chat, ever, snap, per, sales, son, what, so

  5. 尤其注意son是simple
复制代码
我使用的是基于长度Sorting + Set + Iterative的Word Break(https://leetcode.com/problems/word-break/)思路仍然只过了其中9个。

但排序我使用的是Java自带的函数,所以复杂度会比较高。后来想用counting sort,但已经没有时间implement,只在上面写了思路。

因为单词已经按长度排序好了,所以排序后位置靠前的词不可能是靠后的某个词的compound形式。所以对排序后的单词,每个词看能不能使用set里面的词完成word brea。如果不能完成(即是simple word),就加到set里面。这样set只存simple word,空间应该是相对最小。同时时间仍然是O(N k^2)不变,N = 单词数量,k = 单词长度



攒RP


补充内容 (2016-3-31 05:56):.鏈枃鍘熷垱鑷1point3acres璁哄潧
上午告诉HR做完了,下午拿到了电面邀请。所以和之前一样,并不是要求10个test cases都要过。当然,能都过最好~

评分

2

查看全部评分

ok123 发表于 2016-3-30 14:20:41 | 显示全部楼层
用trie 好像能有 O(N)的时间
回复 支持 反对

使用道具 举报

 楼主| user123456 发表于 2016-3-31 05:56:14 | 显示全部楼层
上午告诉HR做完了,下午拿到了电面邀请。所以和之前一样,并不是要求10个test cases都要过。当然,能都过最好~
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-4-3 14:40:10 | 显示全部楼层
用dfs 剪枝是可以通过的。其实dp hit 到 word的长度时候 立即返回 应该也是 能通过的。 我之前先用dp也是发现最后一个过不了,然后立即改成剪枝版本的dfs就过了。事后想想其实dp提前返回应该跟dfs一样的效果。
回复 支持 反对

使用道具 举报

newbiee 发表于 2016-4-10 09:18:32 | 显示全部楼层
cx00001 发表于 2016-4-3 14:40
用dfs 剪枝是可以通过的。其实dp hit 到 word的长度时候 立即返回 应该也是 能通过的。 我之前先用dp也是发 ...

请教一下同学, dfs能剪哪些枝啊?
除非你用trie 做了startWith 判断,不然没法剪啊
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-4-10 09:26:59 | 显示全部楼层
就是backtracking
回复 支持 反对

使用道具 举报

tldxk 发表于 2016-4-10 09:39:21 | 显示全部楼层
Java自带的sort应该是优化最好的,这点可以从leetcode运行时间看出来。会根据具体情况选择计数排序等非比较排序。
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-4-10 12:48:32 | 显示全部楼层
排序没用 通不过三个例子
回复 支持 反对

使用道具 举报

u-r-the-one 发表于 2016-4-10 12:53:22 | 显示全部楼层
最后一个test没有过是因为 有可能输入里含有空string “”  这样的话 这个也算是simple word 如果你没有把这个加到最后的结果里 就会fail最后一个test 并不是因为超时 所以我觉得这种edge case他们应该也不是很在意
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-4-10 23:00:04 | 显示全部楼层
并不是空串 空串根本进不了循环 就是超时了 dp用向后看的那个方法 hit到最后一个位置立即返回就可以通过了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 02:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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