社招面经总结——算法题篇

　　运用你所掌握的数据结构设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作 获取数据 get 和 写入数据 put 。

　　这道题在今日头条、快手或者硅谷的公司中是比较常见的代码要写的还蛮多的难度也是hard级别。

　　最重要的是LRU 这个策略怎么去实现, 很容易想到用一个链表去实现最近使用的放在链表的最前面。 比如get一个元素,相当于被使用过了这个时候它需要放到最前面再返回值, set同理。 那如何把一个链表的中间元素快速的放到链表的开头呢 很自然的我们想到了双端链表。

　　LRU 存储是基于双向链表实现的下面的图演示了它的原理。其中 head 代表双向链表的表头tail 代表尾部。首先预先设置 LRU 的容量如果存储满了可以通过 O(1) 的时间淘汰掉双向链表的尾部每次新增和访问数据都可以通过 O(1)的效率把新的节点增加到对头或者把已经存在的节点移动到队头。

　　下面展示了预设大小是 3 的LRU存储的在存储和访问过程中的变化。为了简化图复杂度图中没有展示 HashMap部分的变化仅仅演示了上图 LRU 双向链表的变化。我们对这个LRU缓存的操作序列如下

　　给定一个二叉树返回其按层次遍历的节点值。 即逐层地从左到右访问所有节点。

　　我们数据结构的书上教的层序遍历,就是利用一个队列,不断的把左子树和右子树入队。但是这个题目还要要求按照层输出。所以关键的问题是如何确定是在同一层的。 我们很自然的想到 如果在入队之前,把上一层所有的节点出队,那么出队的这些节点就是上一层的列表。 由于队列是先进先出的数据结构,所以这个列表是从左到右的。

　　递归的子问题遍历当前节点, 对于当前层, 遍历左子树的下一层层,遍历右子树的下一层

　　这道题目的关键是转换的时候递归的时候记住是先转换右子树再转换左子树。 所以需要记录一下右子树转换完之后链表的头结点在哪里。注意没有新定义一个next指针而是直接将right 当做next指针,那么Left指针我们赋值成null就可以了。

　　用递归解法,用一个stack 记录节点,右子树先入栈左子树后入栈。

　　从根节点开始遍历如果node1和node2中的任一个和root匹配那么root就是最低公共祖先。 如果都不匹配则分别递归左、右子树如果有一个 节点出现在左子树并且另一个节点出现在右子树则root就是最低公共祖先. 如果两个节点都出现在左子树则说明最低公共祖先在左子树中否则在右子树。

　　面了蚂蚁中台的团队,二面面试官根据汇报层级推测应该是P9级别及以上在美国面我面试风格偏硅谷那边。题目是hard难度的,leetcode 295题。 这道题目是Leetcode的hard难度的原题。给定一个数据流求数据流的中位数求中位数或者topK的问题我们通常都会想用堆来解决。 但是面试官又进一步加大了难度他要求内存使用很小没有磁盘但是压榨空间的同时可以忍受一定时间的损耗。且面试官不仅要求说出思路要写出完整可经过大数据检测的production code。

　　不考虑内存的方式就是Leetcode 论坛上的题解。 基本思想是建立两个堆。左边是大根堆右边是小根堆。 如果是奇数的时候大根堆的堆顶是中位数。

　　但是这样做的问题就是可能内存会爆掉。如果你的流无限大那么意味着这些数据都要存在内存中堆必须要能够建无限大。如果内存必须很小的方式用时间换空间。

　　这里边界条件我们处理好之后,关键还是helperOdd 和 helperEven这两个函数怎么去求topK的问题. 我们还是转化为一个topK的问题,那么求top-K和top(K1)的问题到这里我们是不是可以用堆来解决了呢? 答案是不能,考虑极端情况。中位数的重复次数非常多

　　假如我们的划分bucket大小是10000,那么最大的时候区间就是20000。(对应上面的偶数且落到两个分桶的情况) 那么既然划分到某一个bucket了,我们直接用数数字的方式来求topK 就可以了,用堆的方式也可以,更高效一点,其实这里问题规模已经划分到很小了,两种方法都可以。 我们选用TreeMap这种数据结构计数。然后分奇数偶数去求解。

　　至此,我觉得算是一个比较好的解决方案leetcode社区没有相关的解答和探索欢迎大家交流。

　　说下本人现在的基本情况，毕业一年，双非本科，之前是项目外包，坐标上海，目标中大型互联网公司 蚂蚁金服 电话

　　： 主要问做过的项目的一些解决方案（是否有分库分表、是否使用缓存、服务拆分的原则、遇到的有挑战性的技术问

　　，如何解决） Docker是如何实现虚拟化的、JVM运行时数据区、JVM垃圾回收

　　卒，我们公司目前做的主要是企业内部的报销相关的系统，数据量、并发量都比较小，用的技术栈也没那么多，所以项目解决方案的话相对来说比较吃亏，而且.

　　目：有两个序列a,b，大小都为n,序列元素的值任意整数，无序； 要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。 例如: var a = [100,99,98,1,2, 3]，b = [1, 2, 3, 4,5,40]; 思路： 当前数组a和数组b的和之差为： A = sum(a) - sum(b)，a的第i个元素和b的第j个元素交换后，a和b的和之差为...

　　列表： 1、基本语言 1、说一下**static关键字的作用** 2、说一下C++和C的区别 3、说一下C++中static关键字的作用 4、请说一下static的作用 ........ 完整目录

　　岗offer！ - 夕小瑶的文章 - 知乎 推完上一篇文章，订阅号和知乎后台有好多小伙伴跟小夕要

　　都有可能都会问到，所以，对自己负责，欺骗自己等于拿自己的事业开玩笑。2.大部分的

　　试官不是真的要问倒你，他们只是想看看你的解决思路和套路是否能够灵活多变，问到一个你不知道，你就...

　　如下： 1 快排 2 二叉树的深度 3 字符输入纠错 4 top10的tag不超过两个 5 括号匹配 快排 出现好多了，不再介绍了 二叉树的深度 [LeetCode] 104. Maximum Depth of Binary Tree 二叉树的最大深度 设计一个系统，自动纠正用户输入错误的字符串。这道

　　关于Node.js的httpClieint请求报错ECONNRESET的原因和解决措施

　　weixin_47646978:您好，我这个照你这个写完运行报空指针异常，麻烦能给指点下为什么

　　neu_ZZM:如果模型和场景不一样大怎么处理呢？这样的话d这个量就对应不上了呀

作者：admin

抖音快手 站点 QQ交谈