Amazon Onsite: Group Interview

Round 1

亚麻 group 有两个内容，一个是第一题讨论，每个人抽到同一个题目的三种不同解法，根据时间复杂度或者空间复杂度排序，讨论然后总结，
总共有三题，目前。

第一轮的小组discussion，今天我和onsite的另外一个小伙伴对了一下题，貌似亚麻题库就两道题：在n长度的unsorted vector里挑出前k大的元素；以及lc find celebrity的变种。

每个组会得到一个问题，每个组员会拿到同一个问题的不同解决方案。小组讨论每个人的解法有什么优缺点，分析时间复杂度，然后给三个解法排个序，哪个相对来说最好，哪个相对来说最不好。（根据地里面经，一般都是 2 > 1 > 3）一共好像是15分钟。包括讨论和跟一起跟面试官交流。

注意仔细审题
题目要求只考虑时间复杂度，不考虑空间复杂度，不用优化。但是面试官会要求小组提出优化的大概方向。

Find Celebrity (lc 277)

我抽到的是find celebrity的变种，两份代码有bug，一份代码（貌似）是$$O(n)$$的最优解。bug分别是：第一轮循环后找到的celebrity candidate，没有验证这是不是真正的celebrity（少了一次循环）；用内外两重循环，去验证每一个元素是不是celebrity，但是代码有bug（内循环的break其实应该跳过return celebrity这个语句）。如下：

for each element:  
     for each otherelement:  
          if (element == otherelement) : continue;  
          if (otherelement doesn't know element): break;  
     return celebrity  
return null

还有一个应该是正确解，但是验证的循环有点复杂，我到最后也没搞懂。

Top K (lc 347)

求最小／最大的前K个元素, 有quick sort, nested loop, 和 heap

三个不同的解法。

第一个是暴力，

两层for loop循环，复杂度为 $$O(n^2)$$

k次外循环，每次循环遍历数组找出当前的最大元素。$$O(kn)$$

第二个，也就是我拿到的解法，快速选择。

快速排序，选择前k个元素。$$O(nlogn+k)$$

看pivot所在位置是不是第k个，二分，时间复杂度为$$O(n)$$

第三个是用 优先队列(priority queue)。

将数组读入heap，pop出前k个元素。$$O(k+nlogn)$$

将数组扫一遍读入heap，heap中存前k个元素。$$O(nlogk)$$

第二个解法其实是不完整的代码，缺少递归的部分。（不知道我说啥的同学，按照上面三个解法把原题做一遍就知道了，这里就不贴代码了。）

不完整的代码是肯定垫底的

需要注意的是暴力解和quicksort解法会有错，暴力解是下表越界(当i==0), 类似quicksort解法是只有一个pass, 设定int pivot = array[K-1],
不更新pivot, 然后把比pivot小的放左边，比pivot大的放右边。当然，一切以到现场代码为准，如果不确定要看下队友的代码。

然后排序完之后，会给面试官确认。面试官一般都会问问优化的问题。注意表现出领导力，这是亚麻看重的地方（带着其他人审题，分析代码什么的）

最后一道题是leetcode 117, 也是三种解法，按空间复杂度排序，此题详细解释在地里另一篇面经有。

Populating Next Right Pointers in Each Node II (lc 117)

第一部分讨论代码，楼主分到的是一个有关二叉树的。要实现一个方法可以找到每个节点同层的右边节点。

同组两个三哥看代码很快，我还没看完他俩就说上了。。一定要看清题目要求，楼主这道题要求最小化空间复杂度，

所以三哥说到了比较时间复杂度马上被我纠正，哈哈。三份代码分别用了一个arrayList，两个LinkedList和一个Hashmap。

最后我们给出一个arrayList最好，hashmap最差，然后面试官问了每个人手里代码的空间复杂度，也不知道对错就结束了。

Round 2

这就是传说中的送货问题。

Tips: 在写代码中途会有一个30分钟的一对一interview。主要是讲第一小题的解法和第二小题的思路和实现所用的数据结构。自己去选择自己的时间段（一共有4个时间段可以选），我建议选择第二个时间段，当时我就选的第三个时间段，结果轮到我的时候，我基本上都写完了……
把每一道题的时间复杂度分析清楚，因为在提交代码之后还会有一轮15分钟的interview，就会让你解释每个解法的时间复杂度。

题目背景大概如下：（建议配合代码一起看，上传的是Java的版本）

公司的主要业务就是淘宝。那么淘宝就需要送货。从用户下订单到送货，有很多因素需要考虑（库存量，库存所在地，收货地区，运费等等）。
每天公司都会产生很多的订单，每一个订单对应只有一个商品（一个商品ID），而公司在全国几个大的地区都有设置仓库。仓库里有商品，每个商品有不同的ID唯一识别。另外，每个仓库都有能从自己的所在地运送到其他地区的费用和方式。

三个小题：

给定一个商品ID和一个目的地，返回所有对应这个商品的库存和运送花费。

给定一个订单的列表，要么满足运送最多的订单，要么满足最小化迟到的订单（尽量在用户预期时间内送到）

跟第二小题一样的输入，满足平均每单运费最小。

在第二小题和第三小题中，只需要完成核心的算法代码部分，输入和输出都不用担心，并且在运行主函数的时候，会有百分比打印在console上。

我第三小题没有做，但是在第二小题里，基本把第三小题也做了，结果记得是91%的fulfill orders，30%的ontime order，$4的average shipping cost

题目本身并不难，而且也并不需要很复杂的实现，什么树，什么图都用不着，要么排序，要么用优先队列。主要考虑的是很多edge cases和优化。

对于第一小题的建议是，先写暴力的方法（两个for循环嵌套），等出去一对一的时候，就可以让面试官问优化的事，然后一秒钟答上用HashMap。让面试官感觉你反应很快。

对于第二小题，见仁见智，反正写出的算法合理并且复杂度不要太高就行。

对于第三小题，对shippingcost排个序，然后想想优化就行了。

为什么不多说，是因为亚麻考这题就是看每个人的思路，说的细致了就给大家有了先入为主的框架，想edge case就不好想了，另外每个人的解法都不一样，如果能有用树或者图，面试官同意，在2个小时左右能够写出完整代码的话，也是可以的，反正我是没有想到……

第一题: milestone 1

一定要做对,影响到第二题导出的是 list

在skeleton code里面，第一个milestone可以优化，心好累我就不改代码了，我的代码是O(mn)的，下面我说一下优化思路，是临场想起来的。（请反复阅读order，shipping cost，product inventory的类成员都有哪些，这些应该和原题一模一样）
真正的项目skeleton里，有ShippingCostExplorer这个类，可以看做是获取ShippingCostList的接口。也有ProductInventoryExplorer这个类，可以看做是获取product inventory list的接口。

Milestone1需要返回一个List,里面装的是productInventoryShippingCost, 输入是一个产品的productID和目的地，你根据这两个信息调用相应的API能返回所有含有这个产品的仓库列表和所有能运输到目的地的运输类型，然后你把这两者合并在一起返回。楼主也是用hashMap作的，key是shipFrom (Region 类型), value是List<ShippingCost>, 然后在第二个for loop里面一个一个查找仓库，如果hashmap里面有这个仓库的地址(shipFrom),就new 一个productInventoryShippingCost, 然后返回即可

Hash Map

对SCExplorer，输入一个ShipToRegion，可以获得所有可以送达到这个Region的ShippingCostList。先获取这个list。然后scan through这个List，建立 map<FromRegion，vector<ShippingCost>>。这一步是把复杂度从O（nm）到O(n + m)的关键。然后用PIExplorer类，输入一个productID，获取所有含有这个product的ProductInventoryList。第三步，对ProductInventoryList中的每一个Inventory，提取其Region，找map[Region]，这时你就得到了vector<ShippingCost>，然后把该vector和这个ProductInventory结个对扔进结果集里。

public static List<ShippingPlan> milestone1(Order order) {
        List<ShippingPlan> res = new LinkedList<>();
        Region to = order.region;
        List<ShippingCost> allCosts = ShippingCostExporer.getShippingCostList(to);
        int productID = order.getOrderID();
        List<ProductInventory> inventories = ProductInventoryExplorer2.getProductInventoryList(productID, inventory);
        Map<Region, List<ShippingCost>> map = new HashMap<>();
        for (ShippingCost cost : allCosts) {
                Region from = cost.getFrom();
                if (!map.containsKey(from))
                        map.put(from, new LinkedList<>());
                map.get(from).add(cost);
        }
        for (ProductInventory productInventory : inventories) {. from: 1point3acres.com/bbs 
                if (productInventory.getQuantity() == 0)
                        continue;
                Region from = productInventory.getRegion();
                if (map.containsKey(from)) {
                        ShippingPlan plan = new ShippingPlan(productInventory, map.get(from));
                        res.add(plan);
                }
        }
        return res;
}

第二题: milestone 2

不需要导出
Inventory 有数量限制
Inventory 和 order 只能存一种 product
Inventory 里只有 id, region, quantity, 没有时间概念,order 里有时间概念

将所有的order对应的所有shippingCost根据shippingCost.days heapify成了一个min-heap对吧？然后每次选择shippingCost.days最小的shippingCost对应的inventory，如果这个inventory数量足够就一次性发完，不足就分开发，直到order的quantity发完为止。

非常感谢楼主的回答，我感觉这里multi threading的用途是在实际的product中，用户订单的请求肯定非常大，而且这个service也肯定部署在多个server上，所以这里需要multi threading 来同时处理大量的请求。
还有预处理product ID，也是可以把product ID进行分类，然后不同的服务器处理不同类别的product ID，这样我们既可以根据product 的需求量来进行服务器的调整也可以把非常popular的product 放到cache中，加快服务器的响应速度。这是我的个人理解，如果与楼主的想法有出入，希望楼主改正，以免扰乱大家的思路~

对于milestone 2，代码是利用了两次Greedy。我在面试时说这是可以得到optimal的Most Fulfilled Orders，然而并不是。同学说这是个NP hard，没法有最优解……大家面试时，可以说这个策略会得到较多的fullfiled的订单，但这不是最优解。反例大家可以想一想，假设：
A地区可以送达B地区，B地区可以送达B地区，B地区可以送达A地区。B地区送到哪里都是最少的代价+最少的天数。
A有个仓库也有个订单。仓库有商品3件，订单需要4件。B有个仓库也有个订单。仓库有商品6件，订单需要3件。
如果我们首先处理订单数少的订单，然后每个订单选送达最快的地区发货。那么解是：B地区发货3件到B地区的订单。A的订单是unfulfilled。
而最优解是：A发货到B，B发货到A。这样是一个最优解，都能fulfill。当然啦，你可以尝试验证，选择货最多的地区发货是不是可以。

用的是贪心，输入是一个order的list, 让你选择最大化unfulfilled order或者minimize late orders.

每个order里只有一种产品，有这种产品的个数，还有目的地。一开始先从小的产品数的order处理，然后才是大的。这里用一个sort就可以了。sort完之后开始选择仓库发货.
每个仓库只能存一种产品，我这里用的一个优先队列和hashmap, 优先选择发货速度最快的仓库发货，order可以拼单，即从不同仓库发货，需要调用一些给定的method,比如ship(),
transferToShipment, unableToShip()等等，这些到现场再看来的及。。

优先队列和hashmap是为了找出那些满足条件的仓库

public class MileStone{
    static List<Order> orders;
    static List<ProductInventory> inventory;
    static List<ShippingCost> costs;
    public static void milestone2() {
        Map<ProductInventory, Map<Region, ShippingCost>> map = new HashMap<>();
        for(ProductInventory productInventory : inventory){
             Map<Region, ShippingCost> fastShipping = getFastest(productInventory);
             map.put(productInventory, fastShipping);
        }
        Map<Integer, List<Order>> orders = group(orders);
        for(int productID :dfs orders.keySet()){
            List<Order> orderList = groupOrder.get(productID);
            Max max = new Max();
            List<OrderProcess> res = new LinkedList<>();
            List<ProductInventory> inventoryList = ProductInventoryExplorer.getProductInventoryList(productID, inventory);
            max.dfs(orderList, inventoryList, map, 0, res);
            res = max.list;
            if(res != null){

            for(OrderProcess op: res){
                ship(op);//此处要改写
            }
            }
        }
    }

    public static Map<Integer, List<Order>> group(List<Order> orders){
        Map<Integer, List<Order>> orderGroup = new HashMap<>();
        for(Order order: orders){
            int productID = order.getOrderID();
            if(!orderGroup.containsKey(productID))
                orderGroup.put(productID, new LinkedList<Order>());
            orderGroup.get(productID).add(order);
        }
        return orderGroup;
    }

    public static Map<Region, ShippingCost> getFastest(ProductInventory inventory){
        Map<Region, ShippingCost> map = new HashMap<>();
        Region from = inventory.region;
        for(ShippingCost cost : costs){
            if(cost.getFrom()== from){
                Region to = cost.getTo();
                if(!map.containsKey(to))
                    map.put(to, cost);
                else if(cost.days < map.get(to).days){
                    map.put(to, cost);
                }
            }
        }
        return map;
    }
}

class Max{
    int max = 0;
    List<OrderProcess> list;


    public  void dfs(List<Order> orderGroup, List<ProductInventory> inventoryList,Map<ProductInventory, Map<Region, ShippingCost>> map, int i, List<OrderProcess> temp){
        if(i == orderGroup.size()){
            if(temp.size() > max)
                list = new LinkedList<>(temp);
                max = temp.size();
            return;

        }
        Order order = orderGroup.get(i);
        Region to = order.region;
        boolean found = false;
        for(ProductInventory inv: inventoryList){
            if(inv.getQuantity() >= order.quantity && map.containsKey(inv)&&map.get(inv).containsKey(to)){
                found = true;
                inv.reduceQuantity(order.quantity);
                temp.add(new OrderProcess(order, inv,map.get(inv).get(to)));
                dfs(orderGroup, inventoryList,map,i+1, temp);
                temp.remove(temp.size()-1);
                inv.reduceQuantity(0-order.quantity);

            }
        }
        if(!found){
            //dfs(orderGroup, inventoryList,map,i+1, temp); //此处为拼单
        }
    }
}

class OrderProcess{
    Order order;
    ProductInventory inventory;
    ShippingCost cost;
    public OrderProcess(Order order,ProductInventory inventory,ShippingCost cost){
        this.order = order;
        this.inventory = inventory;
        this.cost = cost;
    }
}

第三题: milestone 3

milestone 3：如果选择fulfill最多的订单（拿offer的很多都是做这个优化，推荐），milestone3完全可以复用milestone2的代码。只需让第二个comparator比较谁costPerItem较小就可以了。（原本是days较小）

亚麻 onsite. 感恩地里感恩小伙伴

下午刚面完。感谢地里的面经，skeleton code 很有帮助。时间还是比较紧，如果紧张的话。北狗很难吃，建议自己带点干粮。这边中国城的食物我只能说，祝幸福。小组讨论，我们组是 link binary tree 那个。lc117，直接写并不需要使用额外空间，面的时候我提出了这点，不造面试官怎么想。同组的白人小妹比较坑，她拿到 arraylist 那份，类似 BFS 吧。我的是 hashmap + DFS，还有个国人小哥是两个 linked list。排序我们给的 arraylist < linked list < hashmap。不太确定，看不到他们的代码，也说不太清楚。

第一题想都不用想，直接写没有问题。跑数据出来比例记得是57, 40+。蜜低，但无妨吧。只用到了 ShippingCostExplorer 和 ProductInventoryExplorer。用了 map，30分钟 interview，两个大哥表示第一题酱已经 optimal。jiang信jiang疑

第二题对第一特得到的 productInventoryShippingCostList 进行处理，只用到 ShippingBuilder 里的函数，transfer，ship，cancel，cannotship。我的方法比较 low，当时想建个 map， key 是 shipFrom+shipTo 的 string，value 是最快的方式，后来发现 ShippingCostExplorer 不会用/用不了，这个时候马上要30分钟了，也没改好，那两大哥就说憋 bb先实现囖。回来马上改代码，用很蠢的方法，把 order 按 quantity 排序，遍历 order，每个 order 通过 milestone1 都得到一个 productInventoryShippingCostList，一个循环把 productInventoryShippingCostList 里的 shippingCostList 按 shipping days 排序，之后把 productInventoryShippingCostList 放到 priority queue 里，comparator 比较 p.getShippingCostList.get(0).getShipDays，再之后就 while loop pq，过程中只要 shippingBuilder.getUnShippedQuantitySoFar != 0，就继续 transfer，满了就 break 囖，transfer 函数前面明确写了，订单发货数不能超。之后再 check 一下 shippingBuilder.getUnShippedQuantitySoFar，满了就 ship，不然 shippinBuilder.canNotShipped，shippinBuilder.cancel。得到的数据是 88.多和 75 还是 77 点多。一个小提醒就是，测试的时候记得改数据，我一开始没改看到57和四十多真的吓得投掉，一个小伙伴也没改，不断表示 gg。心疼他。注释我写的一堆，时间复杂度也写。大概一点半开始写。写到最后...... 第三题我把第二题直接复制了，就把 shipping days 改成了 cost..... 最后，虾图十年不遇的寒冷和鹅毛大雪我都遇上了，希望好孕！也祝各位好孕！找工这个磨人的小搓澡巾，是时候扔掉了。最后的最后，我可以帮忙拉 slack。

亚麻Group onsite面经

亚麻 Group 2.8 面试 Tips 分享 & 延迟回复

2.8 在 Day 1 的 group assessment 面试.
刚刚收到邮件， decision 被delay..... 听说本身普通onsite 通过几率不高，所以我不太抱希望，继续moving on. 看起来现在很多人的回复都被延迟，很好奇为什么.

Anyways, 不废话，来分享一下我面下来的感受.
田里的面经真的很全，基本真正的考题跟面经分享的code差不多, 所以大家不用太紧张，只要把面经都准备好了就差不多了. 我同意很多其他人的，重点在于沟通能力，

第一轮我被考到类似于 find celebrity 的那道题.

其实这个第一轮不准备也可以. 具体的format 其他帖子里也有发, 这个就不提了.
重点: 我觉得的是要在 discussion 时表现出你的领导力/ team spirit，这点我做的不是很好. 感觉自己并没有给出属于自己的见解, 我觉得这一点挺重要的.
我和另一个队友的code 都有错，但是面试官仍然要求在这2份之中排哪个比较好哪个比较不好, and why? -当时听到后有点懵，因为都是错的话如何比较...? anyways, 这个就仁者见仁智者见智. 但是如果你给出理由的话一定要able to justify
- 比如当时我们说 version 3 比 version 1 好，因为有些test case 3 可能可以跑过但是1不可以, 于是面试官就追问你们用了什么 test cases........ 但是我们自己讨论的时候并没有用真正的数据....... 所以如果给出一个 reason 最好有个 concrete 根据.

第2轮题目没有什么意外， 2个 1:1 interview 也比较简单。面试官并没有问什么难得问题. 我觉得这个真的是depends on your interviewers.

他们主要就是问我对 Milstone 1, 2, 3 的解法是什么，怎么想的，Milstone 2 可以怎么进一步优化.
- 如果说你用的是贪心作法，那么你可以如何优化这个贪心? 之前sort 的话除了可以 by quantity, 你还可以如何sort?
- 第2位面试官问我之前的面试官给我了什么 advice, 我有根据这个advice 改了吗？这里要注意如果没有改，要说出为什么没有改，如果有机会让你继续work on 这个，你会怎么改.
- 我觉得貌似他们并没有看我的 code...?! anyways, 这些是我记得的
- 最后大家记得问面试官一些问题，可以对Amazon 进一步了解也可以 show initiative
- 还有amazon principle 其实挺重要的，在1:1 面试官会经常问到某一个设计 choice 会对客户造成什么影响, 如何可以进一步提高用户体验.

最后祝大家面试顺利，多多拿 offer!

以下是对我很有帮助的帖子，非常感谢之前分享面经的前辈~! 如果没有这些，这次的面试可能会更悲剧....
传送门 1: https://www.1point3acres.com/bbs/thread-214427-1-1.html
传送门 2: https://www.1point3acres.com/bbs/thread-222944-1-1.html
传送门 3: https://www.1point3acres.com/bbs/thread-223714-1-1.html
传送门 4: https://www.1point3acres.com/bbs/thread-215464-1-1.html
传送门 5: https://www.1point3acres.com/bbs/thread-224260-1-1.html

Amazon Onsite

Amazon Onsite: Group Interview

Round 1

Find Celebrity (lc 277)

Top K (lc 347)

Populating Next Right Pointers in Each Node II (lc 117)

Round 2

题目背景大概如下：（建议配合代码一起看，上传的是Java的版本）

三个小题：