Amazon面试总结(下篇)



  • 小菜鸟面经大放送~

    面经1:
    是个印度小哥,之前已经放了我两次鸽子了。这次迟到了5分钟,我真的以为会放第三次。上来他自我介绍,说了一大堆,然后让我自我介绍,说了大概10多分钟以后做题.

    第一题:
    Number of Islands的变种,就是题目本来是4个方向算连着的对吧。这下算8个方向。一样做的。中间还有一些小插曲。。。collaedit真的挺垃圾的。。我吐槽下。

    第二题:
    之前先问我懂不懂OOD,我说懂,说了一些基本概念以后,问我玩过CHESS没,我说没。。他就换了一个,shopping cart,这个时候只剩下大概20分钟了。他说没时间让你写完了,你就大概说说,我就大概说了下有三个class , product, order, cart,然后说了下其中的组成元素,连函数都没说到,就差不多到时间了。。
    本来很稳的。。来了个OOD,没时间说完我也有点慌了。发面经来攒人品。无论结果如何都要向凉子姐姐那样笑着走下去啊。

    面经2:

    1. a) BQ: Describe a project you owned.
      b) Validate BST.
      c) Word Break.

    2. a) BQ: Describe a project you build outside of work and school.
      b) Reverse Polish Notation.

    3. a) BQ: Describe a project you owned.
      b) Implement lock() and unlock() for TreeNode.
      - You can only lock when all children and parents are unlocked.

    4. a) BQ: Describe a project you owned.
      b) System design (Amazon.com)
      c) Find k pairs with smallest sums

    5. a) Compare version
      b) System Design (something related to graph)

    面经3:
    各位被抽到Onsite的折翼天使们好,三小时前刚刚Onsite完毕。这是我昨天根据一票其他面经总结的Skeleton Code,今天实战演习,验证了很多接口和类的设计基本都是一样的。仅以此与诸君共享

    1. 第一轮的小组discussion,今天我和onsite的另外一个小伙伴对了一下题,貌似亚麻题库就两道题:在n长度的unsorted vector里挑出前k大的元素;以及lc find celebrity的变种。我抽到的是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
      还有一个应该是正确解,但是验证的循环有点复杂,我到最后也没搞懂。

    以下是我总结的群面经验,包含了另一道题:

    • 第一轮 小组讨论:
    1. 3人一组,3份代码(解决同一问题),2个面试官,30分钟讨论,和面试官交流15分钟。

    2. 讨论代码优缺点,代码错误明显,小组讨论给出代码排名,给面试官陈述理由。

    3. 诀窍:快速读题;审题全面,明确约束和条件;快速读代码;快速整理思路(解决了什么问题,用了什么数据结构,用了什么算法,代码错误在哪,时间复杂度如何,空间复杂度如何,可扩展性如何);有效的讨论;有效的总结。

    4. 题目之一:从长度为n的数组中,选出前k大的数。不考虑空间复杂度。
      a. 将数组读入heap,pop出前k个元素。O(n+ klogn)
      b. 快速排序,选择前k个元素。O(k+ nlogn)
      c. k次外循环,每次循环遍历数组找出当前的最大元素。O(kn)

    5. 领导力:在讨论差不多时,勇于站起来总结答案,给面试官讨论结果。他人提出异议时,以理服人,耐心解释。不卑不亢,不抢话也不要不说话。表现自己,给他人机会,让所有人有参与感。

    6. 面经不宜看多,地里的面经有三份总结较好,其中两份随本帖附带。另外一份叫where is 烙印 from,大家一搜就能搜到,因为尺寸太大我上传不了。下文中“仓库”和地区其实是一个意思,因为一个地区就是一个仓库。

    7. 在skeleton code里面,第一个milestone可以优化,心好累我就不改代码了,我的代码是O(mn)的,下面我说一下优化思路,是临场想起来的。(请反复阅读order,shipping cost,product inventory的类成员都有哪些,这些应该和原题一模一样)
      真正的项目skeleton里,有ShippingCostExplorer这个类,可以看做是获取ShippingCostList的接口。也有ProductInventoryExplorer这个类,可以看做是获取product inventory list的接口。
      对SCExplorer,输入一个ShipToRegion,可以获得所有可以送达到这个Region的ShippingCostList。先获取这个list。然后scan through这个List,建立 map<FromRegion,vector>。这一步是把复杂度从O(nm)到O(n + m)的关键。然后用PIExplorer类,输入一个productID,获取所有含有这个product的ProductInventoryList。第三步,对ProductInventoryList中的每一个Inventory,提取其Region,找map[Region],这时你就得到了vector,然后把该vector和这个ProductInventory结个对扔进结果集里。

    8. 对于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。当然啦,你可以尝试验证,选择货最多的地区发货是不是可以。

    我的代码很简单的处理了发货这件事,实际的skeleton中有一个类专门用来发货。你需要调用这个类的构造函数(参数是订单),构造出来这个类,然后这个类会有transfertoshipment方法,相当于是从每个仓库预留货物。有ship,相当于是把所有预留货物发出,对各地区的库存造成永久减少。还有unfullfilorder这个方法,相当于是mark这个订单是没法配送的。还有cancel,我理解是把transfer的东西都退回去,但是不知道结果对不对。

    • 最后的最后:
      大家不要紧张~Amazon是面经摸得最透的公司了,建议大家Onsite之前都用自己熟悉的语言实现以下Skeleton和各个方法,这样上场就不慌了。.

      其实还是想给大家一个最重要的建议,那就是那个发的册子没必要好好看……注释和变量名,一定一定务必务必好好写,多写。我是强迫症,册子看了很久,项目读了很久才动手,导致时间不够。虽然对这个项目的结构已经比较清晰了,时间依然不够,第三个milestone虽然很简单但是没有写。所以后来的小伙伴们,不要觉得2:00提交,时间还长,一定上来就要快,只看面经和本文提到的类就可以了,册子看不看完全可以看心情,你需要了解的信息其实各个面经都给的差不多了。

      一定要快快快,这样你才有时间写注释,clean代码,以及写完全部的题。小小的牢骚,感觉自己准备的还是挺充分的,结果第二题被面试官一吓,临场改成了minimize late orders,到最后怎么跑test case都没有正确的结果。第三题干脆没写,注释也写的很少,估计和亚麻说再见了……所以,大家一定要快快写,只有写完你才有时间去写注释和clean代码,边写边优化,怎么感觉都不靠谱。

    大家可以加入我建立的CS找工作群哦,之后会在群里分享工作信息、面经信息以及交流刷题心得,大家相互鼓励,也欢迎找到工作的朋友一起分享信息哦!
    之后会继续搬运面经给大家哒~

    0_1482295836740_QR.jpg


登录后回复
 

与 BitTiger Community 的连接断开,我们正在尝试重连,请耐心等待