标签: data-structures

哪个是可用于在Python中实现二进制树的最佳数据结构？

二进制搜索树比哈希表有什么优势？

哈希表可以在Theta(1)时间查找任何元素,并且添加元素也同样容易....但我不确定反过来的优势.

这是一个谷歌面试问题:

存储有大约一千个电话号码,每个电话号码具有10个数字.您可以假设每个数字的前5位数相同.您必须执行以下操作:搜索是否存在给定数字.湾 打印所有号码

这样做最有效的节省空间的方法是什么？

我回答哈希表和后来的霍夫曼编码,但我的采访者说我没有朝着正确的方向前进.请帮帮我.

可以使用后缀trie帮助吗？

理想情况下,1000个数字存储每个数字需要4个字节,因此总共需要4000个字节来存储1000个数字.在数量上,我希望将存储空间减少到<4000字节,这是我的采访者向我解释的内容.

如何在Python中整齐地表示图形？(从头开始,即没有库!)什么数据结构(例如dicts/tuples/dict(元组))将快速但内存效率高？一个人必须能够对其进行各种图形操作. 正如所指出的,各种图表表示可能会有所帮助.如何在Python中实现它们？至于图书馆,这个问题有很好的答案.

这个问题可能已经过时了,但我想不出答案.

比如,有两个不同长度的列表,在某一点合并 ; 我们怎么知道合并点在哪里？

条件:

1. 我们不知道长度
2. 我们应该只解析每个列表一次.

我正在阅读布隆过滤器,他们看起来很傻.使用bloom过滤器可以完成的任何事情,你可以在更少的空间内,更有效率地完成,使用单个散列函数而不是多个,或者它看起来像是什么.为什么要使用布隆过滤器？它有什么用？

我可以创建一个所有元素都是类型的NSMutableArray实例吗？SomeClass

我在接受采访时得到了这个问题.你怎么回答？

设计一个在O(1)时间内提供以下操作的数据结构:

• 插入
• 去掉
• 包含
• 获得随机元素

Dijkstra的算法教给我如下

while pqueue is not empty:
    distance, node = pqueue.delete_min()
    if node has been visited:
        continue
    else:
        mark node as visited
    if node == target:
        break
    for each neighbor of node:
         pqueue.insert(distance + distance_to_neighbor, neighbor)

但是我一直在阅读关于算法的一些阅读,我看到的很多版本都使用了reduce-key而不是insert.

为什么会这样,这两种方法之间有什么区别？

我最近注意到,基于创意基础中数字的巧妙使用,部分或全部有很多算法.例如:

• 二项式堆基于二进制数,并且更复杂的偏斜二项式堆基于偏斜二进制数.
• 用于生成按字典顺序排列的排列的一些算法基于事实数字系统.
• 可以将尝试视为一次查看字符串的一位数的树,以获得适当的基础.
• 霍夫曼编码树被设计成使树中的每个边在一些二进制表示中编码为零或一.
• Fibonacci编码用于Fibonacci搜索并反转某些类型的对数.

我的问题是:还有哪些其他算法使用聪明的数字系统作为他们直觉或证据的关键步骤？.我正在考虑就这个问题进行一次讨论,所以我必须从中得到更多的例子.