avatar
Google电面面经并求Bless# JobHunting - 待字闺中
a*n
1
买了之后要多久才能用?我买了有一个多小时了,还用不了。
avatar
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?
avatar
c*a
3
在等一会儿就行了

【在 a*****n 的大作中提到】
: 买了之后要多久才能用?我买了有一个多小时了,还用不了。
avatar
c*r
4
rebuild the alphabet 是指找出所有letter吗?
avatar
s*x
5
up to 24 hours
avatar
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?

avatar
m*r
7
应该是立等可取的

【在 s*****x 的大作中提到】
: up to 24 hours
avatar
x*1
8
fcp, aac 决定了f 在a之前,是应该用拓扑排序
avatar
s*x
9
no, 我的就有第二天才available的。
特意打电话问了。

【在 m*r 的大作中提到】
: 应该是立等可取的
avatar
l*8
10
谢谢!
如果不能完全重建字母表, 输出什么呢?

【在 x******1 的大作中提到】
: fcp, aac 决定了f 在a之前,是应该用拓扑排序
avatar
m*r
11
khols买的bb马上就可以用了
grocery store买的ebay好像也很快

【在 s*****x 的大作中提到】
: no, 我的就有第二天才available的。
: 特意打电话问了。

avatar
w*3
12
不是很明白第二题的意思,怎么样用topological sort?
avatar
a*n
13
bb, amazon都是马上可以用,ebay的我刚才用了,过了大概2-3小时吧.

【在 m*r 的大作中提到】
: khols买的bb马上就可以用了
: grocery store买的ebay好像也很快

avatar
s*a
14
Bless!!
avatar
j*0
15
你好,请问这两个是什么DEAL,我到KHOLS的网站上没见有卖BB的GC啊。。

【在 m*r 的大作中提到】
: khols买的bb马上就可以用了
: grocery store买的ebay好像也很快

avatar
m*y
16
是烙印面的吗?感觉被黑了

[

【在 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?

avatar
j*0
17
你好,请问这个是什么DEAL,我到KHOLS的网站上没见有卖BB的GC啊。。

【在 a*****n 的大作中提到】
: 买了之后要多久才能用?我买了有一个多小时了,还用不了。
avatar
f*r
18
第二题应该就是topological sorting
首先将所有不同的字母找出来,作为directed graph的node,
然后给出的字符串代表了graph中的directed edge,比如fcp,说明有f-->c, c-->p两个
edges。这样就建立了一个directed graph
然后就可以做标准的topological sorting,得到的结果就是字母的顺序。
avatar
j*0
19
你好,请问这个是什么DEAL,我到KHOLS的网站上没见有卖BB的GC啊。。

【在 s*****x 的大作中提到】
: no, 我的就有第二天才available的。
: 特意打电话问了。

avatar
f*r
20
祝福好运!
avatar
j*0
21
你好,请问这两个是什么DEAL,我到KHOLS的网站上没见有卖BB的GC啊。。

【在 a*****n 的大作中提到】
: bb, amazon都是马上可以用,ebay的我刚才用了,过了大概2-3小时吧.
avatar
d*i
22
G家发的面试准备里也没有拓扑排序啊。。被黑了?
avatar
s*y
23
没讨论deal, 纯技术贴,
是哇,lz

【在 j**********0 的大作中提到】
: 你好,请问这两个是什么DEAL,我到KHOLS的网站上没见有卖BB的GC啊。。
avatar
w*3
24
多谢,原来是这个意思

【在 f*******r 的大作中提到】
: 第二题应该就是topological sorting
: 首先将所有不同的字母找出来,作为directed graph的node,
: 然后给出的字符串代表了graph中的directed edge,比如fcp,说明有f-->c, c-->p两个
: edges。这样就建立了一个directed graph
: 然后就可以做标准的topological sorting,得到的结果就是字母的顺序。

avatar
a*n
25
是的,连技术贴都算不上,楼主就是闲得蛋痛.

【在 s**********y 的大作中提到】
: 没讨论deal, 纯技术贴,
: 是哇,lz

avatar
x*1
26
你可以assume肯定会有一个答案

【在 l*********8 的大作中提到】
: 谢谢!
: 如果不能完全重建字母表, 输出什么呢?

avatar
w*s
27
乖,阿姨给你揉揉就不痛了。

【在 a*****n 的大作中提到】
: 是的,连技术贴都算不上,楼主就是闲得蛋痛.
avatar
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?

avatar
m*s
29
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?

avatar
m*s
30
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?

avatar
c*8
31
bless
avatar
f*n
32
mark
avatar
l*r
33
doh,听都没听过这个排序。。。

【在 l*********8 的大作中提到】
: 第二题:
: 因为有tbk, 所以t在d之前,是吧?
: f为什么在a之前?
: 这题是拓扑排序吧
:
: [

avatar
l*u
34
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?

avatar
R*9
35
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?

avatar
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?

avatar
y*9
37
弱问拓扑排序咋用的。是说比如fft就弄一个f到t的edge,一个directed graph,然后
从没有incoming edge的node开始delete,delete完node delete edge?
这应该用啥data structure啊,一般graph不用linked list,感觉复杂度很高啊。
avatar
y*9
38
大牛能看一下我上面说的拓扑序对么。
我查拓扑序不是说是给acyclic graph的么。
复杂度是多少?
用啥data structure?

【在 f*******r 的大作中提到】
: 第二题应该就是topological sorting
: 首先将所有不同的字母找出来,作为directed graph的node,
: 然后给出的字符串代表了graph中的directed edge,比如fcp,说明有f-->c, c-->p两个
: edges。这样就建立了一个directed graph
: 然后就可以做标准的topological sorting,得到的结果就是字母的顺序。

avatar
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?

avatar
i*h
41
Bless!
同被问到类似的题,也是用topological sort做。看来G现在很喜欢问这个。
avatar
w*n
42
G家常考拓扑排序啊。我知道4个去面的2个考了。

【在 d********i 的大作中提到】
: G家发的面试准备里也没有拓扑排序啊。。被黑了?
avatar
p*g
43
谁能写个完整的, 谢谢
avatar
n*n
44
解释错了。

【在 f*******r 的大作中提到】
: 第二题应该就是topological sorting
: 首先将所有不同的字母找出来,作为directed graph的node,
: 然后给出的字符串代表了graph中的directed edge,比如fcp,说明有f-->c, c-->p两个
: edges。这样就建立了一个directed graph
: 然后就可以做标准的topological sorting,得到的结果就是字母的顺序。

avatar
k*i
45
如果不是dag就没法重建字母表了
topological sort就是dfs,复杂度是O(n+E), worst case O(n^2)

【在 y*****9 的大作中提到】
: 大牛能看一下我上面说的拓扑序对么。
: 我查拓扑序不是说是给acyclic graph的么。
: 复杂度是多少?
: 用啥data structure?

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。