一亩三分地论坛

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

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

SnapChatOA新题

[复制链接] |试试Instant~ |关注本帖
shunlin 发表于 2016-1-26 22:31:03 | 显示全部楼层 |阅读模式

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

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

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

x
昨天做了一道OA,感觉和地里看到的不太一样,发出来贡献给大家!

题目大意如下:
给定一个字符串数组,例如["snap","chat", "snapchat"],其中有些单词可以被数组中两个或多个单词拼接起来,例如"snapchat" = "snap"+"chat"。这种单词称之为compound word,其余称之为simple word。

题目要求输出所有的simple word,并按照原数组之前的顺序。上面的例子就要输出["snap", "chat"]。

数组范围很大,我不清楚暴力做法能否AC(感觉应该不行)。我是构建字典树,然后通过DFS查找的。这样感觉不是最优解,不过可以通过所有测试用例。

如果大家有更好的方法,请贡献出来。我觉得应该可以用DP做,类似计算edit distance。

核心代码如下:

        // 如果是复合单词,返回true。isRepeat记录是否重新经过了根节点。
        private static boolean dfsCompound(TreeNode node, String word, int index,
                        boolean isRepeat) {. 1point3acres.com/bbs
                // TODO Auto-generated method stub. 1point 3acres 璁哄潧
                int cPos = word.charAt(index)-'a';. 1point 3acres 璁哄潧
                if (node.children[cPos] == null) return false;
               
                if (index == word.length()-1) {
                        if (node.children[cPos].isEnd) return isRepeat;
                        else return false;
                }
               
                if (node.children[cPos].isEnd && dfsCompound(root, word, index+1, true)) {
                        return true;
                }. visit 1point3acres.com for more.
                . 鍥磋鎴戜滑@1point 3 acres
                return dfsCompound(node.children[cPos], word, index+1, isRepeat);       
        }



OA的题目感觉越来越难了,大家加油!
. From 1point 3acres bbs

评分

1

查看全部评分

eko910817 发表于 2016-1-27 02:37:30 | 显示全部楼层
请问lz是什么时候拿到的OA?
回复 支持 反对

使用道具 举报

 楼主| shunlin 发表于 2016-1-27 10:32:01 | 显示全部楼层
eko910817 发表于 2016-1-27 02:37
请问lz是什么时候拿到的OA?

上周五拿到的OA吧。不过是这周一做的。
回复 支持 反对

使用道具 举报

eko910817 发表于 2016-1-27 12:16:58 | 显示全部楼层
shunlin 发表于 2016-1-26 18:32.1point3acres缃
上周五拿到的OA吧。不过是这周一做的。

我刚做了也是这个题,HR联系你了吗?
回复 支持 反对

使用道具 举报

hitowings 发表于 2016-1-28 10:50:06 | 显示全部楼层
eko910817 发表于 2016-1-27 12:16
我刚做了也是这个题,HR联系你了吗?
. 1point 3acres 璁哄潧
请问收到hr回复了么?
回复 支持 反对

使用道具 举报

hitowings 发表于 2016-1-28 10:50:34 | 显示全部楼层
shunlin 发表于 2016-1-27 10:32
上周五拿到的OA吧。不过是这周一做的。

楼主收到回复了么  我也周一做的  可是还没回复我
回复 支持 反对

使用道具 举报

 楼主| shunlin 发表于 2016-1-28 23:40:52 | 显示全部楼层
hitowings 发表于 2016-1-28 10:50
楼主收到回复了么  我也周一做的  可是还没回复我

回了啊,约了电话面试的时间。

. visit 1point3acres.com for more.记得做完后回复一下邮件,这样可能会快些联系你。
回复 支持 反对

使用道具 举报

 楼主| shunlin 发表于 2016-1-28 23:41:01 | 显示全部楼层
hitowings 发表于 2016-1-28 10:50-google 1point3acres
楼主收到回复了么  我也周一做的  可是还没回复我

回了啊,约了电话面试的时间。

记得做完后回复一下邮件,这样可能会快些联系你。
回复 支持 反对

使用道具 举报

eko910817 发表于 2016-1-29 02:25:22 | 显示全部楼层
hitowings 发表于 2016-1-27 18:50
请问收到hr回复了么?

我也收到了,做完OA的第二天早上,记得回一下邮件。
回复 支持 反对

使用道具 举报

royal_916 发表于 2016-2-15 02:30:57 | 显示全部楼层
没看懂lz的isrepeat是怎么个用法啊  求解释一下!感谢!
回复 支持 反对

使用道具 举报

garderobin 发表于 2016-3-23 05:39:02 | 显示全部楼层
楼主请问你的root是什么?代码里面只出现了一次
回复 支持 反对

使用道具 举报

kemeng1314 发表于 2016-4-23 14:47:03 | 显示全部楼层
楼主您好,我按照您的思路在lc里面的word break做了却发现是tle的,想和您讨论一下
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 18:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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