什么是STL列表,向量和集合的基础数据结构？
我的解决方案
对？
这是一个面试问题.
如何检测并查明程序是否处于死锁状态？是否有一些工具可用于在Linux/Unix系统上执行此操作？
我的想法:
如果程序没有进展并且其状态正在运行,则它是死锁.但是,其他原因也可能导致这个问题.开源工具是valgrind(halgrind)可以做到的.对？
你知道以下面试问题的解决方案吗？
设计电话簿的数据结构,可以安全有效地按名称搜索数字,并按编号搜索名称.
细节:
stackoverflow上的解决方案都是关于哈希表的,但是,我必须为它构建2个哈希表,这需要两倍的空间.
如何以时间和空间效率,类型安全的方式只使用一个数据结构？
给定方阵,每个单元格为黑色或白色.设计算法以找到最大子方块,使得所有4个边界都是黑色的.
我有O(n ^ 2)算法:
从左到右扫描每列,对于每列中的每个单元格,扫描每一行以找到具有后边框的最大子广场.
有更好的解决方案吗？
谢谢
给定一个字符串数组,返回作为字谜的所有字符串组.
我的解决方案
对于数组中的每个字符串字,将其排序为O(m lg m),m是字的平均长度.
构建哈希表<string,list>.
将排序后的单词作为键放入哈希表中,并生成单词的所有排列(O(m!)),使用O(m)搜索字典中的每个排列(前缀树映射),如果它在字典中,将(O(1))放入哈希表中,以便将所有排列的单词放入具有相同键的列表中.
总共有O(n*m*lg m*m!)时间和O(n*m!)空间,n是给定数组的大小.
如果m非常大,那就没有效率了,m!.
更好的解决方案？
谢谢
如何设计最近最新使用的缓存？
假设您访问了一些项目.您需要设计一个数据结构来保存这些项目.每个项目都与最近访问的时间相关联.
每次访问项目时,请在数据结构中进行检查.如果该项目已在缓存中,请更新其访问时间.否则,将其插入缓存中.高速缓存大小是固定的,如果已满,则删除最旧的项目.
我的解决方案
使用地图<item,visitTime>
初始化:使用f(visitTime)按降序对地图进行排序.O(nlg n)
如果访问了某个项目,请使用O(lg n)在地图中搜索该项目.
如果它已在地图中,则更新时间O(1).对地图O(lg n)进行排序.
如果没有,请将其插入地图然后排序.O(lg n)
如果地图大小>固定大小,则删除最后一个元素O(1).
另一种方案:
使用哈希表<item,visitTime>
将它排序为O(n lgn).
如果访问了某个项目,请使用O(1)在该项目中进行搜索.
如果它已在表中,则更新时间O(1).对表O(n lg n)进行排序.
如果没有,请将其插入表中然后排序.O(n lg n)
如果表大小>固定大小,则删除最后一个元素O(1).
有更好的解决方案吗？上) ？
这是一个面试问题:
给定一个字符串,找到它在字典中的单词的所有排列.
我的解决方案
将字典的所有单词放入后缀树中,然后搜索树中字符串的每个排列.
搜索时间是O(n),n字符串的大小在哪里.但字符串可能有n!排列.
如何提高效率？
面试问题.
如何通过添加实现除法？假设他们都是int.
我的想法
quotient * divisor + reminder == dividend.这是O(e^n)什么更好的想法？位操作？
面试问题:
找到书中最常用的单词.
我的想法:
使用哈希表,遍历并标记哈希表.
如果已知书的大小,如果发现任何单词的使用率> 50%,则跳过以下遍历中的任何新单词并仅计算旧单词.如果图书大小未知怎么办？
它是O(n)和O(n)的时间和空间.
有更好的想法吗？
谢谢
面试问题:
给定两个非有序整数序列
a和b,其大小为n时,所有的数字是随机选取的:交换的元素a和b,使得所述元素的总和a减去的元素的总和b是最小的.
举个例子:
a = [ 5 1 3 ]
b = [ 2 4 9 ]
结果是(1 + 2 + 3) - (4 + 5 + 9)= -12.
我的算法:将它们排序在一起,然后将第一个最小的n整数放入a和放入b.它的时间为O(n lg n),空间为O(n).我不知道如何将其改进为时间为O(n)且空间为O(1)的算法.O(1)意味着除了seq 1和2之外我们不需要更多的额外空间.
有任何想法吗 ？
另一个问题是:如果我们需要最小化差异的绝对值(最小化|sum(a) - sum(b)|)怎么办？
首选python或C++思想.