a********9
发帖数: 129 | 1 已挂
电面 1
国人大哥，应该有点放水
1) fabanacia，期待o(lgn)解法,但O(n)也行
2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
只知道worse case 是O(n^2)
onsite1
behavior: 1)有什么跟同事意见冲突的案例，怎么解决
2) 以前做过的项目如果现在再做会有什么不同/改进
3）divide and mod，但不能用/或者%，基本也是leetcode原题了
onsite2
system desgin: 因为我是kernel背景，让我用mutex,cv实现一个semephor，说先考虑
单核，然后拓展到多核，但我只写了单核的就没时间了，不知道多核的会有什么不同，
要求code compilable，MD三哥从一进来就没好脸色，此轮negative
onsite3:
1) 给你10g文件，1g内存，数总共有多少个不同的数，答案是用bit来记录数字，总共
4b个interger,最多用0.5gb来记录，follow up是如果只有400m怎么办，答案是把数字
hash一下或者说scan文件多次，每次取尾数bits不一样的数，不用code
2) read file up to 4K, 也是老题了
3) 求平方根，基本也是leetcode原题，但给的数是double，这样如果给的n是小于1的
数，初始的right就得取1而不是n
onsite4:
也是kernel组的三哥，先上来问了btree跟bst的区别，btree里放多少个index怎么决定
，答案是disk block size / 每个index的长度，如果是内存的话就用cache line size除
还有vm的，我也不大懂，好像是说如何解决内存的fagement问题，如何把多个分开的小
片段移到一起，用到了madvise这个syscall,还问为什么返回一个新的page之前要清零
，答案是因为page上可能是别的process的内容
code题是decode，比如说1 → 1, 2 -- > 01, 3 → 001, 4 → 0001,....，给你一个
无限的stream，要求输出数字，应该没啥难度，follow up是如何优化，我给的答案是
map，就是依次取char而不是bit，然后把char的值对应到string上，他说cpu还有一个
instruction可以直接查询此个char有多少个leading zero
最后祝我跟大家都能拿到满意的offer！ |
d***n
发帖数: 832 | |
a********9
发帖数: 129 | 3 有总共就4个，有个极品老印，千万要小心。。他们就是做optimaztion，比如面我那人
说的fagmental问题
【在 d***n 的大作中提到】
: 谢谢共享。FB有kernel组？具体做什么的
|
b*******e
发帖数: 123 | |
k*******t
发帖数: 144 | |
k*******t
发帖数: 144 | 6 fibonacci吧
【在 b*******e 的大作中提到】
: 什么是fabanacia？
|
a********9
发帖数: 129 | 7 对，不好意思，英语比较烂
【在 k*******t 的大作中提到】
: fibonacci吧
|
s********u
发帖数: 1109 | |
b*******e
发帖数: 123 | |
r*******6
发帖数: 99 | |
|
|
a******e
发帖数: 710 | 11 菲波那契数列为啥都期待o(log n)解法呢。 就是期待你做过这道题么？
我怎么觉得没见过的话，基本上没可能想出来呢。。。
【在 a********9 的大作中提到】
: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了
|
b*******e
发帖数: 123 | 12 Fibo 那题是analytic formula + optimized power function么？ |
k****a
发帖数: 32 | 13 用矩阵
【在 b*******e 的大作中提到】
: Fibo 那题是analytic formula + optimized power function么？
|
s********u
发帖数: 1109 | |
k****a
发帖数: 32 | 15 可以现推导
不过 pow() 里幂是float 还是O(1)么...？
【在 s********u 的大作中提到】
: 其实可以O（1），就是公式背不出来。
: http://discuss.leetcode.com/questions/246/climbing-stairs
|
C****y
发帖数: 77 | |
g**u
发帖数: 504 | |
s********u
发帖数: 1109 | 18 多谢指正
【在 g**u 的大作中提到】
: 公式是 log N
|
a********9
发帖数: 129 | 19 我得到的教训反而是CS基本功以及自己那一块别落下了。。因为code题都很简单。。
【在 C****y 的大作中提到】
: 谢谢分享，看来leetcode得使劲练啊
|
w*******e
发帖数: 154 | 20 "让我用mutex,cv实现一个semephor",
请问这个cv是啥意思？ |
|
|
r*******e
发帖数: 7583 | 21 conditional variable
【在 w*******e 的大作中提到】
: "让我用mutex,cv实现一个semephor",
: 请问这个cv是啥意思？
|
a********9
发帖数: 129 | 22 conditional variable
【在 w*******e 的大作中提到】
: "让我用mutex,cv实现一个semephor",
: 请问这个cv是啥意思？
|
z****u
发帖数: 41 | 23 第二题的时间复杂度不是n^2吧
【在 a********9 的大作中提到】
: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了
|
s******d
发帖数: 424 | 24 cv= condition variable
【在 w*******e 的大作中提到】
: "让我用mutex,cv实现一个semephor",
: 请问这个cv是啥意思？
|
w******g
发帖数: 189 | 25 一个O(logn)的解法
class Solution {
public:
int climbStairs(int n) {
// Start typing your Java solution below
// DO NOT write main() function
if(n==1){return 1;}
if(n==2){return 2;}
if(n==3){return 3;}
int low;
int high;
if(n%2==0){
low = n/2;
high = n/2;
}
else {
low = (n-1)/2;
high = (n+1)/2;
}
return climbStairs(low)*climbStairs(high)+climbStairs(low-1)*climbStairs
(high-1);
}
}; |
x*****0
发帖数: 452 | |
t*********7
发帖数: 255 | |
a********9
发帖数: 129 | 28 已挂
电面 1
国人大哥，应该有点放水
1) fabanacia，期待o(lgn)解法,但O(n)也行
2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
只知道worse case 是O(n^2)
onsite1
behavior: 1)有什么跟同事意见冲突的案例，怎么解决
2) 以前做过的项目如果现在再做会有什么不同/改进
3）divide and mod，但不能用/或者%，基本也是leetcode原题了
onsite2
system desgin: 因为我是kernel背景，让我用mutex,cv实现一个semephor，说先考虑
单核，然后拓展到多核，但我只写了单核的就没时间了，不知道多核的会有什么不同，
要求code compilable，MD三哥从一进来就没好脸色，此轮negative
onsite3:
1) 给你10g文件，1g内存，数总共有多少个不同的数，答案是用bit来记录数字，总共
4b个interger,最多用0.5gb来记录，follow up是如果只有400m怎么办，答案是把数字
hash一下或者说scan文件多次，每次取尾数bits不一样的数，不用code
2) read file up to 4K, 也是老题了
3) 求平方根，基本也是leetcode原题，但给的数是double，这样如果给的n是小于1的
数，初始的right就得取1而不是n
onsite4:
也是kernel组的三哥，先上来问了btree跟bst的区别，btree里放多少个index怎么决定
，答案是disk block size / 每个index的长度，如果是内存的话就用cache line size除
还有vm的，我也不大懂，好像是说如何解决内存的fagement问题，如何把多个分开的小
片段移到一起，用到了madvise这个syscall,还问为什么返回一个新的page之前要清零
，答案是因为page上可能是别的process的内容
code题是decode，比如说1 → 1, 2 -- > 01, 3 → 001, 4 → 0001,....，给你一个
无限的stream，要求输出数字，应该没啥难度，follow up是如何优化，我给的答案是
map，就是依次取char而不是bit，然后把char的值对应到string上，他说cpu还有一个
instruction可以直接查询此个char有多少个leading zero
最后祝我跟大家都能拿到满意的offer！ |
d***n
发帖数: 832 | |
a********9
发帖数: 129 | 30 有总共就4个，有个极品老印，千万要小心。。他们就是做optimaztion，比如面我那人
说的fagmental问题
【在 d***n 的大作中提到】
: 谢谢共享。FB有kernel组？具体做什么的
|
|
|
b*******e
发帖数: 123 | |
k*******t
发帖数: 144 | |
k*******t
发帖数: 144 | 33 fibonacci吧
【在 b*******e 的大作中提到】
: 什么是fabanacia？
|
a********9
发帖数: 129 | 34 对，不好意思，英语比较烂
【在 k*******t 的大作中提到】
: fibonacci吧
|
s********u
发帖数: 1109 | |
b*******e
发帖数: 123 | |
r*******6
发帖数: 99 | |
a******e
发帖数: 710 | 38 菲波那契数列为啥都期待o(log n)解法呢。 就是期待你做过这道题么？
我怎么觉得没见过的话，基本上没可能想出来呢。。。
【在 a********9 的大作中提到】
: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了
|
b*******e
发帖数: 123 | 39 Fibo 那题是analytic formula + optimized power function么？ |
k****a
发帖数: 32 | 40 用矩阵
【在 b*******e 的大作中提到】
: Fibo 那题是analytic formula + optimized power function么？
|
|
|
s********u
发帖数: 1109 | |
k****a
发帖数: 32 | 42 可以现推导
不过 pow() 里幂是float 还是O(1)么...？
【在 s********u 的大作中提到】
: 其实可以O（1），就是公式背不出来。
: http://discuss.leetcode.com/questions/246/climbing-stairs
|
C****y
发帖数: 77 | |
g**u
发帖数: 504 | |
s********u
发帖数: 1109 | 45 多谢指正
【在 g**u 的大作中提到】
: 公式是 log N
|
a********9
发帖数: 129 | 46 我得到的教训反而是CS基本功以及自己那一块别落下了。。因为code题都很简单。。
【在 C****y 的大作中提到】
: 谢谢分享，看来leetcode得使劲练啊
|
w*******e
发帖数: 154 | 47 "让我用mutex,cv实现一个semephor",
请问这个cv是啥意思？ |
r*******e
发帖数: 7583 | 48 conditional variable
【在 w*******e 的大作中提到】
: "让我用mutex,cv实现一个semephor",
: 请问这个cv是啥意思？
|
a********9
发帖数: 129 | 49 conditional variable
【在 w*******e 的大作中提到】
: "让我用mutex,cv实现一个semephor",
: 请问这个cv是啥意思？
|
z****u
发帖数: 41 | 50 第二题的时间复杂度不是n^2吧
【在 a********9 的大作中提到】
: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了
|
|
|
s******d
发帖数: 424 | 51 cv= condition variable
【在 w*******e 的大作中提到】
: "让我用mutex,cv实现一个semephor",
: 请问这个cv是啥意思？
|
w******g
发帖数: 189 | 52 一个O(logn)的解法
class Solution {
public:
int climbStairs(int n) {
// Start typing your Java solution below
// DO NOT write main() function
if(n==1){return 1;}
if(n==2){return 2;}
if(n==3){return 3;}
int low;
int high;
if(n%2==0){
low = n/2;
high = n/2;
}
else {
low = (n-1)/2;
high = (n+1)/2;
}
return climbStairs(low)*climbStairs(high)+climbStairs(low-1)*climbStairs
(high-1);
}
}; |
x*****0
发帖数: 452 | |
t*********7
发帖数: 255 | |
s******d
发帖数: 9806 | 55 "让我用mutex,cv实现一个semephor，说先考虑单核，然后拓展到多核。"
不太理解多核的意思？是说resource count可以大于1么？单核就是binary semaphore?
简单写一个POSIX的，请大家指正。
pthread_mutex_t mutex;
pthread_cond_t convar;
int count = N;//N is the number of threads allows to work at the same time
void sem_wait() {
pthread_mutex_lock(&mutex);
count--;
if (count < 0)//no resource, have to wait
pthread_cont_wait(&convar,&mutex);//mutex will be released when
waiting
pthread_mutex_unlock(&mutex);
}
void sem_post() {
pthread_mutex_lock(&mutex);
count++;
if (count <= 0)//someone's waiting...
pthread_cont_signal(&convar);
pthread_mutex_unlock(&mutex);
}
【在 a********9 的大作中提到】
: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了
|
o***c
发帖数: 32 | 56 数学不好，求大神指导怎么推导这个递推式？
【在 w******g 的大作中提到】
: 一个O(logn)的解法
: class Solution {
: public:
: int climbStairs(int n) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(n==1){return 1;}
: if(n==2){return 2;}
: if(n==3){return 3;}
: int low;
|
b******i
发帖数: 914 | 57 你好，很感谢你的面经，想就此问几个问题：
1. generate all possible parentheses, 这题为什么时间是O(n^2)呢？你是用的类似
于DP的方法做的吗？我看九章和careercup只是一个dfs的方法，复杂度感觉是指数的。
2. onsite 3里面10G文件那题的follow up，不是很懂你的答案：follow up是如果只有
400m怎么办，答案是把数字
hash一下或者说scan文件多次，每次取尾数bits不一样的数，不用code
hash每次取尾数bits不一样的数以后，是再如何找出其中所有不同的数呢？再哈希一遍？
这题careercup150上面有，好像是分block来做的。
谢谢
【在 a********9 的大作中提到】
: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了
|
n******n
发帖数: 12088 | 58 N应该是输入长度吧。
【在 g**u 的大作中提到】
: 公式是 log N
|
s******d
发帖数: 9806 | 59 "让我用mutex,cv实现一个semephor，说先考虑单核，然后拓展到多核。"
不太理解多核的意思？是说resource count可以大于1么？单核就是binary semaphore?
简单写一个POSIX的，请大家指正。
pthread_mutex_t mutex;
pthread_cond_t convar;
int count = N;//N is the number of threads allows to work at the same time
void sem_wait() {
pthread_mutex_lock(&mutex);
count--;
if (count < 0)//no resource, have to wait
pthread_cont_wait(&convar,&mutex);//mutex will be released when
waiting
pthread_mutex_unlock(&mutex);
}
void sem_post() {
pthread_mutex_lock(&mutex);
count++;
if (count <= 0)//someone's waiting...
pthread_cont_signal(&convar);
pthread_mutex_unlock(&mutex);
}
【在 a********9 的大作中提到】
: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了
|
o***c
发帖数: 32 | 60 数学不好，求大神指导怎么推导这个递推式？
【在 w******g 的大作中提到】
: 一个O(logn)的解法
: class Solution {
: public:
: int climbStairs(int n) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(n==1){return 1;}
: if(n==2){return 2;}
: if(n==3){return 3;}
: int low;
|
|
|
b******i
发帖数: 914 | 61 你好，很感谢你的面经，想就此问几个问题：
1. generate all possible parentheses, 这题为什么时间是O(n^2)呢？你是用的类似
于DP的方法做的吗？我看九章和careercup只是一个dfs的方法，复杂度感觉是指数的。
2. onsite 3里面10G文件那题的follow up，不是很懂你的答案：follow up是如果只有
400m怎么办，答案是把数字
hash一下或者说scan文件多次，每次取尾数bits不一样的数，不用code
hash每次取尾数bits不一样的数以后，是再如何找出其中所有不同的数呢？再哈希一遍？
这题careercup150上面有，好像是分block来做的。
谢谢
【在 a********9 的大作中提到】
: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了
|
n******n
发帖数: 12088 | 62 N应该是输入长度吧。
【在 g**u 的大作中提到】
: 公式是 log N
|
s*********y
发帖数: 10 | |
