l*****a
发帖数: 559 | 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***m
发帖数: 5987 | 2 第三题比较简单。第一题大家讨论的结果应该是构建有向图然后topsort？ |
p*****2
发帖数: 21240 | 3
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])
{
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********9
发帖数: 44 | 4 第一题给的例子不明确呀。
只能确定abceg
不能确定 d f 的准确位置呀。 |
l*****a
发帖数: 559 | 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*****2
发帖数: 21240 | 6
嗯。以前做过一次BFS的。
【在 l*****a 的大作中提到】
: 二爷这次没走dfs路线了。
|
h****n
发帖数: 1093 | 7 第三题不简单吧 我感觉是online jugde里面写起来最罗嗦的一道题了
第三题比较简单。第一题大家讨论的结果应该是构建有向图然后topsort？
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 b***m 的大作中提到】
: 第三题比较简单。第一题大家讨论的结果应该是构建有向图然后topsort？
|
h****n
发帖数: 1093 | 8 第一题说的sorted word是指单词里面的letter是sorted还是说单词之间的排序是
sorted的如果是后者则我们需要更多的排序信息
嗯。以前做过一次BFS的。
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 p*****2 的大作中提到】
:
: 嗯。以前做过一次BFS的。
|
l***i
发帖数: 1309 | 9 每次看大牛贴题就想，如果我onsite是这些题就直接吃个lunch回家算了 |
d********t
发帖数: 51 | 10 第一道没有看懂，
为什么不能用
bool array[26] hashtable来做呀? |
|
|
b***m
发帖数: 5987 | 11
我觉得简单的原因是我在国内的时候，design和implement了一整套Windows UI系统，
其中就包括这套文字对齐系统。不仅要做文字对齐，甚至还有图片。;-)
【在 h****n 的大作中提到】
: 第三题不简单吧 我感觉是online jugde里面写起来最罗嗦的一道题了
:
: 第三题比较简单。第一题大家讨论的结果应该是构建有向图然后topsort？
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
h****n
发帖数: 1093 | 12 了解。。放在面试里写起来比较罗嗦，要考虑到各种corner case
不过貌似这道题只需要做一行的justification就行了
leetcode上需要做一个段落的，那个写起来特罗嗦，我感觉给40分钟写bug free基本不
太可能，除非之前练过很多遍
【在 b***m 的大作中提到】
:
: 我觉得简单的原因是我在国内的时候，design和implement了一整套Windows UI系统，
: 其中就包括这套文字对齐系统。不仅要做文字对齐，甚至还有图片。;-)
|
b***m
发帖数: 5987 | 13
嗯，做一行的就足够了。面试考多行纯属吃饱了撑的。
【在 h****n 的大作中提到】
: 了解。。放在面试里写起来比较罗嗦，要考虑到各种corner case
: 不过貌似这道题只需要做一行的justification就行了
: leetcode上需要做一个段落的，那个写起来特罗嗦，我感觉给40分钟写bug free基本不
: 太可能，除非之前练过很多遍
|
s**********y
发帖数: 33 | 14 这个是什么难度的题？给SDE的么？要是我碰到了估计就只能吃完lunch回家了......
cceg
software
about
【在 l*****a 的大作中提到】
: 二爷这次没走dfs路线了。
|
l****o
发帖数: 315 | 15 不一定是正常字母顺序，他给的是一个特例。其实很简单，构个图，不断把每个字母指
向关系放进图。最后toposort一下。
【在 d********t 的大作中提到】
: 第一道没有看懂，
: 为什么不能用
: bool array[26] hashtable来做呀?
|
