m*******i
发帖数: 370 | 1 很郁闷的面挂了，不过还是贡献一下能记住的面试题目，希望对以后的xdjm有用
记不太全了，能记多少写多少吧。可能题目不是那么难对于CS的来说，我是烂校EE的通讯，
实在是EE的通讯opening太少，不好找，无奈投了很多CS的职位。
第一轮电面
1. 为啥投amazon
2. 啥是binary search tree，然后问怎么找least common ancestor
3. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
比如：9=4+5 或者9=2+3+4, 但是8就不可以 这个要写code念code
第二轮电面
1.为啥投amazon（总问）
2. 啥是polymorphism，virtual function 怎么实现的（就是回答机制，virtual
table啦，每个object都有个virtual pointer什么的）
3. design a deck of cards 传说中的设计问题
4. 还问了一个公式的，好像是postfix的啥东西，没听明白
onsite 总共6论，不算hr的话
1. boggle puzzle 找到里面所 |
l******l
发帖数: 497 | 2 能拿到amazon面试，应该是牛人
bless....offer is coming |
a*****p
发帖数: 189 | 3 EE专业的都能去Amazon的Onsite，LZ还是牛人一个。
别难过,job market在转好，相信offer会很快来的。
【在 m*******i 的大作中提到】
: 很郁闷的面挂了，不过还是贡献一下能记住的面试题目，希望对以后的xdjm有用
: 记不太全了，能记多少写多少吧。可能题目不是那么难对于CS的来说，我是烂校EE的通讯，
: 实在是EE的通讯opening太少，不好找，无奈投了很多CS的职位。
: 第一轮电面
: 1. 为啥投amazon
: 2. 啥是binary search tree，然后问怎么找least common ancestor
: 3. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 比如：9=4+5 或者9=2+3+4, 但是8就不可以 这个要写code念code
: 第二轮电面
: 1.为啥投amazon（总问）
|
r**u
发帖数: 1567 | 4 3. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
这个你怎么答的？感觉这个问题不简单啊，brute-force要O（n^2)，back-tracking好
像可以改进一些。
另外，什么是reverse binary tree? mirror binary tree么？还是给一个ordered BST
，构造一棵BST，是原来那棵树的逆序。
BTW, 祝你尽快拿到offer.
【在 m*******i 的大作中提到】
: 很郁闷的面挂了，不过还是贡献一下能记住的面试题目，希望对以后的xdjm有用
: 记不太全了，能记多少写多少吧。可能题目不是那么难对于CS的来说，我是烂校EE的通讯，
: 实在是EE的通讯opening太少，不好找，无奈投了很多CS的职位。
: 第一轮电面
: 1. 为啥投amazon
: 2. 啥是binary search tree，然后问怎么找least common ancestor
: 3. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 比如：9=4+5 或者9=2+3+4, 但是8就不可以 这个要写code念code
: 第二轮电面
: 1.为啥投amazon（总问）
|
t*********n
发帖数: 1292 | |
m*******i
发帖数: 370 | 6 O(n)
如果可以写成两个数的和，那么这个数可以表示成 2a+1,如果三个数，那么3a，如果四
个数那么4a+2，有规律，奇数个就是K*a,偶数个就是K*a+K/2
我是这么写的code
BST
【在 r**u 的大作中提到】
: 3. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 这个你怎么答的？感觉这个问题不简单啊，brute-force要O（n^2)，back-tracking好
: 像可以改进一些。
: 另外，什么是reverse binary tree? mirror binary tree么？还是给一个ordered BST
: ，构造一棵BST，是原来那棵树的逆序。
: BTW, 祝你尽快拿到offer.
|
s*****i
发帖数: 355 | 7 n = i + (i+1) + ... + (i+k-1)
= k*i + k*(k-1)/2
= k * [i+(k-1)/2]
就变成分解质因数的问题了。最土的办法，O(n)，用congruence of squares应该可以
更快
BST
【在 r**u 的大作中提到】
: 3. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 这个你怎么答的？感觉这个问题不简单啊，brute-force要O（n^2)，back-tracking好
: 像可以改进一些。
: 另外，什么是reverse binary tree? mirror binary tree么？还是给一个ordered BST
: ，构造一棵BST，是原来那棵树的逆序。
: BTW, 祝你尽快拿到offer.
|
s*****i
发帖数: 355 | 8 能详细讲讲你那个reverse bst的题目意思吗，谢谢
【在 m*******i 的大作中提到】
: O(n)
: 如果可以写成两个数的和，那么这个数可以表示成 2a+1,如果三个数，那么3a，如果四
: 个数那么4a+2，有规律，奇数个就是K*a,偶数个就是K*a+K/2
: 我是这么写的code
:
: BST
|
m*******i
发帖数: 370 | 9 一个binary tree，不一定非得binary search tree， 从下往上reverse，比如
A (root)
/ \
B C
/ \ / \
D E F G
/ \ \
H I J
reverse 完了是
H I J (root)
\ \ \
D E G F
\ / \ /
B C
\ /
A
为了trace reversed tree，把H I J得存起来
【在 s*****i 的大作中提到】
: 能详细讲讲你那个reverse bst的题目意思吗，谢谢
|
r**u
发帖数: 1567 | 10 我觉得如果一个数可以写成：k * a, k是大于1的奇数，这个数就可以由连续正整数组
成。
这样，a就是这k个数的均值，那么这k个数就是，
a-k/2, a-k/2+1, a-k/2+2, ..., a, ..., a+k/2,
如果，前面那些变负数的话，就会跟a后面的数cancel掉，剩下的还是连续正整数序列。
比如，22＝11＊2，
－3， －2， －1，0， 1， 2， 3， 4， 5， 6， 7 --> 4， 5， 6， 7 ＝ 22
实际上一个数如果是2^n，才不会有奇数因子，所以只要判断这个数是不是2^n就行了，
可以用bit shift，constant time。
【在 m*******i 的大作中提到】
: O(n)
: 如果可以写成两个数的和，那么这个数可以表示成 2a+1,如果三个数，那么3a，如果四
: 个数那么4a+2，有规律，奇数个就是K*a,偶数个就是K*a+K/2
: 我是这么写的code
:
: BST
|
|
|
s*****i
发帖数: 355 | 11 这个方法好，学习了
列。
【在 r**u 的大作中提到】
: 我觉得如果一个数可以写成：k * a, k是大于1的奇数，这个数就可以由连续正整数组
: 成。
: 这样，a就是这k个数的均值，那么这k个数就是，
: a-k/2, a-k/2+1, a-k/2+2, ..., a, ..., a+k/2,
: 如果，前面那些变负数的话，就会跟a后面的数cancel掉，剩下的还是连续正整数序列。
: 比如，22＝11＊2，
: －3， －2， －1，0， 1， 2， 3， 4， 5， 6， 7 --> 4， 5， 6， 7 ＝ 22
: 实际上一个数如果是2^n，才不会有奇数因子，所以只要判断这个数是不是2^n就行了，
: 可以用bit shift，constant time。
|
m*******i
发帖数: 370 | 12 niu，学习，看半天才看明白
列。
【在 r**u 的大作中提到】
: 我觉得如果一个数可以写成：k * a, k是大于1的奇数，这个数就可以由连续正整数组
: 成。
: 这样，a就是这k个数的均值，那么这k个数就是，
: a-k/2, a-k/2+1, a-k/2+2, ..., a, ..., a+k/2,
: 如果，前面那些变负数的话，就会跟a后面的数cancel掉，剩下的还是连续正整数序列。
: 比如，22＝11＊2，
: －3， －2， －1，0， 1， 2， 3， 4， 5， 6， 7 --> 4， 5， 6， 7 ＝ 22
: 实际上一个数如果是2^n，才不会有奇数因子，所以只要判断这个数是不是2^n就行了，
: 可以用bit shift，constant time。
|
c*******d
发帖数: 255 | 13 3这题，应该可以O(sqrt(n))解决
n = (s+1)+(s+2)+...+(s+k)
= ks + k(k+1)/2
其中 s>=0, k>=2 都是整数
所以 k(k+1)/2 <= n，由此可以得到k的upperbound k0，大约是sqrt(n)的量级
然后做个循环，k=2, ..., k0，判断 [n - k(k+1)/2]/k 是否是整数就可以了
BST
【在 r**u 的大作中提到】
: 3. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 这个你怎么答的？感觉这个问题不简单啊，brute-force要O（n^2)，back-tracking好
: 像可以改进一些。
: 另外，什么是reverse binary tree? mirror binary tree么？还是给一个ordered BST
: ，构造一棵BST，是原来那棵树的逆序。
: BTW, 祝你尽快拿到offer.
|
c*******d
发帖数: 255 | 14 不错，因为k是奇数，看到k/2有点别扭，不过
改成a-(k-1)/2, ..., a+(k-1)/2就行了
这k个数的和刚好是 k*a
如果 a-(k-1)/2是正数，则一共有k>=3个连续正整数
如果 a-(k-1)/2是负数，则[a+(k-1)/2] - [-a+(k-1)/2] = 2a >= 2，
至少有两个连续正整数
列。
【在 r**u 的大作中提到】
: 我觉得如果一个数可以写成：k * a, k是大于1的奇数，这个数就可以由连续正整数组
: 成。
: 这样，a就是这k个数的均值，那么这k个数就是，
: a-k/2, a-k/2+1, a-k/2+2, ..., a, ..., a+k/2,
: 如果，前面那些变负数的话，就会跟a后面的数cancel掉，剩下的还是连续正整数序列。
: 比如，22＝11＊2，
: －3， －2， －1，0， 1， 2， 3， 4， 5， 6， 7 --> 4， 5， 6， 7 ＝ 22
: 实际上一个数如果是2^n，才不会有奇数因子，所以只要判断这个数是不是2^n就行了，
: 可以用bit shift，constant time。
|
w**********8
发帖数: 121 | 15 nice observation
【在 m*******i 的大作中提到】
: O(n)
: 如果可以写成两个数的和，那么这个数可以表示成 2a+1,如果三个数，那么3a，如果四
: 个数那么4a+2，有规律，奇数个就是K*a,偶数个就是K*a+K/2
: 我是这么写的code
:
: BST
|
w**********8
发帖数: 121 | 16 it can be O(logn)
【在 w**********8 的大作中提到】
: nice observation
|
h********0
发帖数: 440 | 17 我觉得LZ还是很牛的
下一个offer马上就要来了
能否问下LZ是PhD还是M.S.?
通讯，
【在 m*******i 的大作中提到】
: 很郁闷的面挂了，不过还是贡献一下能记住的面试题目，希望对以后的xdjm有用
: 记不太全了，能记多少写多少吧。可能题目不是那么难对于CS的来说，我是烂校EE的通讯，
: 实在是EE的通讯opening太少，不好找，无奈投了很多CS的职位。
: 第一轮电面
: 1. 为啥投amazon
: 2. 啥是binary search tree，然后问怎么找least common ancestor
: 3. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 比如：9=4+5 或者9=2+3+4, 但是8就不可以 这个要写code念code
: 第二轮电面
: 1.为啥投amazon（总问）
|
c********t
发帖数: 1756 | |
c**********e
发帖数: 2007 | 19
列。
How to do bit shift? thanks.
【在 r**u 的大作中提到】
: 我觉得如果一个数可以写成：k * a, k是大于1的奇数，这个数就可以由连续正整数组
: 成。
: 这样，a就是这k个数的均值，那么这k个数就是，
: a-k/2, a-k/2+1, a-k/2+2, ..., a, ..., a+k/2,
: 如果，前面那些变负数的话，就会跟a后面的数cancel掉，剩下的还是连续正整数序列。
: 比如，22＝11＊2，
: －3， －2， －1，0， 1， 2， 3， 4， 5， 6， 7 --> 4， 5， 6， 7 ＝ 22
: 实际上一个数如果是2^n，才不会有奇数因子，所以只要判断这个数是不是2^n就行了，
: 可以用bit shift，constant time。
|
c*******d
发帖数: 255 | 20 最后用bit shift，应该是O(log n)时间
列。
【在 r**u 的大作中提到】
: 我觉得如果一个数可以写成：k * a, k是大于1的奇数，这个数就可以由连续正整数组
: 成。
: 这样，a就是这k个数的均值，那么这k个数就是，
: a-k/2, a-k/2+1, a-k/2+2, ..., a, ..., a+k/2,
: 如果，前面那些变负数的话，就会跟a后面的数cancel掉，剩下的还是连续正整数序列。
: 比如，22＝11＊2，
: －3， －2， －1，0， 1， 2， 3， 4， 5， 6， 7 --> 4， 5， 6， 7 ＝ 22
: 实际上一个数如果是2^n，才不会有奇数因子，所以只要判断这个数是不是2^n就行了，
: 可以用bit shift，constant time。
|
|
|
r****o
发帖数: 1950 | 21 判断一个数x是不是2^n看x^(x-1)是不是0就可以了吧。 O(1)。
【在 c*******d 的大作中提到】
: 最后用bit shift，应该是O(log n)时间
:
: 列。
|
c*******d
发帖数: 255 | 22 第2个^是异或吗？那么x=2时，(10)^(01) = (11) = 3
你说的是x&(x-1)吗？
【在 r****o 的大作中提到】
: 判断一个数x是不是2^n看x^(x-1)是不是0就可以了吧。 O(1)。
:
:
|
r****o
发帖数: 1950 | 23 我说错了，应该是x&(x-1)。
【在 c*******d 的大作中提到】
: 第2个^是异或吗？那么x=2时，(10)^(01) = (11) = 3
: 你说的是x&(x-1)吗？
|
c*******d
发帖数: 255 | 24 好像是对的，受教了，多谢！
【在 r****o 的大作中提到】
: 我说错了，应该是x&(x-1)。
|
l******c
发帖数: 2555 | 25 10 = ? + ? +?
列。
【在 r**u 的大作中提到】
: 我觉得如果一个数可以写成：k * a, k是大于1的奇数，这个数就可以由连续正整数组
: 成。
: 这样，a就是这k个数的均值，那么这k个数就是，
: a-k/2, a-k/2+1, a-k/2+2, ..., a, ..., a+k/2,
: 如果，前面那些变负数的话，就会跟a后面的数cancel掉，剩下的还是连续正整数序列。
: 比如，22＝11＊2，
: －3， －2， －1，0， 1， 2， 3， 4， 5， 6， 7 --> 4， 5， 6， 7 ＝ 22
: 实际上一个数如果是2^n，才不会有奇数因子，所以只要判断这个数是不是2^n就行了，
: 可以用bit shift，constant time。
|
c*******d
发帖数: 255 | 26 10 = 1+2+3+4
【在 l******c 的大作中提到】
: 10 = ? + ? +?
:
: 列。
|
P****i
发帖数: 1362 | 27 3. 不是只有2^n不行么，其它的都可以
通讯，
【在 m*******i 的大作中提到】
: 很郁闷的面挂了，不过还是贡献一下能记住的面试题目，希望对以后的xdjm有用
: 记不太全了，能记多少写多少吧。可能题目不是那么难对于CS的来说，我是烂校EE的通讯，
: 实在是EE的通讯opening太少，不好找，无奈投了很多CS的职位。
: 第一轮电面
: 1. 为啥投amazon
: 2. 啥是binary search tree，然后问怎么找least common ancestor
: 3. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 比如：9=4+5 或者9=2+3+4, 但是8就不可以 这个要写code念code
: 第二轮电面
: 1.为啥投amazon（总问）
|
l******t
发帖数: 12659 | |
w********e
发帖数: 15 | 29 17 呢?
列。
【在 r**u 的大作中提到】
: 我觉得如果一个数可以写成：k * a, k是大于1的奇数，这个数就可以由连续正整数组
: 成。
: 这样，a就是这k个数的均值，那么这k个数就是，
: a-k/2, a-k/2+1, a-k/2+2, ..., a, ..., a+k/2,
: 如果，前面那些变负数的话，就会跟a后面的数cancel掉，剩下的还是连续正整数序列。
: 比如，22＝11＊2，
: －3， －2， －1，0， 1， 2， 3， 4， 5， 6， 7 --> 4， 5， 6， 7 ＝ 22
: 实际上一个数如果是2^n，才不会有奇数因子，所以只要判断这个数是不是2^n就行了，
: 可以用bit shift，constant time。
|
c****s
发帖数: 241 | 30 任何奇数都可以写成两个连续的整数和
【在 w********e 的大作中提到】
: 17 呢?
:
: 列。
|
|
|
r**u
发帖数: 1567 | 31 obviously 8+9
【在 w********e 的大作中提到】
: 17 呢?
:
: 列。
|
c*******n
发帖数: 112 | 32 Can anyone have some comments how to design an elevator? I think it is more
difficult than the other issues |
c*****u
发帖数: 107 | |
r*****t
发帖数: 712 | 34 reverse bst的interviewer是个大肚子俄国人吧
通讯，
【在 m*******i 的大作中提到】
: 很郁闷的面挂了，不过还是贡献一下能记住的面试题目，希望对以后的xdjm有用
: 记不太全了，能记多少写多少吧。可能题目不是那么难对于CS的来说，我是烂校EE的通讯，
: 实在是EE的通讯opening太少，不好找，无奈投了很多CS的职位。
: 第一轮电面
: 1. 为啥投amazon
: 2. 啥是binary search tree，然后问怎么找least common ancestor
: 3. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 比如：9=4+5 或者9=2+3+4, 但是8就不可以 这个要写code念code
: 第二轮电面
: 1.为啥投amazon（总问）
|
a**********k
发帖数: 1953 | 35 if ( 0 == (x^(x-1) )) then x is 2^n for some n,
constant time(two cycles).
【在 c*******d 的大作中提到】
: 最后用bit shift，应该是O(log n)时间
:
: 列。
|
a**********k
发帖数: 1953 | 36 if ( 0 == (x^(x-1) )) then x is 2^n for some n,
constant time(two cycles).
【在 c*******d 的大作中提到】
: 最后用bit shift，应该是O(log n)时间
:
: 列。
|
a*****r
发帖数: 3 | 37 请问楼主onsite后多久收到消息的？我上周一去面试，现在还没有收到回复，正着急呢
通讯，
【在 m*******i 的大作中提到】
: 很郁闷的面挂了，不过还是贡献一下能记住的面试题目，希望对以后的xdjm有用
: 记不太全了，能记多少写多少吧。可能题目不是那么难对于CS的来说，我是烂校EE的通讯，
: 实在是EE的通讯opening太少，不好找，无奈投了很多CS的职位。
: 第一轮电面
: 1. 为啥投amazon
: 2. 啥是binary search tree，然后问怎么找least common ancestor
: 3. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 比如：9=4+5 或者9=2+3+4, 但是8就不可以 这个要写code念code
: 第二轮电面
: 1.为啥投amazon（总问）
|
c********t
发帖数: 1756 | 38 人多力量大啊,第三题的结果是constant time! |
