FAANG面试在2021年问这5个Python问题

    我的Github上提供了完整的Python代码。

对于任何与数据相关的采访，使用Python编程都是必不可少的技能，也是必须准备的领域!编程问题有四种类型，包括数据结构和算法，机器学习算法，数学和统计以及数据操作(请参阅Emma Ding @Airbnb撰写的精彩文章)。

我在相关文章中阐述了有关数据处理和字符串提取的主题。在今天的帖子中，我将重点介绍数学和统计，并对一些大型科技公司(尤其是FAANG)提出的五个Python编程问题进行实时编码。这种类型的问题为您提供了业务设置，并通过模拟请求统计解决方案。

问题1：谁先赢?微软

艾米和布拉德轮流滚动一个漂亮的六边形模具。谁先掷出" 6"赢得比赛。艾米首先滚动。艾米获胜的机率是多少?

(1) 思路

这是一个核心的模拟问题，没有比模拟大量过程并检查Amy获胜的可能性更好的方法了。

艾米滚第一。如果结果为6，则游戏结束，艾米获胜。否则，布拉德(Brad)翻牌，如果是6，则赢得比赛。如果不是，则转回艾米(Amy)。重复该过程，直到有人以6结束游戏。

在这里，关键是要了解逻辑流程：谁赢了，在什么情况下赢了。如果艾米得到6分，布拉德必须投掷吗?没有。

(2) 解题

1. import numpy as np 
2.  
3. def who_won(die, size): 
4.      
5.     A_count = 0 # initialize A_count 
6.      
7.     B_count = 0 # initialize B_count 
8.      
9.     for i in range(size): # create an iteration  
10.          
11.         A_6 = np.random.choice(die)  # roll the fair dice and choose a random value from 0 to 6 
12.          
13.         if A_6 == 6:       # if A rolls a 6, then A_count adds 1.  
14.              
15.             A_count+=1     # a side-note for Python beginners: the full expression is "A_countA_count = A_count+1." 
16.          
17.         else:              # if the above if condition does not fullfill 
18.              
19.             B_6 = np.random.choice(die)  # then, it's B's turn to roll the dice, which is a random choice from 0 to 6. 
20.              
21.             if B_6 == 6:   # if B rolls a B, B_count adds 1. 
22.                  
23.                 B_count+=1 
24.                  
25.     return A_count/(A_count+B_count)   # return the total number of cases that A won divided by the combined number of A and B wonaka. the result is the probability that Amy wins.   

检查第11行：A_6是Amy的数据分布，如果她的数据为6，则计数为+1。否则，布拉德可以掷骰子。

在最后(第25行)，最终结果应该是Amy获胜的次数除以Amy和Brad获胜的总数。一个常见的错误是将A_count除以仿真总数。这是不正确的，因为当Amy和Brad都未能掷出6时，会有迭代。

让我们测试一下上述算法。

1. np.random.seed(123) 
2.  
3. die = [1,2,3,4,5,6] 
4.  
5. size = 10000 
6.  
7. who_won(die,size) 
8. view raw 

0.531271015467384

事实证明，艾米(Amy)在布拉德(Brad)之前就开始滚动赢得这场比赛。艾米(Amy)在10,000次模拟中获胜的概率为53%。

> Photo by john vicente on Unsplash

问题2：每个主要公司的最大数量为69

-给定一个仅由数字6和9组成的正整数num。-返回最多可更改一个数字可得到的最大数字(6变为9，而9变为6)。https://leetcode.com/problems/maximum-69-number/

(1) 思路

给定一个正整数，只有一种方法可以增大值，即将" 6"变成" 9"，而不是相反。另外，我们必须更改最左边的6;否则，它不是最大数量。例如，我们必须将" 6996"更改为" 9996"，而不是" 6999"。

我想出了这个问题的几种变体：您可以更改一次，也可以全部更改为6。

(2) 解决方法1：替换一次

1. # replace once 
2. def max_69_once(num): 
3.     return int(str(num).replace('6','9',1)) 
4.  
5. # test case 
6. num = 966666669 
7. max_69_once(num) 

996666669

在第3行中，我们将整数转换为字符串，然后将第一个" 6"替换为" 9";使用int()将其返回为整数。

(3) 解决方案2：全部替换

1. def max_69_all(num): 
2.     k = len(str(num)) 
3.     return int(str(num).replace('6','9',k)) 
4.  
5. # test case 
6. num = 966666669 
7. max_69_all(num) 

999999999

对于第二种情况，我们不必指定k，因为replace()方法默认会更改所有合适的值。我出于教学目的指定了k值。这个问题的另一个变体是替换前两个或三个" 6"以使数字最大。

> Photo by Alessandro Capuzzi on Unsplash

问题3：有效的完美正方形。Facebook

-给定正整数num，编写一个函数，如果num是一个完美的平方则返回True;否则返回False。-后续操作：请勿使用任何内置库函数(例如sqrt)。

https://leetcode.com/problems/valid-perfect-square/

(1) 思路

这非常简单：检查正整数是否具有理想的平方根，如果有正整数，则返回True，这可以分两步完成。

• 找到平方根。
• 检查它是否是完美的平方根。

棘手的部分是我们必须使用内置库(例如，数学，Numpy)来计算平方根，这在LeetCode上是一个简单的问题。如果我们不能使用这些库，那么它将成为更具挑战性和反复性的问题，这是LeetCode的一个中等水平的问题。

(2) 解决方案1：内置库

1. import math  
2.  
3. def valid_perfect_square(num): 
4.     return int(math.sqrt(num))**2==num  # the int() method only returns the integer part and leaves out the decimal part. 
5.                                         # For perfect squares, there should be no decimal part. The equation should thus hold. 
6.  
7. # test case  
8. valid_perfect_square(16) 

该算法轻松通过了测试案例。应当指出，我们需要使用int()方法仅获取平方根的整数部分，而忽略任何小数部分。对于完美的正方形，它不会有任何差异，因此等式成立。对于非完美的平方，方程将不成立并返回False。

(特别感谢韩琦发现错误!)

解决方案2：没有内置库和二进制搜索

1. # 1 find the squre root of num 
2. # 2 check if it is a perfect square number 
3.  
4. # solution: no built-in library & binary search 
5. def valid_perfect_square(num): 
6.     if num < 2:  
7.         return True 
8.     left, right = 2, num//2       # create two pointers: left and right  
9.     while left<=right:            # while loop to constantly update left and right  
10.         x = left + (right-left)//2# take a wild guess and treat x as the starting point 
11.         xx_squared = x*x           # calculate the squared value of x 
12.         if x_squared == num:      # use the following 'if-else' statement to constantly update x_squared. 
13.             return True           # if there are the same, return True 
14.         if x_squared <num:        # if x_squared is smaller than num, left increases by 1 
15.             left= x+1  
16.         else:                     # if x_squared is bigger, right decreases by 1 
17.             right= x-1 
18.     return False                  # the while loop should continue looping until left and right converge and no common value obtained 
19.   
20.   
21. # test case 
22. valid_perfect_square(16) 

如果不允许使用任何库，则采用二进制搜索。LeetCode包含一个详细的解释(在此处)，我也对此主题发表了另一篇文章(在这里)。简而言之，我们创建左右两个指针，并将这两个数字的平均值与原始数字进行比较：如果小于该数字，则增加该值;如果更大，我们减少它;或者，如果它们匹配，则返回True。

这些条件将在while循环中自动检查。

#问题4：阶乘尾随零。彭博社

给定整数n，返回n中的尾随零!

后续行动：您能否编写一种适用于对数时间复杂度的解决方案?

https://leetcode.com/problems/factorial-trailing-zeroes/

(1) 思路

这个问题有两个步骤：

• 计算n阶乘n!
• 计算尾随零的数量

对于第一步，我们使用while循环迭代遍历n个阶乘并停止循环直到1。对于第二步，事情变得有些棘手。

该问题要求尾随零而不是总数零。这是个很大的差异。8!是40,320，它有2个零，但只有1个尾随零。我们在计算时必须格外小心。我提出了两种解决方案。

(2) 解决方案1：向后读取字符串

1. # 1 calculate n! 
2. # 2 calculate the number of trailing zeros 
3.  
4. def factorial_zeros(n): 
5.     product = n 
6.     while n > 1 :         # iteratively calculate the product 
7.         product *= (n-1) 
8.         n-=1 
9.          
10.     count = 0  
11.      
12.     for i in str(product)[::-1]:  # calculate the number of trailing zeros 
13.         if i == '0': 
14.             count+=1 
15.         else: 
16.             break 
17.     return count 
18.  
19. factorial_zeros(20) 

计算产品的第一部分是不言而喻的。对于第二部分，我们使用str()方法将乘积转换为字符串，然后向后读取：如果数字为0，则将count加1;否则为0。否则，我们将打破循环。

break命令在这里至关重要。如前所述，上述函数无需中断命令即可计算零的总数。

(3) 解决方案2：while循环

1. def factorial_zeros(n): 
2.     product = n 
3.     while n > 1 :          # step 1: iteratively calculate the product  
4.         product *= (n-1) 
5.         n-=1 
6.     count = 0  
7.      
8.     while product%10 == 0:   # step 2: calculate the number of trailing zeros 
9.         productproduct = product/10 
10.         count+=1 
11.          
12.     return count 

第一部分与解决方案1相同，唯一的区别是我们使用while循环来计算尾随数字：对于乘积除以10的乘积，最后一位必须为0。因此，我们使用while循环不断更新while循环，直到条件不成立为止。

顺便说一句，解决方案2是我最喜欢的计算零的方法。

> Photo by Jamie Fenn on Unsplash

问题5：完美数字，亚马逊

• 理想数字是一个正整数，它等于其正因数之和，但不包括数字本身。
• 整数x的除数是可以将x均匀除的整数。
• 给定整数n，如果n是完美数则返回true，否则返回false。
• https://leetcode.com/problems/perfect-number/

(1) 思路

这个问题可以分为三个步骤：

• 找出正因数
• 计算总和
• 决定：完美与否

第2步和第3步是不言而喻的，最多不超过一层。但是，棘手的部分是找到正除数。为此，我们可以采用野蛮力方法，并在从1到整数的整个序列中进行迭代。

理论上，它应该适用于一个小整数，但是如果我们运行大数，它将超过时间限制。时间效率不高。

(2) 解决方案1：暴力

1. #1. find the positive divisors 
2. #2. calculate the sum  
3. #3. perfect or not  
4.  
5. def perfect_number(num): 
6.     divisors = [] 
7.     for i in range(1,num): 
8.         if num%i==0: 
9.             divisors.append(i) 
10.     if sum(divisors)==num: 
11.         return True 
12.     else: 
13.         return False 
14.          
15. # test case 1 
16. perfect_number(2) 

此方法不适用于较大的值。您的面试官可能会要求更有效的解决方案。

(3) 解决方案2：sqrt(n)

1. # solution 2: sqrt(n) 
2.  
3. def perfect_number(num): 
4.      
5.     if num<=1: 
6.         return False 
7.      
8.     divisors = set([1]) 
9.      
10.     for i in range(2,int(num**0.5)+1):   # from 2 to num**0.5 
11.         if num%i==0: 
12.             divisors.add(i) 
13.             divisors.add(num//i) 
14.  
15.     return sum(divisors)==num 

要找到其除数，我们不必检查最大为整数的值。例如，要找到100的除数，我们不必检查从1到100的数字。相反，我们只需要检查直到100的平方根即10，并且所有其他可用值都已经为包括在内。

这是一种最佳算法，可为我们节省大量时间。

我的Github上提供了完整的Python代码。https://github.com/LeihuaYe/Python_LeetCode_Coding

总结

• 在进行了数十次"实践"编码之后，最大的收获就是理解问题并将问题分为多个可操作的组件。
• 在这些可行的部分中，总会有一个步骤使求职者绊倒。诸如"不能使用内置函数/库"之类的限制。
• 关键是逐步编写自定义函数，并尝试避免在练习例程中尽可能多地使用内置函数。

原文链接：https://towardsdatascience.com/5-python-coding-questions-asked-at-faang-59e6cf5ba2a0)