Massive Algorithms: Airbnb Interview Misc

cross functional
http://www.1point3acres.com/bbs/thread-229065-1-1.html
1. 电面， palindrome pair。安排第二次电面的时候，我还问了一下这一轮的feedback，说coding还可以，就是communication有点少了，可能我只顾闷头写了吧。
2。There are 10 wizards, 0-9, you are given a list that each entry is a list of wizards known by wizard. Define the cost between wizards and wizard[j] as square of different of i and j. To find the min cost between 0 and 9.
说白了，就是带权重的最短距离，最优解是Dijkstra algorithm。似乎面试官说，只要普通的BFS能得到解也是可以的，Dijkstra我最近正好写过，所以也写出来了。

2轮design+1轮resume+2轮culture fit+2轮coding。.鏈枃鍘熷垱鑷�1point3acres璁哄潧
1. key-value database，高频设计题，反正按照一个常见的NOSQL说就好了，dynamo, reddis, cassadra。
2. 设计翻译系统，面经也提到过,因为他们家支持26+语言，每次在页面上更改信息或者添加新的页面，都需要生成不同语言的网页。需要设计一个micro service，需求是要和front end decouple，就是front end engineer在更改完页面之后，不需要自己操作，这个service就能自行的完成翻译。我就是这一点没有答好，我想的是，code change之后总得需要commit什么的吧，在那个时候，send request 到这个service。面试官表示不能认可。我就不知道如何decouple from front end。而且最后feedback是high level都是可以的，但是具体细节不知道怎么实现的。。你们一个内部的service，问我具体怎么实现的。。其他部分的设计可以参考这个link http://nerds.airbnb.com/launching-airbnb-jp/
3. resume
午饭，安排的就是内推我的妹子，非常感谢她，随便就是聊聊，放松一下。
4. crossing functional. 1point3acres.com/bbs
5. crossing functional （有很多人不知道这两个环节如何让面试官感觉你高度认同他们家的公司文化，有空可以多看看engineer blog http://nerds.airbnb.com/，里面有自己人的采访，多看看。而且也可以从blog里延伸出来一些你可以问他们的问题，这样就不会蜜汁尴尬了）
6. IP to CIDR bug free
7. 模拟倒水，自己在画最后结果的时候，一直脑子抽抽，怎么画都画不对。导致之后有一点小bug。最后这一轮feedback就是solution不work。墙裂吐槽这个面试官，他就不懂题目，花了15分钟自己画图试图给我解释，画了又擦，擦了又画，耽误我时间。而且对corner case都不知道，还是我暗示他是不是应该这样啊，那样啊。他就知道最后看结果和答案对不对。最后给recruiter也反应了，但是之前design那一轮也有瑕疵，也就没有办法了。

总体感觉，面试题目：难（电面直接hard 难度），准备难度：中等，因为题库大概30道吧，招人bar：极高，尤其是亚裔，男性，非老兵，非残疾，正常取向，diversity 一样都不占，要你干什么！而且我搜了一下在职跳槽的，地里还没有报过一个pass的面经。或者那些成功跳槽的都不屑于写面经

说真的，如果没有题库的话，完全没有见过的话，有多少人能在30分钟完成像CIDR，sliding game这样的问题，而且test case都要跑过。而且要求bug free。
绝大部分题目我都写过2遍，就是这个模拟倒水，只写了一遍，有些corner case记不清楚了，就导致最后有些test case没有跑对。. from: 1point3acres.com/bbs
.鏈枃鍘熷垱鑷�1point3acres璁哄潧
http://www.1point3acres.com/bbs/thread-282721-1-1.html
有向图最少点遍历：每选中一个点，则可从该点到达的所有点都算作被遍历了求最少选中多少个点可以遍历全图

https://www.zhihu.com/question/29987452

求解这个问题也是通过转化到set cover
所有内部点集即为item set $V$
首先从每个外部节点i出发BFS 得到的点集对应于set cover的集合 $S_i$
set cover尽管是NP-complete的但是可以通过greedy algorithm求解
即初始选择为空，逐个加入marginal gain最大的外部节点
可以证明 greedy algorithmg提供 log |V| 的approximation guarantee
同时也可以证明greedy algorithmg提供的approximation guarantee是紧的。

code 2: Pour water：给一个直方图里面不同位置倒水的问题，输入是倒水位置和倒水的量，要求打印出倒水后的样子design: feed system
两轮cross functional
一轮聊项目，what's the most challendging part?
http://www.1point3acres.com/bbs/thread-209537-1-1.html
电话面试，是一道新题，拓扑排序，aliendictionary做熟了就很简单了

第一轮新题，给一个有向图，如果把一个点放到res那么该点下游的点都当成是被选择了。example: a->b->c，选了a的话bc都被选了。求选最少的点集合让包含整个graph。在国人大哥循循善诱上最后写出来了，然后最后一秒才把bug改出来。面完就感觉想💩，心想第二轮给我来个boggle game让我绝地反击好不好，蓝后

先对整个graph做SCC，然后会得到一个topological graph，然后就直接把根选下去就行啦~

第二轮 ip2cidr 我做了地里30多道题就是没做这道和那个连socket的。看到这题真的是生无可恋，然后想破罐破摔写吧，结果也是在国人大哥提醒下最后一秒把bug改好了。。。

为什么别人都是round num，schedule meeting，csv parser，order meal我就要经历这些磨难

http://www.1point3acres.com/bbs/thread-273389-1-1.html
1. 国人哥哥 alien dict 做的时候还是基本上当作一道没见过的题一步步解释自己的思路一步步引导出一个答案的所以最后写出来的code跟准备的并不一样但是当你对题有一定的了解你知道思路在就知道该怎么写的
2.design 白人大叔 a家翻译系统我准备的东西在10分钟以内已经全部讲了出来面官后来问的很多都是现想的确实是我没想到的地方感觉他一直希望看看我能不能再改进最后我实在想不出更好的了然后面试结束
3. 国人姐姐有向图我一上来就最优解姐姐表示你这个我想应该会work 但是我们先take a step back 不要搞那么复杂先来一个可行的解然后问我这个解不work的example 最后改成最优所以说光背最优真的没有用。。。2轮coding都让我用私人邮箱把code发到他们工作邮箱去了
4. 吃饭她家饭挺好吃的有人表示太菜式健康可能是我比较注重健康吧反正我觉得挺好还有甜点但是种类确实不多
5. cross 1 abc姐姐
6. cross 2 白人哥哥+国人哥哥
7. experience 一个senior abc哥哥迟到了15分钟有工作经历这都不难直接说说现在在做什么因为他迟到了所以顺延了15分钟
过了2天收到了加面说tech面非常不错但是cross需要多加一面 HR的原话是要“extra signal”
当时其实觉得说的还挺好的但是feedback是有点vague HR姐姐特地找了个她的同事来跟我再指导了一番
回家之后就把地里的cross题全部拿出来写了一遍答案
今天刚刚面完有的题目还是需要现想但是HR的帮助还是非常有用的真的非常感谢他们
下午下班的时候就来电话给offer了

还有一个事就是去onsite必须住airbnb 我强烈建议可以的话还是选HR给的list上的我就因为价钱还有各种原因没找到合适的另外自己找了一个结果那个房间的暖气一直有声音最后实在受不了了只能关掉暖气睡加上也是自己紧张一晚上没睡好
最后想说的就是跳槽的人时间都非常有限我自己觉得还是挑几家想去的集中准备太分散准备肯定不理想我还有f家onsite 打算赶紧敲定package不继续面了这一路准备下来确实很累也很容易放弃现在终于可以恢复到正常人的生活了
https://github.com/WeizhengZhou/leetcode3/blob/master/airbnb.txt
1. buddy list
followup是给了一个max值，找出你的buddy的wishlist里不在你的wishlist里的最多max个城市，根据buddy和你的重合程度来排序.
例如你的wishlist是 a,b,c,d
buddy1 的wishlist 是 a,b,e,f, 有两个和你的一样，所以是你的buddy
buddy2 的wishlist 是 a,c,d,g, 有三个和你的一样，也是你的budy

问题是输出一个size最多为max的推荐城市列表
当size为10时，buddy1和buddy2的wishlist中不在你的wishlist中的城市都可以加入推荐中，因为buddy2的重合度更高，所以先输出buddy2中的，所以推荐为 g,e,f
当size为2时，推荐是g,e 或 g,f

2. preference list
也是地里出现过的了，每个人都有一个preference的排序，在不违反每个人的preference的情况下得到总体的preference的排序
拓扑排序解决

http://www.1point3acres.com/bbs/thread-218938-1-1.html

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=220456
Meeting Room 找T1-T2内所有人空的时间段
Q: 给一组meetings（每个meeting由start和end时间组成）。求出在所有输入meeting时间段内没有会议，也就是空闲的时间段。每个subarray都已经sort好。N个员工，每个员工有若干个interval表示在这段时间是忙碌的。求所有员工都不忙的intervals。
举例：
[
  [[1, 3], [6, 7]],
  [[2, 4]],
  [[2, 3], [9, 12]]
]
返回
[[4, 6], [7, 9]]

A: 这题最简单的方法就是把所有区间都拆成两个点，然后排序，然后扫描，每次碰到一个点如果是左端点就把busy_employees加1，否则减1，等到每次busy_employees为0时就是一个新的区间。这样复杂度O(MlogM)，M是总共区间数。
def cmp_moment(m1, m2):
if m1[0] != m2[0]:
      return m1[0] - m2[0]

return int(m1[1]) - int(m2[1])

def find_free_time(schedules):
moment_status = []
for person_schedule in schedules:
      for interval in person_schedule:
         moment_status.append((interval[0], True))
         moment_status.append((interval[1], False))

moment_status.sort(cmp=cmp_moment)

free_start = moment_status[0][0]
busy_count = 0
available_intervals = []

for moment, become_busy in moment_status:
      if become_busy:
         if busy_count == 0:
            if moment > free_start:
                  available_intervals.append((free_start, moment))
         busy_count += 1
      else:
         if busy_count == 1:
            free_start = moment
         busy_count -= 1
return available_intervals

第一轮是preference list，这里的第二题
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=218938
也是地里出现过的了，每个人都有一个preference的排序，在不违反每个人的preference的情况下得到总体的preference的排序
拓扑排序解决

第二轮是水流那道，看这里
http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=218383
店面： palindrome pairs
skype: 往一个int array 代表海拔的格子里倒水，打印出倒水后的图，输入：int[] 海拔， int 水数量， int 倒得位置。Example:
int[] 海拔 {5,4,2,1,2,3,2,1,0,1,2,4}
+
++    +
++  + ++
+++ +++  ++
++++++++ +++
++++++++++++

012345
水数量8，倒在位置5 ->
+
++    +
++www+ ++
+++w+++www++
++++++++w+++
++++++++++++

这题我是只写了一半，水那部分没写完，而且好多corner case要考虑，大家参考参考哈
请问水滴下来。是忘左边走还是右边走呢。还是说我可以假设所有的水滴掉下来都优先往左边走。直到遇见了不能存储的情况才考虑右边？
都可以我假设往左先面试官说可以的
这道题是这样，很多东西都是很面试官确认出来，像我和他讨论出的结果就有：水滴优先往左流，没地流再往右流，也没地了就在当前位置涨；两边有无限高的墙挡着；水滴是一滴一滴的，不能分为小数，所以一滴水会一直往左走到尽头（其实是不符合物理规则的但理他呢。。）
def pour_water(terrains, location, water):
print 'location', location
print 'len terrains', len(terrains)
waters = [0] * len(terrains)
while water > 0:
      left = location - 1
      while left >= 0:
         if terrains[left] + waters[left] > terrains[left + 1] + waters[left + 1]:
            break
         left -= 1

      if terrains[left + 1] + waters[left + 1] < terrains[location] + waters[location]:
         location_to_pour = left + 1
         print 'set by left', location_to_pour
      else:
         right = location + 1
         while right < len(terrains):
            if terrains[right] + waters[right] > terrains[right - 1] + waters[right - 1]:
                  print 'break, right: {}, right - 1:{}'.format(right, right - 1)
                  break
            right += 1

         if terrains[right - 1] + waters[right - 1] < terrains[location] + waters[right - 1]:
            location_to_pour = right - 1
            print 'set by right', location_to_pour
         else:
            location_to_pour = location
            print 'set to location', location_to_pour

      waters[location_to_pour] += 1

      print location_to_pour
      water -= 1

max_height = max(terrains)

for height in xrange(max_height, -1, -1):
      for i in xrange(len(terrains)):
         if terrains + waters < height:.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
            print ' ',
         elif terrains < height <= terrains + waters:
            print 'w',
         else:
            print '+',
      print ''

File System
大概就是增加一个文件目录，比如/a，/a/b，但/c/b就要返回错误。然后每个目录都有一个value，一旦对某个文件目录做了更改，需要call一个callback function

新题是一个OO Design，很简单，就是实现一个tree。具体如下：configuration tree：
三个method：create(path, value), set_value(path, value), get_value(path)

让你实现一个长成这样的tree：

   root
   /       \
NA    EU
  / \
CA  US

其中root是没有name和value，剩下的每个点都有name和value。

create（path，value）：给你一个path，比如“NA/MX”，和value，比如“3”。那么你就在NA下面创建一个点叫MX，值是3。
set_value(path, value): 给你一个path，找到path的叶子，然后set value，如果叶子不存在，返回false；
get_value(path): 给你一个path，返回叶子的值，没有叶子的话返回NULL。

非常简单一个OOD，跟Trie很像。

http://www.1point3acres.com/bbs/thread-209414-1-1.html
电面是经典高频题，LeetCode 336 - Palindrome Pairs
1. 我有一个感兴趣的城市列表，我的朋友们每个人也有感兴趣的城市列表，如果朋友和我感兴趣的城市占总共他总城市个数的至少一半，就输出他的名字，要求按照相同城市个数排序。第二问输出的名字对应相同城市名字。楼主是hashset直接暴力的，最后被问如何优化，也没时间了。现在想想应该用bitset吧，不知道有没有更好的方法
2. 文件系统，每个文件夹或者文件有一个具体的数值，设计一个类，给定key可以update val可以insert val, 要求可以处理exception
应该是file system吧，tree是我自己写的。其实我也是一头雾水，这东西挺好写的，倒是exception的判定条件有点烦
key就是一个文件的路径，我还专门问了他有没有什么trick，他说不用担心trick，写出来就成。我是用C＋＋面的，但是他家最好写python，因为不论C还是Java写出来的速度都不会太快，所以他才临时给我换题的

3. 设计题，设计feed system的底层database schema，问的非常细，有哪些table，table里有哪些column，然后哪个是key，然后优化用哪个做index，甚至还写了好几个mysql query。。吐槽一下跟我想象中的设计题完全不一样，估计是楼主太弱了，他后面其实是会问replica，sharding，cache然后再回到feed system server怎么实现吧

一个重要的经验是：面他们家一定要用自己的电脑！最好用python！他们家的code的是要上机跑实例的。我因为用的机器没有Xcode，折腾了半天，用了命令行，导致第一轮少了10分钟时间。

http://www.1point3acres.com/bbs/thread-215677-1-1.html
面试一轮project deep dive，两轮上机编程，两轮系统设计，两轮cross function。project deep dive，白人大哥。没啥说的，我做过的所有project 我光做presentation就基本做了不知道多少遍。 deep dive 我只怕他问的不够deep。

中国女生。问题地里面经也提到过 (找不到link了），一个有向图。求出最少需要的点能遍历整个图。我之前看面经想过这个题，但是关键是，尼玛想的是有bug的。我一开始拿到题，说了思路，就是找所有in degree 是0的点放进结果，然后bfs／dfs，如果有环，就随机拿一个放进结果，然后bfs／dfs，直到遍历所有的点。面试官想了想，感觉哪有问题，但是也想不出来，就说行吧。然后我就开始写，尼玛写的前十五分钟里，她一直在想corner case 。然后我写了一大半了，她说，你这个思路有bug，也就是下边这种情况：

结果可想而之，没写完。

上机二：亚裔小哥（亚洲哪的就不知道了）这里第一题http://www.1point3acres.com/bbs/thread-209414-1-1.html  上来给我一张letter size的纸，上边写满了题目描述。面经看过，但是并没什么用没写完。本人用的c＋＋，就是个死。input是raw string 模拟document。光parse string，我就写了好几十行。  我感觉用c＋＋就是默写，都写不完。手指头都打酸了。最后compile的时候一屏幕的error。我懒得debug了，就直接说，哥哥我用c＋＋编不完了，我们来聊聊吧，面试小哥说，嗯 c＋＋太吃亏。  然后我面道这里基本上知道没啥希望了。瞎聊了一会结束。

下午系统设计一，亚裔大哥。一脸严肃问题是设计key value pair。  我就按照big table的思路说。大哥一直在质疑。我就一直在defense。  具体的内容记不清了，感觉说的过程中不是很顺，只记得在airbnb那么小的一个面试的屋子里（放了一个桌子两个椅子，站不下第三个

然后是cross functional 两轮，一个是marketing 的白人小哥，一个是culture team的白人美女，有点像taylor swift，聊天过程中知道她之前是fashion industry的。全程高能。中心思想就是我爱旅游，我喜欢不同的文化，世界上的恐惧都是不了解造成的。（我确实爱旅游，我确实喜欢不同文化）然后airbnb 的core value也要看看，把自己的经历往那上扯就好。这两轮是我这一天airbnb面试答的最好的两轮。。。。哎。。。

最后一轮系统设计，中国小哥 new feeds。地里面经也有。感觉中规中矩。

面试两天后 recruiter 告诉我挂了。 feedback是cross functional 两轮表现极好， tech 面试都不好。  好吧。。。。

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=200829
https://instant.1point3acres.com/thread/188826
电面：地里面经，一道关于floor和ceil的题目，很好找。

airbnb家的高频题，低频题，每一道都写了好几遍，其中text justification这个题都快刷吐了。。。最后也没考。

第一题：地里超级高频的一道题，跟开会有关系，大家懂的
用sublime的童鞋们注意了，他家的sublime不支持c++11，你得自己配置环境。此时时间已经过去了25分钟，不过还好最后我的code是bug free。
面试官似乎很着急让我写完，因为在面试开始前，我问了他一个关于airbnb的问题（非technical），他很想就这个问题和我聊一下，然后聊得很愉快，面试结束。

第二题：一道电面时候常常出现的高频题目，跟数组有关系，大概就是增加，移除什么的，如果还是不明白我说的哪一道…………可以问我
bug连连，写的不怎么样，不过大方向没错，而且很快更改了bug。
和小哥聊airbnb的发展，由于我是airbnb的忠实用户，对他家的发展和market策略，想过很多很多，所有也聊了很多很多，小哥很满意，还赞美了我几句，说我很有business mind面试结束。

第三题：这个比较有意思，小哥很年轻，进来就说，咱们这一轮，不coding。我们来聊聊设计database
我一听就懵了！！！！！好不容易抓住airbnb这最后一个机会，可不能栽在你手里！
小哥笑嘻嘻的问我，会不会SQL，有没有设计database的经验。
我心想，我一个front end engineer，你让我设计数据库？？？不太靠谱啊！！！！
我说，小哥，咱们这一轮，还是要coding，因为我的recruiter告诉我了，我一共有3轮coding，现在还差一轮啊，而且database不是我的学习方向。

小哥飞快的拿出手机，查查自己是不是走错门了？？！！！然后并没有。
小哥看着手机说，嗯，那咱们就coding吧。。。。。于是写了一道house robber，升级版，要返回最大值，和抢的房子的index，不会可以问我。

然后我飞快的写完了bug free，给小哥讲了一下，小哥感觉全称都在玩儿手机！后来就airbnb的发展问题聊了聊，小哥非常开心，尤其是知道我经常用airbnb，于是聊得很愉快，面试结束。

house robber 怎么返回抢的房子的index ？
懂了得比较nums + val[i-2]和val[i-1]，一旦前者大就记录其下标

聊聊FB的面经吧。。。。已经决定不去了。。。没缘分，真可惜
店面，给一个数组，找所有的pair符合a+b=c+d
onsite: move zeros, fibonacci, heap sort, binary tree vertical order printout, add expression

关于culture fit,因为我用过airbnb太多次了，可能是所有的面试选手中，用的最多的一个，所以我有很多airbnb住宿经历的回忆，聊天的时候我基本上就在和面试官讲一些有趣的故事。

针对airbnb的发展其实我也想过很多，也有疑问，我就把这些想法都说出来了，给面试官的感觉就是，我用过A家的产品，并且喜欢A家，对他们家的business idea也有过研究，很用心的去对待，这样面试官就很高兴

电面1：unique path
sqrt(x) with precision
我写的不太顺利，小哥说我给你写一个吧！然后他信心满满的，写了一个死循环！剩下的时间就一直在调试，到最后他都没调出来。感觉像是我在面试他。。。。然后小哥说compiler坏了！我说好吧哥哥。
小哥囧囧的给了我2面。

第二面：小哥迟到了20分钟，本来3点开始，3点20才来电话，小哥说他给忘了。。。。我说没关系，我们可以继续面试，写了longest consequtive sequence，迅速写完了，小哥又让我写了一个javascript的题，应该是他现成想的，写完了，4点了，小哥说虽然我们没有按时开始，但是我们按时结束啦！
然后就结束了，也不知道会不会有onsite
http://www.1point3acres.com/bbs/thread-191081-1-1.html

ab家，主力难点在算法 & coding。
算法 & coding
phone 一轮coding，线上写code，然后compile 然后跑实例。
写不完code或者实例结果不对，都很可能挂掉。
他家的难度一般都是在leetcode hard level。之前出面经题的概率挺大，但按lz最近的体会，他家新增了不少新题或者实战题目。
附录airbnb题库. 准备他家的coding，要增加胜率就只能把能见的机经都刷到吐。
leetcode 上hard的题目也要多练习。 lz结束leetcode 第四轮后，基本hard的题目都可以12分钟左右，写完bug free的code。
lz非大牛，只发现出苦力这一条路了。他家一轮面试45分钟。时间还是很紧的。遇到新题目，理解想思路要花5~10分钟。
和考官交流要5~10 分钟。跑测试，至少要5分钟。所以只能努力提速了。大家也加油。

Design ：请参考fb的design区块和下面的题库
基本相通
http://www.1point3acres.com/bbs/thread-191077-1-1.html

Culture fit：
他家这个很有意思，会有两轮。
通过只有一个技巧，他家很有前景，你很喜欢他家的服务，他家的服务能让人更好的感受local的文化
常见问题多练习，参考附录题库。

Backgroud:
这个也没啥，自己的project和经验要准备好，常见问题多看看。

他家的面试难度，主要在coding，其他轮感觉还ok。lz最后fail在了design。 coding 倒是遇到两新题，都解完了，coding的feedback 也不错。
也没啥可惜的了。lz尽力了。

=============================题库了=============================

From Glassdoor：

1. Given a list ofstrings, return all pairs of strings that can make a palindrome. 高频

2. TextJustification, Alien Dictionary

3. How fast can you parse strings?

The problem I was given involved a bunch of ugly string data parsing and using a heuristic to modify

the data in a certain way. It was an easy problem, but they wanted a fully working solution within the short time limit.

I couldn't finish it in time.

Pick a language that has as little verbosity as possible and don't bother engaging with the interviewer

because they don't care to speak with you. They just want to see how fast you can code.

Write a CSV parser. Parse an escaped string into csvformat. 高频

5. Return the coins combination with the minimum number of coins.Time complexity O(MN),

where M is the target value and N is the number ofdistinct coins. Space complexity O(M).

6. I had a phone screen question involving examination of subsets.

7. Check top 10 questions on leetcode

8. Implement a circular buffer using an array.

http://stackoverflow.com/questions/590069/how-would-you-code-an-efficient-circular-buffer-in-java-or-c-sharp

9. Provide a set of positive integers (an array of integers). Each integer represent number of nights

user request on Airbnb.com. If you are a host, you need to design and implement an algorithm to

find out the maximum number a nights you can accommodate. The constrain is that you have to

reserve at least one day between each request, so that you have time to clean the room.
Example:
1) Input: [1, 2, 3]===> output: 4, because you will pick 1 and 3
2) input: [5,1, 2, 6] ===> output: 11, because you will pick 5 and 6
3) input: [5,1, 2, 6, 20, 2] ===> output: 27, because you will pick 5, 2, 20

10. Given a set of numbersin an array which represent number of consecutive days of AirBnB reservationrequested, as a host, pick the sequence which maximizes the number of days ofoccupancy, at the same time, leaving atleast 1 day gap in between bookings forcleaning. Problem reduces to finding max-sum of non-consecutive array elements.

// [5, 1, 1, 5] => 10
The above array would represent an examplebooking period as follows -
// Dec 1 - 5
// Dec 5 - 6
// Dec 6 - 7
// Dec 7 – 12

The answer would be to pick dec 1-5 (5 days)and then pick dec 7-12 for a total of 10 days of occupancy, at the same time,leaving atleast 1 day gap for cleaning between reservations.

Similarly,
// [3, 6, 4] => 7
// [4, 10, 3, 1, 5] => 15

11. Boggle implementation (word search I, II)

12. Given a dictionary, and a matrix of letters, find all thewords in the matrix that are in the dictionary. (Going across, down ordiagonally)

What SQL columns you should index and how would you change the indexing in different lookup scenarios?
What can you teach me in a few minutes?
find all the combinations of a string in lowercase and uppercase. For example, string "ab" -> "ab", "Ab", "aB", "AB". So, you will have 2^n (n = number of chars in the string) output strings. The goal is for you to test each of these string and see if it match a hidden string。
Implement a simple regex parser which, given a string and a pattern, returns a booleanindicating whether the input matches the pattern. By simple, we mean that the regex can only contain special character: * (star), . (dot), + (plus). The star means what you'd expect, that there will be zero or more of previous character in that place in the pattern. The dot means any character for that position. The plus means one or more of previous character in that place in the pattern. . 1point 3acres 璁哄潧
Tell me about why you want to work here.
Find all words from a dictionary that are x edit distance away.
Store a set of sudden-death tournament results in a compact format (eg. a bit array) and a set of predicted match results (also in a bit array). Score the predictions, giving one point per correctly guessed match, without unpacking the bit array into a more convenient format (ie. you have to traverse the tree in-place).

20. Lots of treequestions (implement a BST, score sudden-death tournament results with a minimalbinary tree data structure, encode an alien dictionaryusing a tree and then produce a dictionary using topological traversal), and a"rebuild Twitter from the ground up" scaling/architecture question.

Describe what happens when you enter a url in the web browser
Sort a list of numbers in which each number is at a distance k from its actual position
You have a plain with lots of rectangles on it, find out how many of them intersect
Binary search tree

From MITBBS

1. http://www.mitbbs.com/article_t/JobHunting/32309663.html

regexmatch, slightly complicated version of http://leetcode.com/2011/09/regular-expression-matching.html

find maxium square inside a sqaure, similar tohttp://stackoverflow.com/questio ... argest-square-block

edit distance

2. http://www.mitbbs.com/article_t/JobHunting/32864407.html

3. http://www.mitbbs.com/article_t/JobHunting/32779809.html

alien dictionary，我还被问了两轮这题。。。
还有meetingroom2

4. http://www.mitbbs.com/article_t/JobHunting/33129803.html

电面二话不说上来就做题
一个餐馆，菜单上各种食物价格如下
A， $ X.XX
B， $ Y.YY
C， $ Z.ZZ
D, $ ...

问现在一个人有一定数额的钱，比如 $MM.MM，如何点菜才能把钱全部花完？
面试官要求列出所有可能的组合
我用了recursive的方法，写出来了
但是在比较 floatnumber的时候，细节没有处理好
直接比较 X.XX ==Y.YY 会出现错误，所以必须要做差来比较
经面试官提醒改了过来
然后周一被通知挂了

这题除了用recursive方法，有更好的解法吗？DP?

From 一亩三分地

http://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=145&sortid=311&searchoption[3046][value]=37&searchoption[3046][type]=radio&sortid=311&filter=sortid&page=1

1. http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=176102&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D37%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

RT，白人面试官，感觉非常冷，啥都不问，上来直接做题。题目是2D iterator，加一个remove。

我10多min就写完了，但是面试官说能run，但是design不太好，让我换一种方法。

提示利用iterator的remove方法，我对iterator的remove方法不是很熟，我说能不能查api，他说可以。
然后我就查api，然后lz对api里说的看不大懂，然后面试官帮忙run了一个case，然后我懂了，然后就改，

然后又出了几个很傻逼的bug，最后面试官说再给你1min调，然后lz终于调出来。然后面试官说great。

（感觉安慰我）。然后我就问问题，但是很傻逼的是，我问的问题和那个面试官做的东西不一样，

面试官不懂怎么回答，然后我就让他讲了一下他的工作，然后我又问了2个。然后就Bye了。

2. http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=165457&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D37%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

首先是三个技术面：
1） AlienDictionary
2） Text Justification
3）写echoTCP client，向面试官的server发请求，读回数据。地里比较少人说这种，我来详细说一下，

情境是这样的：想象你开车，踩下油门，车会加速，放开油门，车会减速。 client向server发的请求有以下2种：

（a）STATUS --表示查询现在车的速度和踩下踏板的压力；

（b）THROTTLE 50.1 --- 这条指令是“THROTTLE” 加上一个数字，表示我现在将踩油门的压力调为50.1

EXAMPLE: 比如在telnet中
STATUS
0.0 0.0 (这行是server返回的，第一个数字表示压力，第二个数字表示速度)
THROTTLE 50.1 (这个指令发出 server没有返回)
STATUS
50.1 3.75 (可以看到速度在缓慢上升)
STATUS (过几秒后，你又发STATUS指令过去)
50.1 15.98 (速度依旧上升。。。)

对就是这样，像是简单物理实验。

写完TCP client后，要求是写一个方法将速度控制到达一个target speed

最后一个问题是求这个 delta力和 delta速度之间的函数关系。。。。。。。。醉了。我物理还给老师了。。。。。。时间不够了

补充内容 (2016-1-14 00:55):
补充一下core value面：
1）what bring you to airbnb?
2) what can you teach your co-workers after you get in?
3) describe a person whom you admire most
4) describe your experience with airbnb

补充内容 (2016-1-14 00:55):
5) where have you been to?
6) what will you do if you win a lottery such as Powerball?
7) what is the biggest fear in your life?
8) how do describe Airbnb to a people back to 2003?

补充内容 (2016-1-14 00:56):
9) if you have a book that writes about your whole life, will you read it? why?
10) if you have a time machine, and you can either go back or go forth,

will you choose to go back or to go forth?

补充内容 (2016-1-14 00:56):
11) among all the features of airbnb, what do you want to improve?

补充内容 (2016-1-14 12:59):
12) 描述一件你当时觉得非常risky的事情，你是怎么做的，结果如何

写个tcp client然后发指令到server，返回值做加减乘除。。。。。。这面经描述也是醉醉的。我就只准备了Client怎么写

还有就是，每个面我的engineer风格各不相同（迥异）。。。有的很aggressive，有的还没睡醒（第二题），有的题目都说不清楚要我不停地挖不停地问（就是第三题）

最后一道题最后两个问是不是把公式推导出来, 然后把压力稳定在一个值使得 target speed 稳定就行了?

求问最后一道题，是不是需要读server的clock time，来计算当前的加速度？还是用RTT来估算？

还有是否考虑摩擦力？就是外力为0的话，速度也会下降，还是说是理想状态没有摩擦力？

https://www.jiuzhang.com/qa/2605/

写echo TCP client，向面试官的server发请求，读回数据。地里比较少人说这种，我来详细说一下，情境是这样的：想象你开车，踩下油门，车会加速，放开油门，车会减速。 client向server发的请求有以下2种：（a）STATUS –表示查询现在车的速度和踩下踏板的压力；（b）THROTTLE 50.1 — 这条指令是“THROTTLE” 加上一个数字，表示我现在将踩油门的压力调为50.1

EXAMPLE: 比如在telnet中
STATUS
0.0 0.0 (这行是server返回的，第一个数字表示压力，第二个数字表示速度)
THROTTLE 50.1 (这个指令发出 server没有返回)
STATUS
50.1 3.75 (可以看到速度在缓慢上升)
STATUS (过几秒后，你又发STATUS指令过去)
50.1 15.98 (速度依旧上升。。。)

对就是这样，像是简单物理实验。

写完TCP client后，要求是写一个方法将速度控制到达一个target speed

最后一个问题是求这个 delta力和 delta速度之间的函数关系

你可以用比例。用一次方程求解。

这个题还可以用 Binary Search 做，虽然效果没有公式好。

但是我觉得直接用公式做是有问题的。不过这个题，应该大部分人都挂在 socket 不会写。

Airbnb Interview Misc

Labels

Popular Posts