在本文中，我提出并分享了 FAANG 访谈中经常出现的一些基本算法的解决方案

为什么实践算法是关键？

如果你是 Python 的新手，并且计划开始面试顶级公司(包括 FAANG) ，听听这个: 你现在就需要开始练习算法。

不要像我刚开始解决这些问题时那样天真。尽管我认为时不时破解几个算法很有趣，但我从来没有花太多时间练习，花更少的时间来实现一个更快或更高效的解决方案。就我个人而言，我在想，在一天结束的时候，整天解决算法有点太书呆子气了，它在实际的日常工作环境中并没有真正的实际用途，而且从长远来看，它也不会给我带来多少收入。

“知道如何解决算法将给你在求职过程中带来竞争优势”

好吧... 我错了(至少部分错了) : 我仍然认为，在算法上花费太多时间而不关注其他技能，并不足以让你找到理想的工作，但我明白，既然复杂的问题出现在日常工作中，作为一名程序员，大公司必须找到一个标准化的流程，以收集求职者解决问题的见解和对细节技能的关注。这意味着，知道如何解决算法将使你在求职过程中具有竞争优势，因为即使不那么出名的公司也倾向于采用类似的评估方法。

外面有一个完整的世界

在我开始更加一致地解决算法后不久，我发现有大量的资源可以用来练习，学习最有效的策略来解决它们，并为面试做好心理准备(hackerank、 LeetCode、 CodingBat 和 GeeksForGeeks 只是其中的几个例子)。

这些网站通常会按照公司对算法进行分组，在活跃的博客中分享他们面试经验的详细总结，有时甚至会提供模拟面试问题作为高级计划的一部分。

例如，LeetCode 可以让你根据特定的公司和频率筛选出最重要的面试问题。你也可以选择你感觉舒服的难度级别(简单、中等和难度) :

 

现在有成百上千种不同的算法问题，这意味着要在不到10分钟的时间内识别出通用模式并编写出一个有效的解决方案，需要花费大量的时间和精力。

“如果一开始你真的很难解决这些问题，不要失望，这是完全正常的”

如果一开始你真的很难解决这些问题，不要失望，这是完全正常的。即使是更有经验的 Python 程序员也会发现，如果没有足够的培训，许多算法在短时间内就难以解决。

如果你的面试没有按照你预期的那样进行，而你刚刚开始解决算法问题，也不要失望。有些人为每天解决一些问题准备了好几个月，并且在能够搞定面试之前定期进行排练。

为了帮助您在您的培训过程中，下面我选择了10个算法(主要围绕字符串操作和数组) ，我已经看到一次又一次出现在电话编码采访。这些问题的层次主要是容易的，所以把它们当作一个好的起点。

请注意，我分享的每个问题的解决方案只是许多可以实现的潜在解决方案之一，通常是 BF (“蛮力”)解决方案。因此，您可以自由地编写自己版本的算法，尝试在运行时和使用内存之间找到正确的平衡。

操纵字符串

1. 反向整数

# Given an integer, return the integer with reversed digits.# Note: The integer could be either positive or negative. def solution(x): string = str(x) if string[0] == '-': return int('-'+string[:0:-1]) else: return int(string[::-1]) print(solution(-231))print(solution(345))

view rawreverse_int.py hosted with ❤ by GitHub

Output:
-132
543

一个热身运算法则，可以帮助你练习切片技巧。实际上，唯一棘手的问题是确保考虑到整数为负的情况。我见过这个问题以许多不同的方式出现，但它通常是更复杂的请求的起点。

2. 平均字长

# For a given sentence, return the average word length. # Note: Remember to remove punctuation first. sentence1 = "Hi all, my name is Tom...I am originally from Australia."sentence2 = "I need to work very hard to learn more about algorithms in Python!" def solution(sentence): for p in "!?',;.": sentence = sentence.replace(p, '') words = sentence.split() return round(sum(len(word) for word in words)/len(words),2) print(solution(sentence1))print(solution(sentence2))

view rawavg_words_length.py hosted with ❤ by GitHub

Output:
4.2
4.08

3. 添加字符串

# Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.# You must not use any built-in BigInteger library or convert the inputs to integer directly. #Notes:#Both num1 and num2 contains only digits 0-9.#Both num1 and num2 does not contain any leading zero. num1 = '364'num2 = '1836' # Approach 1: def solution(num1,num2): eval(num1) + eval(num2) return str(eval(num1) + eval(num2)) print(solution(num1,num2)) #Approach2 #Given a string of length one, the ord() function returns an integer representing the Unicode code point of the character #when the argument is a unicode object, or the value of the byte when the argument is an 8-bit string. def solution(num1, num2): n1, n2 = 0, 0 m1, m2 = 10**(len(num1)-1), 10**(len(num2)-1) for i in num1: n1 += (ord(i) - ord("0")) * m1 m1 = m1//10 for i in num2: n2 += (ord(i) - ord("0")) * m2 m2 = m2//10 return str(n1 + n2)print(solution(num1, num2))

Output:
2200
2200

我发现这两种方法同样有效: 第一种方法简洁，直观地使用 eval ()方法动态评估基于字符串的输入; 第二种方法聪明地使用 ord ()函数通过字符的 Unicode 代码点将两个字符串重新构建为实际数字。如果我真的必须在两者之间做出选择，我可能会选择第二种方法，因为它起初看起来更复杂，但在解决需要更高级的字符串处理和计算的“中等”和“硬”算法时，这种方法通常很方便。

4. 第一个独特的角色

# Given a string, find the first non-repeating character in it and return its index. # If it doesn't exist, return -1. # Note: all the input strings are already lowercase. #Approach 1def solution(s): frequency = {} for i in s: if i not in frequency: frequency[i] = 1 else: frequency[i] +=1 for i in range(len(s)): if frequency[s[i]] == 1: return i return -1 print(solution('alphabet'))print(solution('barbados'))print(solution('crunchy')) print('###') #Approach 2import collections def solution(s): # build hash map : character and how often it appears count = collections.Counter(s) # <-- gives back a dictionary with words occurrence count #Counter({'l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1}) # find the index for idx, ch in enumerate(s): if count[ch] == 1: return idx return -1 print(solution('alphabet'))print(solution('barbados'))print(solution('crunchy'))

Output:
1
2
1
###
1
2
1

在这种情况下，还提供了两种可能的解决方案，我猜想，如果您对算法还很陌生，那么第一种方法看起来有点熟悉，因为它从一个空字典开始构建为简单的计数器。

然而，从长远来看，理解第二种方法将对您有更大的帮助，这是因为在这个算法中，我只是使用了集合。计数器不是自己构建一个字符计数器，而是用枚举值替换范围(len (s)) ，这个函数可以帮助您更好地识别索引。

5. 有效回文

# Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.# The string will only contain lowercase characters a-z. s = 'radkar'def solution(s): for i in range(len(s)): t = s[:i] + s[i+1:] if t == t[::-1]: return True return s == s[::-1] solution(s)

Output:
True

“有效回文”问题是一个真正的经典，你可能会发现它在许多不同的口味反复。在这种情况下，任务是通过删除最多一个字符来检查天气情况，字符串与相反的对应字符匹配。当 s = ‘ radkar’函数通过排除‘ k’返回 Trueas 时，我们得到了单词‘ radar’ ，这是一个回文。

数组

6. 单调数组

# Given an array of integers, determine whether the array is monotonic or not.A = [6, 5, 4, 4] B = [1,1,1,3,3,4,3,2,4,2]C = [1,1,2,3,7] def solution(nums): return (all(nums[i] <= nums[i + 1] for i in range(len(nums) - 1)) or all(nums[i] >= nums[i + 1] for i in range(len(nums) - 1))) print(solution(A)) print(solution(B)) print(solution(C))

Output:
True
False
True

这是另一个经常被问到的问题，上面提供的解决方案非常优雅，因为它可以写成一行程序。一个数组是单调的当且仅当它是单调增加的或单调减少的，为了对它进行评估，上面的算法利用了返回 Trueif 一个迭代中的所有项都为真的 all ()函数，否则返回 False。如果可迭代对象为空，则 all ()函数也返回 True。

7. 把零移开

#Given an array nums, write a function to move all zeroes to the end of it while maintaining the relative order of #the non-zero elements. array1 = [0,1,0,3,12]array2 = [1,7,0,0,8,0,10,12,0,4] def solution(nums): for i in nums: if 0 in nums: nums.remove(0) nums.append(0) return nums solution(array1)solution(array2)

Output:
[1, 3, 12, 0, 0]
[1, 7, 8, 10, 12, 4, 0, 0, 0, 0]

当您使用数组时,。移走()及。Append ()方法是宝贵的盟友。在这个问题中，我使用它们首先删除属于原始数组的每个零，然后将它们附加到同一个数组的末尾。

8. 填补空白

# Given an array containing None values fill in the None values with most recent # non None value in the array array1 = [1,None,2,3,None,None,5,None] def solution(array): valid = 0 res = [] for i in nums: if i is not None: res.append(i) valid = i else: res.append(valid) return res solution(array1)

Output:
[1, 1, 2, 3, 3, 3, 5, 5]

在真实的采访中，我被要求解决这个问题好几次，两次的解决方案都必须包括边缘案例(为了简单起见，我在这里略去了)。理论上，这是一个很容易构建的算法，但是您需要清楚地知道您想用 for 循环实现什么，以及 if 语句，并且熟悉使用 None 值。

. 匹配和不匹配的单词

#Given two sentences, return an array that has the words that appear in one sentence and not#the other and an array with the words in common. sentence1 = 'We are really pleased to meet you in our city'sentence2 = 'The city was hit by a really heavy storm' def solution(sentence1, sentence2): set1 = set(sentence1.split()) set2 = set(sentence2.split()) return sorted(list(set1^set2)), sorted(list(set1&set2)) # ^ A.symmetric_difference(B), & A.intersection(B)

Output:
(['The','We','a','are','by','heavy','hit','in','meet','our',
'pleased','storm','to','was','you'],
['city', 'really'])

这个问题相当直观，但是这个算法利用了一些非常常见的集合运算，比如 set ()、 intersection ()或 & 和对称差分()或 ^ ，这些运算非常有用，可以使你的解决方案更加优雅。如果这是你第一次遇到他们，一定要检查这个页面。

10. 素数数组

Given k numbers which are less than n, return the set of prime number among them# Note: The task is to write a program to print all Prime numbers in an Interval.# Definition: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. n = 35def solution(n): prime_nums = [] for num in range(n): if num > 1: # all prime numbers are greater than 1 for i in range(2, num): if (num % i) == 0: # if the modulus == 0 is means that the number can be divided by a number preceding it break else: prime_nums.append(num) return prime_numssolution(n)

Output:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

我想用另一个经典的问题来结束这一部分。如果你同时熟悉素数定义和模运算，可以很容易地找到一个解决方案，即循环槽范围(n)。

总结

在这篇文章中，我分享了10个 Python 算法的解决方案，这些算法在编写面试流程时经常遇到问题。如果你正在准备与一家知名科技公司的面试，这篇文章是一个很好的起点，可以帮助你熟悉常见的算法模式，然后转向更复杂的问题。同时请注意，本文中的练习(以及他们的解决方案)是对 Leetcode 和 GeekForGeeks 上可用问题的轻微重新解释。我远非该领域的专家，因此我提出的解决方案只是指示性的。