Python高手如何破解Google的面试题

阅读本文大概需要15分钟+

开头先讲一下自己的亲身经历,05年的时候,也就是12年前,我去T公司面试,当时T公司在这个城市非常有名,有很多高手(号称小微软).我当时也是抱着初生牛犊不怕虎,想去会一会.在通过第一轮的笔试(当时考算法,程序,还有IQ)和初级面试后,进入第二轮,来了一个台湾技术经理,问了一些问题之后出了一道题,要求3分钟给出答案,这道题就是今天下面要讲的~~这3分钟我当时是又惊又囧,10多年过去了我现在依然记忆犹新(也许我以后会写一篇”10年了外企面试的那些往事”)

今天先说正题,没有想到十多年后,我无意中浏览硅谷的一些网站时候,竟然又碰到了这道题,太有缘了.这次是一个Google大牛分析这道题,而且是用Python解的(Python在Google里号称是最喜欢的语言之一),我觉得太过瘾了,力道雄厚而刚劲,招式非常巧妙,我加上自己的理解一起分享给大家.

题目#翻译成中文:

一个和尚去河边挑水,带了两个桶,一个是能装4斤水,一个能装9斤水

1),要求写出算法,目标是如何装出6斤水

2),假设两个桶容量任意,比如X斤和Y斤,目标是Z斤;要求写出算法

一.就像我们解数学题一样,我们先化繁为简,先从最简单的入手

AB两个桶:一个能装3斤水,一个能装5斤水=>目标4斤

上面只是一个很简单的实例,我相信一个4斤水,一个9斤,大家也能类似的推导出6斤水,只是步骤多一点而已,不是很难.

那么如果用计算机算法来解决任意X,Y的问题的,这个就很有意思了.我们接着分析~~

二.好有了这个感性的认识之后,我们开始抽象化,建模成算法.

我们发现穷举所有的组合,无非就这下面6种操作:

1.B->A

2.A->B

3.Fill A

4.Fill B

5.Empty A

6.Empty B

假设A桶容量是X,B桶容量是Y,A桶里面倒入的水是x,B桶倒入的是y

数据结构,很容易就想到我们应该用字典:我们用元组来表示两个桶的水,用字符串表示操作步骤

我们先从易到难开始说:

1.Empty B

(x,0)=>’Empty Y’ #把B桶的水倒空

2.Empty A

(0,y)=>’Empty X’ #把A桶的水倒空

3.Fill A

(X,y)=>’Fill X’  #把A桶的水加满

4.Fill B

(x,Y)=>’Fill Y’  #把B桶的水加满

5.A倒水到B

这个时候分两种情况

1).若A里的水倒入B,若把B倒满了,这个时候B就的值Y,A倒了Y-y的水进入,那么A剩下的就是X-(Y-y)

if x+y>=Y:

(X-(Y-y),Y):”X->Y”

2).若A里的水倒入B,若没有把B倒满了,这个时候B的值x+y,A为了0(A的水已经全部倒进B了,还是没有倒满)

if x+y

(0,x+y):”X->Y”

6.B倒水到A

这个时候分两种情况

1).若B里的水倒入A,若把A倒满了,这个时候A就的值X,B倒了X-x的水进入,那么B剩下的就是Y-(X-x)

if x+y>=X:

(X,Y-(X-x))

2).若B里的水倒入A,若没有把A倒满了,这个时候A的值x+y,B为了0(B的水已经全部倒进A了,还是没有倒满)

if x+y

(x+y,0):

三.好了上面的铺垫之后,我们来进入主旋律

我们定义一个函数叫def solutions(x,y,X,Y),里面会return (state,action)

就是我们定义的6种情况的数据格式.所以的操作都在这个6种状态机里面转

思路:

其实就是6步就是6个状态机,也就是我们整个的操作始终都在这6个状态机里面操作转圈,我们需要做的就是遍历每一种状态机的下一个状态,除了自己之外一共有5种,看下面的图:

start是起始状态,假设起始的时候两桶水都是空的,然后start可以操作如下操作:

Fill X(把A桶打满)

Fill Y(把B桶打满)

Empty X(把A桶的水倒掉)

Empty Y(把A桶的水倒掉)

然后到了Fill X 这个状态机之后,又可以有其他5种状态,接着转起来,就这样不断的探索下去,我们举个最简单的例子,一桶容量是3斤的水和一桶容量是5斤的水,倒出4斤,看一下状态机的图:

经过6步,到了第7步的时候,就找到了4斤的水了.

那么代码的设计是如何呢:

1).存放所有的有效的探索步骤我们用一个set()来存,大家有没有注意到每一步里面发散下去,会有重复的状态~~

比如第二次的(0,5),和第三次的(0,5)是一样的,所以我们用set很巧妙的过滤掉重复的状态,这样大大优化了我们的代码和搜索的速度.

见如下的图:红色的实心圈是set()要存的,空心的是重复的状态:

set()里面其实就是存的最后我们搜索到的两个桶的状态:

set([(3, 2), (0, 0), (3, 0), (2, 0), (0, 5), (2, 5),(3, 4), (0, 2), (3, 5)])

若4在里面就说明找到了.

2).外面有一个while循环,去遍历所有的状态

3).我们一开始有一个start状态比如(0,0)进入solutions函数,它会返回6种状态机,是用字典表示的

4).我们去判断每一种状态,(state,action),比如(3,4,”Y->X”),如果4出现在state里面,就算找到了break出去

5).若没有找到,我们继续循环搜索,大家一定想问while的入口是什么,也是一个列表:

比如(0,0)状态下可能要操作的所有步骤Path:

[[(0, 0), ‘fill X’, (3, 0)], [(0, 0), ’empty y’, (0, 0)], [(0, 0), ‘fill Y’, (0, 5), ‘Y->X’, (3, 2), ’empty x’, (0, 2), ‘Y->X’, (2, 0), ‘fill Y’, (2, 5)]]

6).每次从这个列表中取一个继续下次的搜索,直到找到目标为止.

看一下结果:一桶4斤,一桶9斤,如何倒出6斤水

[(0, 0), ‘fill X’, (4, 0), ‘X->Y’, (0, 4), ‘fill X’, (4, 4), ‘X->Y’, (0, 8), ‘fill X’, (4, 8), ‘X->Y’, (3, 9), ’empty y’, (3, 0), ‘X->Y’, (0, 3), ‘fill X’, (4, 3), ‘X->Y’, (0, 7), ‘fill X’, (4, 7), ‘X->Y’, (2, 9), ’empty y’, (2, 0), ‘X->Y’, (0, 2), ‘fill X’, (4, 2), ‘X->Y’, (0, 6)]

结论:

其实题目并不是很难,关键是解题的思路,学Python招式掌握之后,关键是心法,而心法其实就是算法和软件技巧,这个没有什么好的诀窍,一半靠悟,一半靠练.以后我还会分享一些精妙而又有趣的Python算法题.

IT文库 » Python高手如何破解Google的面试题
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址