面试准备

1. 求第k大数字

• 采用快速排序，每次去掉一部分，时间近似O(n)
• 使用最小堆（堆顶元素为最小，若数比堆顶大，则替换之），n*logk

2. 最长公共子序列（不需要连续）
   动态规划
   假如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])

3. 最长公共子串（连续的）
   动态规划，和2类似，不过dp[i][j]表示以i，j结尾，然后再遍历一遍求最大
   延伸：k个字符串的最长公共子串（后缀数组）

4. 淘宝有很多商品（几亿个），每天每个商品都有一定点击访问量，要求出点击量前100的商品（考虑离线处理、在线处理，用串行的算法怎么做，并行的怎么做，借助一些大数据处理框架如MapReduce怎么做，最好都聊一聊）

推荐算法：

关于相似度的计算有很多种方法，比如常用的余弦夹角，欧几里德距离度量，皮尔逊相关系数等等。

• 利用用户行为的数据
  协同过滤算法包括基于用户和基于物品的协同过滤算法。

  • 基于用户的协同过滤算法
    在上面求相似邻居的时候，通常是求出TOP K邻居，然后根据邻居的相似度权重以及它们对物品的偏好，预测当前用户没有偏好的未涉及物品，计算得到一个排序的物品列表进行推荐。
  • 基于物品的协同过滤算法
    跟上述的基于用户的协同过滤算法类似，但它从物品本身，而不是用户角度。比如喜欢物品A的用户都喜欢物品C，那么可以知道物品A与物品C的相似度很高，而用户C喜欢物品A，那么可以推断出用户C也可能喜欢物品C。

• 利用用户标签数据
  基于标签推荐最简单的例子比如：统计一个用户最常用的标签，统计每个物品最常被打的标签，然后两者通过一定的关系推荐起来；当然也可以展现标签云，让用户点击自己感兴趣的标签，然后依此个性化推荐。

• 利用上下文信息（时间上下文、地点上下文）
  比如看视频，用户是上班时间看还是下班时间看，在家里看还是在单位看。

• 利用社交网络数据
  比如利用facebook的好友信息给用户推荐好友喜欢的视频。

整个架构大概分为UI，推荐系统，日志系统，用户行为日志存储系统。
用户--> UI -->日志系统--> 用户行为日志存储系统 --> 推荐系统 --> UI -->用户

推荐引擎大概分为以下几个步骤：

1. 生成用户特征向量

• 用户行为的种类（比如浏览物品，收藏物品）
• 用户行为产生的时间（近期买过还是很久以前买过）
• 用户行为的次数
• 物品的热门程度（可能只是跟风，不能代表用户个性）

2. 特征-物品相关推荐
   根据离线的相关表得到对应推荐的物品

3. 过滤模块
   一般过滤掉以下部分：

• 用户已经产生过行为物品
• 候选物品以外的物品（比如用户选了价格区间）
• 某些质量很差的物品

4. 排名模块

• 新颖性排名
• 多样性
• 时间的多样性
• 用户反馈