c******5
发帖数: 84 | 1 一面：
不难，一个挺nice的印度女生给面的，斐波那契数列，还有海量数据中找出现频率最高
的十个数据
二面：
主要就是OOD，经典电梯问题
三面：
给一个二维String数组，里面可能是表达式，也可能包含对数组其它元素的引用，要求
输出一个对应的int二位数组，如果是可以算出值（比如在String数组中对应的是表达
式），之间输出值到这个int数组，如果是circular reference的话，标记出来，我是
用图做的。
上周五三面，今天就知道挂了，估计是三面没面好。。。 还有OOD总感觉说得不太好
明天电面T，求Bless~ |
c******a
发帖数: 115 | 2 bless
【在 c******5 的大作中提到】
: 一面：
: 不难，一个挺nice的印度女生给面的，斐波那契数列，还有海量数据中找出现频率最高
: 的十个数据
: 二面：
: 主要就是OOD，经典电梯问题
: 三面：
: 给一个二维String数组，里面可能是表达式，也可能包含对数组其它元素的引用，要求
: 输出一个对应的int二位数组，如果是可以算出值（比如在String数组中对应的是表达
: 式），之间输出值到这个int数组，如果是circular reference的话，标记出来，我是
: 用图做的。
|
e****e
发帖数: 418 | 3 Bless.
三面不是常规题.
我能想出来可能的解法是用多个Set记录多个circular reference。
The type of element in set is Pair
Class Pair{
int i; // i is the x axis of 2 dimensional array index.
int j; // j is the y axis of 2 dimensional array index.
}
When encounter a reference, trace the reference to the end(The end could be
an expression or reference already added into set.) by adding Pair(x, y)
into set. If the reference already appears in the set, it means a cycle is
found.
There may be multiple cycles. So More than one set might be needed. |
c********t
发帖数: 5706 | 4 bless!
三面的题很难。Amazon电面用什么写程序？google doc or collabedit?
【在 c******5 的大作中提到】
: 一面：
: 不难，一个挺nice的印度女生给面的，斐波那契数列，还有海量数据中找出现频率最高
: 的十个数据
: 二面：
: 主要就是OOD，经典电梯问题
: 三面：
: 给一个二维String数组，里面可能是表达式，也可能包含对数组其它元素的引用，要求
: 输出一个对应的int二位数组，如果是可以算出值（比如在String数组中对应的是表达
: 式），之间输出值到这个int数组，如果是circular reference的话，标记出来，我是
: 用图做的。
|
e***n
发帖数: 68 | 5 我目前为止2面都没有任何云文档，都是说的
今天刚刚2面，2题很简单2sum 和isbst
【在 c********t 的大作中提到】
: bless!
: 三面的题很难。Amazon电面用什么写程序？google doc or collabedit?
|
c********t
发帖数: 5706 | 6 第三题，如果String数组里是reference，怎么处理int二位数组的对应位置？
【在 c******5 的大作中提到】
: 一面：
: 不难，一个挺nice的印度女生给面的，斐波那契数列，还有海量数据中找出现频率最高
: 的十个数据
: 二面：
: 主要就是OOD，经典电梯问题
: 三面：
: 给一个二维String数组，里面可能是表达式，也可能包含对数组其它元素的引用，要求
: 输出一个对应的int二位数组，如果是可以算出值（比如在String数组中对应的是表达
: 式），之间输出值到这个int数组，如果是circular reference的话，标记出来，我是
: 用图做的。
|
c********t
发帖数: 5706 | 7 好像不太行
比如 1,2,3,4,2 这样的循环，结果应该是2,3,4 你用set怎么能把1去掉呢？
我觉得用 linkedlist + hashmap比较好，trace the references into linkedlist,
当current reference已经在hashmap里，把current之前的node都从linkedlist里删掉
就是结果。
不过怎么能去掉duplicate呢？例子中的2,3,4 和 3,4,2是重复的。我觉得还要一个2维
visted flag数组，凡是visited的string就不处理了。
当然最终结果也是多个，返回ArrayList>
be
【在 e****e 的大作中提到】
: Bless.
: 三面不是常规题.
: 我能想出来可能的解法是用多个Set记录多个circular reference。
: The type of element in set is Pair
: Class Pair{
: int i; // i is the x axis of 2 dimensional array index.
: int j; // j is the y axis of 2 dimensional array index.
: }
: When encounter a reference, trace the reference to the end(The end could be
: an expression or reference already added into set.) by adding Pair(x, y)
|
c******5
发帖数: 84 | 8 前两轮都是collabedit 第三轮本来面试我的是一个美国人 本来他打算让我用电话说
可我听不太明白他的题目意思 我申请用了collabedit
【在 c********t 的大作中提到】
: bless!
: 三面的题很难。Amazon电面用什么写程序？google doc or collabedit?
|
c******5
发帖数: 84 | 9 面试的人说可以想成一个excel文件 比如A3这个cell里存的是"1+2+B4+C5"，这样还是
对应int二维数组里面的A3，我想到的方法是先计算这些没有reference的cell，然后比
如A3里面有B4和C5，先找出有计算结果的cell，替换，对剩余部分建个图，比如A3指向
B4，A3指向C5,然后找出所有circle涵盖的节点（不一定要在Circle中)，这题挺坑爹的
，三面就这一个题，现在A家咋这么难呢？估计还是我太菜了。。。
【在 c********t 的大作中提到】
: 第三题，如果String数组里是reference，怎么处理int二位数组的对应位置？
|
j******2
发帖数: 362 | 10 谢谢面筋。不过楼主可否少些typo?
btw bless ur T~
【在 c******5 的大作中提到】
: 一面：
: 不难，一个挺nice的印度女生给面的，斐波那契数列，还有海量数据中找出现频率最高
: 的十个数据
: 二面：
: 主要就是OOD，经典电梯问题
: 三面：
: 给一个二维String数组，里面可能是表达式，也可能包含对数组其它元素的引用，要求
: 输出一个对应的int二位数组，如果是可以算出值（比如在String数组中对应的是表达
: 式），之间输出值到这个int数组，如果是circular reference的话，标记出来，我是
: 用图做的。
|
|
|
c********t
发帖数: 5706 | 11 哦，明白了，可是你要替换多少遍？（如A3里面有B4和C5，先找出有计算结果的cell，
替换)
比如你的例子 如果C5里存的是1+B4, 你要替换两遍才能得到A3, 当然可以替换很多遍
直到无可替换，但感觉应该有优化。
确实挺难的题。可能是因为你去年面过吧。
等高人。
2爷，棋爷，www，快来做难题了。
【在 c******5 的大作中提到】
: 面试的人说可以想成一个excel文件 比如A3这个cell里存的是"1+2+B4+C5"，这样还是
: 对应int二维数组里面的A3，我想到的方法是先计算这些没有reference的cell，然后比
: 如A3里面有B4和C5，先找出有计算结果的cell，替换，对剩余部分建个图，比如A3指向
: B4，A3指向C5,然后找出所有circle涵盖的节点（不一定要在Circle中)，这题挺坑爹的
: ，三面就这一个题，现在A家咋这么难呢？估计还是我太菜了。。。
|
c********t
发帖数: 5706 | 12 面筋 should be 面经。注意少些typo. :D ~run
【在 j******2 的大作中提到】
: 谢谢面筋。不过楼主可否少些typo?
: btw bless ur T~
|
g*****e
发帖数: 282 | 13 第三题要拓扑排序
bless
【在 c******a 的大作中提到】
: bless
|
c******5
发帖数: 84 | 14 呵呵，发得比较匆忙，下次我会注意的，谢谢你的提醒^_^
【在 j******2 的大作中提到】
: 谢谢面筋。不过楼主可否少些typo?
: btw bless ur T~
|
p*****2
发帖数: 21240 | |
h****n
发帖数: 1093 | 16 第三个题要求写代码吗？
如果是的话估计就是要故意为难你吧
首先要把每个cell里面涉及到单元格所对应的值evaluate出来
然后表达式也要evaluate出来吧，又要转postfix又要用栈的 |
c******5
发帖数: 84 | 17
【在 h****n 的大作中提到】
: 第三个题要求写代码吗？
: 如果是的话估计就是要故意为难你吧
: 首先要把每个cell里面涉及到单元格所对应的值evaluate出来
: 然后表达式也要evaluate出来吧，又要转postfix又要用栈的
|
c******5
发帖数: 84 | 18 No, pseudo code is enough...
【在 h****n 的大作中提到】
: 第三个题要求写代码吗？
: 如果是的话估计就是要故意为难你吧
: 首先要把每个cell里面涉及到单元格所对应的值evaluate出来
: 然后表达式也要evaluate出来吧，又要转postfix又要用栈的
|
c********t
发帖数: 5706 | 19 zkss
【在 g*****e 的大作中提到】
: 第三题要拓扑排序
:
: bless
|
c********t
发帖数: 5706 | 20 能给个psuedo codes吗？
【在 h****n 的大作中提到】
: 第三个题要求写代码吗？
: 如果是的话估计就是要故意为难你吧
: 首先要把每个cell里面涉及到单元格所对应的值evaluate出来
: 然后表达式也要evaluate出来吧，又要转postfix又要用栈的
|
|
|
S******1
发帖数: 269 | 21 第三道好像是quantcast家的原题，他们家给两小时编这个程序。。。。Amazon让你一
小时电话答出来，完全是难为你。太背了。
【在 c******5 的大作中提到】
: 一面：
: 不难，一个挺nice的印度女生给面的，斐波那契数列，还有海量数据中找出现频率最高
: 的十个数据
: 二面：
: 主要就是OOD，经典电梯问题
: 三面：
: 给一个二维String数组，里面可能是表达式，也可能包含对数组其它元素的引用，要求
: 输出一个对应的int二位数组，如果是可以算出值（比如在String数组中对应的是表达
: 式），之间输出值到这个int数组，如果是circular reference的话，标记出来，我是
: 用图做的。
|
p*****2
发帖数: 21240 | 22
其实只是伪代码的话也不算过分。
【在 S******1 的大作中提到】
: 第三道好像是quantcast家的原题，他们家给两小时编这个程序。。。。Amazon让你一
: 小时电话答出来，完全是难为你。太背了。
|
c********t
发帖数: 5706 | 23 求伪代码
【在 p*****2 的大作中提到】
:
: 其实只是伪代码的话也不算过分。
|
p*****2
发帖数: 21240 | 24
其实就是BFS。我第一次见这种东西还不知道有topo sort这个东西，用BFS就可以做出
来。你想像。
【在 c********t 的大作中提到】
: 求伪代码
|
S********g
发帖数: 45 | 25 二爷 不理解为什么BFS 我觉得是DFS啊。。
比如 A depends on B 然后B on C， C on D 在DFS的时候 肯定要先算出D 然后 把 C
的结果替换成 数字，然后依次 B A
但是DFS不是很容易解决circular link，我想用个HashSet visited 每次记录访问过的
。。。
TOPOsort我也能理解 就是保证能够先计算没有dependence的 而且是否有circular 一
目了然
请指教
【在 p*****2 的大作中提到】
:
: 其实就是BFS。我第一次见这种东西还不知道有topo sort这个东西，用BFS就可以做出
: 来。你想像。
|
S********g
发帖数: 45 | 26 我乱写的puedo code用dfs 大家请指教
String[] input;
void findValues() {
for(String s: input) {
if(s.notEvaluatedYet()) // 之前没有被访问过 里面还有对其他string的
reference
{
if(!dfs(s,new HashSet())) {
there is a circular ref
}
}
}
}
boolean dfs(String s, HashSet visited) {
if(visited.contains(s) && s.notEvalated()) {
// 之前已经访问过这个s，并且他的reference还没有被solve 就说明这里有
circular reference
return false;
}
visited.add(s) ;
// s 没有reference 或者 所有的refrence已经solve 可以计算对应的int
if(s.hasNoReference()) {
s = cal(s);
update input to reflect the change too;
return true;
}
String[] allReferences = findAllDependencies(s);
for(String ref:allReferences) {
dfs(ref); // ref gets updates in this call..
replace ref with its value in s;
}
return true;
} |
