logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
【非死不可面经】今天FB面试onsite，求bless
avatar
【非死不可面经】今天FB面试onsite，求bless# JobHunting - 待字闺中
l*i
1 楼
贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
一共四轮面试，加一个午餐
早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
partition。
然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
面试环节。
第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
然后问了复杂度的估计。
第三轮：两个阿三或阿拉伯人(一个负责观察)，编程题两道：LCA和倒序打印链表
followup问“程序可能会被abuse的情形及如何处理”
第四轮，ABC女经理，设计题：任给一个手机的位置信号(经纬度)，需要返回附近5mile
的POI，怎么设计这样的系统
不知道最后的反馈如何，不过觉得自己没犯什么大错，希望应该没有问题吧。
BTW，现在进非死不可的话，给多少股票。现在有了推特的卧佛，感觉他家很难给出更
有吸引力的package了。
祝大家旗开得胜，卧佛多多；华人软工，一统天下，菜死烙印
=============================================
结束以后贴面经
avatar
A*u
2 楼
bless

【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
avatar
r*m
3 楼
大大的bless!!!
avatar
S*e
4 楼
Bless

★ 发自iPhone App: ChineseWeb 7.3

【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
avatar
c*r
5 楼
Big big big Bless~
avatar
g*d
6 楼
Bless
avatar
k*d
7 楼
bless!

【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
avatar
I*O
8 楼
bless~

【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
avatar
w*x
9 楼
布莱斯。。。。 在线等你面经
avatar
a*e
10 楼
bless!
avatar
c*n
11 楼
bless!
avatar
m*i
12 楼
bless
avatar
c*n
13 楼
bless
avatar
f*h
14 楼
big bless~~
avatar
t*7
15 楼
膜拜面霸,BLESS
avatar
s*y
16 楼
bless
avatar
p*j
17 楼
bless
avatar
s*v
18 楼
bless ! 等面经

【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
avatar
g*e
19 楼
bless
avatar
m*s
20 楼
Bless

【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
avatar
i*y
21 楼
Bless
avatar
c*p
22 楼
Bless!

【在 i****y 的大作中提到】
: Bless
avatar
l*u
23 楼
bless

【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
avatar
p*p
24 楼
big big bless!
avatar
h*e
25 楼
Bless面霸。

【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
avatar
l*i
26 楼
贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
一共四轮面试，加一个午餐
早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
partition。
然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
面试环节。
第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
然后问了复杂度的估计。
第三轮：两个阿三或阿拉伯人(一个负责观察)，编程题两道：LCA和倒序打印链表
followup问“程序可能会被abuse的情形及如何处理”
第四轮，ABC女经理，设计题：任给一个手机的位置信号(经纬度)，需要返回附近5mile
的POI，怎么设计这样的系统
不知道最后的反馈如何，不过觉得自己没犯什么大错，希望应该没有问题吧。
BTW，现在进非死不可的话，给多少股票。现在有了推特的卧佛，感觉他家很难给出更
有吸引力的package了。
祝大家旗开得胜，卧佛多多；华人软工，一统天下，菜死烙印
avatar
n*r
27 楼
bless!等好消息！
avatar
w*x
28 楼
第一题楼主描述的准确吗？
第三题abuse指的是什么？
最后一题POI是啥？能更具体一点吗？
avatar
j*g
29 楼
POI 我猜是 Points of interest?

【在 w****x 的大作中提到】
: 第一题楼主描述的准确吗？
: 第三题abuse指的是什么？
: 最后一题POI是啥？能更具体一点吗？
avatar
C*U
30 楼
好难啊啊

数目

【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
avatar
l*i
31 楼
准确
abuse我开始也没弄清，后来想是不是别人传入一些非法的数据结构，比如要求是tree
，传入graph等等，另外一点就是multi-thread，一个访问，另外一个thread修改tree
的结构，这时候就要考虑用lock，不过这一点是经他们提醒之后我答的
POI就是point of interests，比如饭店等等

【在 w****x 的大作中提到】
: 第一题楼主描述的准确吗？
: 第三题abuse指的是什么？
: 最后一题POI是啥？能更具体一点吗？
avatar
h*n
32 楼
第一题啥意思啊？ 能举个例子吗？子数组必须是连续的吗？谢谢！
avatar
j*g
33 楼
followup那部分需要把thread-safe的code再写一遍吗还是只要讲讲就行呢。。。
LCA是bst 还是 就普通 binary tree呀。。

tree
tree

【在 l****i 的大作中提到】
: 准确
: abuse我开始也没弄清，后来想是不是别人传入一些非法的数据结构，比如要求是tree
: ，传入graph等等，另外一点就是multi-thread，一个访问，另外一个thread修改tree
: 的结构，这时候就要考虑用lock，不过这一点是经他们提醒之后我答的
: POI就是point of interests，比如饭店等等
avatar
l*i
34 楼
不需要
最简单的解法就是对数组排序，从后向前算sum直到不小于key

【在 h*********n 的大作中提到】
: 第一题啥意思啊？ 能举个例子吗？子数组必须是连续的吗？谢谢！
avatar
l*i
35 楼
不是BST
我写了最简单的：我问有没有parent指针，他们问说有什么区别吗？我说如果有，可以
在o(lg n)完成否则就是o(n)，他们说那你写lg n的吧，囧……

【在 j********g 的大作中提到】
: followup那部分需要把thread-safe的code再写一遍吗还是只要讲讲就行呢。。。
: LCA是bst 还是 就普通 binary tree呀。。
:
: tree
: tree
avatar
x*y
36 楼
膜拜大牛
avatar
C*U
37 楼
第一题用partition好像只要logn的时间
第二个n皇后问题用recursion?
avatar
w*x
38 楼
晕，子数组不用连续那描述就不准确了, 你说的是任意数的组合？？？
avatar
l*i
39 楼
有人问nqueens，我的解法就是暴力解法，用recuisive直接搜索
不知道有没有更好的办法
一会贴code

数目

【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
avatar
l*i
40 楼
至少要O(n)

【在 C***U 的大作中提到】
: 第一题用partition好像只要logn的时间
: 第二个n皇后问题用recursion?
avatar
l*i
41 楼
汗，描述不准确，不好意思，本来想说子集合的，怕大家误会成set，任意数的组合也
不对吧，一个元素不能reuse
大致意思就是数组中元素sum不小于key的最小子集

【在 w****x 的大作中提到】
: 晕，子数组不用连续那描述就不准确了, 你说的是任意数的组合？？？
avatar
l*i
42 楼
贴一下自己的code
BTW，我虽然是CS的PHD但自己本科硕士都不是CS，所以coding很烂，不是什么大牛，跟
版上很多人比差距不小，说一下这个也权当是对大家的鼓励吧
int nQueens(int n){
if(n<=0) return 0;
int *placement = new int[n];
assert(placement);
int cnt = nQueensHelper(placement, n, 0);
delete[] placement;
return cnt;
}
int nQueensHelper(int *placement, int sz, int curr){
if(curr>=sz) return 1;
int cnt = 0;
for(int i=0; iplacement[curr] = i;
if(validatePlacement(placement, sz, curr))
cnt += nQueensHelper(placement, sz, curr+1);
}
}
bool validatePlacement(int *placement, int sz, int curr){
if(curr<0) return false;
if(curr==0) return true;
for(int i=0; iif(placement[i] == placement[curr]) return false;
if(abs(placement[i]-placement[curr]) == curr-i) return false;
}
return true;
}
avatar
c*5
43 楼
LCA??
avatar
C*U
44 楼
ok
是O(n)的时间。。。而且是平均O(n)的时间

【在 l****i 的大作中提到】
: 至少要O(n)
avatar
s*o
45 楼
这都return了还怎么delete？

【在 l****i 的大作中提到】
: 贴一下自己的code
: BTW，我虽然是CS的PHD但自己本科硕士都不是CS，所以coding很烂，不是什么大牛，跟
: 版上很多人比差距不小，说一下这个也权当是对大家的鼓励吧
: int nQueens(int n){
: if(n<=0) return 0;
: int *placement = new int[n];
: assert(placement);
: int cnt = nQueensHelper(placement, n, 0);
: delete[] placement;
: return cnt;
avatar
A*X
46 楼
bless
有了推特的offer，经历onsite时的观察角度就是不一样
avatar
l*i
47 楼
啊，这是个bug
我当时是用的vector，没这个问题

【在 s******o 的大作中提到】
: 这都return了还怎么delete？
avatar
t*t
48 楼
脸书和腿特的interview是有人内推的还是自己递的简历？

数目

【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
avatar
j*t
49 楼
bless
avatar
w*x
50 楼
你的key指的是什么？ 任意一个数， 解法能详细说说不

【在 l****i 的大作中提到】
: 汗，描述不准确，不好意思，本来想说子集合的，怕大家误会成set，任意数的组合也
: 不对吧，一个元素不能reuse
: 大致意思就是数组中元素sum不小于key的最小子集
avatar
s*h
51 楼

他的nlogk 有点奇怪...不知道这个k是什么
define k to be |desired subset|,
use heap, then it is k * log n.
not sure what n * log k is...

【在 w****x 的大作中提到】
: 你的key指的是什么？ 任意一个数， 解法能详细说说不
avatar
s*o
52 楼
貌似 nQueensHelper 最后还缺一个return。。。
另外这个做法似乎过不了leetcode的OJ (N-Queens II)，不知道还有没有更快的方法

【在 l****i 的大作中提到】
: 贴一下自己的code
: BTW，我虽然是CS的PHD但自己本科硕士都不是CS，所以coding很烂，不是什么大牛，跟
: 版上很多人比差距不小，说一下这个也权当是对大家的鼓励吧
: int nQueens(int n){
: if(n<=0) return 0;
: int *placement = new int[n];
: assert(placement);
: int cnt = nQueensHelper(placement, n, 0);
: delete[] placement;
: return cnt;
avatar
w*x
53 楼
第一题是选一个pivot的element, 然后partition同时计算右半边的sum, 如果sum大于k
调整数组如果小于k调整k，这样收敛。想了半天。
皇后问题我居然用二维数组。
楼主还是牛啊，我去直接挂了
avatar
s*o
54 楼
关于第一题还是不明白
能否详细说一下
你这个k是不是楼主说的key

于k

【在 w****x 的大作中提到】
: 第一题是选一个pivot的element, 然后partition同时计算右半边的sum, 如果sum大于k
: 调整数组如果小于k调整k，这样收敛。想了半天。
: 皇后问题我居然用二维数组。
: 楼主还是牛啊，我去直接挂了
avatar
s*o
55 楼
也觉得是k*logn，并且klogn应该比nlogk好吧因为n>=k尤其当n>>k时

【在 s***h 的大作中提到】
:
: 他的nlogk 有点奇怪...不知道这个k是什么
: define k to be |desired subset|,
: use heap, then it is k * log n.
: not sure what n * log k is...
avatar
l*i
56 楼
是的，汗，昨天FB是我的最后一个面试，现在过于放松了，写啥都是bug
昨天应该没有犯这个毛病

【在 s******o 的大作中提到】
: 貌似 nQueensHelper 最后还缺一个return。。。
: 另外这个做法似乎过不了leetcode的OJ (N-Queens II)，不知道还有没有更快的方法
avatar
l*i
57 楼
如果用priority queue做一次scan，应该是O(n log k), k是最后找到的子集所包含的
元素数
更好的做法是用快速排序的partition，复杂度是O(n)

【在 s**********o 的大作中提到】
: 关于第一题还是不明白
: 能否详细说一下
: 你这个k是不是楼主说的key
:
: 于k
avatar
l*i
58 楼
用priority queue是O(n log(k))吧，每次对queue做一次update(或插入或删除或更新)
都是log(k),总共循环n次(对数组做一次scan)，所以是n log(k),k是左后找到的子集和
的大小(priority queue的大小)

【在 s***h 的大作中提到】
:
: 他的nlogk 有点奇怪...不知道这个k是什么
: define k to be |desired subset|,
: use heap, then it is k * log n.
: not sure what n * log k is...
avatar
w*x
59 楼

先heapify然后一个个取最大的数

【在 l****i 的大作中提到】
: 如果用priority queue做一次scan，应该是O(n log k), k是最后找到的子集所包含的
: 元素数
: 更好的做法是用快速排序的partition，复杂度是O(n)
avatar
s*o
60 楼
难道不是每次extractMax，共extract k次，每次O(logn)?
因为你一开始并不知道k是什么，怎么会有一个k大小的heap?
不明白
还有partition怎么做？

新)

【在 l****i 的大作中提到】
: 用priority queue是O(n log(k))吧，每次对queue做一次update(或插入或删除或更新)
: 都是log(k),总共循环n次(对数组做一次scan)，所以是n log(k),k是左后找到的子集和
: 的大小(priority queue的大小)
avatar
l*i
61 楼
不是。
scan一边数组：
如果当前的数比heap的最小值大，更新heap
如果heap的当前sum不足key且当前元素>0，插入
如果heap的当前sum超过key且删除
一遍过后，heap中存的就是值不小于key的最小子集

【在 w****x 的大作中提到】
:
: 先heapify然后一个个取最大的数
avatar
l*i
62 楼
额，是的，你这个方法比我的好。是O(k log n)
partition比较简单，随便找一个pivot，把数组partition成两半，monitor右半部分的
sum
如果sum等于key，直接返回
如果sum>key,接着partition
如果sum
【在 s**********o 的大作中提到】
: 难道不是每次extractMax，共extract k次，每次O(logn)?
: 因为你一开始并不知道k是什么，怎么会有一个k大小的heap?
: 不明白
: 还有partition怎么做？
:
: 新)
avatar
w*x
63 楼
partition解法, 一点都没觉得简单:
int _inner_min_set(int a[], int n, int k)
{
if (n <= 0) return 0;
if (n == 1) return a[0] >= k ? 1 : 0;
swap(a[0], a[n/2]);
int i = 1;
int j = n-1;
while (i <= j)
{
if (a[i] < a[0])
i++;
else if (a[j] >= a[0])
j--;
else swap(a[i], a[j]);
}
swap(a[0], a[j]);
int nSum = 0;
int nLft = 0;
if (j == n-1)
{
nSum = a[j];
nLft = n-1;
}
else
{
for (int x = n-1; x > j; x--)
nSum += a[x];
nLft = j+1;
}
if (nSum >= k)
return _inner_min_set(a + nLft, n - nLft, k);
return _inner_min_set(a, nLft, k-nSum) + n - nLft;
}
int GetMinSet(int a[], int n, int k)
{
if (k < 0)
{
int nMax = a[0];
for (int i = 1; i < n; i++)
nMax = max(a[i], nMax);
return nMax >= k ? 1 : 0;
}
//Get the positive part
int i = 0;
int j = n-1;
while (i <= j)
{
if (a[i] < 0)
i++;
else if (a[j] >= 0)
j--;
else swap(a[i], a[j]);
}
if (i >= n) return 0;
return _inner_min_set(a+i, n-i, k);
}
avatar
w*x
64 楼
N queen
int _inner_get_ways(int pRec[], int n, int nCur)
{
if (nCur >= n)
return 1;
int nRet = 0;
for (int i = 0; i < n; i++)
{
bool bNoneAttack = true;
for (int j = 0; j < nCur && bNoneAttack; j++)
{
if (pRec[j] == i || abs(nCur - j) == abs(i - pRec[j]))
bNoneAttack = false;
}
if (bNoneAttack)
{
pRec[nCur] = i;
nRet += _inner_get_ways(pRec, n, nCur+1);
}
}
return nRet;
}
int GetNQueenWays(int n)
{
if (n <= 0) return 0;
int* pRec = new int[n];
int nRet = _inner_get_ways(pRec, n, 0);
delete []pRec;
return nRet;
}
avatar
r*g
65 楼
bless lz！
听说fb喜欢问大数据的题目，lz的题目有follow up到的吗？比如最后一题points太多
，内存/一个机器放不下之类的。

数目

【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
avatar
f*i
66 楼
bless
avatar
g*d
67 楼
bless
avatar
l*i
68 楼
也没问太多大数据的问题
最后一个面试官是DB出生的，对怎么query比较感兴趣

【在 r********g 的大作中提到】
: bless lz！
: 听说fb喜欢问大数据的题目，lz的题目有follow up到的吗？比如最后一题points太多
: ，内存/一个机器放不下之类的。
:
: 数目
avatar
l*i
69 楼
推特是他们一个manager主动联系我的
F是我主动联系他们一个manager的

【在 t***t 的大作中提到】
: 脸书和腿特的interview是有人内推的还是自己递的简历？
:
: 数目
avatar
r*g
70 楼
啊，我以为最后一个题是关于怎么实现的。。我的一个想法是先得到离这个point x轴
y轴方向各5mile的，然后再一个个比较。但是query是什么？是说比如用sql的话怎么
query？

【在 l****i 的大作中提到】
: 也没问太多大数据的问题
: 最后一个面试官是DB出生的，对怎么query比较感兴趣
avatar
s*o
71 楼
多谢啦！不过还有sum大于key的情况需要特殊考虑。
另外楼主能否详谈一下最后一个设计题
考点在哪？已有的数据是什么类型的？

分找

【在 l****i 的大作中提到】
: 额，是的，你这个方法比我的好。是O(k log n)
: partition比较简单，随便找一个pivot，把数组partition成两半，monitor右半部分的
: sum
: 如果sum等于key，直接返回
: 如果sum>key,接着partition
: 如果sum
avatar
w*x
72 楼

很好的方法啊！

【在 l****i 的大作中提到】
: 不是。
: scan一边数组：
: 如果当前的数比heap的最小值大，更新heap
: 如果heap的当前sum不足key且当前元素>0，插入
: 如果heap的当前sum超过key且删除
: 一遍过后，heap中存的就是值不小于key的最小子集
相关阅读
传统化工行业的ENGINEER和医用材料公司的RESEARCH SCIENTIST?找cs码工工作的话简历里写会verilogOPT13号开始但要过两个礼拜上班需要向学校报告吗？Google的Product Manager找数据库相关职位, 有DBA经验,opt gap问题有谁做过facebook的puzzle？求MS-onsite祝福EE 想转申请data analyst 职位，请问有无专业限制？salary negotiation后收到的回信opt照片要求onsite面试后,一周没给消息,正常吗?OPT I765表格，STATE/PROVINCE手贱多填了，要紧么？Specialist Technical 这个职位是个什么收入水平？有谁用过Bugzilla这个软件Bloomberg on campus之后就没消息了啊How to work out "three months’ notice"?讨论一下: good code, bad code, great code我有个不祥的预感请教disc assessment
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。