三道 Amazon Onsite Coding 题 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

三道 Amazon Onsite Coding 题 (转载)

三道 Amazon Onsite Coding 题 (转载)# JobHunting - 待字闺中

l*a2012-11-26 08:11

1 楼

【以下文字转载自 Programming 讨论区】
发信人: welch (welch), 信区: Programming
标题: 三道 Amazon Onsite Coding 题
发信站: BBS 未名空间站 (Tue Aug 24 01:54:09 2010, 美东)
1.Given ordered/sorted words with some unknown alphabet ordering, find and
return the ordered alphabets, for example, given {“abce”, “bbdf”, “cceg
”} your class/function will return: {a, b, c, d, e, f, g}
2.Design an API class for some Maze algorithms – imagine that the software
team has implemented Maze algorithms, the hardware team needs to call the
API that you designed to run a single robot in Maze (no need to worry about
multi-thread);
After you coded API, then code a simulation to test API with Maze algorithms.
写完了code都一直没明白面试官想考什么? 这题大伙给说说看
3.Design and code in C++ to justify a line of text string: (1) left, (2)
right and (3) full justified.

b*m2012-11-26 08:11

2 楼

第三题比较简单。第一题大家讨论的结果应该是构建有向图然后topsort？

p*22012-11-26 08:11

3 楼

ArrayList topsort(char[][] input)
{
ArrayList res=new ArrayList();
HashMap hm=new HashMap();

for(int i=0;ifor(int j=0;j{
if(input[i][j]!=input[i][j+1])
{
if(!hm.containsKey(input[i][j]))
hm.put(input[i][j], new Letter(input[i][j]));

if(!hm.containsKey(input[i][j+1]))
hm.put(input[i][j+1], new Letter(input[i][j+1]));

hm.get(input[i][j]).out.add(hm.get(input[i][j+1]));
hm.get(input[i][j+1]).in.add(hm.get(input[i][j]));
}
}

Queue queue=new LinkedList();
for(Letter l : hm.values())
{
if(l.in.isEmpty())
queue.add(l);
}

while(!queue.isEmpty())
{
Letter curr=queue.poll();
res.add(curr.val);

for(Letter l : curr.out )
{
l.in.remove(curr);
if(l.in.isEmpty())
queue.add(l);
}
}
return res;
}

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

: 第三题比较简单。第一题大家讨论的结果应该是构建有向图然后topsort？

F*92012-11-26 08:11

4 楼

第一题给的例子不明确呀。
只能确定abceg
不能确定 d f 的准确位置呀。

l*a2012-11-26 08:11

5 楼

二爷这次没走dfs路线了。

【在 p*****2 的大作中提到】

:
: ArrayList topsort(char[][] input)
: {
: ArrayList res=new ArrayList();
: HashMap hm=new HashMap();
:
: for(int i=0;i: for(int j=0;j: {
: if(input[i][j]!=input[i][j+1])

p*22012-11-26 08:11

6 楼

嗯。以前做过一次BFS的。

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

: 二爷这次没走dfs路线了。

h*n2012-11-26 08:11

7 楼

第三题不简单吧我感觉是online jugde里面写起来最罗嗦的一道题了

第三题比较简单。第一题大家讨论的结果应该是构建有向图然后topsort？
★ Sent from iPhone App: iReader Mitbbs Lite 7.56

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

: 第三题比较简单。第一题大家讨论的结果应该是构建有向图然后topsort？

h*n2012-11-26 08:11

8 楼

第一题说的sorted word是指单词里面的letter是sorted还是说单词之间的排序是
sorted的如果是后者则我们需要更多的排序信息

嗯。以前做过一次BFS的。
★ Sent from iPhone App: iReader Mitbbs Lite 7.56

【在 p*****2 的大作中提到】

:
: 嗯。以前做过一次BFS的。