- 求第k大數(shù)字
- 采用快速排序，每次去掉一部分，時(shí)間近似O(n)
- 使用最小堆（堆頂元素為最小斑鼻，若數(shù)比堆頂大，則替換之）橄碾，n*logk
最長(zhǎng)公共子序列（不需要連續(xù)）
動(dòng)態(tài)規(guī)劃
假如s[i] == s[j]卵沉，dp[i][j] = max(dp[i-1][j-1] + 1, max(dp[i][j-1], dp[i-1][j]))
否則dp[i][j] = max(dp[i][j-1], dp[i-1][j])最長(zhǎng)公共子串（連續(xù)的）
動(dòng)態(tài)規(guī)劃，和2類似法牲，不過(guò)dp[i][j]表示以i史汗，j結(jié)尾，然后再遍歷一遍求最大
延伸：k個(gè)字符串的最長(zhǎng)公共子串（后綴數(shù)組）淘寶有很多商品（幾億個(gè)）拒垃，每天每個(gè)商品都有一定點(diǎn)擊訪問(wèn)量停撞，要求出點(diǎn)擊量前100的商品（考慮離線處理、在線處理悼瓮，用串行的算法怎么做戈毒，并行的怎么做，借助一些大數(shù)據(jù)處理框架如MapReduce怎么做横堡，最好都聊一聊）
推薦算法：
關(guān)于相似度的計(jì)算有很多種方法埋市，比如常用的余弦?jiàn)A角，歐幾里德距離度量命贴，皮爾遜相關(guān)系數(shù)等等道宅。
-
利用用戶行為的數(shù)據(jù)
協(xié)同過(guò)濾算法包括基于用戶和基于物品的協(xié)同過(guò)濾算法。- 基于用戶的協(xié)同過(guò)濾算法
在上面求相似鄰居的時(shí)候胸蛛，通常是求出TOP K鄰居污茵，然后根據(jù)鄰居的相似度權(quán)重以及它們對(duì)物品的偏好，預(yù)測(cè)當(dāng)前用戶沒(méi)有偏好的未涉及物品葬项，計(jì)算得到一個(gè)排序的物品列表進(jìn)行推薦泞当。 - 基于物品的協(xié)同過(guò)濾算法
跟上述的基于用戶的協(xié)同過(guò)濾算法類似，但它從物品本身民珍，而不是用戶角度襟士。比如喜歡物品A的用戶都喜歡物品C，那么可以知道物品A與物品C的相似度很高嚷量，而用戶C喜歡物品A敌蜂，那么可以推斷出用戶C也可能喜歡物品C。
- 基于用戶的協(xié)同過(guò)濾算法
利用用戶標(biāo)簽數(shù)據(jù)
基于標(biāo)簽推薦最簡(jiǎn)單的例子比如：統(tǒng)計(jì)一個(gè)用戶最常用的標(biāo)簽津肛，統(tǒng)計(jì)每個(gè)物品最常被打的標(biāo)簽，然后兩者通過(guò)一定的關(guān)系推薦起來(lái)汗贫；當(dāng)然也可以展現(xiàn)標(biāo)簽云身坐，讓用戶點(diǎn)擊自己感興趣的標(biāo)簽秸脱，然后依此個(gè)性化推薦。利用上下文信息（時(shí)間上下文部蛇、地點(diǎn)上下文）
比如看視頻摊唇，用戶是上班時(shí)間看還是下班時(shí)間看，在家里看還是在單位看涯鲁。利用社交網(wǎng)絡(luò)數(shù)據(jù)
比如利用facebook的好友信息給用戶推薦好友喜歡的視頻巷查。
整個(gè)架構(gòu)大概分為UI，推薦系統(tǒng)抹腿，日志系統(tǒng)岛请，用戶行為日志存儲(chǔ)系統(tǒng)。
用戶--> UI -->日志系統(tǒng)--> 用戶行為日志存儲(chǔ)系統(tǒng) --> 推薦系統(tǒng) --> UI -->用戶
推薦引擎大概分為以下幾個(gè)步驟：
- 生成用戶特征向量
- 用戶行為的種類（比如瀏覽物品警绩，收藏物品）
- 用戶行為產(chǎn)生的時(shí)間（近期買過(guò)還是很久以前買過(guò)）
- 用戶行為的次數(shù)
- 物品的熱門程度（可能只是跟風(fēng)崇败，不能代表用戶個(gè)性）
特征-物品相關(guān)推薦
根據(jù)離線的相關(guān)表得到對(duì)應(yīng)推薦的物品過(guò)濾模塊
一般過(guò)濾掉以下部分：
- 用戶已經(jīng)產(chǎn)生過(guò)行為物品
- 候選物品以外的物品（比如用戶選了價(jià)格區(qū)間）
- 某些質(zhì)量很差的物品
- 排名模塊
- 新穎性排名
- 多樣性
- 時(shí)間的多樣性
- 用戶反饋
