Try   HackMD

System Design

system design prep:
最开始刷了 grokking the system design interview， 面了一两轮后觉得这个教程真是扯淡， 花了一周时间看了 Design data intensive application， 非常有启发。在大佬指点下看了很多公司的blog和tech talk， e.g, datadog, uber, airbnb… 收获也很大

system design 里面也有很多经典问题， 比如 twitter time line, whatsapp, kv store. etc, 有很多教程上都写的比较完善了， 剩下的就是结合面经看 company specific system design，这些可以看相关公司的tech blog 或者 medium:
比如 Uber, Lyft 常见的

ML round

在这一轮，你80%会被问到设计一个推荐系统，剩下的20%如果你熟读ML课本不会有问题(如果你申的职位是research或者特别精专的Deep Learning岗另说), 推荐系统的雏形是Netflix Recommender System competition，
不了解的可以搜一下，基本这个问题可以抽象为你有很多user，很多item，一定的历史数据(user买item后的rating)，现在你要决定推荐哪些新的东西给每个user

具体到你被问的问题，可能会有一定的变种，举几个例子

  1. Yelp饭馆的推荐，涉及到了geolocation information
  2. Facebook Newsfeed推荐，涉及到了不同user之前的networking
  3. Ins Story推荐，每条Story是独一无二的并且是有时间性的
  4. Spotify音乐推荐，怎么把音乐做个embedding

这里我希望可以factor out这些问题相同的因子，你会发现每道题除了微妙的不同以外，其它基本可以按照一个套路来
首先对design轮，本来问题就 supposed to be vague，你会发现很多东西没有定义，而面试官也会希望你来导向整个流程
所以切记一定要 be organized !!(划重点)
我们给面试官的印象不仅仅是technical competency，同样作为一个人，我们的思想是make sense的(划重点)。
这个面试，我的建议是，稳妥起见，从基础模型开始，解决问题优先(划重点)，适度go deeper，如果不必要不要秀fancy模型

我一般是分成四个部分

  • I. information and data：5分钟
  • II. feature engineering：10分钟
  • IV. model：15分钟
  • V. evaluation：5分钟

I. Information and data

如果你被问到的问题就是 现在给你一个spotify，请给我设计一个音乐推荐系统, period.
你一定说巧妇难为无米之炊，我首先需要历史数据。
基本上最能用的历史数据可以被再细分为三个主要的table

  1. interaction table or log table, 即每一个点击，每一个购买，每一个评价，都是以一个(user, item) pair的格式记录下来的
    (1) 每一条记录，是可以包含some contextual information的，比如时间戳，音乐听了多久，购买花了多少时间，等等，要动脑筋想想什么信息是有用的，尽量多log下来
    (2) log可能不止记录了购买信息，还有查看信息，scroll down看到但未被点击信息，都是indicate different level of preference
  2. dimension table: user, 即每一个user是有自己的metadata信息的，比如年龄，性别，地域等等demographic信息
  3. dimension table: item, 和上面一样，只不过是item的metadata
    我一般不会在这个stage对item做embedding即向量化，而是存最原始的raw数据

II&III. Feature Enginneering + Modeling

之前把这两个分开的原因是面试官可能会分别问这两个的问题
但实际上，你的feature engineering一定是要为model服务的
这里给出我经常会使用的几种简单的推荐系统模型

  • (0). rule based model (难易程度1, make sense程度5)
  • (1). 转化成classification/regression 模型 (难易程度2, make sense程度5)
  • (2). matrix factorization (难易程度3, make sense程度2)
  • (3). facorization machine (难易程度3, make sense程度3)
  • (4). wide and deep learning (难易程度4, make sense程度4)

我个人最喜欢的，而且觉得比较稳妥的是(0)+(1)，说的好是绝对没问题的
至于(2)(3)(4)网上有大把的资料，但你不能看一篇paper或者video就上了，一定要谨慎想好可能遇到的问题，比如

  • matrix factorization可能会问你怎么加进user and item metadata, 你的retrain plan是什么
  • wide and deep learning可能会问你deep part的神经网络怎么搭的，为什么等等。一句话，追求fancy就要担着玩儿大了的风险

对于(0)来说，作为一个base model有提到的价值，在处理cold start的时候是很有用的，但不可恋战一定尽快带过, rule无外乎根据两个heuristic:

  • 对user_i 找到和ta类似的user，看看别人买了什么，推荐给ta
  • 对user_i买的item_j, 找到类似的东西，推荐给ta
    这里面涉及的知识点就是怎么定义“类似”，即需要一个distance metric，这点大家去网上找吧，很多的similarity metrics

重点是(1)，这里依然拿spotify music 推荐当例子那么如果转化成一个binary classification问题，我们就要拿出所有的music listening history log, 即tuple of (user, item, context)，
比如(berserker888, Titanium, 2019-01-01:12:00:00)当做我们的positive case，即y值为1
那我听了这一首歌，就没有听剩下的所有歌，那我在这个context下所有没听的歌理论上都是negative case, 这里要知道unbalanced data的危害以及一种random sample negative case的逻辑。
同样可以把问题转化成regression问题，就像之前说的，我看了没有听，我听了，和我压根没看的东西代表着3种preference level.

下面简短启发一下feature的展开，user, item, context都是需要vectorize化的
最简单的就是直接join user, item dimension table拿到metadata。
但有的时候比如item是视频图像或者自然语言，就需要我们通过一些方法，比如pretrained deep learning model take bottleneck layer，请大家自行搜索word embedding和image embedding
稍微tricky一点的是contextual feature，这里可能需要aggregate log来达到目的，我建议大家提前想好一些feature，给一个例子：has user_i listened to item_j's category in the past week at night?

IV. Evaluation

一定要区分statistical metric和business metric
前者是你训练模型时候定义的metric，主要用来tune hyperparameter的，比如accuracy, F1-score…
后者定义你的模型是否有意义的metric，比如推荐歌单平均听的时长
一般后者意义更大，更会被问。因为是无法直接直接optimize的，只能通过ab testing才测试，所以也有可能会被问到一点点experiment design的知识

写在最后的话：
Machine Learning是一个积累的过程，在上述流程的任何一个部分，面试官都可以插入问题来看面试者的水平，所以还是要多看多做多学
话说我也只是一个没几年经验的MLE，站在一个peer的角度，为还没进门的人提供点信息，还请各路大神轻踩.

ML round回答模版

面试就是要在有限的时间里，尽量把自己懂的东西都让面试官看到。你懂那么多模型理论，怎么才能让面试官也觉得你很懂呢？要有策略，有重点。什么样的策略好用呢?
抓住核心，兼顾深度和广度。

ML design的核心，万变不离其宗，本质都是train一个model来实现某个task，比如prediction/ranking/classification。有经验的人都知道，实际上给定一个问题，好用/常用的solution基本上只有很少的几种。所以想要显得你懂很多，不仅要从深度上要cover这几种solution，更要从广度上显示你有end-to-end的experience。具体怎么实行呢？

Step 1：理清核心问题。

  • 不是每个面试官都能用一目了然的方式提问。有的面试官水平差，自己也理不清问题的逻辑。遇到问题很模糊的时候，要尽快理清核心问题。抽象出来，可用信息/输入有哪些，要求的输出是什么样的，这是一个classification的问题，还是regression，还是relevance/matching/ranking？理清楚核心问题，就能判断需要train哪种类型的model，整个pipeline就很容易flow out了。

Step 2：理清核心问题后，请白板画图，最好是一个diagram。

有前后逻辑关系的work flow最能展示你思维的广度。

  • 在理清核心问题后，具体分析model之前，先把solution的大体框架在白板上画出来。目的是让整个讲解过程逻辑清晰。按照逻辑的先后关系，typical的解答逻辑包括这几大块：training/testing data, input representation, model, output, evaluation, optimization(parameter estimation). 我一般从model开始画，一个框框摆在中间，这是核心。然后画上游，下游。在这里，只要把框架搭好，告诉面试官，我要讲这些内容，面试官有个心理准备，就可以开始听你讲课了。

Step 3：讨论model。

为什么我用“讨论”这个词？因为能seriously被考到design的人，都不是entry level。对于更senior的人来说，面试的最好氛围不是你问我答，而是我把我知道的都讲给你听，你看看还有什么想听的。所以你讲的过程中要和面试官互动。要看ta的反应，哪里皱眉了，哪里表情不轻松了，你就要停下来，问他Is there anywhere that you want me to talk more? 这给面试官一个机会表达自己，也帮助你更好的address面试官的考点。

  • Model方面，针对task 的类型，propose哪些model可用，把你能想到的都name出来。选择2-3个常用的，比较优劣，然后选择一个大家常用的。不同的model，输入输出可能不一样。所以决定了model，其他的component就很自然的浮现了。这一步，要在你的model框框里，把关键的component列出来，说明它们之间的关系。分析各个model的优劣，可能需要在旁边额外画出model的visualization，比如说到dnn，你就画几层multi perceptron layer，再顺便提一下SGD和ADAM。说到用logistic regression 做classification，你就顺手写一下log likelihood，显得你optimization也很懂。说到regularization，你就写写L1 norm和L2 norm。显示你的深度，主要就靠这一步。

有时候面试官会告诉你ta想用的model，你就按照ta的来，你也可以在讲解完几个model的优劣后，根据经验自己决定一个model。

Step 4：输入输出。

  • 前面一步把model定下来。根据不同的model，解释一下input 和output的format。比如dnn就有one-hot encoding，这种最好用上embedding，顺便讲一下有什么好处。比如需要自己设计feature的，就重点讲一下有哪些常用的feature。

到此，这轮面试的核心你都cover住了，可以得到60分。Step 5和step 6 是能区别ML**和ML老手的部分。如果你做了，答的一般可以再拿20分，答的好可以再拿40分。有ML经验的人在这两个部分，一定要把握。

Step5：data。

不讲data的ML design是没有灵魂的。

  • 从2个方面identify data：training + label, testing + ground truth。1. propose可用的data 来源+data format。2. how to preprocess data -> make training data, how to build/create label, etc. 完成建模。根据具体的问题，data的solution可以非常creative。甚至Training data和testing有时候不一致。比如language model方面的问题：decide一个twitter post是什么语言？training 可能就用wikipedia，testing则可以收集user data或者platform-specific的data，这时候也需要指明testing如何get ground truth(testing label).

Step6：evaluation

  • evaluation很容易讲，重点在metrics。主要有三个部分，一个是ROC/AUC curve。第二个是domain specific metrics，比如广告就有CTR。第三个是confusion matrix，重点是从它延申出来precision/recall/accuracy等等对你的solution重要的metrics。

最后再说几个加分项：

  • 熟练的讲解参数估计，能显示solid的数学背景。讲估计参数可以用哪些optimization的方法(MSE, loglikelihood+GD, SGD-training data太大量, ADAM-sparse input)，比较优劣.
  • 解答逻辑的每个部分，尤其是你熟悉的方面，要自己主动讲，因为每个部分都很重要。别问面试官想不想听你说，除非他明确制止你讲(如果面试官说不用讲，你就失去了一个展示自己的机会)。正确的做法是，lead conversation，一边白板画框图，一边告知面试官我要讲XXX这几个部分。整个design讲完了以后，再问面试官：Is there anywhere that you feel I missed?

The last but not the least: 每一步都尽快和面试官确认，move on，不耽误时间。想要在45分钟之内把面试官讲的心服口服，这么多个component，每个只有很少的时间。

ML 解题思路

  1. 结构化表达:
    通过结构化的表达来让答案显得很有逻辑。结构化表达，针对一个问题，一般讲三点答案，逻辑上依次有递进的关系，这样就会显得你逻辑清楚。超过三点，听的人容易lost，所以也没必要。
    比如被问了一个design的问题，答案比较复杂，有很多部分。回答的时候，第一句话先说，这个问题可以从2(数字)方面来考虑：用户和系统。用户这方面有2(数字)个solution，系统这方面有3(数字)个solution。因为面试官不知道你想讲什么，在讲细节之前，先把框架说出来，这样有助于面试官follow 你的逻辑，即使中间在细节上仔细询问你，他也知道你后面还有内容要讲，会配合让你讲完。

  2. 讲自己做过的项目，怎么讲？
    讲自己的项目时，主题最好和这个组的方向相关，技术越新越厉害，越好。出于NDA，最好避开自己在当前公司的工作。雷区：这样可能会导致只能讲好几年前的工作和技术。怎么解决呢？在报告的结尾，给一个rethink，讲两部分。

    • 第一，反思如果现在做同样的问题，哪些地方可以提高。[重点显示你的见识提高了，不是反思你的缺点]
      分三个部分：新技术[比如以前用 logistic regression，现在可以用 deep learning/LSTM]，data size scale up[比如以前只有10k的data，现在是100M，可以使用更复杂的模型]，system[single pc -> distributed system/GPU，training could be paralleled or in the cloud. 更advanced approach to collect labels，比如大公司都会有自己的crowd sourcing judgment platform]。
    • 第二，概述一下，你在目前的职位做过的工作，使用了哪些最新的技术，这样显得你的skillset在与时俱进，没有过时。

  3. It is your opportunity to shin! 你会被要求讲自己的经历，可能很多次，面试官根据你的经历来问问题。在讲经历的时候，突出哪些关键字和技术？一是和对方相关，二是新技术，三是显得你水平高的内容。当然一定要是你熟悉的，如果你被问到什么，答不上来，会特别减分。

  4. 讲到使用哪个model的时候，列举2-3个相关的model，答案的重点是讲一下各自的优缺点，以及当前问题的特质，基于这些比较，从而决定选哪一个。

  5. Lead conversation，主动推进谈话。比如讲完一段话或者回答了一个问题，主动询问：Does it make sense to you？比如讲一个复杂的系统之前，先告知对方：I’m going to talk about a few components. If you feel interested in some particular ones, you can point out and we’ll discuss more over them.

  6. 会沟通。有些问题问的非常模糊，可能是面试官故意的，也可能是面试官的表达能力差。这种时候，通过rephrase问题 + make concrete example，来主动probe面试官，去除面试官自己的误差，clarify需求。

  7. 会接话，能听出面试官的concern，不要等面试官停下来就接过话题，address面试官的concern。有的面试官在交谈中，不是每个问题都会explicitly的问，然后停下来，然后等你答。你要能在交谈中，听出弦外之音的问题，立刻想答案，然后看准时机，当机立断的接过面试官的话题，给出让人满意的答案。

  8. Stress test。碰到面试官很不友善的时候，没法develop一个很好的答案，要坚持the principle of problem solving: Break down problem to solvable subtasks. 比如被问到这个问题“你deliver了一个ML的产品/系统，用户使用以后，汇报系统的accuracy 远低于你自己test 的accuracy，哪些方面可能出问题了？要求不能看log。” 从problem solving的角度来看，整个系统有两个element：你的ML系统，用户的application。每个element都可能出问题。那么把大问题break down成两个element自己的问题+element之间衔接的问题，就是一个很好的答案。两个element自己的问题包括：产品的问题(overfitting，training data coverage，etc)，用户的application的问题(使用产品的domain和develop 产品的domain不一致， 使用方数据的distribution和training data不一致，etc)，用户的问题(没有按照设计的方式来使用系统，measure的方法不对，使用了和开发方不一样的metrics，etc)。

Last changed by 
 
Shuai Tang
0
1390
Published on HackMD