原创 | 一张图秒杀滴滴大数据场景题(已拿offer)

本文涉及的产品
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
简介: 原创 | 一张图秒杀滴滴大数据场景题(已拿offer)

大家好,我是峰哥。

之前有同学在微信上问了我滴滴的一个大数据场景题,今天我们就聊聊解决这道题的思路。


image.png


在面试中,我们不仅要手写算法,还会碰到一些算法场景题,比如数据量太大,内存完全不够该如何处理,今天我们就结合两个具体问题来探讨一下。


问题一


A 文件有 50 亿条 URL,B 文件也有 50 亿条 URL,每条 URL 大小为 64B,在一台只有 4G 内存的机器上,怎么找出 A、B 中相同的 URL?


不用算都知道内存肯定不够,否则就不会这么问了。面试时,如果对自己的算数能力不够自信,那就直接说出思路,不用计算具体数值,免得尴尬。


针对这种大数据量的问题,通常要想到「分而治之」。为了方便讲解,我这里就先计算一下。


50 亿条 URL 文件的大小:50 * 10^8 * 64 Byte ≈ 32 * 10^10 Byte ≈ 320G

一图胜千言,点击图片即可放大查看。


image.png


借助 Hash 函数,依次扫描 A、B 两个文件,将 URL 分别存储到 1000 个小文件中,那么每个文件大约 300M,满足内存的需求,文件以 0-999 的数字结尾作为编号,下面说下具体过程。

首先遍历 A 文件,对每个 URL 取 hash(url)%1000 的值,该值就是 URL 要存储到小文件的编号,最终所有 URL 分别存储在 1000 个小文件中,文件名记成以下形式: a0、a1、…、a999。

再遍历 B 文件,用同样的方法将 B 文件的 URL 分别存储 b0、b1、…、b999 这 1000 个小文件中。

我们知道 Hash 的一个特点:相同的 key,hash 之后的 value 一定是相同的。所以,对于 A、B 文件中相同的 URL,Hash 之后,一定会存储到相同下标的文件中。

如果 Hash 函数设计合理,将数据均匀分散,每个文件大致 300M。

我们再读取相同下标的小文件到内存中,判断是否存在相同的 URL 即可。

是不是 so easy ?


这让我想起极客时间专栏中同样是内存不够的一个问题。


问题二


如何对 10G 的订单数据按照金额排序?


此时要借助桶排序的思想,订单金额一般是在某个范围内,跨度不会太大。先扫描一遍 10G 的订单数据,找出订单金额的范围,再根据范围进行切分,划分到不同的桶。


比如订单金额在 1 到 10万,切分到 100 个桶里,每个桶中保存的金额范围就是 1000,每个桶其实就是一个小文件,给文件编个号,比如 00 文件:1-1000 元,01 文件:1001-2000,以此类推。


假设订单金额比较均匀,那么每个文件大概 100M,每次读取一个文件进行排序即可。文件之间本来就按照金额划分,已经是有序的。最后将划分的小文件按照编号依次写入结果文件中,那么所有订单就按照金额排好序了。


再一图胜千言。


image.png


实际情况中,订单金额一般是分布不均匀的,此时针对较大的文件复用上面的方法,划分成更小的文件分别排好序,最后再统一汇总。


通过以上两个问题,我们发现大数据处理的重要思想是「分而治之」,下次碰到这类题目不妨从这个角度出发,即使不能吊打面试官,但也能回答个七七八八。


最后这位同学也不枉峰哥的细心指导,顺利拿下滴滴offer。


image.png






相关实践学习
基于MaxCompute的热门话题分析
Apsara Clouder大数据专项技能认证配套课程:基于MaxCompute的热门话题分析
相关文章
|
20天前
|
SQL 缓存 分布式计算
【跨国数仓迁移最佳实践5】MaxCompute近线查询解决方案助力物流电商等实时场景实现高效查询
本系列文章将围绕东南亚头部科技集团的真实迁移历程展开,逐步拆解 BigQuery 迁移至 MaxCompute 过程中的关键挑战与技术创新。本篇为第5篇,解析跨国数仓迁移背后的性能优化技术。 注:客户背景为东南亚头部科技集团,文中用 GoTerra 表示。
|
6月前
|
SQL 分布式计算 运维
StarRocks 在爱奇艺大数据场景的实践
本文介绍了爱奇艺大数据OLAP服务负责人林豪在StarRocks年度峰会上的分享,重点讲述了爱奇艺OLAP引擎的演进及引入StarRocks后的显著效果。在广告业务中,StarRocks替换Impala+Kudu后,接口性能提升400%,P90查询延迟缩短4.6倍;在“魔镜”数据分析平台中,StarRocks替代Spark达67%,P50查询速度提升33倍,P90提升15倍,节省4.6个人天。未来,爱奇艺计划进一步优化存算一体和存算分离架构,提升整体数据处理效率。
StarRocks 在爱奇艺大数据场景的实践
|
7月前
|
SQL 缓存 数据处理
数据无界、湖仓无界,Apache Doris 湖仓一体典型场景实战指南(下篇)
Apache Doris 提出“数据无界”和“湖仓无界”理念,提供高效的数据管理方案。本文聚焦三个典型应用场景:湖仓分析加速、多源联邦分析、湖仓数据处理,深入介绍 Apache Doris 的最佳实践,帮助企业快速响应业务需求,提升数据处理和分析效率
370 3
数据无界、湖仓无界,Apache Doris 湖仓一体典型场景实战指南(下篇)
|
11月前
|
存储 分布式计算 druid
大数据-149 Apache Druid 基本介绍 技术特点 应用场景
大数据-149 Apache Druid 基本介绍 技术特点 应用场景
244 1
大数据-149 Apache Druid 基本介绍 技术特点 应用场景
|
存储 分布式计算 安全
MaxCompute Bloomfilter index 在蚂蚁安全溯源场景大规模点查询的最佳实践
MaxCompute 在11月最新版本中全新上线了 Bloomfilter index 能力,针对大规模数据点查场景,支持更细粒度的数据裁剪,减少查询过程中不必要的数据扫描,从而提高整体的查询效率和性能。
|
11月前
|
SQL 存储 分布式计算
大数据-157 Apache Kylin 背景 历程 特点 场景 架构 组件 详解
大数据-157 Apache Kylin 背景 历程 特点 场景 架构 组件 详解
153 9
|
11月前
|
存储 缓存 NoSQL
大数据-38 Redis 高并发下的分布式缓存 Redis简介 缓存场景 读写模式 旁路模式 穿透模式 缓存模式 基本概念等
大数据-38 Redis 高并发下的分布式缓存 Redis简介 缓存场景 读写模式 旁路模式 穿透模式 缓存模式 基本概念等
269 4
ly~
|
11月前
|
供应链 监控 搜索推荐
大数据的应用场景
大数据在众多行业中的应用场景广泛,涵盖金融、零售、医疗保健、交通物流、制造、能源、政府公共服务及教育等领域。在金融行业,大数据用于风险评估、精准营销、反欺诈以及决策支持;零售业则应用于商品推荐、供应链管理和门店运营优化等;医疗保健领域利用大数据进行疾病预测、辅助诊断和医疗质量评估;交通物流业通过大数据优化物流配送、交通管理和运输安全;制造业则在生产过程优化、设备维护和供应链协同方面受益;能源行业运用大数据提升智能电网管理和能源勘探效率;政府和公共服务部门借助大数据改善城市管理、政务服务及公共安全;教育行业通过大数据实现个性化学习和资源优化配置;体育娱乐业则利用大数据提升赛事分析和娱乐制作水平。
ly~
2373 2
|
人工智能 编解码 搜索推荐
大模型、大数据与显示技术深度融合 加速智慧医疗多元化场景落地
大模型、大数据与显示技术深度融合 加速智慧医疗多元化场景落地
|
传感器 供应链 安全
大数据技术的应用场景
大数据技术的应用场景

热门文章

最新文章