一亩三分地论坛

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

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

刚刚结束的Twitter电面

[复制链接] |试试Instant~ |关注本帖
acming 发表于 2016-4-7 04:55:15 | 显示全部楼层 |阅读模式

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

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

x
1分钟前刚结束的twitter的电面。
题目是这样的:给你一个按照字典序排好的字典,找出其中最长的字符串序列,序列中每两个单词的edit distance的长度为1。

我当时没多想,直接构造了一个graph,然后dfs搜,搜出最长的。这题写完就快没时间了,面试官检查了一下code,挑了一个小毛病就结束了。求下一轮。


补充内容 (2016-4-7 05:14):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我之前没说清楚,是一前一后两个单词one edit distance就行,不需要结果集里面所有单词之间都是one edit distance

评分

3

查看全部评分

adiggo 发表于 2016-4-7 05:09:47 | 显示全部楼层
问一下。 每两个单词edit distance 1 是指这个序列的所有的单词 之间 每两个? 还是一前一后的两个? 比如:  a, ab, ac 或者 a, ab, abc
回复 支持 反对

使用道具 举报

 楼主| acming 发表于 2016-4-7 05:13:46 | 显示全部楼层
adiggo 发表于 2016-4-7 05:09.鐣欏璁哄潧-涓浜-涓夊垎鍦
问一下。 每两个单词edit distance 1 是指这个序列的所有的单词 之间 每两个? 还是一前一后的两个? 比如 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
确实我没说清楚,是一前一后的两个单词是one edit distance就行
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-7 05:21:20 | 显示全部楼层
acming 发表于 2016-4-7 05:13
确实我没说清楚,是一前一后的两个单词是one edit distance就行

谢谢。 那这个用graph 的dfs 然后用一个extra space 来check visited,这样就可以避免cycle和重复计算, 对么。不知道有没有更好的 办法了。
回复 支持 反对

使用道具 举报

 楼主| acming 发表于 2016-4-7 05:23:12 | 显示全部楼层
adiggo 发表于 2016-4-7 05:21
谢谢。 那这个用graph 的dfs 然后用一个extra space 来check visited,这样就可以避免cycle和重复计算,  ...

我就是你说的这个方法做的。我想也想知道有没有更好的办法,当时没想出别的办法
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-4-7 13:54:06 | 显示全部楼层
还是不太明白,我看完题目觉得输入是一个string array,然后输出这个array里最长的string。。。。然而看LZ的解法,题意明显不是这样的。。。请问能再说得详细点吗?最好举个例子

补充内容 (2016-4-7 15:27):
我终于看懂了,原谅我语文没学好。。。
回复 支持 反对

使用道具 举报

 楼主| acming 发表于 2016-4-7 17:48:11 | 显示全部楼层
hison7463 发表于 2016-4-7 13:54
还是不太明白,我看完题目觉得输入是一个string array,然后输出这个array里最长的string。。。。然而看LZ ...

哈哈,确实我描述的也不太清楚,我语文从小不好。而且我不想贴当时直接给的英文题目,怕被老美烙印搜着
回复 支持 反对

使用道具 举报

小艾哥 发表于 2016-4-7 21:19:24 | 显示全部楼层
我语文也不好。。。楼主可以给个例子吗?谢谢!
回复 支持 反对

使用道具 举报

 楼主| acming 发表于 2016-4-7 21:27:10 | 显示全部楼层
小艾哥 发表于 2016-4-7 21:19
我语文也不好。。。楼主可以给个例子吗?谢谢!

输出最长这样的list:bat-cat-cats-mats-mat。每两个单词之前之间只有一个差距。找出最长这样的序列。
回复 支持 反对

使用道具 举报

小艾哥 发表于 2016-4-7 21:35:38 | 显示全部楼层
acming 发表于 2016-4-7 21:27
输出最长这样的list:bat-cat-cats-mats-mat。每两个单词之前之间只有一个差距。找出最长这样的序列。
. 1point3acres.com/bbs
了解了!祝onsite
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 08:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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