一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2072|回复: 17
收起左侧

Facebook on campus面经

[复制链接] |试试Instant~ |关注本帖
sumingche 发表于 2014-2-20 10:20:55 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 硕士 合同工@Facebook - 校园招聘会 - 校园招聘会 |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Facebook (cmu) on campus interview的一些题目:leetcode.

1. word break   
2. sort colors
3. Best time to buy and sell stock
4. Binary Tree traversal

5. Regular Expression Matching
. 1point 3acres 璁哄潧

几道不是leetcode的题目

6. 给你一些平面的点(坐标是整数),求能够成正方形的数目。 这个题感觉和4sum 差不多,可以实现空间复杂度为O(n^2) 的算法,用一个hashset 存任意两个点对(p1,p2) 然后遍历hashet,任取两个点对判断两条线段是否能够成正方形,如果能够成,count++;结果最后应该除以4,因为可能正方形的每条边都会被用到,重复了4次。

7. 给你一个set<object> 然后给你了个compareTo的方法,可以比较出大小(任意两个objects都能比较出大小,但是这种关系不具有传递性,即A>B,B>C但是A不一定大于C),让你找出set中最大的object,如果不存在,就返回null。
. visit 1point3acres.com for more.
8. 假设一个network里面有很多人,任意两个人之间只有一个喜欢另一个的关系,如果有一个人被所有人都喜欢,那么就返回这个人,如果没有就返回null.

乍一看感觉7,8题很相同,其实不然,第7题的A>B和B>A这两种关系是不能共同存在的,但是第8题 可以A喜欢B,B喜欢A,. 1point3acres.com/bbs
第七题的解法,可以联想到擂台赛的解法,就是扫两次,第一扫的时候,找到其中最大的object,第二次扫的时候,让A可所以其它object比,如果还是比其它object大,那么它就是最大的,否则就是返回null
第八题,感觉就是O(n^2) 的解法。

评分

8

查看全部评分

elementary 发表于 2015-3-18 23:22:18 | 显示全部楼层
crazybadboy 发表于 2015-3-17 16:55
请问第七题什么思路?

可以参考celebrity problem,感觉楼主遇到的是抽象版。
回复 支持 1 反对 0

使用道具 举报

lhn9021 发表于 2014-2-20 12:04:09 | 显示全部楼层
问个小问题 第六题是不是最好用hashmap 保存 顺带存入个数 因为点可能有重复 如果用hashset的话 两个重复点例如(1,1) (1,1)就只剩下1个了 谢谢
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2014-2-20 12:08):
另外第八题如果我没有理解错应该是只有A喜欢B或者B喜欢A的情况是吗 如果是这种情况的话就是celebrity problem 可以O(N)解
回复 支持 反对

使用道具 举报

 楼主| sumingche 发表于 2014-2-20 23:43:04 | 显示全部楼层

这个题我没面到,猜想如果第七题和第八题的区别就是A>B,和B>A是否可以共存,如果不能共存,就是O(n),类似于擂台赛,如果可以共存就是O(n^2)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| sumingche 发表于 2014-2-20 23:44:35 | 显示全部楼层
lhn9021 发表于 2014-2-19 23:04
问个小问题 第六题是不是最好用hashmap 保存 顺带存入个数 因为点可能有重复 如果用hashset的话 两个重复点 ...
. visit 1point3acres.com for more.
重复点其实只需要算一个就好了
回复 支持 反对

使用道具 举报

夹心lee 发表于 2014-2-23 10:15:30 | 显示全部楼层
我大米太少不让我评分
在这里给你顶一下吧!
回复 支持 反对

使用道具 举报

 楼主| sumingche 发表于 2014-2-23 10:16:35 | 显示全部楼层
夹心lee 发表于 2014-2-22 21:15 .鏈枃鍘熷垱鑷1point3acres璁哄潧
我大米太少不让我评分
在这里给你顶一下吧!

我回头给你评评分吧~
回复 支持 反对

使用道具 举报

夹心lee 发表于 2014-2-23 10:33:21 | 显示全部楼层
sumingche 发表于 2014-2-23 10:16
我回头给你评评分吧~

待我也写个心经~
回复 支持 反对

使用道具 举报

marstorm08 发表于 2014-4-13 12:15:01 | 显示全部楼层
第八题 取决于这个喜欢不喜欢的关系是怎么给的 和celebrity problem 非常的像啊 应该是O(n)的解法
回复 支持 反对

使用道具 举报

magict42 发表于 2014-4-13 12:36:12 | 显示全部楼层
第八题可以用递归吗?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
把network随机分成两部分,A,B

如果 sub(A) ==null || sub(B) == null return false. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

如果 sub(A) == a, sub(B) b, 测试a是不是被所有B里面的人喜欢,是的话,返回a,同理对b

n*logn ?

补充内容 (2014-4-13 12:37):
SB了,sub(A)可能返回是一个list。请无视
回复 支持 反对

使用道具 举报

johnnywsd 发表于 2014-5-5 10:27:07 | 显示全部楼层
1. Word Break. 自己写的代码,请指教。
  1. class Solution:
  2.     """
  3.     DP
  4.     """

  5.     # @param s, a string
  6.     # @param dict, a set of string
  7.     # @return a boolean. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8.     def wordBreak(self, s, dict):
  9.         length = len(s)
  10.         myset = set(dict)
  11.         possible = [False] * len(s)
  12.         # possible[i] means whether it s[0:i + 1]
  13.         # can be segmented by dictionary
  14.         for i in range(length):
  15.             if s[0: i + 1] in myset:. 1point 3acres 璁哄潧
  16.                 possible[i] = True 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  17.             else:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  18.                 for k in range(i + 1):
  19.                     if possible[k] and s[k + 1: i + 1] in myset:
  20.                         possible[i] = True
  21.                         break
  22.         return possible[-1]
复制代码
回复 支持 反对

使用道具 举报

johnnywsd 发表于 2014-5-5 10:49:21 | 显示全部楼层
2. Sort Color
  1. class Solution:
  2.     # @param A a list of integers
  3.     # @return nothing, sort in place
  4.     def sortColors(self, A):. From 1point 3acres bbs
  5.         ridx = 0
  6.         widx = 0
  7.         bidx = len(A) - 1
  8.         while ridx <= widx <= bidx:
  9.             if A[widx] == 0:
  10.                 A[ridx], A[widx] = A[widx], A[ridx]
  11.                 ridx += 1
  12.                 widx += 1
  13.             elif A[widx] == 1:
  14.                 widx += 1
  15.             elif A[widx] == 2:
  16.                 A[bidx], A[widx] = A[widx], A[bidx]
  17.                 bidx -= 1
  18.         return A
复制代码
回复 支持 反对

使用道具 举报

weiqitoby600 发表于 2014-5-5 20:07:33 | 显示全部楼层
. Waral 鍗氬鏈夋洿澶氭枃绔,
这个题目貌似python不如java短了...
回复 支持 反对

使用道具 举报

johnnywsd 发表于 2014-5-10 00:33:34 | 显示全部楼层
weiqitoby600 发表于 2014-5-5 20:07
这个题目貌似python不如java短了...
. 1point3acres.com/bbs
Java 能写多短呢?
回复 支持 反对

使用道具 举报

crazybadboy 发表于 2015-3-18 05:55:32 | 显示全部楼层
请问第七题什么思路?
回复 支持 反对

使用道具 举报

crazybadboy 发表于 2015-3-19 13:49:21 | 显示全部楼层
elementary 发表于 2015-3-18 23:22
可以参考celebrity problem,感觉楼主遇到的是抽象版。

celebrity problem是:celebrity被所有人认识,而他不认识任何一个人。celebrity 的一个特点是保证有且仅有一个celebrity。第七题的确跟celebrity很像,但是他需要找出set中最大的object, 这并不代表他能是celebrity。我觉得可以试一下directed graph.建立directed graph: B->A when A>B. 然后找out-degree==0的node,如果这样的node个数大于1,就返回NULL, 否则返回该node。兄台你怎么看?
回复 支持 反对

使用道具 举报

elementary 发表于 2015-3-21 09:36:37 | 显示全部楼层
crazybadboy 发表于 2015-3-19 00:49
celebrity problem是:celebrity被所有人认识,而他不认识任何一个人。celebrity 的一个特点是保证有且仅 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
你的思路是可以的,但是建图的话你也需要n^2的复杂度?我觉得这题还是celebrity。因为楼主说任意两个元素都可以比较出大小,只是关系没有传递性(这和celebrity里面a认识b,b认识c,但是a不一定认识c是一样的),所以放到celebrity那个问题来看,就是存在这个一个元素,大于其他所有元素(其他所有人都认识它)。我觉得任意两个元素都可以比较出大小这一点是比较的关键。所以每次compare我们一定可以留下一个淘汰一个,到最后那个就是最大的。意下如何?
回复 支持 反对

使用道具 举报

crazybadboy 发表于 2015-3-23 14:16:23 | 显示全部楼层
elementary 发表于 2015-3-21 09:36
你的思路是可以的,但是建图的话你也需要n^2的复杂度?我觉得这题还是celebrity。因为楼主说任意两个元素 ...

兄台高见!我没考虑到任意两个都可以比较。谢兄台指出
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 14:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表