w***h
发帖数: 415 | 1 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 |
U********d
发帖数: 577 | 2 栈和递归？如果硬件送过来的数据是实时的话，比如探测到一堵墙啥的，blah blah。 |
a*******s
发帖数: 79 | 3 第一题可以用hash,只要26个表元就行，复杂度O(n)
第二题就是个图的遍历算法，DFS,stack实现比较简单，主要就是看看你API的定义能力
第三题是不是考格式调整？左对齐，右对齐和左右都对齐？我觉得这个不是太难，就是
计算子串在绘图空间里面的实际长度，注意切分字串时考虑远东语言等情况。 |
I******c
发帖数: 163 | 4 第一题怎么用hash解？能否详细解释一下？
我的想法是遍列一次所有的字符串，比较相邻的字符串。每一次比较可以得到一个表示
两个字符前后关系的信息。然后把这些信息合并起来。（我使用静态链表）
时间复杂度也是O(n). |
g**e
发帖数: 6127 | 5 hash 26个字母，value=0。按单词字母顺序put，value++
完了以后按顺序输出所有value!=0的
你的方法为什么是O(n)，我怎么觉得是O(n^2)
【在 I******c 的大作中提到】
: 第一题怎么用hash解？能否详细解释一下？
: 我的想法是遍列一次所有的字符串，比较相邻的字符串。每一次比较可以得到一个表示
: 两个字符前后关系的信息。然后把这些信息合并起来。（我使用静态链表）
: 时间复杂度也是O(n).
|
I******c
发帖数: 163 | 6 我的办法只需要遍历一遍，所以是O(n)
例如有三个字符串 bca bab abc aca
静态链表是
0 0 0 向前指针
0 0 0 向后指针
a b c
1 2 3 索引
首先比较bca bab, 可以得到 c>a
-1 0 1
3 0 －1
a b c head=3
然后比较bab abc, 可以得到 b>a
－1 1 2
2 3 －1
a b c head=3
然后比较abc aca, 可以得到 b>c
－1 3 1
3 -1 2
a b c head=2
所以结果就是bca |
I******c
发帖数: 163 | 7 向前，向后指针搞反了
我的办法只需要遍历一遍，所以是O(n)
例如有三个字符串 bca bab abc aca
静态链表是
0 0 0 向后指针
0 0 0 向前指针
a b c
1 2 3 索引
首先比较bca bab, 可以得到 c>a
-1 0 1
3 0 －1
a b c head=3
然后比较bab abc, 可以得到 b>a
－1 1 2
2 3 －1
a b c head=3
然后比较abc aca, 可以得到 b>c
－1 3 1
3 -1 2
a b c head=2
所以结果就是bca |
m*****k
发帖数: 1864 | |
b********h
发帖数: 119 | 9 第一题难道不是topological sort？怎么可能是hash？
【在 a*******s 的大作中提到】
: 第一题可以用hash,只要26个表元就行，复杂度O(n)
: 第二题就是个图的遍历算法，DFS,stack实现比较简单，主要就是看看你API的定义能力
: 第三题是不是考格式调整？左对齐，右对齐和左右都对齐？我觉得这个不是太难，就是
: 计算子串在绘图空间里面的实际长度，注意切分字串时考虑远东语言等情况。
|
n******n
发帖数: 12088 | 10 "1" confusing. what is ordered/sorted words, the letter in the word is
sorted, and these words are also sorted?
"2" also unclear. what is "maze problem" being solved here, finding a path from entry to exit? what code did u write?
cceg
software
about
algorithms.
【在 w***h 的大作中提到】
: 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
|
|
|
N***m
发帖数: 4460 | 11 题3是啥意思？
from entry to exit? what code did u write?
【在 n******n 的大作中提到】
: "1" confusing. what is ordered/sorted words, the letter in the word is
: sorted, and these words are also sorted?
: "2" also unclear. what is "maze problem" being solved here, finding a path from entry to exit? what code did u write?
:
: cceg
: software
: about
: algorithms.
|
G****A
发帖数: 4160 | 12 请问用这里用hash table和用bool words[26]比较，
哪个好？
【在 g**e 的大作中提到】
: hash 26个字母，value=0。按单词字母顺序put，value++
: 完了以后按顺序输出所有value!=0的
: 你的方法为什么是O(n)，我怎么觉得是O(n^2)
|
G****A
发帖数: 4160 | 13 请问用这里用hash table和用bool words[26]比较，
哪个好？
【在 g**e 的大作中提到】
: hash 26个字母，value=0。按单词字母顺序put，value++
: 完了以后按顺序输出所有value!=0的
: 你的方法为什么是O(n)，我怎么觉得是O(n^2)
|
t****t
发帖数: 6806 | 14 ask yourself this question: what kind of data structure is "bool words[26]"?
【在 G****A 的大作中提到】
: 请问用这里用hash table和用bool words[26]比较，
: 哪个好？
|
v****s
发帖数: 1112 | 15 isn't problem 1 using bit array? |
w***h
发帖数: 415 | 16 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. |
U********d
发帖数: 577 | 17 栈和递归？如果硬件送过来的数据是实时的话，比如探测到一堵墙啥的，blah blah。 |
a*******s
发帖数: 79 | 18 第一题可以用hash,只要26个表元就行，复杂度O(n)
第二题就是个图的遍历算法，DFS,stack实现比较简单，主要就是看看你API的定义能力
第三题是不是考格式调整？左对齐，右对齐和左右都对齐？我觉得这个不是太难，就是
计算子串在绘图空间里面的实际长度，注意切分字串时考虑远东语言等情况。 |
I******c
发帖数: 163 | 19 第一题怎么用hash解？能否详细解释一下？
我的想法是遍列一次所有的字符串，比较相邻的字符串。每一次比较可以得到一个表示
两个字符前后关系的信息。然后把这些信息合并起来。（我使用静态链表）
时间复杂度也是O(n). |
g**e
发帖数: 6127 | 20 hash 26个字母，value=0。按单词字母顺序put，value++
完了以后按顺序输出所有value!=0的
你的方法为什么是O(n)，我怎么觉得是O(n^2)
【在 I******c 的大作中提到】
: 第一题怎么用hash解？能否详细解释一下？
: 我的想法是遍列一次所有的字符串，比较相邻的字符串。每一次比较可以得到一个表示
: 两个字符前后关系的信息。然后把这些信息合并起来。（我使用静态链表）
: 时间复杂度也是O(n).
|
|
|
I******c
发帖数: 163 | 21 我的办法只需要遍历一遍，所以是O(n)
例如有三个字符串 bca bab abc aca
静态链表是
0 0 0 向前指针
0 0 0 向后指针
a b c
1 2 3 索引
首先比较bca bab, 可以得到 c>a
-1 0 1
3 0 －1
a b c head=3
然后比较bab abc, 可以得到 b>a
－1 1 2
2 3 －1
a b c head=3
然后比较abc aca, 可以得到 b>c
－1 3 1
3 -1 2
a b c head=2
所以结果就是bca |
I******c
发帖数: 163 | 22 向前，向后指针搞反了
我的办法只需要遍历一遍，所以是O(n)
例如有三个字符串 bca bab abc aca
静态链表是
0 0 0 向后指针
0 0 0 向前指针
a b c
1 2 3 索引
首先比较bca bab, 可以得到 c>a
-1 0 1
3 0 －1
a b c head=3
然后比较bab abc, 可以得到 b>a
－1 1 2
2 3 －1
a b c head=3
然后比较abc aca, 可以得到 b>c
－1 3 1
3 -1 2
a b c head=2
所以结果就是bca |
m*****k
发帖数: 1864 | |
b********h
发帖数: 119 | 24 第一题难道不是topological sort？怎么可能是hash？
【在 a*******s 的大作中提到】
: 第一题可以用hash,只要26个表元就行，复杂度O(n)
: 第二题就是个图的遍历算法，DFS,stack实现比较简单，主要就是看看你API的定义能力
: 第三题是不是考格式调整？左对齐，右对齐和左右都对齐？我觉得这个不是太难，就是
: 计算子串在绘图空间里面的实际长度，注意切分字串时考虑远东语言等情况。
|
n******n
发帖数: 12088 | 25 "1" confusing. what is ordered/sorted words, the letter in the word is
sorted, and these words are also sorted?
"2" also unclear. what is "maze problem" being solved here, finding a path from entry to exit? what code did u write?
cceg
software
about
algorithms.
【在 w***h 的大作中提到】
: 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)
|
N***m
发帖数: 4460 | 26 题3是啥意思？
from entry to exit? what code did u write?
【在 n******n 的大作中提到】
: "1" confusing. what is ordered/sorted words, the letter in the word is
: sorted, and these words are also sorted?
: "2" also unclear. what is "maze problem" being solved here, finding a path from entry to exit? what code did u write?
:
: cceg
: software
: about
: algorithms.
|
G****A
发帖数: 4160 | 27 请问用这里用hash table和用bool words[26]比较，
哪个好？
【在 g**e 的大作中提到】
: hash 26个字母，value=0。按单词字母顺序put，value++
: 完了以后按顺序输出所有value!=0的
: 你的方法为什么是O(n)，我怎么觉得是O(n^2)
|
G****A
发帖数: 4160 | 28 请问用这里用hash table和用bool words[26]比较，
哪个好？
【在 g**e 的大作中提到】
: hash 26个字母，value=0。按单词字母顺序put，value++
: 完了以后按顺序输出所有value!=0的
: 你的方法为什么是O(n)，我怎么觉得是O(n^2)
|
t****t
发帖数: 6806 | 29 ask yourself this question: what kind of data structure is "bool words[26]"?
【在 G****A 的大作中提到】
: 请问用这里用hash table和用bool words[26]比较，
: 哪个好？
|
v****s
发帖数: 1112 | 30 isn't problem 1 using bit array? |
|
|
l*****a
发帖数: 559 | 31 同意，topcoder里有原题。
onsite出这种题夸张了。
http://community.topcoder.com/stat?c=problem_statement&pm=11239
【在 b********h 的大作中提到】
: 第一题难道不是topological sort？怎么可能是hash？
|
