最快方式

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））及其缺點（內存豬），平均速度比散列慢。因此要確保您的客戶（在這種情況下的採訪者）通知其他合理的解決方案，可能更好地滿足整體目標。