Alexa
整理了一些关于Alexa的面经，有时间的话会持续跟新。
OA
两道题都是题库里的题，面的alexa组。
- k nearest point，背景是一个城市有N个牛排馆，牛排馆的坐标都是存在allocations的list里面(类型是List<List<Integer>>)，然后要求返回k个最近的牛排馆给用户，用户位置在坐标(0, 0)。
思路：先建立每个牛排馆location和它到用户位置(0, 0)的距离的关系，然后用大小为k的max heap来拿到k个最近的位置，返回类型是List<List<Integer>>。
这题正常做法是弄一个inner class来把location和距离的关系包装一下，我不知道为啥脑子抽了用hashmap来建立对应关系，最终这题22个test cases我只过了18个，我估摸着四个test cases里有重复的location，我的hashmap把重复location滤掉了。
- two sum closest变形，背景是无人机送货，无人机有最大里程，然后给了两个list，分别是出发和返回的里程数，数据类型是List<List<Integer>>，list里面只有id和里程两个值，要求找出所有出发和返回里程数之和最接近无人机最大里程的pair。比如，最大里程M = 11000，forwarding = [[1, 1000],[2, 7000],[3, 12000]], retrun = [[1, 10000],[2, 9000],[3, 3000],[4, 2000]], 最接近的里程和是10000，所以结果是[[1, 2],[2, 3]].
思路：先用两个list sort一下，因为题目里没说给的list是sort好的，然后用two pointers找到最接近的里程，接着把return list里的id和里程的关系放到hashmap里，用two sum的解法就弄出来了。这题test cases全过了
算法数据结构
- 给一个 array of string，是 user 的 log，每一个 string 是 id，time，求出连续三天都 出现 的 user
- 给一个 video dataset，graph 表示，相连的就是相似的 video。每个 video 也有 rating。求给一个 video id，找出相似的 video 里面最高 rating 的 k 个
- Number of Islands
- The Maze，就是DFS，写完了。他说你优化一下。
- 给一个unique int array，返回所有的可以构成一个sum target的combination。sort了一下稍微trim一下搜索范围，然后recursion dfs搞定，如果不是要具体的combination结果，只要count的话可以dp做。
- Add Two Numbers II两个链表求和
- Longest Substring Without Repeating Characters
- 给a list of number建BST 然后求任意两个数在tree里的距离
- 找一个string里所有长度为k的无重复字母的substring，这里有个坑，如果有重复要dedup
- 链表基本操作, 找到第k个node, 还有 intersection of linkedlist 比较简单, 注意边界条件
- 多重背包题目. 大意是: 有一些不同容量的盒子来装棒球, 比如6, 9, 15 然后有一个n个棒球, 求恰好装满情况下, 使用最小盒子的情况
- Top K Frequent Elements
- 一个数组里有两种颜色 排序数组使得每个颜色的排列在一起； followup 如果有三种颜色怎么办？
- 给一个数组表示一个游戏的board，每个index对应的数代表在这个位置可以往后走的步数，如果走到的位置对应数值为0，就fail了，如果能够走到数组的最后， 则为success。要求输出一个winning path
ex. [1, 3, 0, 2, 1, 2] 一个wining path：0, 1, 3, 5 (index).- Maximum Gap
- Lowest Common Ancestor of a Binary Tree 找binary tree的两个node的最小共同祖先
先有getParent的API。没有getParent的API怎么写。时间空间复杂度。- 合并两个binary tree
- 给一个string，和一组关键字，要求找到最短的包含所有关键字的substring，输出是长度
- 2 sum，3 sum 然后展开问了一下n sum，最后follow up没有写代码
20 . 给定一个整数，求所有的Prime number.- 判断是否有重复的数字；合并两个有序的列表，扩展到特别大的话（可能是扩展到了未排序的），怎么办，外部排序
- find first non repeating character in a word.
- Meeting Rooms II变体，输入是一个list of objects类似如下：
StartTime EndTime BandwidthUse
10:00:01 AM 10:00:28 AM 100
10:00:06 AM 10:00:16 AM 50
10:00:10 AM 10:00:30 AM 150
求Peak BandwidthUse，比如上面例子就是300，在10:00:10 AM和10:00:16 AM这个Interval里，要自己定义Object表示输入。- Max Stack
- 输入preorder和inorder的结果，重新生成树。允许递归，但要求在O(n)之内。
- 各大公司都经常考的题目，设计一个数据结构可以得到最新的股票价格
例如， input 是个stream [google, 1000] [MS, 100] [Appl 180] [AMZN 1600] [MS 101]
然后get (goog) 能拿到1000， get (ms) 能拿到101 ， 再get(ms)返回 空- 写一个函数 找出所有 组合使得 a^2+b^2+c^2+d^2 = k， k是input。写完之后让优化。
- Copy List with Random Pointer秒了，但是follow up叫我不要用hashmap, 解法看这里single linked list的iteration做法， constant space complexity O(1) and linear time complexity O(N)
- Search in Rotated Sorted Array
- Single Number
follow up 如果输入排好序，如何优化
系统设计和OOD
- 设计一个delivery system，如果有单子，就要找一个 carrier。carrier 是可以 register 这个系统，这样就是有单子的时候就是候选。主要是设计怎么传参数，每个 class 都负责什么功能。
- 飞机场设计。跑道的schedule （飞机起飞降落） 登机口的管理（飞机停靠 时间等） 要设计数据结构，考虑尽可能最大化机场的capacity followup会问怎么提高parallelism.
- 设计 customer who bought this also bought的推荐系统。如何deploy。
- 问了怎么设计photosharing website。可以从前后端用什么框架，如何CICD，如何部署，分布式，图片存储用aws s3，load-balancer，加密之类的都可以说。
- 系统设计, CAP理论, 一致性hash, 设计一个爬虫爬 Amazon.com
- 设计一个会议室预定系统 考虑每个会议室会有一系列会议schedule 如果用户有一个新的会议request 怎么找到符合条件的会议室等 设计的时候要考虑OO
- 设计系统可以让用户上传exe程序然后在你的HW上跑，用户需要得到std out。
- 设计alexa和nest对话的接口
- 设计在线图书管理系统
- distributed message system
- 设计LINUX的find函数,设计加code，会一直给你附加要求。知道我写出整个library的structure确保能随时加功能后，大叔表示满意。国人小哥一直在旁边笑，我问问题的时候diss了他一下。时间到了两人离场。
- typeahead，然后用trie实现一个简单的
- 一个巨大文件里面有很多url，验证每个url是否合法
- 一个64bit的random generator 每次call这个function返回一个随机的数，large scale
BQ
- 你工作或者学习中遇到过和队友或者同事意见特别不相同的情况吗？你听他们的还是他们听你的？为什么？最后结果怎么样？
- 你遇到过最难解决的技术问题是什么？如果几乎没有解决方案的话你怎么做的？最后成功了吗？
- 你有没有过ddl前需要做重大决定，这个决定可能造成你meet ddl，也可能造成不能meet ddl？你么做的，最后结果真么样？
- 如果你的manager分配给特别不喜欢的活你怎么办？
- 如果你收到一份function specification照着做，里面很多点你不同意，你怎么和manager或者pm沟通？
- 如果你写的function specification被很多人喷出很多问题，你怎么办？
- 如果你很不同意你的manager的一些做法，你咋办？
- 如果你的队友或者同事有些愿意比如病了或者家庭原因，干不完他们的活，你怎么办？
- 如果你发现一个严重影响客户体验的bug或者问题，但这块不是你负责，你怎么办？
- 如果你发现一个事非常模棱两可，比如function specification你觉得不清楚，或者一段old code 1完全看不懂，你怎么办？
- 你做过最难的project是什么，你负责管理和分配人力吗？
- tell me a time you overcommit to your consumers之类的