蚂蚁面经一

  • 不知道投的哪个部门，反正先来电话了
  • 先是前一天，打了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分钟左右写了个代码实现

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

    下面具体代码：

6A89eI.png

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

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

03/12 update：笔试AC1.14