蚂蚁基础平台研发工程师一面

第一题： 把数组排序后dp，dp[i]代表从1到i最多可以保留几个数。遍历数组，二分查找左边第一个差值大于d的数，假如二分出来下标为j，直接dp[i] = dp[j] + 1。dp之后扫一遍dp数组取全局最大值，答案就是n减去这个全局最大值。注意如果删掉数量为奇数的话，答案得减一第二题：首先对于字符串第一个plog一定是不会被评论的，由此可得只要轮数足够多，所有与第一个plog不同的plog一定会被删除，所以把答案设置为第一个连续的字符的长度。通过观察可得，可以定义一个变量x，遇到一个不同于第一个plog的plog加一，遇到相同的话，如果x大于0就把x减一，否则就把答案减一。第三题：由题可得这是一棵树。如果x>=y，显然可以一个一个节点炸，输出n*x就行。否则我们要让使用操作2的次数尽可能多。要让操作2尽可能多的话，就要通过使用操作一把连通块数量变得尽可能多。这可以用树上dp作。定义dp[u][0]为对该节点使用操作1，dp[u][1]是不使用，以u为根节点得到的子树内最大连通块的数量。对每个节点初始化 dp[u][1] = 1， dp[u][0] = 0转移时通过dfs，对于所有子节点v，有：dp[u][0]  = sum(max(dp[v][0]), dp[v][1]));dp[u][1] = sum(max(dp[v][0]), dp[v][1] - 1));使用操作2最大次数就是max(dp[root][1], dp[root][0])，这个次数乘y加上剩余节点数乘x就是答案了

1、自我介绍2、问了一些个人情况（岗位选择、计算机相关课程、竞赛和保研）3、讲实习4、主机突然断电了，日志会丢失吗5、如何保证日志按时被清理了6、你在重构时，如何考虑和原有的代码兼容7、死锁是什么8、什么是线程安全，Java如何实现线程安全9、数据库中如果对一个数据有读有写的话，要加锁吗10、事务的隔离级别11、事务中的一致性和分布式系统中的一致性是一样的吗12、手撕1：非严格递增序列，原地去掉重复的数字，返回不同数字的个数，例子[1，1，2，3，3，3，4，4]，返回k=4，且原数组需变为[1，2，3，4，_，_，_，_]的形式13、手撕2：顺时针螺旋输出矩阵（hot100原题）14、反问

1、自我介绍2、挑一个项目来介绍一下3、Java 的 GC 过程会有 Stop the World，谈谈为什么要有 STW 的机制？4、谈谈 Java 的SGC、G1、ZGC 垃圾回收器5、G1 已经很不错了，为什么还要有 ZGC 这样的垃圾回收器，为了解决什么问题？6、比如一个订机票的场景，涉及多个外部系统，首先要去看有没有票，然后第二个是支付要调支付宝或者微信去做付款，定完票可能过了半个小时才告诉我订票有没有成功。对于这种场景下的分布式事务，你认为怎么去处理和设计来保证一致性比较好？7、基于消息传递的方案，消息可能传递失败，如何解决？8、如果用消息队列，这种场景，怎么做技术选型？9、做题：新兵报到，指导员命令所有人按身高大小，从低到高，依次站好，每次从头这边开始调整，但是要求，每次一次只能进行一次交换。输入 N(N <=  20)，输出 N 个士兵最终的排列结果。示例：N = 5，heights = [170, 167, 180, 175, 168]，输出：[167, 168, 170, 175, 180]10、谈谈基于数据库的方式如何实现分布式锁？11、谈谈基于 Redis 如何实现分布式锁？12、为什么基于 Redis 实现分布式锁时，Set 命令要加 PX 参数？13、基于数据库方式实现和基于 Redis 实现的区别？应用场景？14、反问

1. 一张表假设有多个字段 abc, 建立了 abc 联合索引，where a = ? and b = ? order by c 能命中索引吗？2. 索引的底层原理3. 单例模式怎么实现4. 为什么要双重检测5. 如果使用反射机制可以破坏单例吗6. MySQL 事务隔离级别介绍，你平时用的哪一个7. Redis 你在什么场景使用8. 旁路缓存会存在脏数据吗9. Redis 获取缓存耗时增加了，原因可能是什么10. OOM 问题怎么处理11. Java OOM 问题处理，原因可能是什么，怎么处理12. 优惠券秒杀（方案描述），这里最核心的问题是什么13. 你是怎么避免超卖的14. 线程池有哪些核...