Amazon onsite面经加求祝福 - 未名空间MITBBS历史存档

l*72013-10-14 07:10

1 楼

上周五面的，New grad，所以题目很简单，之前做了一个online assessment之后直接
onsite
一共四轮，每一轮都是一个来自不同组的人面
第一轮类似一个string替换，问题是HTML中class label的名字太长，会影响网络传输
的速度，想出一个办法如何把这么长的name给替换掉。然后是一些简历以及稍微
behavior问题
第二轮先是问了一些java的概念，然后出了一道题，二维平面上有很多圆，圆心都在原
点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
第三轮第一个题是longest palindromic substring，我没敢用manacher's algorithm
，用了一个简单的O(N^2)的算法，之后面试官也没有问下去，直接问了第二题。第二题
是一颗二叉树，哪个路径上的节点最多，路径不是从root到leaf，而是可以从任何地方
开始，可以从child到parent，返回这样最长的路径上的节点数。我写了一个算法面试
官没看懂，于是后面的时间都在给他证明，不过总算在结束之前他看懂了
第四轮问的题目更简单，判断两个string是不是anagram，一棵二叉树是不是bst，给一
个很大的user log，怎么确定unique的user数量，还有一道忘记了，但也是那种一看就
知道怎么做的
可能是RP好，总的来说题目非常简单，HR说一个礼拜就会知道结果，求RP啊求Blessing
啊求显灵啊！！

b*52013-10-14 07:10

2 楼

问哪两个相邻的圆环之间的点最多
how do u know which two circles are neighbors?

g*j2013-10-14 07:10

3 楼

一定可以拿到offer的！
第二题是一颗二叉树，哪个路径上的节点最多，路径不是从root到leaf，而是可以从任
何地方开始，可以从child到parent，返回这样最长的路径上的节点数。
详细说说这个？

algorithm

【在 l********7 的大作中提到】

: 上周五面的，New grad，所以题目很简单，之前做了一个online assessment之后直接
: onsite
: 一共四轮，每一轮都是一个来自不同组的人面
: 第一轮类似一个string替换，问题是HTML中class label的名字太长，会影响网络传输
: 的速度，想出一个办法如何把这么长的name给替换掉。然后是一些简历以及稍微
: behavior问题
: 第二轮先是问了一些java的概念，然后出了一道题，二维平面上有很多圆，圆心都在原
: 点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
: 第三轮第一个题是longest palindromic substring，我没敢用manacher's algorithm
: ，用了一个简单的O(N^2)的算法，之后面试官也没有问下去，直接问了第二题。第二题

g*j2013-10-14 07:10

4 楼

这个就是 sub array max sum吧？

【在 b**********5 的大作中提到】

: 问哪两个相邻的圆环之间的点最多
: how do u know which two circles are neighbors?

b*52013-10-14 07:10

5 楼

这个是国内的微软的人，写过一个“编程之美”里面的题吧。就是largest
distance between two nodes.

【在 g***j 的大作中提到】

: 一定可以拿到offer的！
: 第二题是一颗二叉树，哪个路径上的节点最多，路径不是从root到leaf，而是可以从任
: 何地方开始，可以从child到parent，返回这样最长的路径上的节点数。
: 详细说说这个？
:
: algorithm

b*52013-10-14 07:10

6 楼

你这个array是什么？

【在 g***j 的大作中提到】

: 这个就是 sub array max sum吧？

q*z2013-10-14 07:10

7 楼

还有new grad所以简单这一说吗？

r*n2013-10-14 07:10

8 楼

问的是“相邻”两个圆

【在 g***j 的大作中提到】

: 这个就是 sub array max sum吧？

m*s2013-10-14 07:10

9 楼

Bless

algorithm

【在 l********7 的大作中提到】

: 上周五面的，New grad，所以题目很简单，之前做了一个online assessment之后直接
: onsite
: 一共四轮，每一轮都是一个来自不同组的人面
: 第一轮类似一个string替换，问题是HTML中class label的名字太长，会影响网络传输
: 的速度，想出一个办法如何把这么长的name给替换掉。然后是一些简历以及稍微
: behavior问题
: 第二轮先是问了一些java的概念，然后出了一道题，二维平面上有很多圆，圆心都在原
: 点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
: 第三轮第一个题是longest palindromic substring，我没敢用manacher's algorithm
: ，用了一个简单的O(N^2)的算法，之后面试官也没有问下去，直接问了第二题。第二题

c*e2013-10-14 07:10

10 楼

bless

h*72013-10-14 07:10

11 楼

Bless ~

algorithm

【在 l********7 的大作中提到】

: 上周五面的，New grad，所以题目很简单，之前做了一个online assessment之后直接
: onsite
: 一共四轮，每一轮都是一个来自不同组的人面
: 第一轮类似一个string替换，问题是HTML中class label的名字太长，会影响网络传输
: 的速度，想出一个办法如何把这么长的name给替换掉。然后是一些简历以及稍微
: behavior问题
: 第二轮先是问了一些java的概念，然后出了一道题，二维平面上有很多圆，圆心都在原
: 点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
: 第三轮第一个题是longest palindromic substring，我没敢用manacher's algorithm
: ，用了一个简单的O(N^2)的算法，之后面试官也没有问下去，直接问了第二题。第二题

s*u2013-10-14 07:10

12 楼

二维平面上有很多圆，圆心都在原
点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
难道不是算所有点离原点的距离，然后看落在哪个范围，对应的count就加1，然后最后
找count数组的最大值？跟subarray和最远距离有何关系。。
就是“看落在哪个范围”没想到好办法，只能将圆环按半径排序后，用二分法去找么

c*a2013-10-14 07:10

13 楼

bless

g*e2013-10-14 07:10

14 楼

“我没敢用manacher's algorithm”
虚

l*72013-10-14 07:10

15 楼

告诉你所有圆的半径

【在 b**********5 的大作中提到】

: 问哪两个相邻的圆环之间的点最多
: how do u know which two circles are neighbors?

l*72013-10-14 07:10

16 楼

我不知道，乱说的，但是我感觉比前辈们报出的experienced要简单

【在 q*******z 的大作中提到】

: 还有new grad所以简单这一说吗？

l*72013-10-14 07:10

17 楼

我当时是写的这个方法，不知道有没有什么O(N)的算法

【在 s********u 的大作中提到】

: 二维平面上有很多圆，圆心都在原
: 点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
: 难道不是算所有点离原点的距离，然后看落在哪个范围，对应的count就加1，然后最后
: 找count数组的最大值？跟subarray和最远距离有何关系。。
: 就是“看落在哪个范围”没想到好办法，只能将圆环按半径排序后，用二分法去找么

l*72013-10-14 07:10

18 楼

对，还是太虚了。。。

【在 g*********e 的大作中提到】

: “我没敢用manacher's algorithm”
: 虚

k*62013-10-14 07:10

19 楼

bless!

J*32013-10-14 07:10

20 楼

Bless

s*92013-10-14 07:10

21 楼

第一题没明白怎么做的？

b*52013-10-14 07:10

22 楼

我看好像就是弄个map， integer对应class name, 传的时候，就只要integer就够了

【在 s*********9 的大作中提到】

: 第一题没明白怎么做的？

N*i2013-10-14 07:10

23 楼

bless, 看上去offer跑不了了

a*62013-10-14 07:10

24 楼

有offer了么？？

s*u2013-10-14 07:10

25 楼

其实现在google那个精简网址的，就是这样做的吧？

【在 b**********5 的大作中提到】

: 我看好像就是弄个map， integer对应class name, 传的时候，就只要integer就够了

l*u2013-10-14 07:10

26 楼

bless

algorithm

【在 l********7 的大作中提到】

: 上周五面的，New grad，所以题目很简单，之前做了一个online assessment之后直接
: onsite
: 一共四轮，每一轮都是一个来自不同组的人面
: 第一轮类似一个string替换，问题是HTML中class label的名字太长，会影响网络传输
: 的速度，想出一个办法如何把这么长的name给替换掉。然后是一些简历以及稍微
: behavior问题
: 第二轮先是问了一些java的概念，然后出了一道题，二维平面上有很多圆，圆心都在原
: 点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
: 第三轮第一个题是longest palindromic substring，我没敢用manacher's algorithm
: ，用了一个简单的O(N^2)的算法，之后面试官也没有问下去，直接问了第二题。第二题

l*72013-10-14 07:10

27 楼

上周五面的，New grad，所以题目很简单，之前做了一个online assessment之后直接
onsite
一共四轮，每一轮都是一个来自不同组的人面
第一轮类似一个string替换，问题是HTML中class label的名字太长，会影响网络传输
的速度，想出一个办法如何把这么长的name给替换掉。然后是一些简历以及稍微
behavior问题
第二轮先是问了一些java的概念，然后出了一道题，二维平面上有很多圆，圆心都在原
点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
第三轮第一个题是longest palindromic substring，我没敢用manacher's algorithm
，用了一个简单的O(N^2)的算法，之后面试官也没有问下去，直接问了第二题。第二题
是一颗二叉树，哪个路径上的节点最多，路径不是从root到leaf，而是可以从任何地方
开始，可以从child到parent，返回这样最长的路径上的节点数。我写了一个算法面试
官没看懂，于是后面的时间都在给他证明，不过总算在结束之前他看懂了
第四轮问的题目更简单，判断两个string是不是anagram，一棵二叉树是不是bst，给一
个很大的user log，怎么确定unique的user数量，还有一道忘记了，但也是那种一看就
知道怎么做的
可能是RP好，总的来说题目非常简单，HR说一个礼拜就会知道结果，求RP啊求Blessing
啊求显灵啊！！

b*52013-10-14 07:10

28 楼

问哪两个相邻的圆环之间的点最多
how do u know which two circles are neighbors?

g*j2013-10-14 07:10

29 楼

一定可以拿到offer的！
第二题是一颗二叉树，哪个路径上的节点最多，路径不是从root到leaf，而是可以从任
何地方开始，可以从child到parent，返回这样最长的路径上的节点数。
详细说说这个？

algorithm

【在 l********7 的大作中提到】

: 上周五面的，New grad，所以题目很简单，之前做了一个online assessment之后直接
: onsite
: 一共四轮，每一轮都是一个来自不同组的人面
: 第一轮类似一个string替换，问题是HTML中class label的名字太长，会影响网络传输
: 的速度，想出一个办法如何把这么长的name给替换掉。然后是一些简历以及稍微
: behavior问题
: 第二轮先是问了一些java的概念，然后出了一道题，二维平面上有很多圆，圆心都在原
: 点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
: 第三轮第一个题是longest palindromic substring，我没敢用manacher's algorithm
: ，用了一个简单的O(N^2)的算法，之后面试官也没有问下去，直接问了第二题。第二题

g*j2013-10-14 07:10

30 楼

这个就是 sub array max sum吧？

【在 b**********5 的大作中提到】

: 问哪两个相邻的圆环之间的点最多
: how do u know which two circles are neighbors?

b*52013-10-14 07:10

31 楼

这个是国内的微软的人，写过一个“编程之美”里面的题吧。就是largest
distance between two nodes.

【在 g***j 的大作中提到】

: 一定可以拿到offer的！
: 第二题是一颗二叉树，哪个路径上的节点最多，路径不是从root到leaf，而是可以从任
: 何地方开始，可以从child到parent，返回这样最长的路径上的节点数。
: 详细说说这个？
:
: algorithm

b*52013-10-14 07:10

32 楼

你这个array是什么？

【在 g***j 的大作中提到】

: 这个就是 sub array max sum吧？

q*z2013-10-14 07:10

33 楼

还有new grad所以简单这一说吗？

r*n2013-10-14 07:10

34 楼

问的是“相邻”两个圆

【在 g***j 的大作中提到】

: 这个就是 sub array max sum吧？

m*s2013-10-14 07:10

35 楼

Bless

algorithm

【在 l********7 的大作中提到】

: 上周五面的，New grad，所以题目很简单，之前做了一个online assessment之后直接
: onsite
: 一共四轮，每一轮都是一个来自不同组的人面
: 第一轮类似一个string替换，问题是HTML中class label的名字太长，会影响网络传输
: 的速度，想出一个办法如何把这么长的name给替换掉。然后是一些简历以及稍微
: behavior问题
: 第二轮先是问了一些java的概念，然后出了一道题，二维平面上有很多圆，圆心都在原
: 点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
: 第三轮第一个题是longest palindromic substring，我没敢用manacher's algorithm
: ，用了一个简单的O(N^2)的算法，之后面试官也没有问下去，直接问了第二题。第二题

c*e2013-10-14 07:10

36 楼

bless

h*72013-10-14 07:10

37 楼

Bless ~

algorithm

【在 l********7 的大作中提到】

: 上周五面的，New grad，所以题目很简单，之前做了一个online assessment之后直接
: onsite
: 一共四轮，每一轮都是一个来自不同组的人面
: 第一轮类似一个string替换，问题是HTML中class label的名字太长，会影响网络传输
: 的速度，想出一个办法如何把这么长的name给替换掉。然后是一些简历以及稍微
: behavior问题
: 第二轮先是问了一些java的概念，然后出了一道题，二维平面上有很多圆，圆心都在原
: 点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
: 第三轮第一个题是longest palindromic substring，我没敢用manacher's algorithm
: ，用了一个简单的O(N^2)的算法，之后面试官也没有问下去，直接问了第二题。第二题

s*u2013-10-14 07:10

38 楼

二维平面上有很多圆，圆心都在原
点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
难道不是算所有点离原点的距离，然后看落在哪个范围，对应的count就加1，然后最后
找count数组的最大值？跟subarray和最远距离有何关系。。
就是“看落在哪个范围”没想到好办法，只能将圆环按半径排序后，用二分法去找么

c*a2013-10-14 07:10

39 楼

bless

g*e2013-10-14 07:10

40 楼

“我没敢用manacher's algorithm”
虚

l*72013-10-14 07:10

41 楼

告诉你所有圆的半径

【在 b**********5 的大作中提到】

: 问哪两个相邻的圆环之间的点最多
: how do u know which two circles are neighbors?

l*72013-10-14 07:10

42 楼

我不知道，乱说的，但是我感觉比前辈们报出的experienced要简单

【在 q*******z 的大作中提到】

: 还有new grad所以简单这一说吗？

l*72013-10-14 07:10

43 楼

我当时是写的这个方法，不知道有没有什么O(N)的算法

【在 s********u 的大作中提到】

: 二维平面上有很多圆，圆心都在原
: 点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
: 难道不是算所有点离原点的距离，然后看落在哪个范围，对应的count就加1，然后最后
: 找count数组的最大值？跟subarray和最远距离有何关系。。
: 就是“看落在哪个范围”没想到好办法，只能将圆环按半径排序后，用二分法去找么

l*72013-10-14 07:10

44 楼

对，还是太虚了。。。

【在 g*********e 的大作中提到】

: “我没敢用manacher's algorithm”
: 虚

k*62013-10-14 07:10

45 楼

bless!

J*32013-10-14 07:10

46 楼

Bless

s*92013-10-14 07:10

47 楼

第一题没明白怎么做的？

b*52013-10-14 07:10

48 楼

我看好像就是弄个map， integer对应class name, 传的时候，就只要integer就够了

【在 s*********9 的大作中提到】

: 第一题没明白怎么做的？

N*i2013-10-14 07:10

49 楼

bless, 看上去offer跑不了了

a*62013-10-14 07:10

50 楼

有offer了么？？

s*u2013-10-14 07:10

51 楼

其实现在google那个精简网址的，就是这样做的吧？

【在 b**********5 的大作中提到】

: 我看好像就是弄个map， integer对应class name, 传的时候，就只要integer就够了

l*u2013-10-14 07:10

52 楼

bless

algorithm

【在 l********7 的大作中提到】

: 上周五面的，New grad，所以题目很简单，之前做了一个online assessment之后直接
: onsite
: 一共四轮，每一轮都是一个来自不同组的人面
: 第一轮类似一个string替换，问题是HTML中class label的名字太长，会影响网络传输
: 的速度，想出一个办法如何把这么长的name给替换掉。然后是一些简历以及稍微
: behavior问题
: 第二轮先是问了一些java的概念，然后出了一道题，二维平面上有很多圆，圆心都在原
: 点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
: 第三轮第一个题是longest palindromic substring，我没敢用manacher's algorithm
: ，用了一个简单的O(N^2)的算法，之后面试官也没有问下去，直接问了第二题。第二题

l*32013-10-14 07:10

53 楼

int sum = 0;
public int hightvalue(Node root){
if(root == null)
return 0;
if(root.left == null && root.right == null)
return 1;
int left = hightvalue(root.left);
int right = hightvalue(root.right);
sum = sum < (left+right) ? (left+right) : sum;
int ret = Math.max(left,right) + 1;
return ret;
}
final return sum

【在 g***j 的大作中提到】

: 一定可以拿到offer的！
: 第二题是一颗二叉树，哪个路径上的节点最多，路径不是从root到leaf，而是可以从任
: 何地方开始，可以从child到parent，返回这样最长的路径上的节点数。
: 详细说说这个？
:
: algorithm

l*52013-10-14 07:10

54 楼

bless！

s*t2013-10-14 07:10

55 楼

ret是干嘛的

【在 l**3 的大作中提到】

:
: int sum = 0;
: public int hightvalue(Node root){
: if(root == null)
: return 0;
: if(root.left == null && root.right == null)
: return 1;
: int left = hightvalue(root.left);
: int right = hightvalue(root.right);
: sum = sum < (left+right) ? (left+right) : sum;

b*f2013-10-14 07:10

56 楼

Bless

b*f2013-10-14 07:10

57 楼

请问一下，第一题string替换是什么意思，在HTML中搜这个string?

R*d2013-10-14 07:10

58 楼

祝福

algorithm

【在 l********7 的大作中提到】

: 上周五面的，New grad，所以题目很简单，之前做了一个online assessment之后直接
: onsite
: 一共四轮，每一轮都是一个来自不同组的人面
: 第一轮类似一个string替换，问题是HTML中class label的名字太长，会影响网络传输
: 的速度，想出一个办法如何把这么长的name给替换掉。然后是一些简历以及稍微
: behavior问题
: 第二轮先是问了一些java的概念，然后出了一道题，二维平面上有很多圆，圆心都在原
: 点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
: 第三轮第一个题是longest palindromic substring，我没敢用manacher's algorithm
: ，用了一个简单的O(N^2)的算法，之后面试官也没有问下去，直接问了第二题。第二题

W*i2013-10-14 07:10

59 楼

big bless

B*42013-10-14 07:10

60 楼

我是这么想的：
N个同心圆，N个半径，n-1 个区间建立数组a[n-1]，每个元素有上下限和count。
M个点，对于每一个点，计算它到原点的距离，一个个插入到a[n-1],同时更新count和
max插完了，max也找到了。
O（NxM).

【在 s********u 的大作中提到】

: 二维平面上有很多圆，圆心都在原
: 点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
: 难道不是算所有点离原点的距离，然后看落在哪个范围，对应的count就加1，然后最后
: 找count数组的最大值？跟subarray和最远距离有何关系。。
: 就是“看落在哪个范围”没想到好办法，只能将圆环按半径排序后，用二分法去找么