l****i
发帖数: 230 | 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了。
祝大家旗开得胜，卧佛多多；华人软工，一统天下，菜死烙印
=============================================
结束以后贴面经 |
A**u
发帖数: 2458 | 2 bless
【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
|
r*******m
发帖数: 457 | |
S*****e
发帖数: 229 | 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皇后的可行的摆法数目
|
c*******r
发帖数: 610 | |
g****d
发帖数: 420 | |
k**d
发帖数: 431 | 7 bless!
【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
|
I**********O
发帖数: 493 | 8 bless~
【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
|
w****x
发帖数: 2483 | |
a***e
发帖数: 67 | |
|
|
c*********n
发帖数: 182 | |
m****i
发帖数: 650 | |
c**********n
发帖数: 13712 | |
f******h
发帖数: 45 | |
t*********7
发帖数: 255 | |
s***y
发帖数: 203 | |
p****j
发帖数: 4762 | |
s**********v
发帖数: 1379 | 18 bless ! 等面经
【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
|
g********e
发帖数: 118 | |
m******s
发帖数: 1469 | 20 Bless
【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
|
|
|
i****y
发帖数: 374 | |
c***p
发帖数: 221 | 22 Bless!
【在 i****y 的大作中提到】
: Bless
|
l*********u
发帖数: 19053 | 23 bless
【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
|
p**p
发帖数: 2493 | |
h****e
发帖数: 928 | 25 Bless面霸。
【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
|
l****i
发帖数: 230 | 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了。
祝大家旗开得胜，卧佛多多；华人软工，一统天下，菜死烙印 |
n****r
发帖数: 120 | |
w****x
发帖数: 2483 | 28 第一题楼主描述的准确吗？
第三题abuse指的是什么？
最后一题POI是啥？能更具体一点吗？ |
j********g
发帖数: 244 | 29 POI 我猜是 Points of interest?
【在 w****x 的大作中提到】
: 第一题楼主描述的准确吗？
: 第三题abuse指的是什么？
: 最后一题POI是啥？能更具体一点吗？
|
C***U
发帖数: 2406 | 30 好难啊啊
数目
【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
|
|
|
l****i
发帖数: 230 | 31 准确
abuse我开始也没弄清，后来想是不是别人传入一些非法的数据结构，比如要求是tree
，传入graph等等，另外一点就是multi-thread，一个访问，另外一个thread修改tree
的结构，这时候就要考虑用lock，不过这一点是经他们提醒之后我答的
POI就是point of interests，比如饭店等等
【在 w****x 的大作中提到】
: 第一题楼主描述的准确吗？
: 第三题abuse指的是什么？
: 最后一题POI是啥？能更具体一点吗？
|
h*********n
发帖数: 46 | 32 第一题啥意思啊？ 能举个例子吗？子数组必须是连续的吗？谢谢！ |
j********g
发帖数: 244 | 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，比如饭店等等
|
l****i
发帖数: 230 | 34 不需要
最简单的解法就是对数组排序，从后向前算sum直到不小于key
【在 h*********n 的大作中提到】
: 第一题啥意思啊？ 能举个例子吗？子数组必须是连续的吗？谢谢！
|
l****i
发帖数: 230 | 35 不是BST
我写了最简单的：我问有没有parent指针，他们问说有什么区别吗？我说如果有，可以
在o(lg n)完成否则就是o(n)，他们说那你写lg n的吧，囧……
【在 j********g 的大作中提到】
: followup那部分需要把thread-safe的code再写一遍吗还是只要讲讲就行呢。。。
: LCA是bst 还是 就普通 binary tree呀。。
:
: tree
: tree
|
x****y
发帖数: 252 | |
C***U
发帖数: 2406 | 37 第一题用partition好像只要logn的时间
第二个n皇后问题用recursion? |
w****x
发帖数: 2483 | 38 晕，子数组不用连续那描述就不准确了, 你说的是任意数的组合？？？ |
l****i
发帖数: 230 | 39 有人问nqueens，我的解法就是暴力解法，用recuisive直接搜索
不知道有没有更好的办法
一会贴code
数目
【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
|
l****i
发帖数: 230 | 40 至少要O(n)
【在 C***U 的大作中提到】
: 第一题用partition好像只要logn的时间
: 第二个n皇后问题用recursion?
|
|
|
l****i
发帖数: 230 | 41 汗，描述不准确，不好意思，本来想说子集合的，怕大家误会成set，任意数的组合也
不对吧，一个元素不能reuse
大致意思就是数组中元素sum不小于key的最小子集
【在 w****x 的大作中提到】
: 晕，子数组不用连续那描述就不准确了, 你说的是任意数的组合？？？
|
l****i
发帖数: 230 | 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; i
placement[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; i
if(placement[i] == placement[curr]) return false;
if(abs(placement[i]-placement[curr]) == curr-i) return false;
}
return true;
} |
c******5
发帖数: 84 | |
C***U
发帖数: 2406 | 44 ok
是O(n)的时间。。。而且是平均O(n)的时间
【在 l****i 的大作中提到】
: 至少要O(n)
|
s******o
发帖数: 2233 | 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;
|
A******X
发帖数: 757 | 46 bless
有了推特的offer，经历onsite时的观察角度就是不一样 |
l****i
发帖数: 230 | 47 啊，这是个bug
我当时是用的vector，没这个问题
【在 s******o 的大作中提到】
: 这都return了还怎么delete？
|
t***t
发帖数: 6066 | 48 脸书和腿特的interview是有人内推的还是自己递的简历？
数目
【在 l****i 的大作中提到】
: 贴一下昨天的面经。总体来说现在他家面的非常简单，bar没有以前高了。BTW，非死不
: 可的工作环境真是像网吧一样一样的呀，坑爹呀有木有
: 一共四轮面试，加一个午餐
: 早上11点开始，第一轮面试，奶昔的同胞老中，论文讨论+1个编程。
: 题目:给一个数组和一个key，找出sum不小于key的数目最少的子数组
: 我开始说用一个priority queue,复杂度是O(n lg k)，被提示可以用快速排序的
: partition。
: 然后是午饭，跟一个在网上认识但没见过面的朋友边吃边聊，这一轮应该不算在正式的
: 面试环节。
: 第二轮：白人软工，编程题：n皇后问题：给一个正整数n，返回n皇后的可行的摆法数目
|
j*t
发帖数: 1480 | |
w****x
发帖数: 2483 | 50 你的key指的是什么？ 任意一个数， 解法能详细说说不
【在 l****i 的大作中提到】
: 汗，描述不准确，不好意思，本来想说子集合的，怕大家误会成set，任意数的组合也
: 不对吧，一个元素不能reuse
: 大致意思就是数组中元素sum不小于key的最小子集
|
|
|
s***h
发帖数: 662 | 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指的是什么？ 任意一个数， 解法能详细说说不
|
s******o
发帖数: 2233 | 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;
|
w****x
发帖数: 2483 | 53 第一题是选一个pivot的element, 然后partition同时计算右半边的sum, 如果sum大于k
调整数组如果小于k调整k，这样收敛。想了半天。
皇后问题我居然用二维数组。
楼主还是牛啊，我去直接挂了 |
s**********o
发帖数: 105 | 54 关于第一题还是不明白
能否详细说一下
你这个k是不是楼主说的key
于k
【在 w****x 的大作中提到】
: 第一题是选一个pivot的element, 然后partition同时计算右半边的sum, 如果sum大于k
: 调整数组如果小于k调整k，这样收敛。想了半天。
: 皇后问题我居然用二维数组。
: 楼主还是牛啊，我去直接挂了
|
s**********o
发帖数: 105 | 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...
|
l****i
发帖数: 230 | 56 是的，汗，昨天FB是我的最后一个面试，现在过于放松了，写啥都是bug
昨天应该没有犯这个毛病
【在 s******o 的大作中提到】
: 貌似 nQueensHelper 最后还缺一个return。。。
: 另外这个做法似乎过不了leetcode的OJ (N-Queens II)，不知道还有没有更快的方法
|
l****i
发帖数: 230 | 57 如果用priority queue做一次scan，应该是O(n log k), k是最后找到的子集所包含的
元素数
更好的做法是用快速排序的partition，复杂度是O(n)
【在 s**********o 的大作中提到】
: 关于第一题还是不明白
: 能否详细说一下
: 你这个k是不是楼主说的key
:
: 于k
|
l****i
发帖数: 230 | 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...
|
w****x
发帖数: 2483 | 59
先heapify然后一个个取最大的数
【在 l****i 的大作中提到】
: 如果用priority queue做一次scan，应该是O(n log k), k是最后找到的子集所包含的
: 元素数
: 更好的做法是用快速排序的partition，复杂度是O(n)
|
s**********o
发帖数: 105 | 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的大小)
|
|
|
l****i
发帖数: 230 | 61 不是。
scan一边数组：
如果当前的数比heap的最小值大，更新heap
如果heap的当前sum不足key且当前元素>0，插入
如果heap的当前sum超过key且删除
一遍过后，heap中存的就是值不小于key的最小子集
【在 w****x 的大作中提到】
:
: 先heapify然后一个个取最大的数
|
l****i
发帖数: 230 | 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怎么做？
:
: 新)
|
w****x
发帖数: 2483 | 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);
} |
w****x
发帖数: 2483 | 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;
} |
r********g
发帖数: 1351 | 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皇后的可行的摆法数目
|
f********i
发帖数: 8412 | |
g****d
发帖数: 420 | |
l****i
发帖数: 230 | 68 也没问太多大数据的问题
最后一个面试官是DB出生的，对怎么query比较感兴趣
【在 r********g 的大作中提到】
: bless lz！
: 听说fb喜欢问大数据的题目，lz的题目有follow up到的吗？比如最后一题points太多
: ，内存/一个机器放不下之类的。
:
: 数目
|
l****i
发帖数: 230 | 69 推特是他们一个manager主动联系我的
F是我主动联系他们一个manager的
【在 t***t 的大作中提到】
: 脸书和腿特的interview是有人内推的还是自己递的简历？
:
: 数目
|
r********g
发帖数: 1351 | 70 啊，我以为最后一个题是关于怎么实现的。。我的一个想法是先得到离这个point x轴
y轴方向各5mile的，然后再一个个比较。但是query是什么？是说比如用sql的话怎么
query？
【在 l****i 的大作中提到】
: 也没问太多大数据的问题
: 最后一个面试官是DB出生的，对怎么query比较感兴趣
|
|
|
s**********o
发帖数: 105 | 71 多谢啦！不过还有sum大于key的情况需要特殊考虑。
另外楼主能否详谈一下最后一个设计题
考点在哪？已有的数据是什么类型的？
分找
【在 l****i 的大作中提到】
: 额，是的，你这个方法比我的好。是O(k log n)
: partition比较简单，随便找一个pivot，把数组partition成两半，monitor右半部分的
: sum
: 如果sum等于key，直接返回
: 如果sum>key,接着partition
: 如果sum
|
w****x
发帖数: 2483 | 72
很好的方法啊！
【在 l****i 的大作中提到】
: 不是。
: scan一边数组：
: 如果当前的数比heap的最小值大，更新heap
: 如果heap的当前sum不足key且当前元素>0，插入
: 如果heap的当前sum超过key且删除
: 一遍过后，heap中存的就是值不小于key的最小子集
|
