Tag: 数据结构

采访难题：使用有限的内存对一百万个输入进行排序

我尝试使用外部排序来回答这个问题，但是访问者回答说复杂性是高nn（log（n）），即n square * logn。 有没有更好的选择。 简化问题：假设我们有1000个元素要排序，只为100个元素分配空间。 什么是比外部排序花费更少时间的最佳算法。

C等价于C ++ STL

可能重复： C中的标准数据结构库？ C是否有类似于C ++ STL的任何数据结构实现？ 特别是关联容器，哈希映射或任何其他具有大致恒定时间检索的结构？ 谢谢！

在像C这样的编程语言的上下文中，数组数据结构和数组数据类型之间有什么区别？

Wikipedia区分arrays数据结构和arrays数据类型 。 在像C这样的编程语言的上下文中，数组数据结构和数组数据类型之间有什么区别？ 这是什么： int array[]={1, 2, 3, 4, 5}; ？ 它是arrays数据结构还是arrays数据类型？ 为什么？

连接/合并/连接两个AVL树

假设我有两个AVL树，并且第一个树中的每个元素都小于第二个树中的任何元素。 将它们连接成一个单独的AVL树的最有效方法是什么？ 我到处搜索，但没有找到任何有用的东西。

设计一个支持海量数据存储和查询的系统

面试官要求我设计一个存储千兆字节数据的系统，系统也必须支持某种查询。 描述： 在IDC中生成大量记录，每个记录由URL，访问URL的IP以及访问发生的时间组成。 该记录可能被声明为这样的结构，但我不确定应该选择哪种数据类型来代表它们： struct Record { url; //char * IP; //int? visit_time; //time_t or simply a number? } 要求： 设计一个存储1000亿条记录的系统，系统至少支持2种查询： 首先，给定时间段（t1，t2）和IP，查询该IP在给定时间段内访问了多少URL。 其次，给定时间段（t1，t2）和URL，查询该URL被访问的次数。 我被绊倒了，这是我的愚蠢解决方案： 分析： 因为每个查询都是在给定的时间段内执行的 ，所以： 1. 创建一个集合 ，将所有访问时间放入集合中，并根据从旧到最新的时间值保持集合的顺序。 2. 使用散列（visit_time）作为键创建散列表，该散列表称为时间散列表，然后特定桶中的每个节点 具有分别指向另外2个散列表的2个指针 。 另外两个哈希表是ip-hash-table和url-hash-table 。 ip-hash-table使用hash（ip）作为密钥，同一ip-hash-table中的所有ips具有相同的访问时间; url-hash-table使用hash（url）作为密钥，同一url-hash-table中的所有url都具有相同的访问时间。 给出如下图纸： time_hastbl [] [] []–>[visit_time_i]–>[visit_time_j]…[visit_time_p]–>NIL [] | | [] ip_hastbl url_hastbl [] [] : : [] [] […]

算法和数据结构最适合拼写检查器，字典和同义词库

实施的最佳方式 字典（有没有比Trie for Dictionary更好的DS） 词库（不知道，因为词语的含义相似，含义相似） 拼写检查器（比哈希映射更好的东西），如果可能的话，使用正确的拼写建议。 当在一小时的采访中被问到时，我们是否希望为算法编写ac / c ++代码？

需要一个通用的库，纯C

你能为C推荐一个好的通用数据容器库（纯C，而不是C ++）吗？ 我只需要基本结构，如动态数组，哈希表等。 （注意：“好”我指的是快速+优雅的界面）。

__attribute __（（packed））会影响程序的性能吗？

我有一个名为log的结构，里面有13个字符。 在执行sizeof（log）之后，我看到大小不是13而是16。我可以使用__attribute __（（packed））将其设置为13的实际大小，但我想知道这是否会影响程序的性能。 它是一种经常使用的结构。 我希望能够读取结构的大小（13而不是16）。 我可以使用宏，但如果这个结构被更改，即添加或删除字段，我希望在不更改宏的情况下更新新大小，因为我认为这很容易出错。 有什么建议吗？

解析数学表达式

（在c90）（linux） 输入： sqrt(2 – sin(3*A/B)^2.5) + 0.5*(C*~(D) + 3.11 +B) a b /*there are values for a,b,c,d */ c d 输入： cos(2 – asin(3*A/B)^2.5) +cos(0.5*(C*~(D)) + 3.11 +B) a b /*there are values for a,b,c,d */ c d 输入： sqrt(2 – sin(3*A/B)^2.5)/(0.5*(C*~(D)) + sin(3.11) +ln(B)) /*max lenght of formula is 250 characters*/ a b /*there […]

什么是哈希表，你如何在C中创建它？

我对一个称为哈希表（也称为关联数组）的数据结构以及如何在C中实现它有几个问题。 你如何在C中创建哈希表？ 什么是哈希表，你如何实现它？ 为什么我要使用哈希表而不是数组？ 注意：我知道这是一个非常广泛的问题，需要大量的答案，但我这样做是因为我有些人问我这是什么。 所以我把它放在这里，以充分解释它并帮助其他任何人。