最快方式

Question

面试问题更复杂，所以我简化它作为

1. 输入数据将在A,B
2. A的格式是0和18446744073709551615之间的数（MySQL的BIGINT）
3. B是一个随机字符串
4. 我们将提供IO部分

你应该提供T路WO在C/C++

1. 组函数（unsigend长长A，字符* B）
2. 的get（unsigend长长A）

数据结构和算法是由你。

要求

1. 集应该是O（1）
2. GET应该是O（1）

将记住，我们可以称之为设定了100万次

任何想法？我没有给一个好的答案

我的答案是不完整的：

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

集只是一个malloc的新的数据并追加到列表

但在获取部分失败。

Answer 1

我用C这样做过。我想你会从代码中理解我的想法。 （由nos注：这个算法被称为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变量中释放内存除外。

UPDATE。声明node s作为数组（建议HolyBlackCat）。

UPDATE。提高算法速度（建议Serge Rogatch）

Answer 2

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

考虑

1. 散列通过@PaulMcKenzie

2. 字典树建议通过@Serge Rogatch提出并通过@vadim_hr

3. 巨大阵列char *even[18446744073709551615u/2+1]; char *odd[18446744073709551615u/2+1];

回答

要求“设置为O（1），得到的应该是O（1）”抛开哈希解决方案，因为它不是真正的O（1）。仍然哈希可以有优秀的平均速度和资源评级。

然而，没有内存效率的要求，也没有内存限制，也没有设置大小（除了隐含的1亿1亿个隐含的<）。理论上，＃3（数组）的幼稚实现肯定会超过实际的内存预算，但它是O（1）。尽管它符合规定的要求，并且在记忆范围内（理论上是无界的），但它仍然不是真实的候选人。

Trie的问题是它的底部叶子通常是大量的指针 - 使得这种方法内存密集。但是，如果计数（未知）很小，这不是一个问题。

---

放在心中，我们可以称之为设定了100万次

这一点并没有反映在执行特里作为提醒是也考虑过所有的效率。即使使用O（1）get/set，一个trie可能会非常浪费内存，并且集合数很高，平均而言比动态散列更慢。

这就是采访部分的目的不仅仅是提供满足要求的技术解决方案，当然是一种技术方案，而是展示其优势（获取/设置的O（1））及其缺点（内存猪），平均速度比散列慢。因此要确保您的客户（在这种情况下的采访者）通知其他合理的解决方案，可能更好地满足整体目标。