蚂蚁面经一

• 不知道投的哪个部门，反正先来电话了
• 先是前一天，打了10分钟电话，了解下学校、专业、学习情况。重点问了下学校经历，是偏项目还是偏竞赛，以及常见的Linux命令的了解
• 然后约了时间写一道题
• 题目如下，说是阿里项目中遇到过的常见：

// 两个java interface
interface Action {
    public String getType();        // 类型
    public long getTimestamp();        // 动作时间 越大表示约接近当前时间
    public String getInfo();        // 附带的信息
}

interface ActionHistory {
    public void addNewAction(Action action);        // 加入
    public List<Action> getRecentActions(int n);    // 获得最近N次动作记录
    public List<Action> getRecentActions(String type, int n);        // 获得type类型动作的最近N次记录
}

要求 ActionHistory 的实现，并且时间 空间都尽可能的优，任意语言都行。

• 对于类型的n个，直接unordered_map<string, vecotr<Action>>就行了，时间复杂度

• 开始就说了两倍的空间，然后对方说可以再优的空间

• 后来瞎扯了个，每个Type提出N个，但是复杂度上升到了

• 继续想了5 6分钟，问了提示，然后说我上个方法其实很接近了，再想想怎么降低复杂度

• 然后就会了...

• 先所有的Type都提出来一个，丢到堆里，然后弹出一个，再加入弹出类型的下一个Action，一次类推，操作N次，如果无法操作了就退出。时间复杂度

• 接下来大概10分钟左右写了个代码实现

• 然后问了具体校园经历，我说主要竞赛的，感觉没有项目可能拉跨了点，然后说再评估下，要过几天有结果。

  下面具体代码：

• 总结：虽然感觉估计是感谢信了，还是记录下吧。

03/11 update: 上课时候，突然加微信，说可以接下去二面，然后笔试

03/12 update：笔试AC1.14

• 第一题裸的BFS，不到10分钟写完
• 第二题思维题，找环。思维变弱了，没想到，直接输出m，过了14%
  ps: nb群友翻出了原题，CF1141C https://blog.csdn.net/wwhcpp/article/details/113837172