x******1
发帖数: 155 | 1 周一google电面，现在还在等消息，发发面经，攒攒RP，也希望得到大家的Bless！
第一题，水题，数组加一操作，for example, 输入[2, 7, 8, 9] 数组，加一后变成 [
2, 7, 9, 0]
第二题，给定输入这样的字符串
fft, fcp, aac, act, acd, atp, tbk, tdf, …
这些都是按照字母排序好的，但是字母顺序改了，比如 f 在 a之前，t在d之前等等，
给定一些这样的rule，问怎么rebuild the alphabet? | c*******r
发帖数: 610 | 2 rebuild the alphabet 是指找出所有letter吗？ | l*********8
发帖数: 4642 | 3 第二题：
因为有tbk, 所以t在d之前，是吧？
f为什么在a之前？
这题是拓扑排序吧
[
【在 x******1 的大作中提到】
: 周一google电面，现在还在等消息，发发面经，攒攒RP，也希望得到大家的Bless！
: 第一题，水题，数组加一操作，for example, 输入[2, 7, 8, 9] 数组，加一后变成 [
: 2, 7, 9, 0]
: 第二题，给定输入这样的字符串
: fft, fcp, aac, act, acd, atp, tbk, tdf, …
: 这些都是按照字母排序好的，但是字母顺序改了，比如 f 在 a之前，t在d之前等等，
: 给定一些这样的rule，问怎么rebuild the alphabet?
| x******1
发帖数: 155 | 4 fcp, aac 决定了f 在a之前，是应该用拓扑排序 | l*********8
发帖数: 4642 | 5 谢谢！
如果不能完全重建字母表， 输出什么呢？
【在 x******1 的大作中提到】
: fcp, aac 决定了f 在a之前，是应该用拓扑排序
| w****3
发帖数: 110 | 6 不是很明白第二题的意思，怎么样用topological sort？ | s*******a
发帖数: 501 | | m*********y
发帖数: 111 | 8 是烙印面的吗？感觉被黑了
[
【在 x******1 的大作中提到】
: 周一google电面，现在还在等消息，发发面经，攒攒RP，也希望得到大家的Bless！
: 第一题，水题，数组加一操作，for example, 输入[2, 7, 8, 9] 数组，加一后变成 [
: 2, 7, 9, 0]
: 第二题，给定输入这样的字符串
: fft, fcp, aac, act, acd, atp, tbk, tdf, …
: 这些都是按照字母排序好的，但是字母顺序改了，比如 f 在 a之前，t在d之前等等，
: 给定一些这样的rule，问怎么rebuild the alphabet?
| f*******r
发帖数: 1086 | 9 第二题应该就是topological sorting
首先将所有不同的字母找出来，作为directed graph的node，
然后给出的字符串代表了graph中的directed edge，比如fcp,说明有f-->c, c-->p两个
edges。这样就建立了一个directed graph
然后就可以做标准的topological sorting，得到的结果就是字母的顺序。 | f*******r
发帖数: 1086 | | | | d********i
发帖数: 582 | 11 G家发的面试准备里也没有拓扑排序啊。。被黑了？ | w****3
发帖数: 110 | 12 多谢，原来是这个意思
【在 f*******r 的大作中提到】
: 第二题应该就是topological sorting
: 首先将所有不同的字母找出来，作为directed graph的node，
: 然后给出的字符串代表了graph中的directed edge，比如fcp,说明有f-->c, c-->p两个
: edges。这样就建立了一个directed graph
: 然后就可以做标准的topological sorting，得到的结果就是字母的顺序。
| x******1
发帖数: 155 | 13 你可以assume肯定会有一个答案
【在 l*********8 的大作中提到】
: 谢谢！
: 如果不能完全重建字母表， 输出什么呢？
| s*******y
发帖数: 45 | 14 请问楼主在写第二题的时候，写了多少行代码？
我试着写，发现得用至少60行C++，才能写完。
请教楼主如何在短时间内写清楚的啊？
谢谢！
[
【在 x******1 的大作中提到】
: 周一google电面，现在还在等消息，发发面经，攒攒RP，也希望得到大家的Bless！
: 第一题，水题，数组加一操作，for example, 输入[2, 7, 8, 9] 数组，加一后变成 [
: 2, 7, 9, 0]
: 第二题，给定输入这样的字符串
: fft, fcp, aac, act, acd, atp, tbk, tdf, …
: 这些都是按照字母排序好的，但是字母顺序改了，比如 f 在 a之前，t在d之前等等，
: 给定一些这样的rule，问怎么rebuild the alphabet?
| m******s
发帖数: 1469 | 15 Bless
[
【在 x******1 的大作中提到】
: 周一google电面，现在还在等消息，发发面经，攒攒RP，也希望得到大家的Bless！
: 第一题，水题，数组加一操作，for example, 输入[2, 7, 8, 9] 数组，加一后变成 [
: 2, 7, 9, 0]
: 第二题，给定输入这样的字符串
: fft, fcp, aac, act, acd, atp, tbk, tdf, …
: 这些都是按照字母排序好的，但是字母顺序改了，比如 f 在 a之前，t在d之前等等，
: 给定一些这样的rule，问怎么rebuild the alphabet?
| m******s
发帖数: 1469 | 16 Bless
[
【在 x******1 的大作中提到】
: 周一google电面，现在还在等消息，发发面经，攒攒RP，也希望得到大家的Bless！
: 第一题，水题，数组加一操作，for example, 输入[2, 7, 8, 9] 数组，加一后变成 [
: 2, 7, 9, 0]
: 第二题，给定输入这样的字符串
: fft, fcp, aac, act, acd, atp, tbk, tdf, …
: 这些都是按照字母排序好的，但是字母顺序改了，比如 f 在 a之前，t在d之前等等，
: 给定一些这样的rule，问怎么rebuild the alphabet?
| c***8
发帖数: 188 | | f******n
发帖数: 279 | | l****r
发帖数: 118 | 19 doh，听都没听过这个排序。。。
【在 l*********8 的大作中提到】
: 第二题：
: 因为有tbk, 所以t在d之前，是吧？
: f为什么在a之前？
: 这题是拓扑排序吧
:
: [
| l*********u
发帖数: 19053 | 20 bless
[
【在 x******1 的大作中提到】
: 周一google电面，现在还在等消息，发发面经，攒攒RP，也希望得到大家的Bless！
: 第一题，水题，数组加一操作，for example, 输入[2, 7, 8, 9] 数组，加一后变成 [
: 2, 7, 9, 0]
: 第二题，给定输入这样的字符串
: fft, fcp, aac, act, acd, atp, tbk, tdf, …
: 这些都是按照字母排序好的，但是字母顺序改了，比如 f 在 a之前，t在d之前等等，
: 给定一些这样的rule，问怎么rebuild the alphabet?
| | | R******9
发帖数: 267 | 21 big bless~
[
【在 x******1 的大作中提到】
: 周一google电面，现在还在等消息，发发面经，攒攒RP，也希望得到大家的Bless！
: 第一题，水题，数组加一操作，for example, 输入[2, 7, 8, 9] 数组，加一后变成 [
: 2, 7, 9, 0]
: 第二题，给定输入这样的字符串
: fft, fcp, aac, act, acd, atp, tbk, tdf, …
: 这些都是按照字母排序好的，但是字母顺序改了，比如 f 在 a之前，t在d之前等等，
: 给定一些这样的rule，问怎么rebuild the alphabet?
| o***g
发帖数: 2784 | 22 第二题可以用hash
你的目的是找到一种哈希算法，使得哈希代码能够正确的表达字符串顺序
如果就是给出的这些字符串的话，就是最长只有3个字符
可以定义f=25 a=24 .. t=21... z=0，空字符=26
然后fft = 25*26*26 + 25*26 + 21，ff = 25*26*26 + 25*26 + 26
因为你要将ff排到fft前面
由大到小排就行了
这个复杂度就是O(n*lg(n))吧
拓扑的复杂度是多少？
而这个题目，我发现你开始给出的字符串序列是根据你的新规则排好序的，是不是题目
记得有问题？
比如输入的时候是正常的排序规则下得序列：
aac, acd, act, atp, fcp, fft, tbk, tdf
如果f变成在a前面了，该怎么办？
这样的话，就是将排好序的字符串序列分组，找到a开头的字符串序列，是0-3，找到f
开头的字符串序列是4-5，然后将4-5整个搬到0之前。
然后递归，0-3都是a开头，然后查第二个字符，再找a在第二个的和f在第二个的，再整
体搬迁。f开头的这一串也查一遍第二个字符，后面t开头的这段再查第二个字符。
然后第三个字符。。。
[
【在 x******1 的大作中提到】
: 周一google电面，现在还在等消息，发发面经，攒攒RP，也希望得到大家的Bless！
: 第一题，水题，数组加一操作，for example, 输入[2, 7, 8, 9] 数组，加一后变成 [
: 2, 7, 9, 0]
: 第二题，给定输入这样的字符串
: fft, fcp, aac, act, acd, atp, tbk, tdf, …
: 这些都是按照字母排序好的，但是字母顺序改了，比如 f 在 a之前，t在d之前等等，
: 给定一些这样的rule，问怎么rebuild the alphabet?
| y*****9
发帖数: 149 | 23 弱问拓扑排序咋用的。是说比如fft就弄一个f到t的edge，一个directed graph，然后
从没有incoming edge的node开始delete，delete完node delete edge？
这应该用啥data structure啊，一般graph不用linked list，感觉复杂度很高啊。 | y*****9
发帖数: 149 | 24 大牛能看一下我上面说的拓扑序对么。
我查拓扑序不是说是给acyclic graph的么。
复杂度是多少？
用啥data structure?
【在 f*******r 的大作中提到】
: 第二题应该就是topological sorting
: 首先将所有不同的字母找出来，作为directed graph的node，
: 然后给出的字符串代表了graph中的directed edge，比如fcp,说明有f-->c, c-->p两个
: edges。这样就建立了一个directed graph
: 然后就可以做标准的topological sorting，得到的结果就是字母的顺序。
| K******g
发帖数: 1870 | 25 Bless
[
★ 发自iPhone App: ChineseWeb 8.6
【在 x******1 的大作中提到】
: 周一google电面，现在还在等消息，发发面经，攒攒RP，也希望得到大家的Bless！
: 第一题，水题，数组加一操作，for example, 输入[2, 7, 8, 9] 数组，加一后变成 [
: 2, 7, 9, 0]
: 第二题，给定输入这样的字符串
: fft, fcp, aac, act, acd, atp, tbk, tdf, …
: 这些都是按照字母排序好的，但是字母顺序改了，比如 f 在 a之前，t在d之前等等，
: 给定一些这样的rule，问怎么rebuild the alphabet?
| s*********y
发帖数: 10 | | i*****h
发帖数: 1534 | 27 Bless!
同被问到类似的题，也是用topological sort做。看来G现在很喜欢问这个。 | w******n
发帖数: 61 | 28 G家常考拓扑排序啊。我知道4个去面的2个考了。
【在 d********i 的大作中提到】
: G家发的面试准备里也没有拓扑排序啊。。被黑了？
| p*********g
发帖数: 2998 | | n******n
发帖数: 12088 | 30 解释错了。
【在 f*******r 的大作中提到】
: 第二题应该就是topological sorting
: 首先将所有不同的字母找出来，作为directed graph的node，
: 然后给出的字符串代表了graph中的directed edge，比如fcp,说明有f-->c, c-->p两个
: edges。这样就建立了一个directed graph
: 然后就可以做标准的topological sorting，得到的结果就是字母的顺序。
| | | k****i
发帖数: 128 | 31 如果不是dag就没法重建字母表了
topological sort就是dfs，复杂度是O(n+E), worst case O(n^2)
【在 y*****9 的大作中提到】
: 大牛能看一下我上面说的拓扑序对么。
: 我查拓扑序不是说是给acyclic graph的么。
: 复杂度是多少？
: 用啥data structure?
|
|
