I**A
发帖数: 2345 | 1 第一次，一个中国小伙儿，人特别NICE
1) Introduce himself
2) Introduce myself
3) About web services
a. Horizontal vs Vertical Fillings
4) Java Abstract vs Interface， give samples for each
5) A list of unsorted numbers a[0..n] and a target number x, check if
there is a pair of numbers in the array can sum to x
Extended question, how do we find three numbers that can sum up to a
target value
6) A list of array of n+1 numbers contains the natural number from 1 to N
, each number occurs exa |
j**l
发帖数: 2911 | 2 我四面后都一周了，还没有任何消息，发信也没有回复，看来是被默拒了，无语... |
I**A
发帖数: 2345 | 3 pat pat
amazon一般都不默拒的，再等等。。
【在 j**l 的大作中提到】
: 我四面后都一周了，还没有任何消息，发信也没有回复，看来是被默拒了，无语...
|
l******4
发帖数: 729 | 4 奇怪，我只有2面就onsite乐。 不过最后还是挂了。
另外，我想问一点。有2面，是不是说明第一面的结果还不错？ 还是每个人至少都有2
个电面？ |
j**l
发帖数: 2911 | |
h**6
发帖数: 4160 | 6 这段时间面amazon的很多啊，貌似google和micrsoft的少了一些。 |
p******n
发帖数: 32 | 7 bless
楼主能把第5题extension和第6题的解法讲讲吗？
if
【在 I**A 的大作中提到】
: 第一次，一个中国小伙儿，人特别NICE
: 1) Introduce himself
: 2) Introduce myself
: 3) About web services
: a. Horizontal vs Vertical Fillings
: 4) Java Abstract vs Interface， give samples for each
: 5) A list of unsorted numbers a[0..n] and a target number x, check if
: there is a pair of numbers in the array can sum to x
: Extended question, how do we find three numbers that can sum up to a
: target value
|
h*****z
发帖数: 4732 | 8 bless
【在 I**A 的大作中提到】
: 第一次，一个中国小伙儿，人特别NICE
: 1) Introduce himself
: 2) Introduce myself
: 3) About web services
: a. Horizontal vs Vertical Fillings
: 4) Java Abstract vs Interface， give samples for each
: 5) A list of unsorted numbers a[0..n] and a target number x, check if
: there is a pair of numbers in the array can sum to x
: Extended question, how do we find three numbers that can sum up to a
: target value
|
i*****e
发帖数: 113 | 9 1.5) a[0..n], 夹挤定理
ext:
定义三个指针，第一个最慢，两个逐渐增大
如果超过，则移动第一个指针，其他两个往小的方向移动
以此类推
1.6) E1 = Sigma(1..N)
S1 = Sigma(a[1..N+1])
X = S1 - E1
ext:
X+Y = S1 - E1
E2 = Sigma(1^2..N^2)
S2 = Sigma(a[1^2..(N+2)^2)
X^2+Y^2 = S2 - E2
3.a)
node_t *p1 = head, *p2 = head;
int n = N;
while (n-- && p2->next) {
p2 = p2->next;
}
while (p2->next) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
【在 I**A 的大作中提到】
: 第一次，一个中国小伙儿，人特别NICE
: 1) Introduce himself
: 2) Introduce myself
: 3) About web services
: a. Horizontal vs Vertical Fillings
: 4) Java Abstract vs Interface， give samples for each
: 5) A list of unsorted numbers a[0..n] and a target number x, check if
: there is a pair of numbers in the array can sum to x
: Extended question, how do we find three numbers that can sum up to a
: target value
|
I**A
发帖数: 2345 | 10 5 extension..
我先给点儿提示，你再想想，想不出来我再说答案？
hint: 想办法把三个数的sum转化为两个数的sum。。
6 是比较常见的一个，sum of array - sum of (1..n)就是duplicate
哦，你楼下给答案了
【在 p******n 的大作中提到】
: bless
: 楼主能把第5题extension和第6题的解法讲讲吗？
:
: if
|
|
|
I**A
发帖数: 2345 | 11 1.5 ext这个详细说说？
我当时给了一个O(n^2)的，貌似interviewer很满意。。
【在 i*****e 的大作中提到】
: 1.5) a[0..n], 夹挤定理
: ext:
: 定义三个指针，第一个最慢，两个逐渐增大
: 如果超过，则移动第一个指针，其他两个往小的方向移动
: 以此类推
: 1.6) E1 = Sigma(1..N)
: S1 = Sigma(a[1..N+1])
: X = S1 - E1
: ext:
: X+Y = S1 - E1
|
z*z
发帖数: 837 | 12 bless
【在 I**A 的大作中提到】
: 第一次，一个中国小伙儿，人特别NICE
: 1) Introduce himself
: 2) Introduce myself
: 3) About web services
: a. Horizontal vs Vertical Fillings
: 4) Java Abstract vs Interface， give samples for each
: 5) A list of unsorted numbers a[0..n] and a target number x, check if
: there is a pair of numbers in the array can sum to x
: Extended question, how do we find three numbers that can sum up to a
: target value
|
l******4
发帖数: 729 | 13 6月份我onsite的时候，就是这个题。 不过只问了2个数的情况。
最让我惊讶的事，interviewer好像不知道有O(n)的解法。 我给他解释了半天去
complementary
array里面找。 他很惊讶，最后说very nice solution.
【在 I**A 的大作中提到】
: 5 extension..
: 我先给点儿提示，你再想想，想不出来我再说答案？
: hint: 想办法把三个数的sum转化为两个数的sum。。
: 6 是比较常见的一个，sum of array - sum of (1..n)就是duplicate
: 哦，你楼下给答案了
|
K******g
发帖数: 1870 | 14 请问把1.5解释详细点吗？多谢。
【在 i*****e 的大作中提到】
: 1.5) a[0..n], 夹挤定理
: ext:
: 定义三个指针，第一个最慢，两个逐渐增大
: 如果超过，则移动第一个指针，其他两个往小的方向移动
: 以此类推
: 1.6) E1 = Sigma(1..N)
: S1 = Sigma(a[1..N+1])
: X = S1 - E1
: ext:
: X+Y = S1 - E1
|
I**A
发帖数: 2345 | 15 嗯，我说，有两种办法，一种呢O(nlgn)，一种呢,可以借助hashtable达到O(n)，
interviewer自己就说了，听听O(n)的，不过显然他知道这个算法。。
你这个interviewer自己不把题目搞清楚的确是比较奇怪。。
【在 l******4 的大作中提到】
: 6月份我onsite的时候，就是这个题。 不过只问了2个数的情况。
: 最让我惊讶的事，interviewer好像不知道有O(n)的解法。 我给他解释了半天去
: complementary
: array里面找。 他很惊讶，最后说very nice solution.
|
d*********3
发帖数: 79 | 16 re
【在 I**A 的大作中提到】
: 第一次，一个中国小伙儿，人特别NICE
: 1) Introduce himself
: 2) Introduce myself
: 3) About web services
: a. Horizontal vs Vertical Fillings
: 4) Java Abstract vs Interface， give samples for each
: 5) A list of unsorted numbers a[0..n] and a target number x, check if
: there is a pair of numbers in the array can sum to x
: Extended question, how do we find three numbers that can sum up to a
: target value
|
e****9
发帖数: 316 | 17 1.5的一个想法
数组排序后第一个元素指向a[0],然后看a[1]到a[n]中有没有sum－a[0]的组合，以此类推
网上还看到一个变形题目，未排序数组a[0]到a[n]中存储0到n，有没有好的求sum组合
的方法 |
e****9
发帖数: 316 | |
I**A
发帖数: 2345 | 19 好的就是idesire的那个方法.
【在 e****9 的大作中提到】
: 还有6Ext那个有什么好办法吗？
|
f*********5
发帖数: 576 | 20 第6题 n很大，求和会溢出，怎么办？
【在 I**A 的大作中提到】
: 5 extension..
: 我先给点儿提示，你再想想，想不出来我再说答案？
: hint: 想办法把三个数的sum转化为两个数的sum。。
: 6 是比较常见的一个，sum of array - sum of (1..n)就是duplicate
: 哦，你楼下给答案了
|
|
|
I**A
发帖数: 2345 | 21 那就边求着边减着吧
【在 f*********5 的大作中提到】
: 第6题 n很大，求和会溢出，怎么办？
|
f*********5
发帖数: 576 | 22 每次都减？
减多少？MAX_INT?
【在 I**A 的大作中提到】
: 那就边求着边减着吧
|
f*********5
发帖数: 576 | 23 Could u share us your idea of linux file system,security system
if
【在 I**A 的大作中提到】
: 第一次，一个中国小伙儿，人特别NICE
: 1) Introduce himself
: 2) Introduce myself
: 3) About web services
: a. Horizontal vs Vertical Fillings
: 4) Java Abstract vs Interface， give samples for each
: 5) A list of unsorted numbers a[0..n] and a target number x, check if
: there is a pair of numbers in the array can sum to x
: Extended question, how do we find three numbers that can sum up to a
: target value
|
M********5
发帖数: 715 | 24
如果这一题可以使用一个额外的存储空间，就很简单
不过如果你的条件里面有n很大，那么使用一个长度为N的数组就不是很合算
如果允许破坏原数组的顺序，这一题其实很容易，不用求和，不用额外的存储空间，并
且保证O(n)的执
行效率
【在 f*********5 的大作中提到】
: 第6题 n很大，求和会溢出，怎么办？
|
I**A
发帖数: 2345 | 25 你是说swap? 这个当然也行，不过要慢一些
【在 M********5 的大作中提到】
:
: 如果这一题可以使用一个额外的存储空间，就很简单
: 不过如果你的条件里面有n很大，那么使用一个长度为N的数组就不是很合算
: 如果允许破坏原数组的顺序，这一题其实很容易，不用求和，不用额外的存储空间，并
: 且保证O(n)的执
: 行效率
|
I**A
发帖数: 2345 | 26 做题的时候这个问题没有被bring up
你刚才问的时候我就随脑子那么一想。。
我们不是两个SUM相减么？
其实我想的是别两个SUM相减了，一对一滴减算了。。
你问的那两个design我也说不好。。
主要是问需要哪些classes, class之间的relation. etc
比如linux file system
需要有File, Permission, Directory等等
然后File里面有Permission， Directory里面有File等
当然各个class的variables, methods需要哪些。。。
Security System是用来control building rooms的
需要People, Room, Badge, BadgeReader 等等
People有Badge, Room有BadgeReaders等等
据说我这个amazon已经就算是挂了。。
所以这些DESIGN你随便看看就是。。
不过大家要是合力把AMAZON的那些FAMOUS DESIGN QUESTIONS做做倒是肯定有用～～
【在 f*********5 的大作中提到】
: 每次都减？
: 减多少？MAX_INT?
|
M********5
发帖数: 715 | 27
还没面，照你的样子看估计我也八成挂了
【在 I**A 的大作中提到】
: 做题的时候这个问题没有被bring up
: 你刚才问的时候我就随脑子那么一想。。
: 我们不是两个SUM相减么？
: 其实我想的是别两个SUM相减了，一对一滴减算了。。
: 你问的那两个design我也说不好。。
: 主要是问需要哪些classes, class之间的relation. etc
: 比如linux file system
: 需要有File, Permission, Directory等等
: 然后File里面有Permission， Directory里面有File等
: 当然各个class的variables, methods需要哪些。。。
|
f*********5
发帖数: 576 | 28 not swap
a[a[i]%(N+1)-1]+=N+1
if a[k]>2*N+1 then k+1 is duplicate
【在 I**A 的大作中提到】
: 你是说swap? 这个当然也行，不过要慢一些
|
I**A
发帖数: 2345 | 29 我运气不是很好，
你还没面，怎么知道就挂了？
加油加油。。
【在 M********5 的大作中提到】
:
: 还没面，照你的样子看估计我也八成挂了
|
T*******e
发帖数: 4928 | 30 bless.
【在 I**A 的大作中提到】
: 我运气不是很好，
: 你还没面，怎么知道就挂了？
: 加油加油。。
|
|
|
I**A
发帖数: 2345 | 31 没看懂，太复杂了。。
以后我要是interview别人
谁写这么难理解的code先拖出去扁。。
【在 f*********5 的大作中提到】
: not swap
: a[a[i]%(N+1)-1]+=N+1
: if a[k]>2*N+1 then k+1 is duplicate
|
f*********5
发帖数: 576 | 32 since it will add N+1
【在 I**A 的大作中提到】
: 没看懂，太复杂了。。
: 以后我要是interview别人
: 谁写这么难理解的code先拖出去扁。。
|
I**A
发帖数: 2345 | 33 嗯，我后来明白了。。
半夜我脑子不转了
干脆你用语言描述一下的方法吧
【在 f*********5 的大作中提到】
: since it will add N+1
|
N*D
发帖数: 3641 | 34 use XOR
int dup = a[0];
for (int i=1; i<=N; i++) {
dup = dup ^ i ^ a[i];
}
return dup;
【在 f*********5 的大作中提到】
: 每次都减？
: 减多少？MAX_INT?
|
M********5
发帖数: 715 | 35
后面的条件是不适要改成
if a[k]-N-1 > N+1
因为前面不是每个都加了N+1的么
【在 f*********5 的大作中提到】
: not swap
: a[a[i]%(N+1)-1]+=N+1
: if a[k]>2*N+1 then k+1 is duplicate
|
f*********5
发帖数: 576 | 36 I know this...
for the 2nd question,
split the array and 1toN to 2 group with the first bit=1 of dup..
then ...
【在 N*D 的大作中提到】
: use XOR
: int dup = a[0];
: for (int i=1; i<=N; i++) {
: dup = dup ^ i ^ a[i];
: }
: return dup;
|
f*********5
发帖数: 576 | 37 yes
it should be 2*N+1...
【在 M********5 的大作中提到】
:
: 后面的条件是不适要改成
: if a[k]-N-1 > N+1
: 因为前面不是每个都加了N+1的么
|
M********5
发帖数: 715 | 38
这个算法聪明
【在 N*D 的大作中提到】
: use XOR
: int dup = a[0];
: for (int i=1; i<=N; i++) {
: dup = dup ^ i ^ a[i];
: }
: return dup;
|
I**A
发帖数: 2345 | 39 有两个duplicate就不work了
【在 N*D 的大作中提到】
: use XOR
: int dup = a[0];
: for (int i=1; i<=N; i++) {
: dup = dup ^ i ^ a[i];
: }
: return dup;
|
N*D
发帖数: 3641 | 40 still work， see the post next to me.
go through 3 times. We have this discussion in the club.
【在 I**A 的大作中提到】
: 有两个duplicate就不work了
|
|
|
f*********5
发帖数: 576 | 41 if a[i]==5 ,it mean 5 already appeared
so we update a[4]...
if there is a[m]==a[n]==K
then we need to update a[K-1] twice,it should greater than 2*N+1 (in fact
>=2*N+3)
【在 I**A 的大作中提到】
: 嗯，我后来明白了。。
: 半夜我脑子不转了
: 干脆你用语言描述一下的方法吧
|
I**A
发帖数: 2345 | 42 啊，明白了，多谢～～
【在 f*********5 的大作中提到】
: if a[i]==5 ,it mean 5 already appeared
: so we update a[4]...
: if there is a[m]==a[n]==K
: then we need to update a[K-1] twice,it should greater than 2*N+1 (in fact
: >=2*N+3)
|
A***J
发帖数: 478 | |
I**A
发帖数: 2345 | 44 要么没看，要么看了视而不见脑子里悄然飘过，反正没印象。。
for the 2nd question,
split the array and 1toN to 2 group with the first bit=1 of dup..
没看懂
【在 N*D 的大作中提到】
: still work， see the post next to me.
: go through 3 times. We have this discussion in the club.
|
N*D
发帖数: 3641 | 45 http://mitbbs.com/clubarticle/InterviewHackers/31137707_3.html
【在 I**A 的大作中提到】
: 要么没看，要么看了视而不见脑子里悄然飘过，反正没印象。。
: for the 2nd question,
: split the array and 1toN to 2 group with the first bit=1 of dup..
: 没看懂
|
I**A
发帖数: 2345 | |
I**A
发帖数: 2345 | |
g****n
发帖数: 431 | 48 这个夹挤好像有问题吧：先说用这个办法解决2个数sum的情况。假设排好序的数组是：
[1,10,11,12,13,14,15,...,22,23,25], sum是25。唯一解是10+15。如果用2个指针，
第一个
指向1，第二个遍历到25时发现sum超过25，然后第一个指向10，这时第二个指针不论从
哪个方向开始查
找，都需要O(n)时间。这个办法总的时间是O(n^2)，属于brute force。
【在 i*****e 的大作中提到】
: 1.5) a[0..n], 夹挤定理
: ext:
: 定义三个指针，第一个最慢，两个逐渐增大
: 如果超过，则移动第一个指针，其他两个往小的方向移动
: 以此类推
: 1.6) E1 = Sigma(1..N)
: S1 = Sigma(a[1..N+1])
: X = S1 - E1
: ext:
: X+Y = S1 - E1
|
