為什么練習算法是關鍵？ 如果你是Python新手，并且打算面試頂尖公司（FAANG），聽著，你需要從現在開始就好好練習算法。 不要像我第一次練習算法時那么天真。盡管我認為從早到晚死磕算法很有趣，但是我從來沒有花過太多時間練習，甚至更少花時間去使用快捷、高效的解決方法。在我看來，我認為花一天的時間解決算法問題有點太傻了，而且在實際工作環境中很不適用，而且長期來看這也不會給我帶來多大的收益。 “知道如何解決算法問題將會成為你在找工作過程中極有競爭力的優勢” 好吧……我錯了（至少在某種程度上來說）：我仍然認為花費太多時間在算法上而不注重其他技能遠遠不能讓你找到理想的工作，但是我知道作為一個程序員，復雜的問題總會自己出現在日常的工作當中，因此大公司不得不找到一個標準化的流程來收集應聘者在問題解決和細節技能關注的見解。這意味著知道如何解決算法問題將會成為在找工作的你的一個競爭優勢，甚至不那么出名的公司也傾向于采納這樣的評估方法。 那里有一整個世界 在我開始更專注地解決算法問題之后不久，我發現有很多資源可供練習、學習最有效的策略以及為面試做好充足的心理準備，比如以下幾個例子：

HackerRank：

https://www.hackerrank.com/interview/interview-preparation-kit

LeetCode：

https://leetcode.com/explore/interview/card/top-interview-questions-easy/

CodingBat ：

https://codingbat.com/python

GeeksForGeeks：

https://www.geeksforgeeks.org/python-programming-language/?ref=leftbar

練習頂級的面試問題，這些網站通常會按照公司對算法問題進行分組，并且把人們分享詳細的面試經驗總結的活躍博客嵌入進去，有時也會提供模擬面試問題作為優選計劃（premium plans）的一部分。 例如，LeetCode可以通過特定的公司以及頻率篩選頂尖的面試問題。你也可以選擇自己覺得合適的試題難度（簡單、中等、困難）：

來源：https://leetcode.com/problemset/all/ 那里有上百道不同的算法問題，這意味著，要做到能夠識別出常見的模式并在10分鐘以內得出有效的解決方法需要大量的時間和投入。 “如果你一開始感覺到解決這些算法問題很困難千萬不要灰心喪氣，這是很正常的事。” 如果你一開始感覺到解決這些算法問題很困難千萬不要灰心喪氣，這是很正常的事。即使有經驗的Python程序員在沒有充分的訓練之前，也會感覺到有很多算法題很難解。 如果你的面試不如預期并且你才剛開始刷題，也不要沮喪。有很多人會刷好幾個月的算法題，并且做有規律地復習才能最終拿下一場面試。 為了在你的練習過程中幫到你，我精選了10個在電話面試過程中反復出現的算法（主要是關于字符串操作和數組）。這些問題的難度大都比較容易，所以這會是一個很好的開始。 請注意我給出的每個問題的解答僅僅是許多潛在解決方法的其中之一，通常是一個蠻力解法（“Brute Force”）。因此請自主選擇你自己的解法，嘗試在運行時間和所用內存之間找到適當的平衡。

字符串處理

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))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))Output:4.2 4.08

要求使用字符串來進行一些簡單計算的算法非常常見，因此你需要對.replace()和.split()這些方法非常熟悉，這樣才能幫助你刪除不想要的字符并且創建單詞長度容易計算和求和的單詞表。

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 在這種情況下，也是有兩種潛在的解決方法，我猜測如果你是算法小白，第一種看起來更熟悉，因為它是從空字典開始構建的簡單計數器。 然而理解第二種方法將會從長期來看幫助你更多，這是因為在這個算法當中我簡單地使用了collection.Counter(s)代替創建字符計數器，并且用enumerate(s)代替了range(len(s))，enumerate(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’時，函數返回True，因為除去’k’之后，我們獲得單詞’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 這是另外一個常見的問題，以上提供的解決方法也是非常漂亮的，因為可以用一行解決。當且僅當某一數組單調遞增或單調遞減時才被稱為單調數組，為了評估它，以上算法利用了all()函數，當所有可迭代項為真，則返回True，否則返回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] 當你在處理數組的時候，.remove()和.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值。 9. 匹配和失匹配單詞

#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) print(solution(sentence1, sentence2))Output:(['The','We','a','are','by','heavy','hit','in','meet','our','pleased','storm','to','was','you'],['city', 'really']) 這個問題非常直觀，但是該算法利用了一些非常常見的set操作，例如set(), intersection() or &以及symmetric_difference() or ^這些方法都會讓你的解題過程更漂亮。如果你是第一次見到它們，請查看一下這個網址：https://www.programiz.com/python-programming/set 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] 我想用另外一個經典問題來結束這一部分。如果你熟悉質數的定義和模運算，就可以輕而易舉地找到遍歷range(n)的解法。 結論 本文當中我分享了10個在編程面試當中常被問到的Python算法。如果你正在準備一家知名技術公司的面試，這篇文章對你熟悉常見算法模式并且循序漸進到更復雜問題來說，是一個好的開始。順便請注意本文當中的練習（及其解決方案）只是針對Leetcode和GeekforGeeks上存在的問題稍微做了重新解釋。在這個領域我還遠非達得到一個專家的水平，因此我呈現的解決方法僅僅是指示性的。

責任編輯：xj

原文標題：在Python編程面試前需要學會的10個算法

文章出處：【微信公眾號：數據分析與開發】歡迎添加關注！文章轉載請注明出處。