依图三面凉经-【算法工程师-上海/杭州/北京】

没有笔试，投递简历过了以后，偶然HR打电话约的面试。

一面

自我介绍。面试官见我想介绍项目，就先让我介绍了项目。然后做题。

1. 给定多条公交线路（可以认为是环线），以及一个初始出发点，以及目的地。求乘坐最少公交车的次数（不存在则返回-1）。

   可以将每个线路看作一个set，然后题目就类似于leetcode的word ladder了。使用BFS搜索即可。

   最开始考虑成最少站点了，面试官提示以后，确定正确的思路。注意起点是换乘站点的考虑。然后面试官问，知不知道双端搜索，就是从头尾分别搜索，最后确定线路的方法。大概说了一下思路。

2. 数学题。有一个一次只能读取buffer，一个不知道有多少元素的链表。现在想基于这个链表与这个buffer实现一个获取链表中随机元素的函数。

   题目类似与leetcode的Linked List Random Node。要求one-pass的。
   经过提示以后，大概理解了方法。
   每次读取一个元素，保证每个元素的值在buffer的概率相等即可。
   以 【1 2 3】为例。第一读到1，buffer的值就是1。取到1的概率就是100%。读入2以后，为了保证1，2在buffer的概率保持相等。那么1以50%的概率丢弃即可。读取3的时候，为了，保证1 2 3 概率相等。已知 1 2 都是 1/2 那么 让 1 2 的概率变成1/3，只要buffer以2/3的概率保持不变即可。依次类推。

二面

简单自我介绍。然后做题。

1. 两个排序数组的中位数。
   写了O（n）的解法，介绍了一下lgn的方法的思路
2. 概率题。 有n个人，m个坏人。每次检查一个人无论是不是坏人都会导致这个人死亡。那么查到第一个坏人的死掉好人的期望是多少。

   先写了期望的计算公式，然后让我简单算了一下需要多少次加法，多少次乘法。估计复杂度。
   如果是查到2个坏人的情况再计算了一下公式。时间复杂度很大，怎么办。考虑DP，我只推到出来了1个坏人的。
   E(m,n) = n/m*0+ (m-n)/m *(E(m-1,n)+1)
   k个人的当时没转过弯来。面试官就直接写出来了。

三面

介绍项目。
题目。

1. 给定一个n*m的矩阵，从中找出a*a的矩阵，使得和最大。返回最大的数值。
   计算一个n*m矩阵，每个是左上角元素和的值。然后再遍历计算。

可能我表达的有问题吧。边界条件也没处理好。就在这儿戛然而止了。等一个明天的感谢信了。

感谢一下之前有个同学的依图面经。掷骰子，求概率可以使用动态规划那个。看了那个题目之后才知道原来还可以这么做。