Integer分區

我遇到了以下面試問題。Integer分區

考慮這個函數聲明：
void quiz(int i) 
{ 
    if (i > 1) 
    { 
     quiz(i/2); 
     quiz(i/2); 
    } 
    writeOutput("*"); 
} 
多少個星號通過函數調用quiz(5)印刷？

我的回答是：

語言（JavaScript中，PHP等）整數除法結果類型爲浮動 - 七個星號。函數測驗被稱爲：

隨着i = 5 - 一旦打印星號。

隨着i = 2.5 - 兩次，打印星號。

i = 1.25 - 四次，打印星號。

其中i = 0.625 - 八次，沒有星號印刷

語言（C/C++，C＃，Java等）的除法結果類型名稱是整數 - 三個星號。函數測驗被稱爲：

隨着i = 5 - 一旦打印星號。

隨着i = 2 - 兩次，打印星號。

隨着i = 1 - 四次，未打印星號。

問題的語法是像C/C++，Java，所以答案應該是三個

採訪是a closed book exam - 面試我無法運行該代碼，並檢查過程中。面試官告訴我，我的回答並不完全正確（或者至少，他們沒有想到會是這樣）。 Hovewer，我在家裏運行了這個代碼（用PHP，Javascript和C＃），結果如我所描述的那樣。

那麼，有沒有一些注意事項我錯過了，或者我的回答只是比他們期待的更詳細？

來源

2011-08-29 J0HN

我不知道我的頭頂有多準確或正確的答案（儘管如果我正在進行面試，我會認爲這是一個很好的答案），但總是有可能面試官不正確或只是普通人不知道更好，即使他認爲他確實如此。我一直在公平地分享面試，桌子後面的人沒有資格參加面試的工作。 – David

運行該代碼不會給我你所描述的答案。 –

如果你的代碼改成這樣：

void quiz(int i) 
{ 
    if (i > 1) 
    { 
     quiz(i/2); 
     quiz(i/2); 
    } 
    printf("* for %d\n", i); 
}

你會看到，quiz(5)結果是：

* for 1 
* for 1 
* for 2 
* for 1 
* for 1 
* for 2 
* for 5

所以，你有電話的正確數量每我，你只是沒有注意到writeOutput在if之外，而不在裏面。

來源

2011-08-29 18:24:59 Douglas

是的，絕對正確。我想我已經回答了他們真正要求的，但不是問題本身。謝謝你的答案。 – J0HN

writeOutput將在我< = 1時被調用。

來源

2011-08-29 18:19:39

就像往常一樣，很簡單。感謝你的回答。 – J0HN

鑑於該函數將int作爲參數，它將（在通常情況下）永遠不會獲得2.5作爲參數。除非有人說#define double int，但在這種情況下，再也沒有東西可靠了。

所以你的答案應該只是你答案的第二部分。

來源

2011-08-29 18:23:03

但他的答案的第二部分是錯誤的。 –

用PHP或Javascript運行它 - 當然會。 – J0HN

我在Java中得到7：

public class fun { 



public void quiz(int i) 
{ 

    if (i > 1) 
    { 
     quiz(i/2); 
     quiz(i/2); 
    } 
    System.out.println("Value of i = " + i); 
    System.out.println("*"); 
} 

public static void main(String[] args){ 

    fun f = new fun(); 
    f.quiz(5); 

} 
}

輸出=

Value of i = 1 
* 
Value of i = 1 
* 
Value of i = 2 
* 
Value of i = 1 
* 
Value of i = 1 
* 
Value of i = 2 
* 
Value of i = 5 
*

有兩件事情讓這個簡單的功能很難手動跟蹤。

第一：遞歸。遞歸函數使用調用堆棧，並且可能很難在紙上保留i的狀態......尤其是在採訪中;-)

第二：和其他人一樣，print（*）在如果...也許有點抓到！

來源

2011-08-29 18:37:34 Cygnusx1

是的，'writeOutput'在if之外。我在裏面運行'writeOutput'的代碼。 – J0HN

我想和答案一樣，如果你能提供複雜性分析，面試官會很高興。的複雜性是3210（其中**是電運營商）：

您可以通過編寫一棵樹想象這一點，我們得到的是一個嚴格而完整的二叉樹（下面是對於n = 5和幾個節點不再贅述）

 
      5 
     / \ 
     2  2 
    /\ /\ 
     1 1 1 1 
    /\ .......... 
    0 0 ..............

同樣來自這個問題，我不認爲面試官期待其他語言如Python 3.x中，其中默認行爲是浮點除法和*將被打印出來，甚至更多次的分析。當浮點數是預設的，來電的號碼是：2 ** (ceil(lg(n))+1) -1，（調用樹甚至會超過一個整數除法更大，讓作爲鍛鍊; Tibial :)）

您可以運行此Python代碼：

nCalls = 0 
def quiz(n): 
    global nCalls 
    nCalls += 1 
    if n>1: 
     quiz(n/2) 
     quiz(n/2) 

test = [5, 9, 15] 
for n in test: 
    nCalls = 0 
    quiz(n) 
    print("nCalls for %d : %d" % (n,nCalls))

有關python 2.X：（整數除法）

nCalls for 5 : 7 
nCalls for 9 : 15 
nCalls for 15 : 15

有關python 3.x的：（浮點）

nCalls for 5 : 15 
nCalls for 9 : 31 
nCalls for 15 : 31

HTH。

來源

2011-08-31 08:19:37

回答

相關問題