logo资料库

airbnb 面试题库 深秋版 pdf.pdf

发布时间：2022-06-03 发布人：admin 分类：说明书 资料大小：1.46M 资料格式：pdf 举报 版权申诉
第1页 / 共66页
第2页 / 共66页
第3页 / 共66页
第4页 / 共66页
第5页 / 共66页
第6页 / 共66页
第7页 / 共66页
第8页 / 共66页
资料共66页，剩余部分请下载后查看
    Airbnb ⾯试题 2017 深秋版 一. Disclaim ................................................................................................................................ 3 二. Coding/Design Questions ..................................................................................................... 3 1. Collatz Conjecture .......................................................................................................... 4 2. Implement Queue with Limited Size of Arrays .............................................................. 5 3. List of List (2D List) Iterator .......................................................................................... 7 4. Display Page (Pagination) ............................................................................................... 8 5. Calculator ...................................................................................................................... 12 6. Travel Buddy (Buddy List) ........................................................................................... 12 7. File System ................................................................................................................... 15 8. Palindrome Pairs ........................................................................................................... 17 9. Find Median in Large File of Integers .......................................................................... 17 10. IP Range to CIDR ......................................................................................................... 19 11. CSV parser .................................................................................................................... 21 12. Text Justification ........................................................................................................... 23 13. Regular Experssion ....................................................................................................... 24 14. Water Drop/ Water Land .............................................................................................. 25 15. Hilbert Curve
 .............................................................................................................. 28 16. Simulate Diplomacy ...................................................................................................... 29 17. Meeting Time ................................................................................................................ 30 18. Round Prices ................................................................................................................. 31 19. Sliding Game (8 Puzzles) .............................................................................................. 34 20. Maximum Number a Night You Can Accommodate ................................................... 37 21. Find Case Combinations of a String ............................................................................. 38 22. Menu Combination Sum ............................................................................................... 39 23. K Edit Distance ............................................................................................................. 40 24. Boggle Game ................................................................................................................ 42 25. Minimum Cost with At Most K Stops .......................................................................... 45 26. String Pyramids Transition Matrix ............................................................................... 47 27. Finding Ocean ............................................................................................................... 50 28. Preference List .............................................................................................................. 51 29. Minimum Vertices to Traverse Directed Graph ........................................................... 53 30. 10 Wizards .................................................................................................................... 55 31. Number of Intersected Rectangles ................................................................................ 56 32. echo TCP client ............................................................................................................. 57 33. Guess Number ............................................................................................................... 58 34. Tagged as AirBnB at Leetcode ..................................................................................... 61 三. Design questions ................................................................................................................. 61 1. RSS 订阅系统 / Feed System ....................................................................................... 62
    2. key value storage ........................................................................................................... 62 3. Bank System ................................................................................................................. 62 4. 设计翻译系统............................................................................................................... 63 四. Cross Functional Questions ................................................................................................ 64
    一. Disclaim 这些题目是从地里, glassdoor, CSDN, GeekForGeeks等地收集来的。如果有任何建议或问题，请联系 coolguy@一亩三分地。欢迎撒米。 参考链接： • http://www.1point3acres.com/bbs/forum.php?mod=collection&action=view&ctid=277 • http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=282721 • http://community.bittiger.io/topic/626/airbnb%E9%9D%A2%E7%BB%8F-%E4%B8%8A%E7%AF% 87 • http://community.bittiger.io/topic/627/airbnb%E9%9D%A2%E7%BB%8F-%E4%B8%8B%E7%AF% 87 • https://github.com/jxr041100/system_design 二. Coding/Design Questions 一些问题的 source codes: • 一些问题的 Python 解法: http://www.1point3acres.com/bbs/thread-220456-1-1.html • 一些问题的 C++解法: http://zhangpin.info/2017/06/01/airbnb%E9%9D%A2%E8%AF%95%E9%A2%98%E6%B1%87%E6 %80%BB/ 问题的大致分类： • • • • 数学问题: § Collatz Conjecture 数据结构: § Design Queue with Limited Size of Array § List of List (2D List) Iterator § Display Page (Pagination) § Calculator § Travel Buddy (Buddy List) § Trie: File System § Trie: Palindrome Pairs Find Median in Large File of Integers o Bit Operations IP Range to CIDR § Binary Search: § 状态机或矩阵变化 § CSV Parser § § Water Land § Hilbert Curve § Text Justification § Regular Experssion Simulate Diplomacy
    • • • • • • Find Case Combinations of a String Time Interval § Meeting Time Greedy § Round Numbers § A*: Sliding Game DP § Maximum Number a Night You Can Accommodate Permutation/Combination/Search(BFS/DFS)： § § Menu Combination Sum § K Edit Distance § Boggle Game § Minimum Cost with At Most K Stops § 图论 § § Topological Sorting： Preference List § Minimum Verticaes to Traverse Directed Graph § 有向图最短路径: 10 Wizards § Union Find: Number of Intersected Rectangles Calling AirBnB Internal Services § echo TCP client § Guess Number String Pyramids Transition Matrix Flood Filling: Finding Ocean Coding Exercise： https://www.hackerrank.com/tests/52d6d0953bddb/357c91cd6d50039a74f53a47501e23d7 https://www.hackerrank.com/tests/9e26m70rtfm/cfa8b776a12fb5661055772b4297e8ca 1. Collatz Conjecture https://en.wikipedia.org/wiki/Collatz_conjecture http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=273149 题目是给你公式，比如偶数的话除 2，奇数的话就变成 3*n+1，对于任何一个正数，数学猜想是最 终他会变成 1。每变一步步数加 1，给一个上限，让找出范围内最长步数。 比如 7，变换到 1 是如下顺序：7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1, 总 共需要 17 步。 Map map = new HashMap<>(); private int findSteps(int num) { if (num <= 1) return 1; if (map.containsKey(num)) return map.get(num); if (num % 2 == 0) return 1 + findSteps(num / 2); return 1 + findSteps(3 * num + 1);
    } public int findLongestSteps(int num) { if (num < 1) return 0; int res = 0; for (int i = 1; i <= num; i++) { int t = findSteps(i); map.put(i, t); res = Math.max(res, t); } return res; } Collatz Conjecture 2. Implement Queue with Limited Size of Arrays https://www.cs.bu.edu/teaching/c/queue/array/types.html http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=279191 Design a Queue with arrayList, 但是有限制条件, arraylist 的长度最多为 10, queue 不限制长度。 简单点儿方法可以把每个 array 最后一个 item 存下一个 array 的指针，这样每个 size 为 10 的 array 可以存 9 个元素。在空间上没有很高效，但是实现起来容易一些。 pop, 先看外边的 list 中最后一个 list 的大小, 如果是 1, 删了当前的 list, 返回, 如果不是, 返回当前 list 最后一个元素 push, 和上边相反, 当前最后一个 list 的大小是 10, 就建个新的. queue 啊 更简单了, pop 的时候用 iterator, 自动每次都走第一个 push 的时候没区别 楼主可以看下 circular buffer,感觉可以用双指针解决 http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=215975 implement 一个 queue，但是要求用 int[]储存，并且一次生成的 int[]长度不可以超过 5。 其实这是 一个内存分配的模型，每个 int[]可以看成一个 block 的抽象，每次需要加更多元素的时候就要申 请多分配 block，remove 的时候就要回收 block。标准做法是用 linkedlist，结果秀逗了用了 tree， 面试官居然就让我这么写了，他多追问一下我就想出来了。不过还好过了。 http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=294918 其实就是 linkedlist 来解。面试官的思路也是需要自己创建 listnode 里面包含 limied size 的 array。 如果这样的话，就比较简单了，就用一长串 linked list 存储就好了，每个位置 node 放 limited size 元素。
    public class QueueWithFixedArray { private int fixedSize; private int count; private int head; private int tail; private List headList; private List tailList; public QueueWithFixedArray(int fixedSize) { this.fixedSize = fixedSize; this.count = 0; this.head = 0; this.tail = 0; this.headList = new ArrayList<>(); this.tailList = this.headList; } public void offer(int num) { if (tail == fixedSize - 1) { List newList = new ArrayList<>(); newList.add(num); tailList.add(newList); tailList = (List)tailList.get(tail); tail = 0; } else { tailList.add(num); } count++; tail++; } public Integer poll() { if (count == 0) { return null; } int num = (int)headList.get(head); head++; count--; if (head == fixedSize - 1) { List newList = (List)headList.get(head); headList.clear(); headList = newList; head = 0; } return num; } public int size() { return count; } } Implement Queue with Fixed size of Arrays
    3. List of List (2D List) Iterator Leetcode 相似问题: • • Leetcode #251 Flatten 2D Vector Leetcode #341 Flatten Nested List Iterator For example, Given 2d vector = [
[1,2], [3], [4,5,6] ] By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6]. • boolean hasNext() return true if there is another element in the set • • int next() return the value of the next element in the array void remove() remove the last element returned by the iterator. o o That is, remove the element that the previous next() returned. o This method can be called only once per call to next(), otherwise an exception will be thrown. Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next(). The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method. So the remove() method actually removes the element returned from the next(). http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=167190 remove 是 remove 上一个 getNext() get 到的数。就是说不 remove 还没 getNext 的数的意思 举个例子： 如果函数被 call 的顺序是这样的：hasnext() getnext() hasnext() getnext() remove() 假设 data 是 ［［1，2］［3］］ 那么返回 true, 1, true, 2, void data 变为 [[1], [3]] public class Solution implements Iterator { private Iterator> rowIter; private Iterator colIter; public Solution(List> vec2d) { rowIter = vec2d.iterator(); colIter = Collections.emptyIterator(); } @Override public Integer next() { return colIter.next();
    } @Override public boolean hasNext() { while ((colIter == null || !colIter.hasNext()) && rowIter.hasNext()) colIter = rowIter.next().iterator(); return colIter != null && colIter.hasNext(); } @Override public void remove() { while (colIter == null && rowIter.hasNext()) colIter = rowIter.next().iterator(); if (colIter != null) colIter.remove(); } } List of List Iterator 4. Display Page (Pagination) This is well known as OA2. http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=278720 You’re given an array of CSV strings representing search results. Results are sorted by a score initially. A given host may have several listings that show up in these results. Suppose we want to show 12 results per page, but we don’t want the same host to dominate the results. Write a function that will reorder the list so that a host shows up at most once on a page if possible, but otherwise preserves the ordering. Your program should return the new array and print out the results in blocks representing the pages. Input:
An array of csv strings, with sort score number of results per page. example: "host_id,listing_id,score,city" "1,28,300.1,San Francisco" http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=299158 linkedlist 的 remove 是 O(1), remove 之后，只是改变一下指针就完事了，但是 arraylist 在 remove 之后，需要 copy 剩余的数值，全体移动，虽然这个操作没有体现在 arraylist 的 remove 中，但是 cost 要比 linkedlist 的修改指针慢很多，所以这道题要用 linkedlist 而不是 arraylist。 当你 traverse 这个 linkedlist 的时候，当你 traverse 到这个 entry 并且把他加到 page 里，这个时候 完全可以马上删除掉这个 entry，没有必要再用一个 for loop 第二次访问它，所以不存在 remove() 大于 O(1)的可能性。帖子里有人说 remove 最后一个 node 的时间复杂度是 O(n)，这种说法是错误 的，应该是 search，或者说 visit 最后一个 node 的时间复杂度是 O(n),但是 remove 永远是 O(1)。
    分享到：
    赞 收藏

    相关推荐

    资料库

    行业

    共收录7266份资料，累计15个分类，关注成员有19位，主要包括：物流,旅游,餐饮零售,网络游戏,咨询,金融,电子政务,外包,教育,制造,医疗,嵌入式,互联网,交通,电信

    热门标签

    物流 旅游 餐饮零售 网络游戏 咨询 金融 电子政务 外包 教育 制造 医疗 嵌入式 互联网 交通 电信

    最新资料