What should I do when meeting this question in interview - A step by step guide
Code first.\n\nclass MultiMap {\n    public TreeMap<Integer, Integer> map;\n    private int cnt = 0;\n    private double sum = 0.0;\n    \n    public MultiMap()
Code first.\n```\nclass MultiMap {\n    public TreeMap<Integer, Integer> map;\n    private int cnt = 0;\n    private double sum = 0.0;\n    \n    public MultiMap() {\n        this.map = new TreeMap<>();\n    }\n    \n    public void add(Integer key) {\n        this.cnt ++;\n        this.sum += key;\n        this.map.put(key, this.map.getOrDefault(key, 0) + 1);\n    }\n    \n    public boolean containsKey(Integer key) {\n        return this.map.getOrDefault(key, 0) > 0;\n    }\n    \n    public void remove(Integer key) {\n        if (!this.map.containsKey(key)) {\n            return;\n        }\n        \n        this.cnt --;\n        this.sum -= key;\n        this.map.put(key, this.map.get(key)-1);\n        \n        if (this.map.get(key) == 0) {\n            this.map.remove(key);\n        }\n    }\n    \n    public Integer getMin() {\n        return this.map.firstKey();\n    }\n    \n    public Integer getMax() {\n        return this.map.lastKey();\n    }\n    \n    public int avg() {\n        return (int)(this.sum/this.cnt);\n    }\n    \n    public int size() {\n        return this.cnt;\n    }\n}\n\nclass TripleMap {\n    public MultiMap small;\n    public MultiMap mid;\n    public MultiMap big;\n    private int m;\n    private int k;\n    \n    public TripleMap(int m, int k) {\n        this.small = new MultiMap();\n        this.mid = new MultiMap();\n        this.big = new MultiMap();\n        this.m = m;\n        this.k = k;\n    }\n    \n    public void add(int num) {\n        if (mid.size() == 0) {\n            mid.add(num);\n            return;\n        }\n        \n        if (num < mid.getMin()) {\n            small.add(num);\n        } else if (num > mid.getMax()) {\n            big.add(num);\n        } else {\n            mid.add(num);\n        }\n        \n        this.balance();\n    }\n    \n    private void balance() {\n        int size = small.size() + mid.size() + big.size();\n        \n        if (size < m) {\n            return;\n        }\n        \n        while (small.size() > k) {\n            int victim = small.getMax();\n            small.remove(victim);\n            mid.add(victim);\n        }\n        \n        while (big.size() > k) {\n            int victim = big.getMin();\n            big.remove(victim);\n            mid.add(victim);\n        }\n        \n        while (small.size() < k) {\n            int victim = mid.getMin();\n            mid.remove(victim);\n            small.add(victim);\n        }\n        \n        while (big.size() < k) {\n            int victim = mid.getMax();\n            mid.remove(victim);\n            big.add(victim);\n        }\n    }\n    \n    public void remove(int num) {\n        if (small.containsKey(num)) {\n            small.remove(num);\n        } else if (mid.containsKey(num)) {\n            mid.remove(num);\n        } else if (big.containsKey(num)) {\n            big.remove(num);\n        }\n        \n        this.balance();\n    }\n    \n    public int avg() {\n        return this.mid.avg();\n    }\n}\n\nclass MKAverage {\n    private TripleMap map;\n    private Queue<Integer> q;\n    private int m;\n\n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.map = new TripleMap(m, k);\n        this.q = new LinkedList<Integer>();\n    }\n    \n    public void addElement(int num) {\n        this.q.add(num);\n        this.map.add(num);\n        \n        if (this.q.size() > m) {\n            int victim = this.q.remove();\n            this.map.remove(victim);\n        }\n    }\n    \n    public int calculateMKAverage() {\n        if (this.q.size() < m) {\n            return -1;\n        }\n                \n        return this.map.avg();\n    }\n}\n```\n\nLong code, and nearly un-implementable during a 1-hour interview. \n\nThe trick is: define the interface, implement the core logic, and implement the interface when having time. I define 2 extra classes in this solution `TripleMap` and `MultiMap`. During an intervew, you can call out these 2 data structure, and define the function signature first. Then, write down the MKAverage first without implementing the functions in  `TripleMap` and `MultiMap`.\n\nLike below\n\n```\nclass MultiMap {\n    public void add(Integer key) {\n    }\n    \n    public boolean containsKey(Integer key) {\n    }\n    \n    public void remove(Integer key) {\n    }\n    \n    public Integer getMin() {\n    }\n    \n    public Integer getMax() {\n    }\n    \n    public int avg() {\n    }\n    \n    public int size() {\n    }\n}\n\nclass TripleMap {\n    public MultiMap small;\n    public MultiMap mid;\n    public MultiMap big;\n    private int m;\n    private int k;\n    \n    public void add(int num) {\n    }\n\n    public void remove(int num) {\n    }\n    \n    public int avg() {\n    }\n}\n\nclass MKAverage {\n    private TripleMap map;\n    private Queue<Integer> q;\n    private int m;\n\n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.map = new TripleMap(m, k);\n        this.q = new LinkedList<Integer>();\n    }\n    \n    public void addElement(int num) {\n        this.q.add(num);\n        this.map.add(num);\n        \n        if (this.q.size() > m) {\n            int victim = this.q.remove();\n            this.map.remove(victim);\n        }\n    }\n    \n    public int calculateMKAverage() {\n        if (this.q.size() < m) {\n            return -1;\n        }\n                \n        return this.map.avg();\n    }\n}\n```\n\nThen, walk through the core algorithm with your interviewer. And start to implement the 2 classes
[]