w***h
发帖数: 415 | 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 | f*k
发帖数: 95 | | M********5
发帖数: 715 | | M***t
发帖数: 1636 | 4 分散对齐
【在 M********5 的大作中提到】
: 第三题不太明白什么是justify
| w***h
发帖数: 415 | 5 说了限制处理一行文本字符串, 不考虑前后断行. 就是给定一行文本字符串<=行宽.
【在 f*k 的大作中提到】
: 3有啥限制没，不然很复杂的啊
| y*********e
发帖数: 518 | 6 貌似是输出不重复的字符？那么用一个bitmap就可以了，遍历每一个word的每一个单词
，看到一个字符，就set对应的bit即可。最后输出只需要遍历bitmap即可。
伪代码：
for i in [0, 128)
clear_bit(i)
for each word
for each char i
set_bit(i)
for i in [0, 128)
if check_bit(i)
print(i)
不过没有用到ordered words这个性质。感觉题目是否缺少了什么？ | y*********e
发帖数: 518 | 7 这个题目我的理解是，已经有一个robot了，它在你的Maze里面。Robot需要call你给定
的API来做行为判断。
所以，Maze的API应该这么来：
bool canGoUp();
bool canGoLeft();
bool canGoRight();
bool canGoDown();
bool inMaze();
这个是2维的，而且只能朝着4个方向走。复杂点，可以朝多个方向走：
bool canGo(Direction dir);
Direction 是一个enum，定义robot可以走的方向。
最后，要是我面的话，还可以来个好玩的：
bool isMonsterAhead(); // :P | y*********e
发帖数: 518 | 8 假设字符都是等宽的。输入是字符串 string 以及行宽 width。
let len = string.length
left就容易了，在输入的字符串后面贴 width - len 个空白。若是len > width ? 那
么直接返回吧。
right就是在输入的字符串前面贴 width - len 个空白。
full justified有点麻烦了，算算有多少个word，然后平均的插入 width - len 个空
白。 | h**k
发帖数: 3368 | 9 题目是要根据排好序的字符串重构特定的字母顺序。
比如输入是
{“abce”, “bbdf”, “cceg”}
我们得到下列关系
a -> b -> c -> e 第一个字符串
b -> d -> f 第二个
c -> e -> g 第三个
组合起来，就是一个有向图，而且对某些输入可能会出现下面这样的情况：
a-> b -> d
a-> c -> d
我们不知道 b 和 c的关系，不知道这种情况面试官要求如何输出。
对于构建好的地有向图，我们可以发现一些字母，它是只有outedge 没有inedge，输出
它们；然后生成从它们到其他字母的最大路径，按照这个最大路径依次输出其他字母。
【在 y*********e 的大作中提到】
: 貌似是输出不重复的字符？那么用一个bitmap就可以了，遍历每一个word的每一个单词
: ，看到一个字符，就set对应的bit即可。最后输出只需要遍历bitmap即可。
: 伪代码：
: for i in [0, 128)
: clear_bit(i)
: for each word
: for each char i
: set_bit(i)
: for i in [0, 128)
: if check_bit(i)
| g******d
发帖数: 511 | 10 第一道应该是老题了,原题是:给定一个足够多的按字典排序的words set.learn
alphabet order.
对每个学到的rule,加入一个数据结构.例如:
a->b, e, f, z, ....
b->d, g, ...
...
z->
z 为空,即为尾.然后再将a->y中所有的Z去掉,再找空的char.数据结构的要求O(1)时间
去掉一个char,最快时间找到为空的char.
第二题也在本版见过.好像是靠hardware与sofware的协调问题, API的flexibility.
第三道没有搞百,给定string X (size sx) and Y (size sy),将Y从X的0, (sx-sy)/2,
sx-sy处开始插入? | j*******a
发帖数: 61 | 11 I think Maze is an interface design. Imagine a blind person and a
guiding dog. The blind is like the Maze algorithm and the guiding dog is
like the robot. The guiding dog provides current road situation and asks
for the instruction of next step. The blind asks the road situation and
provides the instruction.
Regards the API for the dog below are the most basic interface that I
can think of:
IsLeftOpen, IsRightOpen (queried by the blind)
ShouldTurnLeft, ShouldTurnRight, ShouldGoBack (queried by t
【在 w***h 的大作中提到】
: 说了限制处理一行文本字符串, 不考虑前后断行. 就是给定一行文本字符串<=行宽.
| w***h
发帖数: 415 | 12 I believe it's generally right, as said by other ppl above.
But, that's it! Define whatever the API is and write the simulation logic.
Not really sure what it means for flexibility, blah blah. It's just straight
logic without much to say. Other than that, it's all "virtually"
interesting - just my 2 cents, I may be wrong, :)
【在 j*******a 的大作中提到】
: I think Maze is an interface design. Imagine a blind person and a
: guiding dog. The blind is like the Maze algorithm and the guiding dog is
: like the robot. The guiding dog provides current road situation and asks
: for the instruction of next step. The blind asks the road situation and
: provides the instruction.
: Regards the API for the dog below are the most basic interface that I
: can think of:
: IsLeftOpen, IsRightOpen (queried by the blind)
: ShouldTurnLeft, ShouldTurnRight, ShouldGoBack (queried by t
| h**6
发帖数: 4160 | 13 我终于知道了，我得google onsite就fail在第一题上。
每相邻两项能得到一条rule，全部rule学会之后，需要根据传递性扩展rule生成一个
rule matrix
生成这个rule matrix有两个方法：
1.是用BFS或者DFS进行图的遍历
2.使用Floyd-Warshall算法。当时我在面试官面前Warshall说了半天，结果写出来成了
这样：
for(int i=0; i
for(int j=0; j
for(int k=0; k
if(rules[i][k] && rules[k][j])
rules[i][j] = 1;
看出错在哪里了吗，k应该在外层循环，结果我把他写到最内层去了。悔啊，没想到栽
这上面了。 |
|
