头条面试--凉经

发表于 | 分类于 |

hold不住，终面的时候，基础挂掉了。。。

一面

自我介绍：

MySQL索引优化

求m^n

找钱问题

LRU实现

二面：

自我介绍：

MySQL优化

在一个有序有重数组中，找到特定元素的最大下标， 没有返回-1

怎样买票最省差旅费用

公司在一个城市内有很多办公地点，作为项目负责人，你可能会到任意一个地点办公。在接下来的一年里，你要出行的日期将以一个数组给出。每一项是一个从 1 到 365 的整数。在办公地点之间通勤可以用地铁，地铁有三种不同的销售方式：一张为期一天的通行证售价为 costs[0] 元；一张为期七天的通行证售价为 costs[1] 元；一张为期三十天的通行证售价为 costs[2] 元。通行证允许数天无限制的旅行。 例如，如果我们在第 1 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 1 天、第 2 天、第 3 天、第 4 天、第 5 天、第 6 天和第 7 天。返回你想要完成在给定的出行数组中列出的每一天的通勤所需要的总的最低消费。

输入描述

1
输入是两个以 ，分割的数组，如：[40, 78, 223],[2, 7, 20]第一个数组，是这一年中出行的所有天数的集合（每一项 1 <= item <= 365，没有重复，升序排列）第二个数组，数组 length === 3，数组项是 一天、七天、三十天 三种通行证的价格（非负整数）

输出描述

1
返回你想要完成在给定的 出行数组 中列出的每一天的通勤，所需要的总的最低消费。

示例1

输入

1
2
[40, 78, 223]
[2, 7, 20]

输出

1
6

示例2

输入

1
2
[1, 4, 6, 7, 8, 20]
[2, 7, 15]

输出

1
11

三面：

自我介绍：

说一下LinkedHashMap

说一下ConcurrentHashMap

说一下ConcurrentHashMap的扩容

JVM内存布局

图的最短路径算法

说一下Dijkstra算法的思想，时间复杂度

LRU的升级版，LFU的实现思路，O(1)

二叉树的
Node {
left right
int value
}

求最大连续“子树”和
“子树”每个节点的边数<=2
总边数无限制

总结：

算法全过，基础卡了ConcurrentHashMap的扩容，和JVM内存布局，然后挂掉了，继续刚基础叭~