问题标签 [data-structures]

确定链表中是否有循环的最佳（停止）算法是什么？

[编辑] 时间和空间的渐近复杂度分析会很不错，因此可以更好地比较答案。

[编辑] 原始问题不是解决 outdegree > 1 的节点，但有一些讨论。这个问题更像是“在有向图中检测循环的最佳算法”。

在我们正在进行的项目中，我们需要一个“评级”系统，类似于 SO 中的系统。但是，在我们的系统中，有多个实体需要通过投票来“标记”（仅向上，从不向下，就像增量一样）。有时我们需要按照评分最高的顺序显示所有实体，不管实体类型如何，我猜基本上是混合结果集。您使用什么数据结构/算法来实现这一点，以便灵活且仍可扩展？

我有一个信息检索应用程序，它创建数以千万计的位数组。数组中“设置”位的数量变化很大，从全部清除到全部设置。目前，我使用的是直截了当的位数组 ( java.util.BitSet)，所以我的每个位数组都需要几兆字节。

我的计划是查看前N位的基数，然后决定其余部分使用什么数据结构。显然，一些数据结构更适合非常稀疏的位数组，而另一些数据结构在设置了大约一半的位时更好（当设置了大多数位时，我可以使用否定将其视为一组稀疏的零）。

• 什么结构可能在每个极端都有好处？
• 中间有吗？

以下是一些限制或提示：

1. 这些位仅设置一次，并且按索引顺序设置。
2. 我需要 100% 的准确率，所以像布隆过滤器这样的东西还不够好。
3. 建立集合后，我需要能够有效地迭代“集合”位。
4. 这些位是随机分布的，因此游程编码算法不太可能比一个简单的位索引列表好多少。
5. 我正在尝试优化内存利用率，但速度仍然很重要。

具有开源 Java 实现的东西是有帮助的，但不是绝对必要的。我对基础知识更感兴趣。

我的数据库中有以下表，它们具有多对多关系，由一个连接表表示，该连接表具有到每个主表的主键的外键：

• Widget：WidgetID (PK)、标题、价格
• 用户：用户 ID (PK)、名字、姓氏

假设每个 User-Widget 组合都是唯一的。我可以看到关于如何构造定义数据关系的连接表的两个选项：

1. UserWidgets1：UserWidgetID (PK)、WidgetID (FK)、UserID (FK)
2. UserWidgets2：WidgetID（PK、FK）、UserID（PK、FK）

选项 1 有一个主键列。但是，这似乎没有必要，因为表中存储的唯一数据是两个主表之间的关系，而这种关系本身可以形成唯一键。因此导致选项 2，它具有两列主键，但丢失了选项 1 具有的一列唯一标识符。我还可以选择在第一个表中添加一个两列唯一索引（WidgetID、UserID）。

两者在性能方面是否有任何真正的区别，或者有任何理由更喜欢一种方法而不是另一种方法来构建 UserWidgets 多对多表？

诚然，XML 非常有用，但可能非常冗长。有哪些替代品，它们是否专门用于任何特定目的？轻松查询内容的库支持是一大优势。

您使用什么特定的方法/应用程序在您的应用程序和数据库之间进行通信？带有存储过程的自定义代码？亚音速？休眠？实体框架？林克？

我想知道人们如何在不使用基类库实现的情况下在 C# 中实现以下数据结构：-

• 链表
• 哈希表
• 二叉搜索树
• 红黑树
• B树
• 二项式堆
• 斐波那契堆

以及人们能想到的任何其他基本数据结构！

我很好奇，因为我想提高对这些数据结构的理解，很高兴看到 C# 版本而不是互联网上的典型 C 示例！

我有一个想要从多个地方调用的 Linq 查询：

如何创建一个方法，将这段代码放入其中，然后调用它？

在候选人筛选过程中，您发现哪些简单的算法或数据结构相关的“白板”问题是有效的？

我有一些简单的方法可以用来验证解决问题的能力，可以简单地表达，但有一些机会应用一些启发式方法。

我用于初级开发人员的基础知识之一是：

编写一个 C# 方法，该方法接受一个包含一组单词（一个句子）的字符串，并将这些单词向右旋转 X 个位置。当句子最后位置的单词被旋转时，它应该出现在结果字符串的前面。

当候选人回答这个问题时，我希望看到他们可以使用 .NET 数据结构和方法（string.Join、string.Split、List 等）来解决问题。我还寻找他们来识别优化的特殊情况。就像单词需要旋转的次数并不是真正的 X，而是 X % 的单词数。

您在面试候选人时使用了哪些白板问题，以及您在答案中寻找哪些内容（不需要发布实际答案）。

在 MySQL 数据库中存储链表的最佳方法是什么，以便插入简单（即您不必每次都重新索引一堆东西）并且可以轻松地按顺序拉出列表？