datadog新鲜面经

system design

设计mint.com


problems coding:

第一题：地里高频的logs and queries match

设计一个queries search object，它每次读取一行信息string。当这个string格式是
"Q: hello world" 表示这是个queries， 内容是 hello world
如果string 格式是 “L: hello morning world”那么表示这是个log， 内容是 hello morning world。 每次读取query要保存query内容并赋予query id， 每次读取log要把所有在这个log中出现的query id给出来。 这里出现的定义是如果query的每一个word都在log中出现了。注意这里有可能要求log中相同word的出现次数要多于或等于在query中出现的次数，也可能不要求次数，word只要出现即可。但不管怎样，在log中的每个word都能和不同的query中的word重复而独立的匹配。解法是用地里之前提到的reverted index 去记录每一个word在哪些query中出现了，然后遇到log把每个word带入reverted index 去重建 qid-> words list 结构然后和那个qid的word list相比较。

这里列一下我的解法代码：

```

from collections import defaultdict, Counter



class LogsAnd

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

                  result.append(cq)
            print("recieve log and the relevant queries are {}".format(result))
```
注 这个代码是对应于需要考虑相同word在每个query中出现次数的情况，如果不需要考虑出现次数，那么做相应简化即可，思路是一样的。

第二题： implement a buffered writer: 这个writer存在一个buffer 和可设置的最大buffer size，这里的buffer工作方式是
1， 读取的数据先存在buffer里面不写入硬盘
2， 当buffer里的数据量达到buffer size的时候，一次性清空所有buffer内的数据到硬盘中。如此往复。

讲讲极高频的mint.com design，

以下仅代表我个人准备的内容，仅供参考, 反正我遇到的面试官在我说了以下一半内容不到的情况下（时间关系）就让我过了。

functional 和 nonfunctional requirements

functional requirement:

1, user bind account to financial accounts
2, going to the target financial accounts to get users' expenses information
3, categorize these expenses records to several buckets types and calculate total amounts of each for each month
4, users can read monthly report about their expenses distributions
5, if users spend more than the threshold defined, it will notify the users.



non-functional:

available 10millions users, read 1/day and 10expenses/day, 100millions write/day 1200 rps, 1kB/write, 100GB/day to storage  3T/month distrubuted DB and multiple servers
reliable
performance: fast computation and fast data receiving/writing low users waiting time for a report
scalable:
security


我准备的图见附件

system design面试60分钟，留给你讨论题目的时间只有45~50分钟。必须在10分钟之内讨论完functional， nonfunctional requirements和back envelope calculation。calculation不需要很精确，只要通过每天/每月增加的storage 和 RPS证明必须要用distributed system面试官就认为你上道了。然后你必须在另外20分钟内画完所有functional requirement的service graph和列出来Data Storage里面要存储的数据的大体内容和互相关系。这个题我列的data storage conent就是 users table，users finance accounts table, users expenses records from bank accounts, reports DB, (如果你在reports DB 和 users expenses raw data 之间加一个aggregated data by user,month,expenses bucket 作为中间的dynamic data storage用作动态生成功能更多的reports的作用那也很好)。 然后你必须有最后15到20分钟讲讲整个系统的bottle neck，怎么优化，或者对于data storage你怎么选型，最好能把理由归结到你之前列的non-functional requirements上。这里面可讲的部分包括：

1， scheduled expenses records crawling 和 data aggregation calculation是 batch job 还是 streaming job
2， 根据data storage内容的性质分析是用SQL还是nonSQL，并列出理由（我在附件中写的是 users， finance accounts data 用 SQL。 users expenses raw data用 BLOB like s3, reports DB 用 nonSQL mangoDB）
3， 讨论系统的性能瓶颈，这里可以是reports DB的读取，也可以是持续读取users expenses来计算更新reports，取决于你之前back envelope number的设定。而writing如果是batch job 可以讨论会在writing的时候，怎么缓解对reading的影响，streaming的话writing强度如何等等，然后就自然引入下面几点的对reading和writing的优化。
4，reports DB用partitions做horizontal sharding, 讨论用user id做partition key。然后谈谈怎么做partitions load balance to avoid skewed hot data, 然后提到consisitent hash之类的。然后对每一个partition 加多个read replicas， 然后谈谈这个 read replicas和 master node之间怎么data sync. 这个例子你可说expenses reports不需要很强的最新数据同步性，所以可以用async write更新read replicas来增加writing的performance, 如果你认为writing performance不重要因为writing not intensive，而users reading latest and consistent reports 更重要那就说要用synchronous way去更新read replicas

5， 添加cache缓存最近读过的reports

6， 讨论是否可以通过区分active users 和non-active users来采用不同的reports生成策略。因为active users的data reading intensity更大，那么是否可以设batch job主动生成reports以减少用户request等待时间？non-active users 几乎很少request reports，是否可以不主动生成reports减少系统资源开销？这样可以通过有request的时候临时生成reports来应对。那么由此带来的用户等待时间极其长怎么办，可以引入第7点

7， display reports service 接到request，可以先查看cache，如果cache没有则用async模式把request放入队列中由reports query/generation service读取队列。这样display reports service可以先返回客户端消息表示reports正在生成。reports query/generation service读取request之后先查询DB是否存在reports，如果没有则现场query aggregated dataset去生成reports存入DB，存入cache然后返回客户端reports或者用另一个队列把消息送会给display reports service（display reports service这时候需要保持与客户端的long term TCP链接？），或者用另一个notification service去通知用户reports已生成。这些各种options都可以讲讲去实现异步生成reports的功能。

8， 出于security（non-functional requirements），可以设定在用户添加或查看银行账户的时候，需要额外的认证。可以讲讲怎么设计一个给用户手机发送passcode然后让用户输入passcode来认证用户，然后在front end service生成一个加强版短期有效的cookie的方案。我随便写了一下可见于附件图中。

9， 讲一讲怎么monitor 你的DB partition nodes， 各个servers去异常检测，比如让这些node每隔10秒1分钟之类的发送 heartbeat， CPU usage， memory usage rate给monitoring server，如果需要scale怎么办，如果node not responding怎么办，然后就可以讨论一下DB nodes replicas re-election来生成新的master nodes， hot ready servers fail-over backup, 怎么scale DB partitions， replicas， 和 service servers之类的

10， 因为datadog就是做monitoring的，它很希望你说一说给这个系统设计一个logs based monitoring system架构。这个内容我有被面试官主动问道，所以我就在附件中附上了monitoring and alerting system架构参考图。

这10点只是我认知范围内可以谈的内容的举例。相信大家还会有其他很好的提高nonfunctional requirement的点可以详细谈。实际上因为时间关系你不可能谈这么多点。我的经验是如果你谈到了3个点，那就很有可能过关了，如果你谈了4到5点，那你就相当稳了。

最后说一点我的感受吧。

1， 多看看 youtube上的interviewing.io 这个频道 https://www.youtube.com/@interviewingio，FLAANG面试官真人和训练者实战，非常权威非常有帮助。

2， the easiest way to sound like a smart guy in system design interview: 画图的时候直接用这个模版 client -> load balancer -> rate limiter(prevent malfunctional users sending abnormally high volume of requests) -> front end servers(act like api gateway，authentication etc) -> each service components based on your functional requirements -> DB 无脑用，百利而无一弊。

3， 不要有题家思维认为system design会有一个在面试官脑海中的标准答案，而我要做的就是要揣测这个标准答案然后回答出来让面试官满意。实际上面试官没有标准答案，连requirement是什么都是高度开放的。面试官就是想让你自己折腾，想看你对系统设计的理解深度怎么样。你要做的就是自己假设一个requirement，然后自圆其说为了达到这个requirement该怎么设计系统，这个系统的瓶颈在哪儿，怎么改进。面试官的评判标准就是看你是否能利用系统设计的知识对你自己提的假设所产生的难点提出一个解决方案，并且这个解决方案逻辑自洽，符合行业广泛共识。

4， 不要问面试官太多requirements问题，自己假设自己说。不要花太多时间在requirements gathering和back envelope data calculation上。不要怕自己不和面试官沟通自说自话导致偏离了面试官的本意。因为面试时间非常非常有限，时间过得很快，你必须在10分钟之内进入画图设计阶段才有充足时间谈细节，谈瓶颈，谈优化，而这些才是面试官真正想听的。面试官真的没有太多预设的本意藏着不说故意等你问。你尽管假设然后往下说根据这个假设自己的想法，如果面试官觉得你偏离了其预设的内容TA会自动纠正你的。你要做的就是如果TA明确指出你的方向之后，不要和TA犟，接受这个设定，然后在此基础上继续假设继续说，直到下次TA纠偏你。面试官不会因为纠偏你而扣你分，因为考点根本不是猜requirements是什么，考点永远是你针对你提出的requirement有什么好的system design解决方案。当然面试官也有可能会challenge你提出的解决方案而打断你，那你要判断是否是你的设计不合理或者是你也可以坚持己见用自洽的逻辑和知识储备捍卫你的观点，这也可以是亮点，当然取决于面试官和你自己的硬实力了，就不多说了。

5， mock interview 真的很重要，对于我们这种英语不是母语的人来说更重要。看人吃豆腐牙快，自己上了才知道原来这么不顺手。强烈推荐去一些付费的找真实FLANNG面试官mock interview的平台练练。你即使不用和真人mock interview也要自己找个没人的地方假设处于面试中把整个流程走一遍，一切和真实面试一样去画图，对着图大声说，然后掐时间算好，就能发现原来自己有这么多问题之前都没意识到。然后结合网上mock interview的真人视频（比如上面第1点的）去听听面试官给训练者的反馈，反复自己模拟练习，会很有帮助。

面筋中常见非LC题目的代码。解法是根据之前帖子的讨论和自己的理解：

Buffered File
# 注意这个buffer是达到buffered threshold之后一次性清空所有buffer写入硬盘的情况

class BufferedFile:
    def __init__(self, maxBufferedSize):
        self.maxBufferedSize=maxBufferedSize
        self.diskStorage=[]
        self.buffer=[]

    def write(self, content):
        for ch in content:
            self.buffer.append(ch)
            if len(self.buffer)==self.maxBufferedSize:
                self.flush()

    #面试的时候会给你专门的dummy writing to hard disc API，只要调用就好
    def flush(self):
        self.diskStorage.extend(self.buffer)
        self.buffer = []


CoinCounts 的各个种类coins分别的个数
# 给你一个数组的硬币面值种类，求组合一个target面额的最少硬币个数方案下各个种类硬币数。
# 如果给你的硬币种类最小单位是1，可以用贪心算法。但是如果没有1，那贪心算法未必可行，必须用heuristic DFS,即用贪心算法回溯性的尝试。
class CoinCounts:
    def getCoins(self, coinTypes, value):

        def helper(target, coinIdx):
            if target==0:
                return [0]*len(coinTypes)
            if target<0:
                return None
            if coinIdx<0:
                return None
            choices = target//coinTypes[coinIdx]
            for cnt in range(choices, -1, -1):
                rest = helper(target-coinTypes[coinIdx]*cnt, coinIdx-1)
                if rest is not None:
                    rest[coinIdx] += cnt
                    return rest
            return None

        res= helper(value, len(coinTypes)-1)
        if res:
            return res
        else:
            return []


delete directories

class FileSystem:
    def __init__(self):
        pass

    def findList(self,path):
        pass

    def delete(self, path):
        pass

    def isDir(self, path):
        pass

fs = FileSystem()
def deleteDirs(path, fs):
    if isDir(path):
        children = fs.findList(path)
        for child in children:
            deleteDirs(child, fs)
    fs.delete(path)

high performance filter
  
    有一个数据流会进来一些tags比如
['apple, facebook, google', 'banana, facebook', 'facebook, google, tesla', 'intuit, google,
facebook']
然后有一个filter list， 根据filter list输出这些Tags的补集
比如filter by ['apple']那么return ['facebook', 'google'] (只有第一个里面有APPLE）
比如filter by ['facebook', 'google']那么return ['apple', 'tesla','intuit']

有人给出用reverted index。我就按照这个思路给一个解法：

class HighPerformanceFilter:
   
    def __init__(self):
        self.tagsList = {}
        self.revertedIdx = defaultdict(list)
        self.id=1

    def addTags(self, tagsStr):
        tags = list(map(lambda x: x.strip(), tagsStr.split(",")))
        self.tagsList[self.id]=tags
        for t in tags:
            self.revertedIdx[t].append(self.id)
        self.id+=1


    def filter(self, inputTags):
        res = []
        idxGroups = defaultdict(list)
        for tag in inputTags:
            if tag in self.revertedIdx:
                for tid in self.revertedIdx[tag]:
                    idxGroups[tid].append(tag)
        for idx in idxGroups:
            targetSet = set(self.tagsList[idx])
            allIncluded=True
            for ctag in inputTags:
                if ctag in targetSet:
                    targetSet.remove(ctag)
                else:
                    allIncluded=False
                    break
            if allIncluded:
                res.extend(targetSet)
        return res


Flights Vacations

# 地里汇报这题没有LC中的城市间flights约束，默认所有城市都有航班，所以比较简单。但是有一个follow up： 要求总flights最少。这哥么说的很简单，没有继续解释。所以我只能猜测他说的是指还是要求vacation days最多，但是如果有两个方案vacation days一样多，那就选需要flights少的那个方案，并返回总vacation days 和 相对应的flights counts。 以下代码基于这个假设。

class Solution:

    def maxVacationDays2(self, days: list[list[int]]) -> (int, int):
        # dp{week}[cityIdx]=(vday, flight) compare: (vday1, flight1) (vday2, flight2) if vday1>vday2: 1
        # if vday1<vday2: 2  if vday1==vday2 flight1>=flight2? 1:2
        nweek=len(days)
        mcities=len(days[0])

        thisWeekDp=[]
        if nweek<1:
            return 0
        for i in range(mcities):
            vday = days[0][i]
            if i==0:
                thisWeekDp.append((vday, 0))
            else:
                thisWeekDp.append((vday, 1))

        for i in range(1, nweek):
            ntWeekDp=thisWeekDp.copy()
            for j in range(0, mcities):
                for k in range(0, mcities):
                    if thisWeekDp[k][0]+days[i][j]>ntWeekDp[j][0]:
                        if j==k:
                            ntWeekDp[j]=(thisWeekDp[k][0]+days[i][j], thisWeekDp[k][1])
                        else:
                            ntWeekDp[j] = (thisWeekDp[k][0] + days[i][j], thisWeekDp[k][1]+1)
                    elif thisWeekDp[k][0]+days[i][j]==ntWeekDp[j][0]:
                        if j==k:
                            if thisWeekDp[k][1]<ntWeekDp[j][1]:
                                ntWeekDp[j][1]=thisWeekDp[k][1]
                        else:
                            if thisWeekDp[k][1]+1<ntWeekDp[j][1]:
                                ntWeekDp[j][1] = thisWeekDp[k][1]+1
            thisWeekDp=ntWeekDp
        best=(0, 0)
        for choice in thisWeekDp:
            if choice[0]>best[0]:
                best=choice
            elif choice[0]==best[0]:
                if choice[1]<best[1]:
                    best=choice
        return best

这周一开始就收到recruiter消息说过了hiring commitee，接着就约team match。有一个HM对我感兴趣约了今天聊，聊完双方觉得听对口的结束二十分钟就收到recruiter电话说同意我入组，感觉整个过程超级快。

感觉地里的datadog面筋对我帮助相当大。为了回馈社区，我接下来会把准备的一些Leetcode上没有的面筋题的代码和system design高频题我的模版发在这里吧。

这些题包括：

coding部分：

Buffered File
CoinCounts 的各个种类coins分别的个数
delete directories
high performance filter
Flights Vacations 的 无flights限制 但有最小flights约束的follow up question
Log Query(已经在上面贴了)

System Design:

mint.com

楼主可以给一个buffered writer的解法吗？已加米～

这两道coding题是要在一轮面试中完成的？感觉很难啊

你好楼主，mint.com具体是那些需求可以说一下吗？谢谢！

匿名用户 发表于 2024-5-15 19:57
这两道coding题是要在一轮面试中完成的？感觉很难啊

不是，分两轮coding

博野菠萝蜜 发表于 2024-5-17 14:30
这周一开始就收到recruiter消息说过了hiring commitee，接着就约team match。有一个HM对我感兴趣约了今天聊 ...

恭喜啊楼主，请问你面的是什么级别的swe呢

楼主,  請問一下從VO完到過hiring committee 隔多久啊?

博野菠萝蜜 发表于 2024-5-17 14:30
这周一开始就收到recruiter消息说过了hiring commitee，接着就约team match。有一个HM ...

你好，可不可以分享下MINT.COM哪些需求呢？

请问楼主面的什么级别？谢谢