i*****e
发帖数: 113 | 1 VOD组，不过应该没有什么参考意义，因为题目太简单了。不知道能不能进入第二面。
怎么说也不要第一面就把我拍死吧
美白
- why amazon
- your experience/strength/etc
- what is BST, the complexity in best case and worst case, how to know the
BST is in worst case
- write code: recursively visit a binary tree
- how to find a key in BST
- write code: given an array, find the second maximum value
- do you have any questions
奇怪的是一点C++的东西都没问我
如果失败那一定是英语表达的问题，在念代码的时候，我还老改，不知道他明白没有 |
P*******b
发帖数: 1001 | 2 bless
【在 i*****e 的大作中提到】
: VOD组，不过应该没有什么参考意义，因为题目太简单了。不知道能不能进入第二面。
: 怎么说也不要第一面就把我拍死吧
: 美白
: - why amazon
: - your experience/strength/etc
: - what is BST, the complexity in best case and worst case, how to know the
: BST is in worst case
: - write code: recursively visit a binary tree
: - how to find a key in BST
: - write code: given an array, find the second maximum value
|
j**l
发帖数: 2911 | 3 找第二大那个虽然方法都是O(n),但比较次数还可以改进。
一般方法是先比较n-1次找到最大，然后比较n-2次找到次大，总共比较2n-3次
如果两个一组先比较，可以减少总的比较次数。 |
s*********t
发帖数: 1663 | 4 高人
【在 j**l 的大作中提到】
: 找第二大那个虽然方法都是O(n),但比较次数还可以改进。
: 一般方法是先比较n-1次找到最大，然后比较n-2次找到次大，总共比较2n-3次
: 如果两个一组先比较，可以减少总的比较次数。
|
i*****e
发帖数: 113 | 5 用的就是这个方法，步长为2递增
下面就是我给他念的代码，略微有点不同，比如static/inline的修饰什么的，以及有
符号数和无符号数比较，当时没注意到
static inline void elect(int& max1, int& max2, int num)
{
if (num > max1) {
max1 = num;
} else if (num > max2) {
max2 = num;
}
}
int find_2nd_max(const int* array, size_t len)
{
int max1 = MININUM_INTEGER, max2 = MINUM_INTEGER;
int tmp;
for (unsigned i = 0; i < len; i += 2) {
tmp = std::max(a[i], a[i+1]);
elect(max1, max2, tmp);
}
if ((len & 0x01) != 0) {
【在 j**l 的大作中提到】
: 找第二大那个虽然方法都是O(n),但比较次数还可以改进。
: 一般方法是先比较n-1次找到最大，然后比较n-2次找到次大，总共比较2n-3次
: 如果两个一组先比较，可以减少总的比较次数。
|
f*********5
发帖数: 576 | 6 问题是这个题的最少比较次数是N+log2N-2
【在 s*********t 的大作中提到】
: 高人
|
i*****e
发帖数: 113 | |
i*****e
发帖数: 113 | 8 哪样空间复杂度就上去了
【在 f*********5 的大作中提到】
: 问题是这个题的最少比较次数是N+log2N-2
|
j**l
发帖数: 2911 | 9 好像用清华老严版本数据结构的那个锦标赛排序的树图来解释的。这种比赛假定没有爆
冷，实力高的一定获胜。亚军可能决赛输给冠军，也可能运气不好，第一轮就输给冠军
，反正亚军只可能在logN的树高上，某轮次输给冠军的选手中产生。
假如N是2的整数次方
N个选手产生最后的冠军比较N-1次
败给冠军的logN个选手中产生最后的亚军再比较logN-1次
总共N + logN - 2次
N为一般整数时候思路类似，需要取整操作
【在 i*****e 的大作中提到】
: N+log2N-2
: 这个怎么整
|
s*******t
发帖数: 248 | 10 Thanks for sharing.
It seems to me that your code is not right.
Suppose the array is monotonic increasing, I think max2 will remain as the I
NT_MIN, only max1 updates each time you call elect().
Please correct me if I am wrong.
【在 i*****e 的大作中提到】
: 用的就是这个方法，步长为2递增
: 下面就是我给他念的代码，略微有点不同，比如static/inline的修饰什么的，以及有
: 符号数和无符号数比较，当时没注意到
: static inline void elect(int& max1, int& max2, int num)
: {
: if (num > max1) {
: max1 = num;
: } else if (num > max2) {
: max2 = num;
: }
|
i*****e
发帖数: 113 | 11 Thanks a lot! The function elect() has problem, it should update both max1 and max2.
BTW, I don't know you guys how to process the phone silent when writing code
on your paper. I always rush to write it out and read it to interviewer,
just being afraid of that the phone keep silent. And in case the interviewer
think: "hum, this guy takes too long time to write the simple function". It
takes me around 2 minutes to finish this function. After I finished a
skeleton, I began reading it and changed t
【在 s*******t 的大作中提到】
: Thanks for sharing.
: It seems to me that your code is not right.
: Suppose the array is monotonic increasing, I think max2 will remain as the I
: NT_MIN, only max1 updates each time you call elect().
: Please correct me if I am wrong.
|
j**l
发帖数: 2911 | 12 其实有的Amazon面试官也会用类似Google Doc之类的在线共享文档的，有的还是要你电
话里读code |
i*****e
发帖数: 113 | 13 logN的那个树，要存起来的话，也要空间的
【在 j**l 的大作中提到】
: 好像用清华老严版本数据结构的那个锦标赛排序的树图来解释的。这种比赛假定没有爆
: 冷，实力高的一定获胜。亚军可能决赛输给冠军，也可能运气不好，第一轮就输给冠军
: ，反正亚军只可能在logN的树高上，某轮次输给冠军的选手中产生。
: 假如N是2的整数次方
: N个选手产生最后的冠军比较N-1次
: 败给冠军的logN个选手中产生最后的亚军再比较logN-1次
: 总共N + logN - 2次
: N为一般整数时候思路类似，需要取整操作
|
