Feedback

# re: 騰訊面試中一道題 2009-04-16 22:08 func

為啥不能為每個用戶追加一個登錄時間字段呢？
每次登錄，判斷下時間。

請教~  回復  更多評論   

# re: 騰訊面試中一道題 2009-04-17 17:50 Mark

也就是一個時間鏈表，一個5段的循環(huán)Buffer. 每段循環(huán)Buffer使用HashTable就OK了。  回復  更多評論   

# re: 騰訊面試中一道題[未登錄] 2009-04-27 15:19 terry

@func
因為用戶數(shù)目可能很多，比如一億個，可是我5分鐘的時間最多有300萬個不同的用戶

如果給用戶追加登錄時間，當然可以用來判斷是否超時，但是你準備怎么保存這些用戶數(shù)據(jù)

1。如果只想保存5分鐘的話，
那么我有一個用戶到期了，按照你的登錄時間字段，怎么迅速的找出誰過期，然后把這個數(shù)據(jù)刪掉  回復  更多評論   

# re: 騰訊面試中一道題 2009-04-30 11:04 func

感謝回復

我的意思是在數(shù)據(jù)庫里的相關表中追加一個登錄時刻字段和下線時刻字段。每次登錄時，用當前時刻比對這些時刻字段，看是不是重復上線。

我沒看出題目中有清除過期數(shù)據(jù)的需求，麻煩指出一下 ：）  回復  更多評論   

# re: 騰訊面試中一道題[未登錄] 2009-05-06 17:43 terry

@func
這么說吧，比如我第1－5分鐘上線了300萬個不同的用戶，第6－10分鐘上線了另外300萬個不同的用戶
現(xiàn)在有600萬個用戶，你準備把這600萬個用戶的數(shù)據(jù)都保存在數(shù)據(jù)庫里嗎？
如果按照你的做法，50分鐘就得存3000萬個用戶的數(shù)據(jù) （這里假設上線的都不重復），這樣就很浪費空間

因為題目的要求只有一個： 判斷用戶是否在5分鐘之內(nèi)登錄，所以我只要保存距當前時間最近5分鐘用戶的數(shù)據(jù)，5分鐘之前登錄的鐵定是不算重復的，保存了也沒用。所以最多這需要保存300萬個用戶的數(shù)據(jù)，無論時間怎么推移

因為每次保存的都是最近5分鐘時間的用戶的數(shù)據(jù)，當時間流逝的時候，其中的數(shù)據(jù)就有一些發(fā)生了超時（即距離當前時間已經(jīng)從5分鐘內(nèi)變成了超過5分鐘），這個時候就要刪掉，同時最近上線的用戶也要更新進來  回復  更多評論   

# re: 騰訊面試中一道題[未登錄] 2009-05-06 17:48 terry

當然你也可以說，你每次都會檢查登錄時刻字段距當前時刻是否超過5分鐘，如果超過5分鐘就刪掉

假設你數(shù)據(jù)庫保存的是300萬個用戶的數(shù)據(jù)，每一個新的時刻（比如下一秒之類的），你都得把這個300萬個用戶的時間檢查一遍，用的時間就是O（n）了  回復  更多評論   

# re: 騰訊面試中一道題 2009-05-10 01:09 func

我覺得你這種設計只在某一類系統(tǒng)中有必要，比如投票系統(tǒng)。

投票系統(tǒng)中，用戶一般不是注冊用戶，這樣就不存在數(shù)據(jù)庫用戶表，就沒法在數(shù)據(jù)庫中記錄用戶登錄時刻。就必須在內(nèi)存中用某種數(shù)據(jù)結(jié)構(gòu)來記錄用戶投票信息，即IP信息等。每次投票，都要查找一下這個數(shù)據(jù)結(jié)構(gòu)，看看在一定時間中是否重復投票。

但是題目所用的文字太讓人誤解為注冊用戶登錄的系統(tǒng)。如果是注冊用戶登錄的系統(tǒng)的重復登錄判斷，完全可以查看用戶表中最后一次登錄時刻和最后一次下線時刻來做此類判斷啊。  回復  更多評論   

# re: 騰訊面試中一道題 2009-05-10 01:19 func

注冊用戶登錄的系統(tǒng)，上線時向數(shù)據(jù)庫更新（不是添加）上線時刻，下線時向數(shù)據(jù)更新下線時刻。不需要另開個定時器啥的更新這個數(shù)據(jù)啊。
至于時間復雜度，登錄一次檢查一次，如果檢查的時間接受不了，系統(tǒng)的登錄本身就成問題了。所以這個不是問題。
  回復  更多評論   

# re: 騰訊面試中一道題[未登錄] 2009-05-11 15:50 terry

@func
你這樣子說也是有道理的，在實際中我覺得確實可以按你的這么做，可是個人的看法是面試中會考你的數(shù)據(jù)結(jié)構(gòu)之類的，  回復  更多評論   

# re: 騰訊面試中一道題[未登錄] 2009-09-10 20:02 noName

放在客戶端就行了咯  回復  更多評論