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

没有笔试,投递简历过了以后,偶然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矩阵,每个是左上角元素和的值。然后再遍历计算。

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


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

#依图科技##算法工程师##面经##校招#
全部评论
请问是三面连着面的吗?
点赞 回复
分享
发布于 2019-09-24 21:06
太强了,劝退题
点赞 回复
分享
发布于 2019-09-24 21:17
英特尔
校招火热招聘中
官网直投
tql
点赞 回复
分享
发布于 2019-09-24 21:24
呜呜呜tql
点赞 回复
分享
发布于 2019-09-25 13:05
很棒了我觉得,题目比我当时的难一些要,可能碰到一些大佬要求比较高吧
点赞 回复
分享
发布于 2019-09-25 19:49

相关推荐

4 41 评论
分享
牛客网
牛客企业服务