[請益] interview被問倒的一題

[sundance (Mars)]

知道這裡有很多cs背景的人
想來問一題今天被問倒的題目

假設你要設計一個電話簿比如說存這種資料
JOHNL 212-999-0000
..

要使用Hash table, 假設username是唯一, 而且必定是長度5
有可能A-Z, 0-9, 或者space

現在要你寫一個hash function, 產生出的key可以map到電話號碼

如何寫這個hash function, 使得這個設計
1. no collisions
2. min memory

min memory的提示是:
這個username長度為5, 每個都有37種可能(A-Z,0-9,space), 因此有37^5種可能


不管有沒有被錄取, 很想知道這題如何解答!
先謝謝啦!

--
※ 發信站: 批踢踢參(ptt3.cc)
◆ From: 69.22.232.46

> -------------------------------------------------------------------------- <

作者: HYL (hyl@UofArizona) 看板: Job
標題: Re: [請益] interview被問倒的一題
時間: Tue Jan 24 02:59:53 2006

※ 引述《sundance (Mars)》之銘言：
: 知道這裡有很多cs背景的人
: 想來問一題今天被問倒的題目
: 假設你要設計一個電話簿比如說存這種資料
: JOHNL 212-999-0000
: ...
: 要使用Hash table, 假設username是唯一, 而且必定是長度5
: 有可能A-Z, 0-9, 或者space
: 現在要你寫一個hash function, 產生出的key可以map到電話號碼
: 如何寫這個hash function, 使得這個設計
: 1. no collisions
: 2. min memory
: min memory的提示是:
: 這個username長度為5, 每個都有37種可能(A-Z,0-9,space), 因此有37^5種可能
: 不管有沒有被錄取, 很想知道這題如何解答!
: 先謝謝啦!

  我不是CS背景的，這題應該算是好猜解答的

  把username的五個位數當做五個位元來看，每個單位有 37 種可能，
  然後再把他當成 37 進位來看。

  hash function f(x) = 37^4 * x1 + 37^3 * x4 + 37^2 * x3 + 37 * x4 + x5
  應為37剛好是質數，所以這樣不會有collisions產生

  搬手指頭算算 37^5 = 69343957 < 2^32(4294967296)  所以一個 int剛好就可
  以存 key了。

--

  Interview 時人真的會變笨，上週跟某家 400億市值的公司面試，天
  知道我在想什麼，對方要我念個解某個數是不是 power of 2 的程式
  ，結果我回他二的倍數的程式 -.-;;

  掛上電話後才想起來，還好家住在二樓，不然就跳下去了.....

  最扯的是，昨天接到信，叫我去onsite interview 0rz...

--
※ 發信站: 批踢踢參(ptt3.cc)
◆ From: 24.5.191.38
推 sundance:厲害! 我覺得我就是沒想到可以這樣做, 感謝解答!
推 jphant:記得好像某繪圖晶片公司也問過那個問題...2的power.
> -------------------------------------------------------------------------- <

作者: dollar (dollar) 看板: Job
標題: Re: [請益] interview被問倒的一題
時間: Tue Jan 24 18:24:25 2006

挑個毛病

:   我不是CS背景的，這題應該算是好猜解答的
:   把username的五個位數當做五個位元來看，每個單位有 37 種可能，
:   然後再把他當成 37 進位來看。
:   hash function f(x) = 37^4 * x1 + 37^3 * x4 + 37^2 * x3 + 37 * x4 + x5
:   應為37剛好是質數，所以這樣不會有collisions產生

不會有collisions 並不是因為37剛好為質數. 只要x1, x2, x3, x4, x5 小於37且大於0
就可以了.


:   搬手指頭算算 37^5 = 69343957 < 2^32(4294967296)  所以一個 int剛好就可
:   以存 key了。

--
※ 發信站: 批踢踢參(ptt3.cc)
◆ From: 129.46.218.191
推 HYL:反正看到找Hashing function就往質數找就對了
推 irene7:dollar說的沒錯. 這跟質數沒關係