May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

snapchat OA 2.14.16 解法之我见。

[复制链接] |试试Instant~ |关注本帖
singledog2016 发表于 2016-2-24 09:58:25 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Snapchat - 内推 - 在线笔试 |Passfresh grad应届毕业生

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

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

x
given an array of words. output array of simple words.
compound word are made of multiple simple words.. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

chat ever snapchat snap salesperson per person sales son whatsoever what so
其中simple word是chat, ever, snap, per, sales, son, what, so
. 鍥磋鎴戜滑@1point 3 acres
我的做法是:感觉很leetcode word break很像。那题是问一个string能否break成字典的word. 如果string长度是s, 复杂度是O(s^2)用dp方法可做。 这题可以把每个单词看做是string. 这样如果不能break就是simple words.
但有一点很tricky. 因为把所有词加入字典,包含了自身。比如chat, 可以用chat本身去break.  我想到在检查每个单词是否能被break之前,把自身从字典set里面删掉。检查完之后再加进去,检查下一个单词。这样就可搞定。. from: 1point3acres.com/bbs
复杂度是O(n s^2) n是总的单词数目,s是最长单词长度。. Waral 鍗氬鏈夋洿澶氭枃绔,

足够详细吧! 求加米啊!!

评分

3

查看全部评分

motn 发表于 2016-3-18 18:33:16 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
LZ好牛,这个方法不错
回复 支持 反对

使用道具 举报

fengyubo0352 发表于 2016-3-25 03:47:09 | 显示全部楼层
关注一亩三分地微博:
Warald
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

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

使用道具 举报

fengyubo0352 发表于 2016-3-25 03:50:14 | 显示全部楼层
不需要每次删除和加回原set,因为每一次加进去都需要耗费多余时间。我做的方法是看一个词能被拆成几种组合。如果是1,那么就是自己;如果是大于1,那么说明这个词是一个compound; 如果小于1,那么说明这个词是空串,也是属于词根。这样对每个词过一次就行了,不需要反复添加和删除。
回复 支持 反对

使用道具 举报

 楼主| singledog2016 发表于 2016-3-25 03:52:58 | 显示全部楼层
adding and removing from hashset is O(1) no big deal
回复 支持 反对

使用道具 举报

fengyubo0352 发表于 2016-3-25 03:57:38 | 显示全部楼层
singledog2016 发表于 2016-3-25 03:52
adding and removing from hashset is O(1) no big deal

I don't know how Java implement set, but are you sure adding and removing from set in C++ is O(1)? how set is implemented in C++?
回复 支持 反对

使用道具 举报

 楼主| singledog2016 发表于 2016-3-25 04:02:19 | 显示全部楼层
Java HashSet is O(1), C++ should have hash table as well. unorder_map ?
some word has multiple ways of breaking. snapchat can break into 1. snapchat, or 2 snap, chat.  You have to check multiple possibilities.
However, without self word, you only need to check if it can break out out. Just a true or false choice. So it is Leetcode word break I.

回复 支持 反对

使用道具 举报

fengyubo0352 发表于 2016-3-25 04:12:11 | 显示全部楼层
singledog2016 发表于 2016-3-25 04:02
Java HashSet is O(1), C++ should have hash table as well. unorder_map ?
some word has multiple way ...

Should be unordered_set.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Yes, for second point, I agree with you. Actually I tried this one in the beginning, but later I changed my idea since it is annoying to deal with delete and insert, so I change my mind. But you are right.
回复 支持 反对

使用道具 举报

u-r-the-one 发表于 2016-3-26 09:47:39 | 显示全部楼层
LZ的OA过了吗?
回复 支持 反对

使用道具 举报

 楼主| singledog2016 发表于 2016-3-26 09:51:40 | 显示全部楼层

OA过了,但是最后跪了
回复 支持 反对

使用道具 举报

u-r-the-one 发表于 2016-3-26 09:54:21 | 显示全部楼层
singledog2016 发表于 2016-3-25 20:51
OA过了,但是最后跪了

能不能问一下是电面跪了还是onsite。。。有没有面经 snapchat练练手 lz肯定更有好的offer
回复 支持 反对

使用道具 举报

 楼主| singledog2016 发表于 2016-3-26 10:03:30 | 显示全部楼层
有点忙。下周若有空写一下。
回复 支持 反对

使用道具 举报

fantasiasango 发表于 2016-9-5 05:31:24 | 显示全部楼层
感谢楼主分享!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-27 09:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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