airbnb 面经（店面+onsite）

果然挂了。 拖了我一个月。 airbnb家最近对candidate大概也就如此了吧。  希望大家运气都能好一些，至少比我好点...

zhangzitong001 发表于 2019-2-27 23:58
polynomia的要求. 我觉得bfs肯定不行.  其次能最优为啥不最优呢哈哈.  我的算法他明白 也解释清楚了.  只 ...

（1）. 为什么是Polynominol?  
(2). cheapest flight 面试官的打印思路是什么？我和你一样，用pre[] 来记录前一个stop

sifangyou1 发表于 2019-3-1 08:27
（1）. 为什么是Polynominol?  
(2). cheapest flight 面试官的打印思路是什么？我和你一样，用pre[] 来 ...

要求是polynominal. 用dp bellman ford可以是 O(kE) 时间复杂度

他只是说我方法不好，他的方法我随便听了下觉得是错的（但是当时不好challenge）。
这里你必须要记录第k个flight的情况下 pre[]. 如果你只记录一个pre[] 你可能会只找出最短路径。 但是最短路径的flights数量可能大于k

zhangzitong001 发表于 2019-3-1 08:31
要求是polynominal. 用dp bellman ford可以是 O(kE) 时间复杂度

他只是说我方法不好，他的方法我随便 ...

有道理啊。那就是要二维的pre[k][N]. 那他propose什么样的方案, 为什么楼主觉得不可行啊？

sifangyou1 发表于 2019/03/01 09:51:03


有道理啊。那就是要二维的pre[k][N]. 那他propose什么样的方案, 为什么楼主觉得不可行啊？

他没说..  他只是在question我的方法.  我的代码的具体实现他也要指指点点（比如说这里while 用for更好） 我在努力解释哈哈.   后来我说 那你觉得可以怎么改进. 他说了一些不对的statement 但是我还是努力点头哈哈哈

lz能详细说下k次飞机是什么意思吗? 没明白题意; 原题是一架飞机停k stops, 那改成k次飞机是什么意思呢? 多谢啦

chipmunks123 发表于 2019/03/01 16:40:45
lz能详细说下k次飞机是什么意思吗? 没明白题意; 原题是一架飞机停k stops, 那改成k次飞机是什么意思呢? 多谢啦

k次航班..就是k-1次stops

zhangzitong001 发表于 2019-2-28 14:43
linkedin找了下发现的

自己人何苦呢

zanzan 积分等看帖好麻烦~

这题BF时间复杂度不是最优啊.