c++ - c/c++ 中的 url 缩短算法 - 面试

Question

引用 - https://stackoverflow.com/a/742047/161243

上面的算法说我们使用数据库来存储数据。现在如果面试官说你不能使用数据库。那么在那种情况下我们可以有一个结构:

struct st_short_url{
  char * short_url;
  char * url;
} 

然后是一个哈希表 - st_short_url* hashTable[N];

现在我们可以有一个每次递增的 int id 或一个随机数生成的 id，它被转换为 base62。

我看到的问题:

-- 如果此进程终止，那么我将失去对 int id 的跟踪并从 RAM 中完成 hashTable。那么我是否继续将 hashTable 写回磁盘以使其持久化？如果是，那么将使用 B 树？我们还需要将 id 写入磁盘吗？

附言哈希表+写入磁盘是数据库，但如果我不能使用 DBMS 怎么办？如果我需要提出自己的实现方案怎么办？

你的想法...

另一个问题:

一般来说，我们如何处理 URL 缩短中的无限重定向？

Answer 1

如果您不能使用任何类型的数据库(即没有持久存储；文件系统只不过是原始数据库!)，那么我看到的唯一方法是无损压缩 + 允许字符编码.压缩算法可能会使用有关 URLS 的知识(例如，它们很可能以 http:// 或 https:// 开头，很多继续www.，域名最常以.com、.org或.net结尾。此外，您还可以始终假设主机名后有一个斜杠(因为 http://example.org 和 http://example.org/ 是等价的)。您也可以假设URL 只包含有效字符，以及一些很可能出现在 URL 中的子字符串的特殊情况(例如，频繁链接的域，或某些站点的已知命名方案)。压缩方案应该具有版本字段，以便您可以更新使用模式发生变化时的算法(例如，一个新的网站变得流行，你也想对其进行特殊处理，或者一个受欢迎的网站改变了你特殊处理的 URL 模式)，而不会冒旧链接失效的风险。

这样的方案也可以通过扩展直接在浏览器中得到支持，从而节省服务器带宽(对于没有浏览器扩展的用户来说，服务器仍然必须在那里，如果扩展还没有最新的压缩，则作为回退数据)。