12.7 FB 电面 挂经

12月面了两轮技术电面
第一轮，1，给两个List，一个表示去程的票价，一个表示回程的票价，index是对应日期，

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

， 有原题，不是很难，感觉也做出来了差不多，但是挂了，，，，

求大米！！

分享一下我的思路

一面第一题：
（这题比较像 leetcode 84 题）
新开一个list，长度和原来两个list长度相同。第i元素存储i日期及之前的去程票价最便宜的那个。O(n)时间。
再开一个list，同理，第i元素存i日期及之后回程最便宜的那个。O(n)时间。
扫描两个list。O(n) 时间。

二面第一题：
既然是double linked list 了，每个node 交换向前向后的指针就可以了。

Hexess 发表于 2019-2-4 01:59
求问一下dp O(N)的做法，谢谢！

同问 不是先要排序么？

pengdu 发表于 2019-2-3 11:22
是不是交流问题？

第一题是从后往前找，每次都放到一个bst，然后找lower bound，nlogn的复杂度。

我也不知道为啥，早就听说印度面试官好像不太好过。最后我还问他这个题有什么好解法，他说觉得我的做法是对的，可能是因为我的代码不够简洁吧，他提到我有一些操作是重复的，（意思是另写一个函数？我也不懂）。反正感觉挂了挺意外的。。。。

是不是交流问题？

第一题是从后往前找，每次都放到一个bst，然后找lower bound，nlogn的复杂度。

第一题第一问DP O(n)可解 第二问每个元素value都不一样吗？

cobbjixu 发表于 2019-2-4 00:10
第一题第一问DP O(n)可解 第二问每个元素value都不一样吗？

求问一下dp O(N)的做法，谢谢！

Hexess 发表于 2019/02/04 01:59:49


求问一下dp O(N)的做法，谢谢！

从前向后扫描 记录当前最小去程价钱 如果当前回程加上最小去程小于最优解 就更新最优解 从后向前扫描也可以 记录最小回程就行了

cobbjixu 发表于 2019-2-4 00:10
第一题第一问DP O(n)可解 第二问每个元素value都不一样吗？

value值好像是不一样的，但其实这个值没有用，只是用来标记不同节点吧

ef50mm 发表于 2019-2-4 02:08
同问 不是先要排序么？

我第一个的做法就是倒着找，因为只返回最低的票价是多少，不用管日期，所以只要有一个res记录全程中的最小值即可

ashun 发表于 2019/02/04 12:46:49


我也不知道为啥，早就听说印度面试官好像不太好过。最后我还问他这个题有什么好解法，他说觉得我的做法是对的，可能是因为我的代码不够简洁吧，他提到我有一些操作是重复的，（意思是另写一个函数？我也不懂）。...

最近也在准备面FB，我的HR是中国人，我跟他说有口音的英语我可能听不太清楚，特别是电话里面。他说会尽量帮我安排。