x*1
2 楼
周一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?
第一题,水题,数组加一操作,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
4 楼
rebuild the alphabet 是指找出所有letter吗?
s*x
5 楼
up to 24 hours
l*8
6 楼
第二题:
因为有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?
因为有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
8 楼
fcp, aac 决定了f 在a之前,是应该用拓扑排序
w*3
12 楼
不是很明白第二题的意思,怎么样用topological sort?
s*a
14 楼
Bless!!
f*r
18 楼
第二题应该就是topological sorting
首先将所有不同的字母找出来,作为directed graph的node,
然后给出的字符串代表了graph中的directed edge,比如fcp,说明有f-->c, c-->p两个
edges。这样就建立了一个directed graph
然后就可以做标准的topological sorting,得到的结果就是字母的顺序。
首先将所有不同的字母找出来,作为directed graph的node,
然后给出的字符串代表了graph中的directed edge,比如fcp,说明有f-->c, c-->p两个
edges。这样就建立了一个directed graph
然后就可以做标准的topological sorting,得到的结果就是字母的顺序。
f*r
20 楼
祝福好运!
d*i
22 楼
G家发的面试准备里也没有拓扑排序啊。。被黑了?
s*y
28 楼
请问楼主在写第二题的时候,写了多少行代码?
我试着写,发现得用至少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?
我试着写,发现得用至少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?
c*8
31 楼
bless
f*n
32 楼
mark
o*g
36 楼
第二题可以用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?
你的目的是找到一种哈希算法,使得哈希代码能够正确的表达字符串顺序
如果就是给出的这些字符串的话,就是最长只有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
37 楼
弱问拓扑排序咋用的。是说比如fft就弄一个f到t的edge,一个directed graph,然后
从没有incoming edge的node开始delete,delete完node delete edge?
这应该用啥data structure啊,一般graph不用linked list,感觉复杂度很高啊。
从没有incoming edge的node开始delete,delete完node delete edge?
这应该用啥data structure啊,一般graph不用linked list,感觉复杂度很高啊。
K*g
39 楼
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?
[
★ 发自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
40 楼
i*h
41 楼
Bless!
同被问到类似的题,也是用topological sort做。看来G现在很喜欢问这个。
同被问到类似的题,也是用topological sort做。看来G现在很喜欢问这个。
p*g
43 楼
谁能写个完整的, 谢谢
相关阅读
求refer!!!请教个prefix tree (trie)和boggle的问题在哪里求refer呢?求Thomson Reuters内推Job Opening: Associate of Analytics内推.net程序员工作,Chinese Speakinig is preferred谁读了今年的移民Bill。opt还能再延期一次么?请教LeetCode的3Sum请大家比较ebay, Yahoo, Walmart Lab有经验的跳槽进大公司也需要做题吗H1B 2号已经批了,结果又收到email alert说成acceptance了是怎么回事?大家去实习时填过I9表吗?H-1b transfer mailing address?GE的职位问题 (转载)工作 Open (转载)H1B 有效期请问Vitera Healthcare Solutions Assessment Test考些什么PP的收到退包了么OPT EAD卡没收到,收到个approval notice是啥意思???A家onsite一直没消息,是什么情况?