阿里开发者招聘节 | 面试题02-04:给定一个二叉搜索树(BST),找到树中第K小的节点

栏目: 数据库 · 发布时间: 5年前

内容简介:为帮助开发者们提升面试技能、有机会入职阿里,这一次,不仅是知识的收获,还将间接地与技术大牛们做了直观的沟通,了解他们的出题思路与考察要点,并加以消化吸收,这对自己技术能力本身就是一种极大的提升。走上编程之路,不断丰富自己方能与世接轨,努力做最优秀的自己。

摘要: 阿里巴巴资深技术专家们结合多年的工作、面试经验总结提炼而成的笔试真题这一次将陆续放出(面试题答案将在专辑分享结束后统一汇总分享)。并通过这些笔试真题开放阿里巴巴工作机会,让更多的开发者加入到阿里这个大平台。

为帮助开发者们提升面试技能、有机会入职阿里, 云栖社区 特别制作了这个专辑——阿里巴巴资深技术专家们结合多年的工作、面试经验总结提炼而成的面试真题这一次将陆续放出(面试题官方参考答案将在专辑结束后统一汇总分享, 点此进入答题并围观他人答案 )。并通过这些笔试真题开放阿里巴巴工作机会,让更多的开发者加入到阿里这个大平台。

这一次,不仅是知识的收获,还将间接地与技术大牛们做了直观的沟通,了解他们的出题思路与考察要点,并加以消化吸收,这对自己技术能力本身就是一种极大的提升。走上编程之路,不断丰富自己方能与世接轨,努力做最优秀的自己。

4月25日,我们给开发者的第2~4道面试题。

02.已知sqrt(2)约等于1.414,要求不用数学库,求sqrt(2)精确到小数点后10位

考察点:

  1. 基础算法的灵活应用能力(二分法学过数据结构的同学都知道,但不一定往这个方向考虑;如果
    学过数值计算的同学,应该还要能想到牛顿迭代法并解释清楚)
  2. 退出条件设计

03. 给定一个二叉搜索树(BST),找到树中第K小的节点

考察点:

  1. 基础数据结构的理解和编码能力
  2. 递归使用

示例

如下图,输入K=3, 输出节点值3

阿里开发者招聘节 | 面试题02-04:给定一个二叉搜索树(BST),找到树中第K小的节点

说明

保证输入的K满足1<=K<=(节点数目)

04.LRU缓存机制

设计和实现一个 LRU(最近最少使用)缓存 数据结构,使它应该支持以下操作: get 和 put 。

get(key) ‑ 如果key存在于缓存中,则获取key的value(总是正数),否则返回 ‑1。 put(key,

value) ‑ 如果key不存在,请设置或插入value。当缓存达到其容量时,它应该在插入新项目之前使

最近最少使用的项目作废。

案例:

LRUCache cache = new LRUCache( 2 /  容量  / );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // 返回 1

cache.put(3, 3); // 该操作,会将 key 2 作废

cache.get(2); // 返回 ‑1 (结果不存在)

cache.put(4, 4); // 该操作,会将 key 1 作废

cache.get(1); // 返回 ‑1 (结果不存在)

cache.get(3); // 返回 3

cache.get(4); // 返回 4

测试用例: s = [["put","put","get","put","get","put","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],

[4,4],[1],[3],[4]]]

考察点:

对LRU实现的基本原理和数据结构的理解。

阿里巴巴出题专家:文景

阿里云CDN资深技术专家,浙大硕士,在高性能服务端产品开发、稳定性、服务质量优化及成本优化等各项功能都有10年以上的经验。在网易杭州研究院负责底层开源软件研发,国内最早核心Nginx研发人员之一,曾任tengine研发负责人,热衷于参与开源项目。

现在是CDN技术负责人,连续7年服务双11,保障整个阿里集团95%以上的流量分发稳定性。从2014年开始,从0到1构建阿里云CDN的商业化基础设施,包括点播、直播、动态、安全加速等各项产品线,阿里云CDN现在是中国用户数最多的CDN、也是国内规模最大的CDN。正在将CDN打造成互联网的基础设施,为全球用户提供接入、加速、安全的稳定服务。

阿里开发者招聘节 | 面试题02-04:给定一个二叉搜索树(BST),找到树中第K小的节点

招聘职位: 点此进入查看CDN大量职位并投递简历

本文作者:山哥在这里

阅读原文

本文为云栖社区原创内容,未经允许不得转载。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

断层地带

断层地带

杰弗里·摩尔 (Geoffrey A.moore) 著 / 季晓楠,凌炜 译 / 机械工业出版社 / 2009-1 / 33.00元

从股东权益谈起,并把“股东权益管理”作为根本立场,明确阐述了公司市场价值的内涵:在竞争环境中,公司的市场价值等于在当前和计划的生产经营活动下,未来可预计的收益用风险系数贴现后的现值。断层地带:经济中的危险境地,在这里勇敢的创新者给市场带来了惨烈的竞争,撕杀得天昏地暗。每家公司都处在这样的环境中,但是没有一个管理者能够控制它。一起来看看 《断层地带》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具