当前位置: 首页 > 科技观察

十大系统设计面试问题

时间:2023-03-17 01:01:50 科技观察

在我作为Microsoft和Facebook的高级软件工程师和面试官的10年里,我与数百名申请人一起工作,他们解决了不同的系统设计问题。开发人员倾向于SDI问题,因为它们是如此开放,并且通常需要一种在其他编码面试挑战中没有实践过的批判性思维。尽管SDI问题随着时间的推移发生了变化,但其中一些问题在各种顶级公司的面试中仍然很受欢迎。今天,我们将探讨10大系统设计面试问题,每个问题中必须解决的常见问题,以及一些可以帮助您做到这一点的工具。针对任何SDI问题的提示通过陈述您对问题的了解来开始每个问题:列出系统的所有必需功能、此类系统可能遇到的常见问题以及系统预期处理的流量。列出流程可以让面试官在着手解决方案之前审查您的计划技能并纠正任何可能的误解。描述任何权衡:每个系统设计选择都很重要。在每个决策点,至少列出该选择的正面和负面影响。请面试官澄清:大多数系统设计问题都故意含糊不清。提出澄清性问题,向面试官展示您如何看待问题以及您对系统要求的了解。讨论新兴技术:在每个问题的末尾都有一个系统如何以及在何处可以从机器学习中受益的概述。这将表明您不仅为当前的解决方案做好了准备,而且为未来的解决方案做好了准备。1.设计一个全球聊天服务,例如FacebookMessenger或WhatsApp针对这个问题,您将设计一个服务,让用户可以通过Internet相互聊天。对话可以是一对一的,也可以是与许多成员的群聊。对话中包含的消息只能访问这些消息。所需功能:必须通过Internet发送和接收消息。服务必须支持一对一和群聊。应存储消息以供以后查看。用户应该能够发送图片和视频以及短信。消息在传输过程中应该加密。消息应该以最小的延迟可见。常见问题:如果在没有互联网连接的情况下发送邮件会怎样?恢复连接时是否发送?如何在不增加延迟的情况下加密和解密消息?用户如何接收通知?消息是从设备中拉取(如果服务器正在等待发送消息,服务器会定期提示设备)还是将消息推送到服务器(设备会提示服务器发送消息)?要考虑的工具:将数据库模式划分为多个表:用户表(包含用户ID和联系人)、聊天表(包含聊天ID和参与用户ID列表)和消息表(包含聊天ID引用的过去消息)。使用WebSocket的设备和服务器之间的双向连接。使用推送通知通知成员,即使他们处于离线状态。2.设计像Uber或Lyft这样的拼车服务这个问题要求你创建一个拼车服务,将用户与附近的司机相匹配。用户可以输入目的地并发送他们的当前位置,在几秒钟内通知附近的司机。然后,该应用程序会跟踪驾驶员与用户当前位置之间的路线,然后跟踪从用户位置到目的地的路线。必备功能:系统必须跟踪所有用户和驾驶员的当前位置。在运输过程中,用户和司机必须收到更新的旅行信息。必须在此过程中的各个阶段支持成千上万的用户,并相应地进行扩展。驱动程序和用户必须始终连接到服务器。常见问题解答:您如何在繁忙时段保持低延迟?驱动程序如何与用户配对?遍历所有驱动程序以找到欧几里得距离是低效的。如果司机或用户失去连接会怎样?您如何存储所有缓存的位置数据?要考虑的工具:使用S2Geometry库将位置拆分为单元格。只有与用户在同一单元格中的驾驶员才会用于计算驾驶员距离。采用分布式存储方式存储所有用户的位置,每个用户的位置数据只有1Kb左右。如果位置数据暂停,设备会在等待重新连接时继续报告其先前的位置。在提示最近的司机行驶后留下缓冲区。如果他们拒绝,请转到下一个司机。3.设计一个URL缩短服务,例如TinyURL或bit.ly这个问题要求你创建一个程序来缩短长URL,例如TinyURL或bit.ly。这些程序采用长URL并生成新的唯一短URL。他们还可以输入缩短的URL并取回原始的完整URL。必备功能:返回短于原始URL的URL必须存储原始URL新生成的URL必须能够链接到存储的原始URL缩短的URL应允许重定向必须支持自定义短URL必须同时支持许多请求多个用户输入相同的自定义URL?如果用户多于预期怎么办?数据库如何扩展存储?要考虑的工具:使用散列链接原始URL和新URL使用RESTAPI负载平衡高流量并处理前端客户端通信使用多线程一次处理多个请求使用NoSQL数据库存储原始URL(没有存储URL之间的关系)4.设计大众社交媒体服务,如Facebook、Twitter或Instagram像Instagram这样被数十万用户使用的社交媒体服务。用户应该能够查看包含关注者帖子的新闻提要并推荐用户喜欢的新内容。面试官通常希望听到您深入讨论新闻来源。必备功能:强大的新闻提要和推荐系统用户可以发布公开帖子其他用户可以评论或点赞帖子必须同时舒适地容纳许多用户系统必须高度可用与用户相比,他们会处理吗?系统将如何按年龄分配权重?与新帖子相比,较旧的帖子被查看的可能性较小。集合中读取节点与写入节点的比率是多少?是否可能有更多的读取请求(用户正在查看帖子)或写入请求(用户正在创建帖子)?如何提高可用性?系统如何更新?如果一个节点发生故障怎么办?您如何有效地存储帖子和图像?需要考虑的工具:使用滚动更新和副本节点来最大化可用性。使用训练有素的机器学习算法来推荐帖子。创建一个数据库模式来分别存储名人和用户。使用社交图进一步跟踪以下习惯5.设计一个社交网络和留言板服务,例如Quora、Reddit或HackerNews对于这个问题,您将设计一个类似于论坛的系统,用户可以在其中发布问题和链接。其他用户可以查看和评论问题。问题有代表其主题的标签,用户可以跟随标签查看有关特定主题的问题。用户有一个新闻源,突出显示他们关注的标签和相关主题中的常见问题。必备功能:用户必须能够创建公开帖子并应用标签帖子必须按标签排序其他用户必须能够实时发表评论。数据库必须存储每个帖子的数据(查看次数、喜欢等)。新闻源必须显示来自以下标签的帖子以及来自用户希望的其他标签的帖子。必须支持高流量受众和新帖子。常见问题解答:我们的产品是否只需要在网络上运行?用户上传的图片/链接存储在哪里?系统将如何确定相关标签?提要中显示了多少来自未关注标签的帖子?帖子如何在服务器网络中分布?要考虑的工具:使用SQL数据库映射关系数据(用户有帖子,帖子有评论/喜欢,类别有相关帖子等)使用多线程和负载平衡器层来帮助支持更高的流量。使用分片来破坏系统。考虑按类别分片以在一台计算机中存储具有相同标签的帖子。使用机器学习和自然语言处理来寻找标签之间关系的相关性6.设计一个全局文件存储和共享服务,例如Dropbox、GoogleDrive或GooglePhotos对于这个问题,您将创建一个同步的跨平台存储系统,例如作为Dropbox。用户可以存储文件和照片并从其他设备访问它们。必备功能:用户应该能够通过网络保存/删除/更新/共享文件应该保存旧版本的文档以供回滚文件更新应该在多个设备之间同步常见问题解答:文件存储在哪里?你如何处理更新?你是不是整个文件都重新上传了一遍?小更新是否需要完整文件更新?系统如何处理两个用户同时更新文档?要考虑的工具:使用分块将文件拆分为多个部分。更新仅重新上传该部分,而不是整个文件。将AmazonS3等云存储用于内部数据库。让客户端不断检查服务器以确保应用并发更新。7.设计一个全球视频流服务,如YouTube或Netflix这个问题要求你创建一个在线视频流服务,如YouTube。该服务将存储和传输数百拍字节的视频数据。它还必须存储统计数据(观看次数、喜欢次数、观看次数等)并允许用户发表评论。您的解决方案必须具有可扩展性以支持数以千计的并发用户。必备功能:视频应可通过网络上传用户应通过互联网接收不间断的流媒体应存储每个视频的视频统计信息并可访问。必须保存评论并与视频一起显示给其他网民评论应支持数千用户的高流量常见问题解答:您的服务将如何确保在各种互联网质量上流畅地播放视频?您的服务将如何应对流式传输速度的突然下降(缓冲、质量损失等)?视频是如何存储的?考虑的工具:使用云技术来存储和传输视频数据。使用机器学习来推荐新的视频内容。防止由不一致的连接引起的卡顿。用户查看了几分钟前的数据,而不是输入数据。8.为Firebase或Github等网站设计API速率限制器对于这个问题,您将创建一个API速率限制器来限制服务在给定时间段内可以接收的API调用数量,以避免过载。采访者可以提出任何规模的请求,从单台机器到整个分布式网络。必备功能:该设备限制为每小时10个请求,如果用户的请求被阻止,限制器必须通知用户。必须处理适合其大小的流量。常见问题解答:您的系统如何衡量每小时的请求数?如果用户在1:20发出10个请求,然后在2:10发出另外10个请求,他们仍然在同一个1小时窗口中,尽管时间更改了20个请求。分布式系统的设计与本地系统有何不同?要考虑的工具:使用滑动时间窗口以避免每小时重置。保存一个计数器整数而不是请求本身以节省空间。9.设计像Yelp或附近的地方/朋友这样的近距离服务器对于最后一个问题,您将设计一个近距离服务器来存储和报告到餐馆等地方的距离。用户可以按距离或受欢迎程度搜索附近的地点。数据库必须以低延迟存储来自全球5亿个位置的数据。必备功能:存储多达5亿个位置。位置必须具有唯一标识,并具有相应的数据,例如质量检查和服务时间。搜索必须以最小的延迟返回结果。用户必须能够按距离或质量搜索结果。常见问题:那么多的位置数据是怎么存储的?您如何获得快速搜索结果?您的系统如何处理不同的人口密度?刚性纬度/经度网格将导致基于密度的变化响应。我们如何优化常见的搜索位置?要考虑的工具:使用关系数据库来存储位置列表和相关数据。使用缓存来存储最流行位置的数据。使用分片按区域拆分数据。在动态网格中搜索位置。如果您在一个单元格中有超过500个位置,请将网格分成4个较小的单元格。重复直到您只需要搜索少于500个位置。10.设计搜索引擎相关服务,如Type-Ahead,它将部分完成搜索查询并显示5条建议以完成查询。它应该实时适应高度搜索的内容并将其推荐给其他用户。例如,“海鹰队赢得了超级碗”将在比赛结束后的几分钟内被推荐。必备功能:该服务应将部分查询与流行查询相匹配。应更正小错别字,例如“dgo→dog”应该根据查询猜测5个最有可能的选项结果应该随着查询的写入而更新常见问题解答:您在纠正拼写错误方面做得如何?如何在不引起延迟的情况下更新选择?您如何确定最有可能完成的查询?它是否适应用户的搜索?如果用户快速输入怎么办?建议只有在完成时才会显示吗?要考虑的工具:使用自然语言处理机器学习算法来预测下一个字符。使用马尔可夫链对排名最高的查询概率进行排名。每小时或每天(而不是实时)更新ML算法以减轻负担。接下来要研究什么这些问题应该可以帮助您了解您将在系统设计面试中解决的问题类型。练习解决和解释此类问题是为下一次面试做准备的最有效方法。本文翻译自TheEducativeTeam的文章《Top 10 System Design Interview Questions》。