依图科技算法.md

#依图面试

一面

• 问项目
• 算法题1： 给定数组{a1, a2, a3, ... an}，要求挑出一些数，这些数不能相邻，使得加起来的和最大。
  • 如果是环怎么处理？
  • 裸写环情况的代码
• 算法题2：连连看
  • 给定一个N x M的数组，0表示空格，>1表示颜色
  • 要求在O(NM)的时间内，找到一条合理的连连看的连线作为提示输出
  • 连连看的连线定义为：只能经过0，且最多有两个转折
  • 抽象 + Hash表

二面

• 问项目
• 算法题1：给定H x W的数组，表示一个迷宫，0表示空格，1表示障碍，求从0, 0点到右下角最少多少步走到
  • 简单BFS，要求裸写代码
• 智力题：一个国王有10000桶酒，已知有一桶酒是有毒的，喝了之后一定会在23小时~24小时这个时间段死亡（例如0点喝，则23点到第二天0点一定死亡）。现在国王要在48小时后举办一个宴会，需要把这桶酒挑出来，可以用罪犯实验，问最少多少个罪犯？
  • 允许混合酒

三面

• 介绍一个项目
• 算法题1：给定集合A = {a1, a2..., an}, a1an都是正整数，给定N，要求求一个集合B = {b1, b2, .. bm}，要求A并B里面的元素组合起来的和可以表示1N之间所有数，且B里面元素的个数最小。

HR面

• 问要求，期望等。