小编max*_*yne的帖子

我在论坛中阅读了以下内容:

合并排序对于链接列表等不可变数据结构非常有效

和

当数据存储在内存中时,快速排序通常比合并排序更快.但是,当数据集很大并且存储在外部设备(如硬盘驱动器)上时,合并排序在速度方面是明显的赢家.它最大限度地减少了外部驱动器的昂贵读取

和

在链表上操作时,合并排序只需要少量的辅助存储

有人能帮助我理解上述论点吗？为什么合并排序首选排序庞大的链表？它如何最大限度地减少对外部驱动器的昂贵读取？基本上我想了解为什么会选择合并排序来排序大链表.

给定一组数字,将数字划分为两个子集,使得两个子集中的数字之和之间的差异最小.

这是我的想法,但我不确定这是否是一个正确的解决方案:

1. 对数组进行排序
2. 采取前两个元素.将它们视为2组(每组有1个元素)
3. 从数组中获取下一个元素.
4. 决定该元素应该在哪个集合中(通过计算sum =>它应该是最小的)
5. 重复

这是正确的解决方案吗？我们可以做得更好吗？

这是一个面试问题.考虑以下:

struct A {}; 
struct B : A {}; 
A a; 
B b; 
a = b;
b = a; 

为什么b = a;抛出错误,虽然a = b;完全没问题？

低级别位操作从来都不是我的强项.我将理解一些有助于理解按位运算符的以下用例.考虑...

int age, gender, height, packed_info;

. . .   // Assign values 

// Pack as AAAAAAA G HHHHHHH using shifts and "or"
packed_info = (age << 8) | (gender << 7) | height;

// Unpack with shifts and masking using "and"
height = packed_info & 0x7F;   // This constant is binary ...01111111
gender = (packed_info >> 7) & 1;
age    = (packed_info >> 8);

我不确定这段代码是什么以及如何完成的？为什么使用幻数0x7F？如何完成包装和拆包？

资源

假设数组的整数在1到1,000,000之间.

我知道解决这个问题的一些流行方法:

1. 如果包含1到1,000,000之间的所有数字,找到数组元素的总和并从总和中减去它(n*n + 1/2)
2. 使用哈希映射(需要额外的内存)
3. 使用位图(减少内存开销)

我最近遇到了另一个解决方案,我需要一些帮助来理解它背后的逻辑:

保留一个基数累加器.您使用索引和该索引处的值进行异或或累加器.

x ^ C ^ x == C这个事实在这里是有用的,因为每个数字将被xor'd两次,除了那里的两次,这将出现3次.(x ^ x ^ x == x)最终索引,将出现一次.因此,如果我们使用最终索引对累加器进行种子处理,则累加器的最终值将是列表中的数字两次.

如果有人能够帮助我理解这种方法背后的逻辑,我会很感激(用一个小例子!).

我最近遇到了这个面试问题(在一个论坛上发布了一些......看起来这是一个真实的面试问题):

设计一个只有在没有可能的死锁时才提供锁的类.

没有提供其他信息.我不太清楚如何解释这一点.假设pthreads模型,面试官是否正在寻找锁定经理类？任何想法都会有所帮助

这是一个面试问题.我不是C++专家,所以我需要一些帮助来找到这个问题的答案(我首先想要理解这个问题......这是一个有效的问题吗？)

题:

假设我有一个派生自A类的B类,我想重用一些但不是A的所有方法.我如何有选择地限制对超类的方法的访问？

谢谢!

我遇到过这个面试问题,并希望在尝试理解其解决方案时提供一些帮助:

编写一个方法来用'%20'替换字符串中的所有空格.

解决方案(来自论坛):

char str[]="helo b";
int length = strlen(str);
int spaceCount = 0, newLength, i = 0;

for (i = 0; i < length; i++) {
if (str[i] == ' ') {
    spaceCount++; //count spaces...
}
}

newLength = length + spaceCount * 2;   //need space for 2 more characters..
str[newLength] = '\0';

for (i = length - 1; i >= 0; i--) {
    if(str[i] == ' ') {
        str[newLength - 1] = '0'; //???
        str[newLength - 2] = …

我需要帮助理解这个面试问题:

问:找到一个算法,在二元搜索树中找到给定节点的下一个节点(例如,顺序后继节点),其中每个节点都有一个到其父节点的链接.

父母是指有序的前任还是直接的父母？如何创建一个树,其中节点具有到根节点的链接或者有前导的链接？任何帮助理解下面的数据结构和程序将不胜感激......

解决方案(如表格中所示)如下所示:

 public static TreeNode inorderSucc(TreeNode e) {
   if (e != null) {
     TreeNode p;

     // Found right children -> return 1st inorder node on right
     if (e.parent == null || e.right != null) {
       p = leftMostChild(e.right);
     } else {
       // Go up until we’re on left instead of right (case 2b)
       while ((p = e.parent) != null) {
         if (p.left == e) {
           break;
         }
         e = p;
       }
     }
     return p;
   }
   return null;
 } …

我在一个论坛上遇到过这个问题.答案是这样的:

#define ISUNSIGNED(a) (a >= 0 && ~a >= 0) 

//Alternatively, assuming the argument is to be a type, one answer would use type casts: 

#define ISUNSIGNED(type) ((type)0 - 1 > 0)

我对此有几个问题.为什么我们需要检查~a >= 0？第二个解决方案是什么？我不明白这句话:"论证是一种类型".更重要的是,作者指出,首先#define不适用于ANSI C(但在K&R C中可以使用).为什么不？

我需要帮助理解下面剪切的代码... allocate是一个函数,由重载的new运算符调用以分配内存.我在尝试理解以下演员表时遇到问题:

*static_cast<std::size_t*>(mem) = pAmount; //please explain?

return static_cast<char*>(mem) + sizeof(std::size_t); //? 

和..

// get original block
void* mem = static_cast<char*>(pMemory) - sizeof(std::size_t); //?

代码如下所示:

const std::size_t allocation_limit = 1073741824; // 1G
    std::size_t totalAllocation = 0;

    void* allocate(std::size_t pAmount)
    {
        // make sure we're within bounds
        assert(totalAllocation + pAmount < allocation_limit);

        // over allocate to store size
        void* mem = std::malloc(pAmount + sizeof(std::size_t));
        if (!mem)
            return 0;

        // track amount, return remainder
        totalAllocation += pAmount;
        *static_cast<std::size_t*>(mem) = pAmount;

        return static_cast<char*>(mem) …