问题标签 [algorithm]

我正在开发一个应用程序，用户必须拨打电话并使用手机键盘输入验证码。

我希望能够检测他们输入的数字是否正确。电话系统无法访问有效号码列表，但它会根据算法（如信用卡号码）验证号码。

以下是一些要求：

• 输入有效的随机码一定很困难
• 如果我打错字（数字换位，错误数字），一定很难有一个有效的代码
• 我必须有合理数量的可能组合（比如说 1M）
• 代码必须尽可能短，以避免用户出错

鉴于这些要求，您将如何生成这样的数字？

编辑 ：

@Haaked：代码必须是数字，因为用户是用手机输入的。

@matt b：第一步，代码显示在网页上，第二步是调用并输入代码。我不知道用户的电话号码。

跟进：我发现了几种算法来检查数字的有效性（请参阅这个有趣的 Google 代码项目：checkDigits）。

假设我想实现一个相当有效的“关键字识别算法”，首先给出一个关键字列表，然后如果另一个给定的单词在列表中，则必须回答。

在命令式语言中，我会将关键字存储在树中（每个字符一个节点）。然后，当接收到要测试的单词时，我会扫描我的树以测试该单词是否是关键字。

我想了解如何用功能语言对这种算法进行编码。如何在保持“命令式”算法的效率的同时获得“无状态”编程的好处。如果您不想每次都重建它，是否有必要在查找之间的某处存储树？

给定一个构成单词句子的字符数组，给出一个有效的算法来反转其中单词（不是字符）的顺序。

示例输入和输出：

它应该是 O(N) 时间和 O(1) 空间（split()并且不允许推入/弹出堆栈）。

谜题取自这里。

我需要一个快速算法来从通用列表中选择 5 个随机元素。例如，我想从 a 中获取 5 个随机元素List<string>。

如何在 50,000 个 HTML 页面中找到电话号码？

Jeff Attwood 为申请工作的程序员发布了 5 个问题：

为了让电话筛查员的生活更简单，我整理了这份清单，列出了您在 SDE 筛查期间需要问的五个基本问题。他们不能保证你的候选人一定会很棒，但他们会帮助淘汰大量在我们今天的流程中溜走的候选人。

1) 编码考生必须使用 C、C++ 或 Java 编写一些具有正确语法的简单代码。

2) OO 设计候选人必须定义基本的OO 概念，并提出类来建模一个简单的问题。

3) 脚本和正则表达式考生必须描述如何在 50,000 个 HTML 页面中查找电话号码。

4) 数据结构候选人必须展示最常见数据结构的基本知识。

5) 位和字节考生必须回答有关位、字节和二进制数的简单问题。

请理解：我在这里寻找的是这些区域之一的完全真空。如果他们稍微挣扎一下然后弄清楚就可以了。如果他们需要一些小提示或提示也没关系。我不介意它们是否生锈或缓慢。您正在寻找的是对相关领域完全一无所知或极度困惑的候选人。

>>> Jeff 原帖的全部内容 <<<

注意： Steve Yegge 最初提出了这个问题。

在工作中，我们经常需要从字符串列表中找到与其他输入字符串最匹配的字符串。目前，我们正在使用 Needleman-Wunsch 算法。该算法经常返回很多误报（如果我们将最低分数设置得太低），有时它在应该找到匹配时（当最低分数太高时）找不到匹配，而且大多数时候，我们需要手动检查结果。我们认为我们应该尝试其他替代方案。

你有算法方面的经验吗？你知道算法之间的比较吗？

我真的很感激一些建议。

PS：我们用 C# 编码，但你不应该关心它——我问的是一般的算法。

哦，对不起，我忘了提到这一点。

不，我们没有使用它来匹配重复数据。我们有一个我们正在寻找的字符串列表——我们称之为搜索列表。然后我们需要处理来自各种来源（如 RSS 提要、网站、论坛等）的文本——我们提取这些文本的一部分（有整套规则，但这无关紧要），我们需要匹配那些反对搜索列表的人。如果该字符串与搜索列表中的一个字符串匹配 - 我们需要对该事物进行一些进一步的处理（这也是无关紧要的）。

我们无法进行正常的比较，因为从外部来源提取的字符串大多数时候都包含一些额外的单词等。

无论如何，它不是用于重复检测。

我注意到这里有一些关于字符串匹配的帖子，这让我想起了一个我想解决的老问题。有没有人有一个很好的类似于 Levenshtein的算法，它偏向于 Qwerty 键盘？

我想比较两个字符串，并允许拼写错误。Levenshtein 没问题，但我更愿意接受基于 Qwerty 键盘上按键之间物理距离的拼写错误。换句话说，算法应该更喜欢“yelephone”而不是“zelephone”，因为在大多数键盘上，“y”键比“z”键更靠近“t”键。

任何帮助都会很棒......这个功能不是我项目的核心，所以当我应该做一些更有成效的事情时，我不想转向一个老鼠洞。

有没有人对任何用于图形算法的 Java 库有很好的经验。我试过JGraph，发现没问题，google 里有很多不同的。是否有人实际在生产代码中成功使用或会推荐？

澄清一下，我不是在寻找生成图形/图表的库，而是在寻找有助于图形算法的库，例如最小生成树、Kruskal 算法节点、边等。理想情况下，它具有一些好的算法/数据一个不错的 Java OO API 中的结构。

有没有人有一个体面的算法来计算轴最小值和最大值？

在为给定的一组数据项创建图表时，我希望能够给出算法：

• 集合中的最大值 (y)
• 集合中的最小值 (y)
• 出现在轴上的刻度线数量
• 必须显示为刻度的可选值（例如，显示 +ve 和 -ve 值时为零）

算法应该返回

• 最大轴值
• 最小的轴值（尽管可以从最大值、间隔大小和刻度数推断出）
• 区间大小

刻度线应该有规律的间隔应该是“合理的”大小（例如 1、3、5，甚至可能是 2.5，但不再是 sig figs）。

可选值的存在会扭曲这一点，但如果没有该值，最大的项目应该出现在顶部两个刻度线之间，底部两个刻度线之间的最小值。

这是一个与语言无关的问题，但如果周围有 C#/.NET 库，那就太棒了；）

自从 2006 年从一所规模很小的学校毕业后，课程的形式很糟糕且过时（我是外国人，当时不知道更好的学校），我开始意识到我错过了很多基本概念数学和软件视角，主要是其他更高概念的基础。

即我试图听/看麻省理工学院关于算法介绍的开放课件，但很快意识到我错过了几个数学概念以更好地理解这门课程。

那么一个优秀的软件工程师应该知道哪些核心数学概念呢？您会向我推荐哪些可能的书籍/网站？