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 楼
谁能写个完整的, 谢谢
相关阅读
收到ME方向的offer一个星期搞定工作IT行业2012薪水水平诡异的EE面试onsite以后3个星期联系HR怎么样?微软的那些组工作不是那么忙呢,拖家带口的,拼不过小单身了是不是只要专业是在STEM list上面的,找CS的工作都可以算related to field of study有人amazon是从fulltime 的申请拿internship的么?如何判断一个数独是否合法?哪位大虾能贴一个 k way merge sorted arrays c++ code大家怎么处理N轮面试的着装问题的办H1B, 还没拿到offer letter公司律师就联系我要我提供材料递归法parse计算数字string[合集] 生日被雷,求助大家如何转专业工作?面google, fackbook前拿什么公司练手?求bless,希望能尽快拿到OPT不错的网上cs课程在start-up实习好不好啊?准备好好做做leetcode上的题