NO IMAGE

挺感謝面試官了,問了我將近50分鐘,自己也更加了解自己欠缺什麼了。

1 C 多型如何實現

    常規套路,這個很基礎就不說了。

2 把解構函式宣告為虛擬函式的作用,和實現的原理

    自己沒懂實現原理應該怎麼回答,回來後想了想,應該按照多型的思路去回答,子類重寫了父類的解構函式,那麼在呼叫到解構函式的時候就會發生多型,從而呼叫子類的解構函式,再呼叫父類的解構函式。先子類析構再父類析構是C 標準的規定,實現原理自己沒有搜到,但這麼做的原因很好找。

3 C 中static關鍵字總結

    類外:

        靜態全域性變數:檔案之外不可見

        靜態區域性變數:

                1 存在全域性區,程式執行期間始終存在。

                2 只初始化1次。

                3 作用域是區域性的。

        修飾函式:檔案之外不可見

    類中

        修飾成員變數:

                1 所有物件共享一個資料,沒有建立物件已經存在。

                2 在類外初始化

                3 優勢:有訪問許可權控制,不在全域性變數的名字空間中

        修飾成員函式

                1 沒有this指標,只能使用靜態成員變數

    普通成員函式可以使用靜態成員變數和靜態成員函式。

一個很好的總結連結送給大家:

https://www.cnblogs.com/BeyondAnyTime/archive/2012/06/08/2542315.html

4 概率題,54張撲克牌,連摸三張,花色相同的概率

    考慮大小王,應該是52/54 * 12/53 * 11/52 

5 outptr瞭解過嗎?

    下來之後百度都搜不到。

6 在陣列n中找第k大的數,怎麼找?

    最蠢的肯定是對所有資料快排或歸併O(NlogN)。自己知道這個題最快肯定是O(N)但是當時緊張,沒能仔細思考。

    再者就是冒泡k次,能把前k大的數全部找出來,O(kN)。

    下來之後又搜了一下,看了別人的思路:

    1 利用快排

        random()一個數做pv值,大於pv放右邊(n個),小於pv放左邊(m個)。

        比較m和k的大小

            m<k, 把右邊的n個數再選pv值,做排序,比較new_m和(k-m)的關係,遞迴。

            m>k, 把左邊的m個數再選pv值,做排序,比較new_m和k的關係,遞迴。

        據說時間複雜度是O(N*logk),怎麼證明我就不知道了。

        自己後來想了想,貌似用這個方法複雜度應該是O(N):

            首先,如果使用快排找第k大的數,那麼時間複雜度肯定和k無關的,再者有aT(n/b) O(n^d)這個公式:子問題的重複次數是1,因為只選擇一側繼續選pv值做劃分,子問題的規模是一個概率值,應該是1/2,b為2,d應該是1,這就是每次劃分需要遍歷陣列。那麼logba = 0 < d –>O(logN)

https://blog.csdn.net/wangbaochu/article/details/52949443

7 問了雜湊實現的方法有哪些,解決雜湊衝突的方法有哪些。

    基礎題。

後面就開始魔幻問題了,畢竟自己沒有做過專案,答題基本全靠想象

8 qq使用者ID是32位的整數,現在要你儲存所有使用者的狀態,狀態僅有線上和不線上兩種,日均線上使用者數量大約2億。

    完全不知道怎麼去思考,自己知道的所有和大資料相關的基本就只有堆排序和布隆過濾器了,一時腦抽就問是不是布隆過濾器,面試官微笑說那你就講講吧,可是自己對布隆過濾器也只是瞭解,從來沒用過,面試官等我說完就問我,那你資料怎麼刪除。然後就投降了。

    自己下來之後看了看,應該是bitmap吧,因為只有兩種狀態,所以1bit就可以表示一個使用者的狀態,對於40億的使用者量,需要 5億位元組的記憶體,就是2^29,500MB吧。目前只能這樣了。

9 領導讓你給微信搶紅包增加一個限制功能:每個使用者每分鐘最多搶5個,問每個使用者的資料結構什麼樣,用什麼結構儲存,怎麼避免記憶體的浪費。

    自己從來沒遇到過,一開始連1分鐘怎麼確定都不知道,居然回答了timer()定時器和中斷函式,面試官哈哈大笑…畢竟自己做硬體的,思維還是轉變不過來,後面一想,額,sys_time可以查的,那果斷加一個時間戳額。所以每個使用者的資料就是

char num; 表示搶了多少次紅包。

sys_time; 存放系統時間。

int User_ID;

後面自己慌慌張張,亂說一通,最後答道了用map存放資料,key是User_ID。

邏輯是第一次搶紅包的時候(map中沒有)就記錄一個sys_time(),然後num 。

再搶紅包的時候查詢到使用者ID對應的節點,然後比較sys_time()是否到了5分鐘,如果到了,那麼num=0,如果沒到,num!=5,還可以搶,num ,如果num==5那麼不能搶。

然後面試官問那麼過期的資料如何刪除呢,然後就懵逼了。

自己下來後想了想,或許可以用hash map的方法。維護60個map,新增的參加搶紅包的使用者資料輪流儲存在map中,根據sys_time()%60,決定儲存在哪一個map,然後每隔一秒就clear()一個map。

舉例:

在sys_time() == 7.00秒的時候(具體可能用定時器實現吧),清空7號map的所有資料。

在sys_time()==7.20秒的時候,有一個使用者搶紅包了,那麼,就在0-59號map中找,如果找到了,就判斷num。如果沒找到,那麼就插入7號map。

在sys_time()==1分鐘 7.00秒的時候,刪除7號map中的所有元素,表示1分鐘已經到了,num限制解除。

這樣的話精度是1s,也就是你在0.99秒第一次搶紅包(存在0號map中),只需要等待59.01秒就可以再次搶紅包了。

 每個節點儲存
int User_ID; //做key值
char num; //表示剩餘的搶紅包次數
時間戳sys_time(); //第一次搶紅包時候的時間

然後就結束了,最後面試官建議我繼續回去做硬體。