數據結構歧義

我無法確定這個採訪問題。你有一個整數數組。您需要提供另一個具有以下功能的數據結構：數據結構歧義

int get(int index) 
void set (int index, int value) 
void setall(int value)

他們都做你猜他們應該做的事。限制是每個函數都在O（1）中。

你怎麼設計它，以便setAll將是O（1）。

我想爲每個整數添加另一個字段，它會指向每次調用setAll時都會更改的整數。問題出現時有人打電話setAll然後設置然後得到。

編輯：我改變了變量的名稱，所以它會更清晰。另外，既然你問了，得到是假設返回數組[i]，set（index，value）假設把數值放在數組[index]中。

後setall(index, value)你應該get (get(i) == get(j) == value)爲陣列中的每個i，j。

來源

2011-05-02 Eyal

什麼是'i'在'set'和'setall'？ – 2011-05-02 12:35:37

我假設n =陣列的長度，效率是O（n）？ – 2011-05-02 12:35:55

爲什麼會有問題，如果有人卡萊特setAll，然後設置，然後得到？（按順序，顯然）此外，感覺這是一個家庭作業問題，而不是屬於「面試問題」部分的問題。 – 2011-05-02 12:37:55

爲數組中的每個元素，一個setAllValue變量和一個setAllDateTime變量保留一個DateTime字段（或簡單地說是一個計數器）。對每一組，更新元素的日期時間/計數器。使用SetAll，更新setAllDateTime的值和DateTime。

在get中，將SetAll的DateTime與元素的DateTime進行比較，以較新者爲準，返回該值。

來源

2011-05-02 12:41:02

謝謝！所以簡單.. – Eyal 2011-05-02 14:41:29

@ Hammar的解決方案使用版本號可能更好。時間戳的問題是您依賴於沒有兩次更改具有相同的時間戳。這絕對取決於更改的頻率和時間戳的分辨率。例如，Windows以其低準確性而聞名。 – 2011-05-02 14:51:14

@Matthieu @Hammer我認爲一般情況下，你可以選擇最能幫助你的答案，因爲你問了這個問題，而你正在尋找一些具體的東西。在這種情況下，Hammer確實給出了一個非常好的解決方案，一個完整的答案，我同意。但我需要的是Sanrag Sood所說的。唯一的想法:)再說一次，這並不是說Hammer的回答不好:)這太棒了！ – Eyal 2011-05-04 06:04:51

如何存儲「版本號」與每個變量，即

int globalValue, globalVersion; 
int nextVersion; 
int[] localValue, localVersion; 

int get(int i) { 
    if (localVersion[i] > globalVersion) 
     return localValue[i]; 
    else 
     return globalValue; 
} 


void set(int i, int value) { 
    localValue[i] = value; 
    localVersion[i] = nextVersion++; 
} 

void setAll(int value) { 
    globalValue = value; 
    globalVersion = nextVersion++; 
}

來源

2011-05-02 12:41:05 hammar

謝謝！這真是太好了.. – Eyal 2011-05-02 14:40:32

@Eyal：根據更新的數量，不要忘記處理版本循環（回到0代表未簽名，並且變成負號）。 – 2011-05-02 14:49:35

這個問題說'set（i）'not'set（i，value）':-) – 2011-05-02 17:06:51

數據結構歧義

回答

相關問題