• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            zhgw01

            騰訊面試中一道題

            題目:1分鐘內用戶上線的數目是60萬,如果用戶在5分鐘內重復上線,就給他發警告,問如何設計?

            考慮:要判斷用戶是否在5分內重復上線,那么至少要(也只需要)保存距當前時刻5分鐘內的登錄用戶的信息(只要簡單的ID)
                       從這個開始出發,需要考慮的問題為2個:
                       1.如何在迅速判斷用戶是否在保存的數據中 (這個理所當然想道用hash)
                       2. 如果把過期的數據刪掉  (這個就想到維護一個時間鏈表,把到期的通過鏈表來刪除)


            這個是半年前騰訊面試的時候碰到的題目,當時覺得很難,今天走在路上突然想起,想了想,突然想到這種方法,也許不是最好,但至少解決了,也了解了一件事

            posted on 2009-04-16 20:39 apacs 閱讀(2547) 評論(10)  編輯 收藏 引用 所屬分類: 算法

            Feedback

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

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

            請教~  回復  更多評論   

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

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

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

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

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

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

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

            感謝回復

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

            我沒看出題目中有清除過期數據的需求,麻煩指出一下 :)  回復  更多評論   

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

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

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

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

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

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

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

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

            我覺得你這種設計只在某一類系統中有必要,比如投票系統。

            投票系統中,用戶一般不是注冊用戶,這樣就不存在數據庫用戶表,就沒法在數據庫中記錄用戶登錄時刻。就必須在內存中用某種數據結構來記錄用戶投票信息,即IP信息等。每次投票,都要查找一下這個數據結構,看看在一定時間中是否重復投票。

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

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

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

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

            @func
            你這樣子說也是有道理的,在實際中我覺得確實可以按你的這么做,可是個人的看法是面試中會考你的數據結構之類的,  回復  更多評論   

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

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


            My Links

            Blog Stats

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久精品无码免费不卡| 国产成人综合久久精品红| 无码精品久久久天天影视| 亚洲国产另类久久久精品| 97久久天天综合色天天综合色hd| 国内精品久久久久久99| 久久99精品久久久久久不卡| 午夜精品久久久久久影视riav| 久久精品亚洲中文字幕无码麻豆 | 无码日韩人妻精品久久蜜桃| 久久婷婷激情综合色综合俺也去| 99久久免费国产精品| 精品综合久久久久久98| 91麻豆精品国产91久久久久久| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 国产精品99久久99久久久| 久久久久亚洲av成人无码电影| 新狼窝色AV性久久久久久| 久久久久亚洲av成人无码电影| 人妻无码αv中文字幕久久| 手机看片久久高清国产日韩| 99久久精品费精品国产一区二区| 少妇熟女久久综合网色欲| 久久精品国产精品亚洲下载| 99久久精品国产免看国产一区| 亚洲欧美成人久久综合中文网 | 色婷婷综合久久久久中文一区二区| 99久久国产主播综合精品| 久久精品亚洲中文字幕无码麻豆 | 国产成人久久激情91 | 蜜桃麻豆www久久国产精品| 久久精品视频网| 99久久成人国产精品免费| 精品国产一区二区三区久久久狼| 久久久久久久97| 久久精品国产色蜜蜜麻豆| 香蕉久久永久视频| 欧美亚洲国产精品久久| 一日本道伊人久久综合影| 2020久久精品亚洲热综合一本| 久久综合一区二区无码|