Chapter 46 Facebook 2017 Interview Questions Part 2
集合: http://bit.ly/2wOwWB1, http://practice.geeksforgeeks.org/company/facebook
46.2 Design Memcached
https://github.com/shadowwalker2718/memcached
http://www.jianshu.com/p/b4c34ee9e411
Compile memcached from source:
git clone git@github.com:shadowwalker2718/memcached.git
cd memcached
apt-get install libevent-dev -y
./autogen.sh
./configure --prefix=/opt/share/software/memcached
make
make installhttps://dev.mysql.com/doc/mysql-sourcebuild-excerpt/5.5/en/installing-development-tree.html
https://dev.mysql.com/doc/mysql-sourcebuild-excerpt/5.5/en/source-configuration-options.html
Compile MySQL-Server from source:
✔ /opt/share/mysql-server [5.7 {origin/5.7}|✔]
23:25 # cmake . -LH -DDOWNLOAD_BOOST=1 -DWITH_BOOST=boost1590/ -DENABLE_DOWNLOADS=1http://blog.symedia.pl/2015/12/profiling-mysql-memory-valgrind-massif.html
MySQL + Memcached
Source Folder: /opt/share/mysql-server/plugin/innodb_memcached
Python + Memcached
https://pymemcache.readthedocs.io/en/latest/getting_started.html
[5733][henrymoo][1][bash](22:34:57)[0](root) : /opt/share/software/memcached/bin
$./memcached -u henrymoo46.3 Design POI
2017(4-6月) 码农类 硕士 全职 Facebook - 网上海投 - Onsite |Fail在职跳槽
电面:word breakII,输出一组结果即可
Onsite:
1, behavior question & number cipher match pairs 类似LC二零五
2, move zeros & first bad version
3, Design Memcache
4, 3 sum, decode ways
5, POI
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=288175
2017(7-9月) 码农类 硕士 全职 Facebook - 内推 - Onsite |Failfresh grad应届毕业生 一共三轮 第一轮: 第一题给两个排好序的没重复array要求返回两个array中共有的element.followup是有重复怎么做.前面的都用的两个指针的方法时间复杂度是\(O(N)\),面试官说有没有比这个更优化的做法,我只是简单说说用二分法,两个array都做二分,面试官说按照这个思路想对的但是没有让继续说思路就换下一题了.第二题是把一个树转换成双向的list,面经题.
第二轮:一老头,不做题也不问简历,纯behavioral.第一个问题是你每天的动力是什么,他特意说是技术方面的动力.然后问了最喜欢的课是什么,最不喜欢的课是什么,讲一个和队友有冲突的故事,讲一个和队友配合很好的故事,最喜欢的教授是谁,最不喜欢的教授是谁.
第三轮: 就一道题,设计一个数据结构实现get(key), put(key, value), delete(key)和getLast()来存放k-v对.这个getLast返回的是上一次操作的k-v对,但是删除的操作不算,因为删除的k-v已经不在数据结构里了.
www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=288076
46.4 Length of Longest Arithmetic Progression (LLAP)
Find longest Arithmetic Progression in an integer array and return its length. More formally, find longest sequence of indeces, 0 < i1 < i2 < … < ik < ArraySize(0-indexed) such that sequence A[i1], A[i2], …, A[ik] is an Arithmetic Progression. Arithmetic Progression is a sequence in which all the differences between consecutive pairs are the same, i.e sequence B[0], B[1], B[2], …, B[m - 1] of length m is an Arithmetic Progression if and only if B[1] - B[0] == B[2] - B[1] == B[3] - B[2] == … == B[m - 1] - B[m - 2].
Examples
1) 1, 2, 3(All differences are equal to 1)
2) 7, 7, 7(All differences are equal to 0)
3) 8, 5, 2(Yes, difference can be negative too)
Samples
1) Input: 3, 6, 9, 12; Output: 4
2) Input: 9, 4, 7, 2, 10; Output: 3(If we choose elements in positions 1, 2 and 4(0-indexed))
https://www.interviewbit.com/problems/longest-arithmetic-progression/
2017(4-6月) 码农类 博士 全职 Facebook - 内推 - Onsite |Pass在职跳槽
面试结束,回报
一共四轮,Coding 2 轮, design 1 轮, BQ 1 轮.
大部分都是面经,像罗马数字, 稀疏矩阵什么.
一道题目不太常见,但地里也有人提到过. 求最长等差数列个数.
1,3,2,5,7,4,10. 答案是4, (1,3,5,7). 用DP 就行.
设计是 news API design, 也是面经了.注意pagination. 看看twitter的 API developer’s guide 会有帮助.
http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array
http://jeffe.cs.illinois.edu/pubs/pdf/arith.pdf
http://www.lai18.com/content/8624958.html
An entry dp[i][j] in this table stores LLAP with v[i] and v[j] as first two elements of AP and j > i. The last column of the table is always 2 (Why – see the meaning of dp[i][j]).
T: \(O(N^2)\)
int Longest_Arithmetic_Progression(vector<int> &v) {
int L=v.size(), r=2;
if(L<=2) return L;
sort(v.begin(), v.end());
vector<vector<int>> dp(L,vector<int>(L, 2));// a matrix with all 2
for(int j=L-2; j>=1; --j){ // starting from the second last column
int i=j-1, k=j+1;
while(i>=0 && k<=L-1){
if(v[i]-v[j]+v[k] < v[j]) k++; // avoid overflow
else if(v[i]-v[j]+v[k] > v[j]) i--;
else{
dp[i][j] = dp[j][k]+1;
r=max(r, dp[i][j]);
break; // i--, k++;
}
}
}
return r;
}46.5 Interview URLs
2017(7-9月) 码农类 硕士 实习 Facebook - 内推 - 技术电面 |Passfresh grad应届毕业生
今天下午刚出的FB实习面经,问了两道从未见过的题.
Almost palindrom
"""
A string S is an ‘almost palindrome’ if you can remove 0 or 1 character from S to make a palindrome..
e.g. momo
Given a string S determine if it is an almost palindrome.
"""
用了two pointer, 如果不一样就check s[left:right]和s[left+1:right+1]有没有一个是palindrom 有就return True.这里我出了个错,不过在提示下改过来了.
第二题似曾相识,给一个binary tree, 有两个node是marked,找到它们之间最近的距离.我用的方法是先找到它们的lowest common ancestor,然后用BFS做.在面试官提示下改进了代码,最后做出来了. http://bit.ly/2wOj9KS
2017(1-3月) 码农类 硕士 实习 Facebook - 内推 - 技术电面 |Passfresh grad应届毕业生
一面2.28,国人大哥,第一题是字符串去重, 第二题是利特扣十五,但数组内元素可重复使用.followup优化时间复杂度.
二面3.8,越南大叔,第一题是打印二叉树所有路径, 空间复杂度问很细,followup优化空间复杂度.第二题是利特扣一四零,返回切分好的插入空格的字符串.
3.9收到offer.
感想:
感谢去年亚麻实习六个月没给return,迫使我不得不重新找实习和工作.让我明白到拼命完成完整service、website、test、deploy、metric analysis,check in 一万多行code也是枉然,上面不想给就是什么都没有.无论何时何地都不能耽于安逸,疏于刷题.毕竟所有工作都是at will,唯有刷题才能救自己.
http://bit.ly/2wOaic5
http://bit.ly/2wOT7r8
2017(4-6月) 码农类 博士 全职 Facebook - 内推 - Onsite |Otherfresh grad应届毕业生
面完脸家,回报地里发个昂塞特面经,不知道nda要求有多严格,所以写的稍微模糊一点,见谅.
1. 合并k数据流的迭代器;电话本的变种.这是lz找工生涯的第一个面试,今年行情好差,本来以为phd至少店面得有吧,谁知道人家根本不跟你fresh谈…特别frustrated,有种“怀才不遇”的感觉..只有脸还理我…真的紧张死了,高考都没这么紧张..由于是第一次昂塞特,开始把握不是太好,话说太多解释太详细,导致第一题做完只剩15分钟,小哥说第二题做不完也没关系,我一听就急了,心想lc都刷了5遍了,要是跪在做题上岂不太不甘心,于是对小哥说,下面我要进入高速processing模式,于是五分钟秒了电话本,小哥被明显impress,看起来还不错.
2. 机器学习面.简单的推荐新闻系统,实在是没什么难的,但也没什么惊艳的地方可以讲,一般般吧.
3. 行为面.说好的三十分钟thesis presentation居然被面试官直接一句没啥卵用就pass了,可惜我准备了整整两周,每天白板讲两遍啊,,,行为面了四十多分钟,也不知道自己答得合不合口味,唉.最后验证一下搜索树,3分钟秒了.
4. 新题,无向图上两点最短距离.写了bfs,小哥不满意空间复杂度,又写了dfs,小哥不满意时间复杂度,想了想又写了双向bfs,小哥挺满意.然后瞎聊followup,说有重量怎么办,我又精神抖擞写了个dijkstra,觉得还行,没辜负自己辛苦刷题.
5. 系统.一个找最近朋友系统.做了三种核心,geohash,quadtree,kdtree,我觉得自己纯属找抽,为啥非要讲这个东西有这么几种方法,(((φ(◎ロ◎;)φ))),然后就是各种系统tradeoff,scaleup…
唯一的面试,也说不来是不是面的足够好,没有比较没有经验.真是感觉有时候天命难违,准备的再好再多,依旧要看天吃饭,人能做的只有抓住自己手上仅有的几个机会而已.只求bless,求offer.
46.6 383. Ransom Note
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
Note: You may assume that both strings contain only lowercase letters.
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> truehttps://leetcode.com/problems/ransom-note/
struct Solution {
bool canConstruct(string ransomNote, string magazine) {
int m[26]={};
for(char c : magazine)
m[c-'a']++;
for(char c : ransomNote)
if (--m[c-'a'] < 0) return 0;
return 1;
}
};2017(7-9月) 码农类 硕士 全职 Facebook - 猎头 - Onsite |Other在职跳槽
一共只有四轮1:383 七十六变形
2:设计end to end fb app的搜索
3:经历 和 一领伍
4:而要而
设计答得很渣,写了后端实现到前端读取,什么aggregation,cache,elasticsearch,schema,content access level都答了,但是最后面试官问:如果你从trie里拿的结果太多的posts了怎么办?我想了半天说rank top k然后只返回那些top的.对方不置可否,反正就是感觉没达到点子上的感觉. 求RP加面设计…
http://bit.ly/2iLiEhU
2017(7-9月) 码农类 硕士 全职 Facebook - 猎头 - Onsite |Other在职跳槽
Phone:
1. 矩阵乘法
2. Task schedule, 任务间有冷却时间K 相邻task必须隔至少K, 保持task顺序 , 求需要多少时间
Onsite
1a. flatten nest LinkedList, 最后返回一个单个的没有nest的LinkedList
1b. 给一个NxM的矩阵, 里面是字母, 给一个word 问能不能用矩阵里的某个letter作为起点然后上下左右移动形成
2 Behavior
3 system design, 网络爬虫系统
4a valid IP in string format and return the uint32 format,注意corner case.
4b given BST and two vals(lo an hi), return sum of nodes whose val in [lo , hi]. O(N) and O(logN) solution
5 system design, client 给 server 传输文件 的系统. 一个/多个clients <-> 一个／多个 server
coding都是秒了, design 渣渣了. good luck吧
http://bit.ly/2iLrTOU
46.7 304. Range Sum Query 2D - Immutable
Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
https://leetcode.com/problems/range-sum-query-2d-immutable/
bunafish 发表于 2017-8-18 03:55:56 | 只看该作者 回帖奖励
2017(7-9月) 码农类 硕士 全职 Facebook - 内推 - 技术电面 |Other在职跳槽
朋友帮忙内推 大概一周不到recruiter联系 约电面. 两天前电面 两道题:
1. 给两个坐标左上和右下 求围成的矩阵里的所有元素的和 (lc 3零4)
2. longest arithmetic sequence 面经题 唯一和我看到的不同处是要求返回最长sequence
刚收到recruiter电话 说面试feedback不错 我工作经验太少 没有headcount了 有了再联系我… (迷之微笑脸) 内推的朋友说正在盖新大楼盖完应该就有了
46.8 350. Intersection of Two Arrays II
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
Note:
Each element in the result should appear as many times as it shows in both arrays. The result can be in any order.
Follow up:
1. What if the given array is already sorted? How would you optimize your algorithm?
2. What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
3. What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
https://leetcode.com/problems/intersection-of-two-arrays-ii/
46.8.2 Algo 2: Two pointers
class Solution { // O(NLogN)
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
int i = 0, j = 0;
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
while (i < nums1.size() && j < nums2.size()) {
if (nums1[i] == nums2[j]) {
res.push_back(nums1[i]);
++i; ++j;
} else if (nums1[i] > nums2[j]) {
++j;
} else {
++i;
}
}
return res;
}
};# If the given array is not sorted and the memory is unlimited:
# - Time: O(m + n)
# - Space: O(min(m, n))
# elif the given array is already sorted:
# if m << n or m >> n:
# - Time: O(min(m, n) * log(max(m, n)))
# - Space: O(1)
# else:
# - Time: O(m + n)
# - Soace: O(1)
# else: (the given array is not sorted and the memory is limited)
# - Time: O(max(m, n) * log(max(m, n)))
# - Space: O(1)
# Given two arrays, write a function to compute their intersection.
#
# Example:
# Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
#
# Note:
# Each element in the result should appear as many times as it shows in both arrays.
# The result can be in any order.
#
# Follow up:
# - What if the given array is already sorted? How would you optimize your algorithm?
# - What if nums1's size is small compared to num2's size? Which algorithm is better?
# - What if elements of nums2 are stored on disk, and the memory is limited such that
# you cannot load all elements into the memory at once?
# If the given array is not sorted and the memory is unlimited.
# Time: O(m + n)
# Space: O(min(m, n))
# Hash solution.
import collections
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
if len(nums1) > len(nums2):
return self.intersect(nums2, nums1)
lookup = collections.defaultdict(int)
for i in nums1:
lookup[i] += 1
res = []
for i in nums2:
if lookup[i] > 0:
res += i,
lookup[i] -= 1
return res
def intersect2(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
c = collections.Counter(nums1) & collections.Counter(nums2)
intersect = []
for i in c:
intersect.extend([i] * c[i])
return intersect
# If the given array is already sorted, and the memory is limited, and (m << n or m >> n).
# Time: O(min(m, n) * log(max(m, n)))
# Space: O(1)
# Binary search solution.
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
if len(nums1) > len(nums2):
return self.intersect(nums2, nums1)
def binary_search(compare, nums, left, right, target):
while left < right:
mid = left + (right - left) / 2
if compare(nums[mid], target):
right = mid
else:
left = mid + 1
return left
nums1.sort(), nums2.sort() # Make sure it is sorted, doesn't count in time.
res = []
left = 0
for i in nums1:
left = binary_search(lambda x, y: x >= y, nums2, left, len(nums2), i)
if left != len(nums2) and nums2[left] == i:
res += i,
left += 1
return res
# If the given array is already sorted, and the memory is limited or m ~ n.
# Time: O(m + n)
# Soace: O(1)
# Two pointers solution.
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1.sort(), nums2.sort() # Make sure it is sorted, doesn't count in time.
res = []
it1, it2 = 0, 0
while it1 < len(nums1) and it2 < len(nums2):
if nums1[it1] < nums2[it2]:
it1 += 1
elif nums1[it1] > nums2[it2]:
it2 += 1
else:
res += nums1[it1],
it1 += 1
it2 += 1
return res
# If the given array is not sorted, and the memory is limited.
# Time: O(max(m, n) * log(max(m, n)))
# Space: O(1)
# Two pointers solution.
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1.sort(), nums2.sort() # O(max(m, n) * log(max(m, n)))
res = []
it1, it2 = 0, 0
while it1 < len(nums1) and it2 < len(nums2):
if nums1[it1] < nums2[it2]:
it1 += 1
elif nums1[it1] > nums2[it2]:
it2 += 1
else:
res += nums1[it1],
it1 += 1
it2 += 1
return res2017(7-9月) 码农类 本科 全职 Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生
报一个最近的面经,脸熟电面,攒点人品希望能有昂赛
1. 里口 易二武, 比原题更简单一点,判断回文的时候只考虑字母,数字空格和其他字符都不考虑
2. 里口 叁舞零, 数组已经sorted了,先用的two pointer写的,问了时空复杂度,test case
follow up: 如果两个数组中有一个数组特别长,怎么办,答 binary search,问了具体怎么用binary search来实现,然后要求写binary search 找lower bound.
每一问都问了时间复杂度,空间复杂度,列test case,口头跑其中一个test case. 攒攒人品,求昂赛!
http://bit.ly/2vSKbA3