我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
查看: 2610|回复: 9
收起左侧

SnapChat OA passed 9/10 test cases

[复制链接] |试试Instant~ |关注本帖
我的人缘0
user123456 发表于 2016-3-30 13:51:42 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

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个。. 1point3acres

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

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


攒RP
. 1point3acres

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

评分

2

查看全部评分


上一篇:报个snapchat offer
下一篇:BrightEdge OA + 电面
我的人缘0
ok123 发表于 2016-3-30 14:20:41 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
用trie 好像能有 O(N)的时间
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| user123456 发表于 2016-3-31 05:56:14 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
上午告诉HR做完了,下午拿到了电面邀请。所以和之前一样,并不是要求10个test cases都要过。当然,能都过最好~
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
newbiee 发表于 2016-4-10 09:18:32 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
cx00001 发表于 2016-4-3 14:40
用dfs 剪枝是可以通过的。其实dp hit 到 word的长度时候 立即返回 应该也是 能通过的。 我之前先用dp也是发 ...
. 牛人云集,一亩三分地
请教一下同学, dfs能剪哪些枝啊?
除非你用trie 做了startWith 判断,不然没法剪啊
回复 支持 反对

使用道具 举报

我的人缘0
cx00001 发表于 2016-4-10 09:26:59 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
就是backtracking
回复 支持 反对

使用道具 举报

我的人缘0
tldxk 发表于 2016-4-10 09:39:21 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
Java自带的sort应该是优化最好的,这点可以从leetcode运行时间看出来。会根据具体情况选择计数排序等非比较排序。
回复 支持 反对

使用道具 举报

我的人缘0
cx00001 发表于 2016-4-10 12:48:32 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
排序没用 通不过三个例子
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
cx00001 发表于 2016-4-10 23:00:04 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
并不是空串 空串根本进不了循环 就是超时了 dp用向后看的那个方法 hit到最后一个位置立即返回就可以通过了
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-28 11:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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