Facebook Fulltime电面

朋友内推，10天后收到8.18号的面试安排面试小哥上来先介绍了一下自己，在messenger工作了2年半，然后转组开始做product framework(没听清具体在那个组)。
然后让我做自我介绍。
跟着做了三道题，最后让我问问题。前两题都是leetcode.

1. First Bad Version. leetcode 278. 问了时间空间复杂度

2. Valid Palindrome. leetcode 125. 问了时间空间复杂度。这题要求要in-place， 然后输入是char[]，不过做法跟leetcode一样。做这题居然忘记了Character.toLowerCase()这个method。小哥人很好的提醒了一下。

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

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

trong>
第三题的输入就是稀疏数组的非0的数列出来了，A=[[1, a1], [300, a300], [5000, a5000]]的意思就是A中第1个数是a1,第300个是a300,第5000个是a5000，其他都是0.

补充内容 (2016-8-23 06:06):
上周四的店面，今天拿到onsite通知

用Treemap也可以实现。建一个sparse vector class，遇到value是0的不要insert，不是0的value insert进去treemap， insert和get复杂度是log（n），treemap是有排序的，所以可以顺序loop key。followup的问题和使用binary tree 找到B里A对应的index值， 时间度一样，空间度是o（k），k是A和B里所有有效不为0的值。

祝LZ onsite顺利！

补充内容 (2016-8-25 13:14):
第三题是哪里的原题？ 求解。。 我也就想到treemap和lz的binary search方法。有更好的吗

zzh730 发表于 2016-8-19 12:50
sparse vector prodcut为什么不能用hashtable， 反正是求product，顺序无所谓啊

我也觉得可以，但是面试小哥要一个可以顺序的iterative的，其实我觉得他只是为了要引出后面题目中input的结构。所以面试官是老大，他说不想要你只能想出另外一个来回答他。

wujingzhishui 发表于 2016-8-19 15:39
楼主自我介绍说的什么啊  new grad 感觉没太多可以展现的

就简单介绍了一下自己，然后说了一下实习时候做的项目，感觉面试官也没有期待你会说很多，说了两三分钟就开始做题了

第3题的input那个形式什么意思？[1, a1], ... 输入是这种形式的？就把数组A遍历一遍，然后对于每个A里有的index，去B里binary search一遍？

这个follow up有点奇怪啊，如果b比a长，算a和b的点乘， 不是只要在b上截取a的长度做点乘吗？

wtcupup 发表于 2016-8-19 05:12
这个follow up有点奇怪啊，如果b比a长，算a和b的点乘， 不是只要在b上截取a的长度做点乘吗？

应该是长度一样，但是A比B稀疏很多，input A和B是只有非0元素的一个list或者array。。

iPhD 发表于 2016-8-19 04:54
第3题的input那个形式什么意思？[1, a1], ... 输入是这种形式的？就把数组A遍历一遍，然后对于每个A里有的i ...

1是index, a1是那个位置上的val

wtcupup 发表于 2016-8-19 05:12
这个follow up有点奇怪啊，如果b比a长，算a和b的点乘， 不是只要在b上截取a的长度做点乘吗？

我觉得楼主说的是如果b中的非0位置比a多很多。

你人品真好 全是原题最后一个也是面经的题

zyoppy008 发表于 2016-8-19 11:39
你人品真好 全是原题最后一个也是面经的题

运气确实不错，他出完这三道题后，我自己也被震惊了。

StellaJiang 发表于 2016-8-19 12:21
运气确实不错，他出完这三道题后，我自己也被震惊了。

我今天才面的 两轮完全没见过的题

zyoppy008 发表于 2016-8-19 12:45
我今天才面的 两轮完全没见过的题

运气什么的果然重要啊。我也是今天面的，那你面的如何？