k**o
发帖数: 3006 | 1 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
发了两篇小paper，做过几个research里的小project，C++ coding能力还行
Facebook intern面试，因为时间紧，HR没有general interview
Technical interview有两轮
第一轮:
1. 怎样de-dup一个sorted array？
我先写了一个linear scan的算法，很弱
后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
出来了T_T
follow-up: 如果有一个big single file, many servers, how to use these
servers to compute this problem? 要求尽量balance load
我有点晕，这个听上去有点太简单了，不知道有什么trick...但是还是老老实
实说每个server 读一部分file，分别计算，最后用个很简单的merge就可以了。还可能
让第一个CPU |
s***l
发帖数: 129 | 2 thanks for sharing!
背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
发了两篇小paper，做过几个research里的小project，C++ coding能力还行
Facebook面试，因为时间紧，HR没有general interview
Technical interview有两轮
第一轮:
1. 怎样de-dup一个sorted array？
我先写了一个linear scan的算法，很弱
后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
出来了T_T
follow-up: 如果有一个big single file, many servers, how to use these
servers to compute this problem? 要求尽量balance load
我有点晕，这个听上去有点太简单了，不知道有什么trick...但是还是老老实
实说每个server 读一部分file，分别计算，最后用个很简单的merge就可
【在 k**o 的大作中提到】
: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these
|
s******t
发帖数: 2374 | |
L*******o
发帖数: 895 | |
b****u
发帖数: 37 | 5 2. 怎样check circular in a linked list
另外一种算法是什么？
【在 k**o 的大作中提到】
: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these
|
k**o
发帖数: 3006 | 6 reverse the list and check if the head appears twice~
【在 b****u 的大作中提到】
: 2. 怎样check circular in a linked list
: 另外一种算法是什么？
|
c********t
发帖数: 1756 | |
S******n
发帖数: 1009 | 8 just curious, how do you optimize de-dup problem using binary search?
I think linear is enough.
【在 k**o 的大作中提到】
: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these
|
h*****a
发帖数: 1992 | 9 Search "teleporting turtle"
【在 k**o 的大作中提到】
: reverse the list and check if the head appears twice~
|
S******n
发帖数: 1009 | 10 nice
【在 k**o 的大作中提到】
: reverse the list and check if the head appears twice~
|
|
|
P*******e
发帖数: 1353 | 11 cong!
【在 k**o 的大作中提到】
: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these
|
r****o
发帖数: 1950 | 12 谢谢，请问de-dup怎么用binary search优化啊？
binary search每次只能处理半边啊？
是不是可以用divide and conquer?
【在 k**o 的大作中提到】
: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these
|
r****o
发帖数: 1950 | 13 第二题为什么要用hash table 来存每个department工资最高的人啊？
直接用个变量存不行吗？
【在 k**o 的大作中提到】
: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these
|
k**o
发帖数: 3006 | 14 啊，其实不应该叫Binary search，我当时没说清楚
大概的作法是遇到一个数a[i]，然后看a[i+2], a[i+4], a[i+8], ..., a[i+2^n]
看是不是和a[i]相同
如果a[i+2^(n-1)]=a[i], a[i+2^n] != a[i]，就从a[i+2^(n-1)]开始线性向后找
直到遇到j使a[j] != a[i]
这样最坏情况下还是O(n)，但是如果dup很多的话肯定会快些
【在 S******n 的大作中提到】
: just curious, how do you optimize de-dup problem using binary search?
: I think linear is enough.
|
r****o
发帖数: 1950 | 15 谢谢。
我的想法是divide and conquer. mid=(start+end)/2
每次递归调用如下。
0)开始 end
1)比较a[mid]和a[end],如果相同，则a[mid+1]..a[end]全部不用考虑。 end=mid.
2)比较a[mid]和a[start],如果相同，则a[start]..a[mid-1]全部不用考虑。start=mid.
3)然后
递归左半边(start..mid-1)
如果a[mid]!=a[mid-1] 则打印a[mid]//也可以push a[mid]到一个新的vector。
递归右半边(mid+1..end)
我觉得这样的话，复杂度是O(n')。 n'是n除掉重复元素后剩下的元素数目。
大家觉得我的方法可以吗？
【在 k**o 的大作中提到】
: 啊，其实不应该叫Binary search，我当时没说清楚
: 大概的作法是遇到一个数a[i]，然后看a[i+2], a[i+4], a[i+8], ..., a[i+2^n]
: 看是不是和a[i]相同
: 如果a[i+2^(n-1)]=a[i], a[i+2^n] != a[i]，就从a[i+2^(n-1)]开始线性向后找
: 直到遇到j使a[j] != a[i]
: 这样最坏情况下还是O(n)，但是如果dup很多的话肯定会快些
|
l***r
发帖数: 241 | |
L*****s
发帖数: 24744 | 17 LZ你要是进去了,能帮我找几个人的背景资料不撒.哇咔咔 |
r****o
发帖数: 1950 | 18 自己顶一下。
mid.
【在 r****o 的大作中提到】
: 谢谢。
: 我的想法是divide and conquer. mid=(start+end)/2
: 每次递归调用如下。
: 0)开始 end: 1)比较a[mid]和a[end],如果相同，则a[mid+1]..a[end]全部不用考虑。 end=mid.
: 2)比较a[mid]和a[start],如果相同，则a[start]..a[mid-1]全部不用考虑。start=mid.
: 3)然后
: 递归左半边(start..mid-1)
: 如果a[mid]!=a[mid-1] 则打印a[mid]//也可以push a[mid]到一个新的vector。
: 递归右半边(mid+1..end)
|
k**o
发帖数: 3006 | 19 我说binary search的时候想法跟你差不多，也是比较start, end 和mid的关系
你可以再具体想想看能不能code出来，complexity是多少~~
我觉着最坏情况下有可能还不如linear scan，但是不确定~~
【在 r****o 的大作中提到】
: 自己顶一下。
:
: mid.
|
r****o
发帖数: 1950 | 20 我code完了可以打印出来啊。
为啥最坏情况下可能还不如linear scan呢？最坏就是O(n)吧。
【在 k**o 的大作中提到】
: 我说binary search的时候想法跟你差不多，也是比较start, end 和mid的关系
: 你可以再具体想想看能不能code出来，complexity是多少~~
: 我觉着最坏情况下有可能还不如linear scan，但是不确定~~
|
|
|
c**m
发帖数: 535 | 21 赞！
连夜赶VLDB?
【在 k**o 的大作中提到】
: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these
|
s********f
发帖数: 510 | 22 那个array是sorted,所以可以search每一个value的last position
【在 S******n 的大作中提到】
: just curious, how do you optimize de-dup problem using binary search?
: I think linear is enough.
|
s******t
发帖数: 2374 | 23 这个可以这么写么？
Node slow = root;
Node fast = root;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast) return true;
}
return false;
===
. 怎样check circular in a linked list
。。。这个大家都知道吧。。。
我写完常规解法后说，我还知道另一种算法，就是小尾羊之前说的那种 |
s******t
发帖数: 2374 | 24 int a[];
int b[];
如果是升序
========
int i= lena + lenb - 1, j = lena - 1, k = lenb - 1;
for(;j >= 0 && k >= 0;){
if(a[j] >= b[k]) a[i--] = a[j--];
else a[i--] = b[k--];
}
while(k >= 0) a[i--] = b[k--];
=====
于是他就出了道merge two sorted array的问题，
如果array A有足够空间，如何in-place merge A and B (both sorted) |
k**o
发帖数: 3006 | 25 good, this is what i wrote during the interview
【在 s******t 的大作中提到】
: int a[];
: int b[];
: 如果是升序
: ========
: int i= lena + lenb - 1, j = lena - 1, k = lenb - 1;
: for(;j >= 0 && k >= 0;){
: if(a[j] >= b[k]) a[i--] = a[j--];
: else a[i--] = b[k--];
: }
: while(k >= 0) a[i--] = b[k--];
|
k**o
发帖数: 3006 | 26 yes it is sorted
【在 s********f 的大作中提到】
: 那个array是sorted,所以可以search每一个value的last position
|
s******t
发帖数: 2374 | 27 我被加面一轮了。上一轮答的太差。recruiter刚给我写信了。
【在 k**o 的大作中提到】
: good, this is what i wrote during the interview
|
k**o
发帖数: 3006 | 28 是啊……哭
写得烂，还是投了
万恶啊
【在 c**m 的大作中提到】
: 赞！
: 连夜赶VLDB?
|
k**o
发帖数: 3006 | 29 汗，也就是说总共有三次面试的机会？
FB看来还是很想要人的，这么有耐心
【在 s******t 的大作中提到】
: 我被加面一轮了。上一轮答的太差。recruiter刚给我写信了。
|
h**6
发帖数: 4160 | |
|
|
h*******x
发帖数: 12808 | 31 赞！
of
engineering
【在 k**o 的大作中提到】
: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these
|
g*********s
发帖数: 1782 | 32
why linear scan is weak? how does the binary search work? O(lgN) is just
for a single element. To de-duplicate the whole sorted array, i think O(N)
is the best.
【在 k**o 的大作中提到】
: 汗，也就是说总共有三次面试的机会？
: FB看来还是很想要人的，这么有耐心
|
c******w
发帖数: 1108 | 33 u can do better on average. but worst case is O(N)
【在 g*********s 的大作中提到】
:
: why linear scan is weak? how does the binary search work? O(lgN) is just
: for a single element. To de-duplicate the whole sorted array, i think O(N)
: is the best.
|
g*********s
发帖数: 1782 | 34 for each element, do equal_range?
even on average i don't see how it is better...
【在 c******w 的大作中提到】
: u can do better on average. but worst case is O(N)
|
j********x
发帖数: 2330 | |
j*****u
发帖数: 1133 | 36 thanks for sharing!
follow-up: 如果有一个big single file, many servers, how to use these
servers to compute this problem? 要求尽量balance load
我觉得这个题没什么意义，除非这个file是存储在distributed FS，有replica。因为
如果在单机上，要distribute要首先split这个file，这就已经是一次读写了，读写中
还有一个是remote的。有这一次读写去重已经完成了。
如果是unsorted并且bitmap不能fit到single memory，这时并行才有意义。
【在 k**o 的大作中提到】
: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these
|
c**m
发帖数: 535 | 37 赞！多谢分享！
PS：
突然发现你原来已经不做PhotoGear版主了。。。
【在 k**o 的大作中提到】
: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these
|
J*********n
发帖数: 370 | 38 congrats~ 请问lz二面后多久知道结果？ |
J*********n
发帖数: 370 | 39 突然发现这个帖子是去年的.....居然被二楼给考古出来了...... |
y**q
发帖数: 246 | 40 kyro你好，
我想请教一下，你说的第一个问题中，那个binarysearch来优化的算法是什么？
谢谢！
【在 k**o 的大作中提到】
: 背景：东部排名30/40左右的州立大学CS PHD第三年，Database方向
: 发了两篇小paper，做过几个research里的小project，C++ coding能力还行
: Facebook intern面试，因为时间紧，HR没有general interview
: Technical interview有两轮
: 第一轮:
: 1. 怎样de-dup一个sorted array？
: 我先写了一个linear scan的算法，很弱
: 后来扯到Binary search来optimize，但是当时没说清楚，后来放下电话就想
: 出来了T_T
: follow-up: 如果有一个big single file, many servers, how to use these
|
|
|
i**********e
发帖数: 1145 | 41 我想就是如果有非常多 duplicates 的时候，用 binary search 来优化。。。
例如，排好序之后成为
aa
bb
cc
cc
cc
cc
... 非常多的 'cc'
cc
cc
dd
如果 linear scan 的话要一个一个去除 'cc'.
如果使用 binary search 的话就可以 lg n 的时间来找到 cc 和 dd 的交界处.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 y**q 的大作中提到】
: kyro你好，
: 我想请教一下，你说的第一个问题中，那个binarysearch来优化的算法是什么？
: 谢谢！
|
i****d
发帖数: 35 | 42 如果每次都找交界的话，岂不是O(nlgn)了
【在 i**********e 的大作中提到】
: 我想就是如果有非常多 duplicates 的时候，用 binary search 来优化。。。
: 例如，排好序之后成为
: aa
: bb
: cc
: cc
: cc
: cc
: ... 非常多的 'cc'
: cc
|
