在数据集中查找整数的最快方法

Question

面试题比较复杂，我简化为

输入数据的格式为A,B
A 是一个介于 0 和 18446744073709551615 之间的数字(mysql bigint)
B 是一个随机字符串
我们会提供IO部分

你应该在 c/c++

中提供两个函数

set(unsigend long long A, char *B)
get(unsigend long long A)

数据结构和算法由你决定。

要求

集合应该是 O(1)
get 应该是 O(1)

请记住，我们可能会调用 set 1 亿次

有什么想法吗？我没有给出很好的答案

我的回答不完整：

typedef data {
    unsigned long long A;
    char *B;
    data *next;
}

set 只是 malloc 一个新数据并追加到列表中

但获取部分失败。

Answer 1

我在C中就是这样实现的。我想你会从代码中理解我的想法。（注：nos: this algorithm is known as Trie）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node node;

struct node {
    node *nodes[0x10];
    char *text;
};

node *top;

void set(unsigned long long A, char *B)
{
    unsigned char n;
    node *way;

    way = top;

    for (;A>0;A>>=4)
    {
        n = A & 0xf;

        if (way->nodes[n] == NULL)
        {
            way->nodes[n] = malloc(sizeof(node));
            memset(way->nodes[n], 0, sizeof(node));
        }

        way = way->nodes[n];
    }

    if (way->text != NULL)
    {
        free(way->text);
    }

    way->text = strdup(B);
}

char *get(unsigned long long A)
{
    unsigned char n;
    node *way;

    way = top;

    for (; A>0 && way != NULL; A>>=4)
    {
        n = A & 0xf;
        way = way->nodes[n];
    }

    if (A == 0 && way != NULL)
    {
        return way->text;
    }

    return NULL;
}

int main()
{
    top = malloc(sizeof(node));
    memset(top,0,sizeof(node));

    set(1230294381243, "test1");
    set(12934839, "test2");
    set(1,"tezt");

    printf("%s", get(1230294381243));
    printf("%s", get(12934839));
    printf("%s", get(1));

//    todo: free memory
//    free_way(top); 

    return 0;
}

最多 16 次迭代以找到任何 unsigned long long 键。此代码 100% 有效并经过测试，除了从 top 变量中释放内存。

更新。将 nodes 声明为数组（HolyBlackCat 的建议）。

更新。提高算法速度（Serge Rogatch的建议）

Answer 2

作为面试题，考虑编码目标的影响是合理的。

考虑

and answered by
巨大的数组char *even[18446744073709551615u/2+1]; char *odd[18446744073709551615u/2+1];

要求 "set should be O(1), get should be O(1)" 搁置哈希解决方案，因为它不是真正的 O(1)。哈希仍然可以具有出色的平均速度和资源评级。

然而没有内存效率要求，也没有内存限制，也没有设置大小（隐含的 < 1 亿除外）。

#3（数组）的简单实现肯定会超出实际内存预算，但理论上它是 O(1)。仍然不是 真正的 候选人，即使它满足规定的要求并且在内存限制（理论上是无限的）内。

Trie 的问题是它的底部叶子通常是一大堆 NULL 指针 - 使这种方法占用大量内存。然而，如果集合计数（未知）很小，这不是问题。

Put in mind that we might call set 100 million times

这一点并未反映在 trie 实现中，因为提醒是还要考虑整体效率。一个 trie 可以是非常低的内存效率，具有高集合计数并且平均比动态哈希慢 - 即使它的 O(1) get/set.

这是面试部分的用武之地，不仅要提供满足要求的技术解决方案，当然是 trie，还要展示它的优点（O(1) for get/set）及其缺点comings (memory hog)，平均速度比散列慢。因此，确保您的客户（本例中的面试官）被告知可能更好地满足总体[的其他合理解决方案 =51=] 目标。

在数据集中查找整数的最快方法

fastest way to find an integer in a dataset

c

c++

algorithm

lookup

search