c/c++ - interview中的url缩写算法
Refer - https://stackoverflow.com/a/742047/161243
上面的algo说我们使用DB来存储数据。现在，如果面试官说你不能使用数据库。在这种情况下，我们可以有一个结构：
struct st_short_url{
char * short_url;
char * url;
} 然后是哈希表- st_short_url* hashTable[N];
我看到问题了：
--如果这个进程终止，那么我将失去对int id的跟踪，并从内存中完成hashTable。那么，我是否要一直将hashTable写回磁盘，以便将其持久化呢？如果是，那么会使用B树吗？我们还需要把id写到磁盘上吗？
附注:磁盘的Hashtable+writing是数据库，但如果我不能使用数据库管理系统怎么办？如果我需要想出我自己的实现呢？
你的想法请...
另一个问题：
一般来说，我们如何处理URL缩短中的无限重定向？
回答 3
Stack Overflow用户
发布于 2012-04-04 01:54:42
如果您不能使用任何类型的DB (即没有持久存储；文件系统只是一个原始DB!)，那么我看到的唯一方法就是无损压缩+使用允许的字符进行编码。压缩算法可以使用关于URLS的知识(例如，它们很可能以http://或https://开始，相当一部分以www.开始，并且域名最常以.com、.org或.net结束。此外，您始终可以在主机名后面使用斜杠(因为http://example.org和http://example.org/是等效的)。您还可以假设URL只包含有效字符，以及一些很可能出现在URL中的子字符串的特殊情况(例如，频繁链接的域或某些站点的已知命名方案)。Probaby压缩方案应该有一个版本字段，这样你就可以在使用模式改变时更新算法(例如，一个新的网站变得流行，你也想要特殊的情况，或者一个流行的网站改变了你特殊情况下的URL模式)，而不会冒着旧链接失效的风险。
这样的方案也可以通过扩展直接在浏览器中支持，从而节省服务器带宽(对于那些没有浏览器扩展的人来说，服务器仍然必须在那里，如果扩展还没有最新的压缩数据，则作为后备)。
Stack Overflow用户
发布于 2012-04-04 02:56:24
这个要求是不实际的，但你不必给出一个实际的答案。只要使用文件系统，他就不会意识到这一点。
要存储：
- 将输入的URL转换为字符串，例如base64 base64同名的文件
- 将inode编号返回为短url (例如ls、-i文件名)或()等。
要检索，请执行以下操作：
- 从用户获取索引节点编号。
- find/ -inum n -print或其他从文件名返回mechanism.
- convert的地址。
Stack Overflow用户
发布于 2012-04-04 01:23:06
数据库是支持项目的插入、移除和搜索的数据结构。正如在对OP的评论中所指出的那样，几乎所有的东西都是数据库，所以这个约束看起来有点不知情。
如果不允许使用现有的数据库管理系统，您可以求助于将项目存储在磁盘上，利用tmpnam()或类似的不受竞争条件影响的技术。tmpnam()生成唯一的ID，您可以使用关联的文件来存储信息。
https://stackoverflow.com/questions/9997637
复制相似问题
腾讯云开发者
