全文共7259字，預計學習時長19分鐘
圖源：unsplash
如果你正打算面試包括美國五大科技公司在內的頂級公司，卻對Python還比較陌生，事不宜遲，你需要馬上開始練習算法。
不要重複我走過的彎路了！筆者剛開始學習時非常天真，儘管認為偶爾學習幾個算法非常有趣，但並沒有花大量時間練習，或者試圖實現更快更有效的解法。
在我看來，花一整天求解算法實在是太呆板了。算法在日常的工作環境中並沒有什麼實際的用處，長遠來看，它也不會給我帶來多少收入，但我錯了。
「了解算法將成為求職中的競爭優勢」
事實證明，這個想法（至少部分）是錯誤的：筆者仍然認為在算法上花費太多時間而忽視其他技能無法找到理想的工作。
但是現在筆者了解到，為了挑選程式設計師面對每天工作中的複雜問題，大公司必須採取一個標準化的選拔過程來考察候選人求解問題的能力和對細節的關注度。即使不太知名的公司也會採用這樣的評價標準，這意味著掌握算法將在求職過程中成為競爭優勢。
算法是一個全新的世界
開始投入精力學習算法求解後不久，筆者發現了大量可供練習使用的資源。利用這些資源網站（比如HackerRank, LeetCode, CodingBat和GeeksForGeeks）你可以學習最佳的解題策略，為面試做好心理準備。
除了練習面試中的熱門問題，這些網站也常常會按公司將算法分類，並且包含一些相關博客，人們在這些博客中詳細總結了自己的面試經驗。網站有時候還會提供模擬面試題作為用戶獎勵計劃的一部分。
例如，在Leetcode網站上，用戶可以根據特定公司和問題出現頻率篩選最熱門的面試問題，也可以自行選擇適合自己的難度等級（簡單，中等或困難）。
來源: https://leetcode.com/problemset/all/
網站上有數百種不同的算法問題，這意味著你需要耗費大量的時間和精力，才能在十分鐘內識別出問題的常見模式並編寫有效的解決方案。
「如果開始時感到非常困難，不要過於沮喪，這非常正常。」
在開始時感到非常困難是件很正常的事。如果沒有經過充分培訓，即使是經驗豐富的Python程式設計師也難以在短時間想到一些算法的解決方案。
如果面試結果難以滿足預期也不要失望，你的算法之旅才剛剛起步。有人會花幾個月的時間準備，每天解決幾個問題，並定期複習，最終才能搞定面試。
圖源：unsplash
筆者為你選擇了十個經常出現在電話面試中的算法（主要圍繞字符串操作和數組）。這些問題並不難，非常適合算法初學者。請注意，筆者為每個問題提供的解決方案只是諸多可行方案之一，通常是BF（暴力）算法。你也可以自由編寫自己的算法版本，在運行時間和內存消耗之間找到平衡點。
1. 翻轉整數（Reverse Integer）
# Given aninteger, return the integer with reversed digits. # Note: The integercould be either positive or negative. defsolution(x): string =str(x) if string[0] =='-': returnint('-'+string[:0:-1]) else: returnint(string[::-1]) print(solution(-231)) print(solution(345))這是一個用於練習切片技能的熱身訓練。唯一靈活的地方在於需要考慮輸入整數為負的情況。這類問題有許多不同的表現形式，但這個問題常常是更加複雜的要求的基礎。
2. 平均單詞長度（Average WordsLength）
# For a given sentence, return the averageword length. # Note: Remember toremove punctuation first. sentence1 ="Hi all, myname is Tom...I am originally from Australia." sentence2 ="I need towork very hard to learn more about algorithms in Python!" defsolution(sentence): for p in"!?',;.": sentence = sentence.replace(p, '') words = sentence.split() returnround(sum(len(word) for word in words)/len(words),2) print(solution(sentence1)) print(solution(sentence2)) Output: 4.2 4.08很多算法都要求程式設計師進行字符串運算，因此熟練掌握.replace()和.split()兩種方法非常重要。它們可以用來刪除不需要的字符、創建單詞列表，以便進行計算列表長度。
3. 添加文本（Add Strings）
# Given two non-negative integers num1 andnum2 represented as string, return the sum of num1 and num2. # You must not useany built-in BigInteger library or convert the inputs to integer directly. #Notes: #Both num1 and num2contains only digits 0-9. #Both num1 and num2does not contain any leading zero. num1 ='364' num2 ='1836' # Approach 1: defsolution(num1,num2): eval(num1) +eval(num2) returnstr(eval(num1) +eval(num2)) print(solution(num1,num2)) #Approach2 #Given a string oflength one, the ord() function returns an integer representing the Unicode codepoint of the character #when the argumentis a unicode object, or the value of the byte when the argument is an 8-bitstring. defsolution(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 returnstr(n1 + n2) print(solution(num1, num2)) Output: 2200 2200我認為兩種方法都很不錯：第一種十分簡潔，並且靈活使用eval()方法來計算基於字符串的輸出；第二種則明智地使用了ord()函數，把字符當作數字，通過Unicode編碼來重構兩個字符串。
如果一定要選一個，筆者可能會選擇第二種。因為它雖然乍看複雜，卻能實現更加複雜的字符串操作，方便地解決「中等」甚至「困難」的算法。
圖源：unsplash
4. 第一個獨特字符（First Unique Character）
# Given a string, find the firstnon-repeating character in it and return its index. # If it doesn'texist, return -1. # Note: all the input strings are already lowercase. #Approach 1 defsolution(s): frequency = {} for i in s: if i notin frequency: frequency[i] =1 else: frequency[i] +=1 for i inrange(len(s)): if frequency[s[i]] ==1: return i return-1 print(solution('alphabet')) print(solution('barbados')) print(solution('crunchy')) print('###') #Approach 2 import collections defsolution(s): # build hash map : character and how often it appears count = collections.Counter(s) # <-- gives backa dictionary with words occurrence count #Counter({'l':1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1}) # find the index for idx, ch inenumerate(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)), 前一個函數能夠更加優雅地判斷下標。
5. 有效迴文字符串（Valid Palindrome）
# Given a non-empty string s, you maydelete at most one character. Judge whether you can make it a palindrome. # The string willonly contain lowercase characters a-z. s ='radkar' defsolution(s): for i inrange(len(s)): t = s[:i] + s[i+1:] if t == t[::-1]: returnTrue return s == s[::-1] solution(s) Output: True有效迴文串問題非常經典，它將以許多不同的形式出現。在這個例子中，任務是判斷能否刪除一個字符從而將字符串變為迴文串。當輸入字符串為」radkar」時，函數返回True，因為通過刪除k可以將該字符串變為迴文串。
6. 單調數組（Monotonic Array）
# Given an array of integers, determinewhether 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] defsolution(nums): return (all(nums[i] <= nums[i +1] for i inrange(len(nums) -1)) or all(nums[i] >= nums[i +1] for i inrange(len(nums) -1))) print(solution(A)) print(solution(B)) print(solution(C)) Output: True False True這也是一個常見的問題，此處提供的算法十分優雅，只用一行就可以寫完。一個數組是單調的，若且唯若它單調增加或單調減少。為了判斷數組是否單調，這個算法利用了all()函數，這個函數在一輪疊代結果都為True時返回True，否則返回False。如果疊代對象為空返回值也為True。
7. 移動零（Move Zeroes）
#Given an array nums, write a function tomove all zeroes to the end of it while maintaining the relative order of #the non-zeroelements. array1 = [0,1,0,3,12] array2 = [1,7,0,0,8,0,10,12,0,4] defsolution(nums): for i in nums: if0in 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()方法非常好用。在這個問題中，筆者先使用它們移除了原數組中的所有0，然後把它們添加到原數組的末尾。
8. 填空（Fill The Blanks）
# Given an array containing None valuesfill in the None values with most recent # non None value inthe array array1 = [1,None,2,3,None,None,5,None] defsolution(array): valid =0 res = [] for i in nums: if i isnotNone: res.append(i) valid = i else: res.append(valid) return res solution(array1) Output: [1, 1, 2, 3, 3, 3, 5, 5]好幾次面試中我都遇到了這個問題，每一次解決方案中都要考慮邊界情況（此處我為了保證簡潔將其省略）。在草稿紙上構思這個算法很容易，但是必須明確使用for循環和if語句的目的，簡便地處理空值。
圖源：unsplash
9. 匹配和打亂單詞（Matched & Mismatched Words）
#Given two sentences, return an array thathas the words that appear in one sentence and not #the other and anarray with the words in common. sentence1 ='We are reallypleased to meet you in our city' sentence2 ='The city washit by a really heavy storm' defsolution(sentence1,sentence2): set1 =set(sentence1.split()) set2 =set(sentence2.split()) returnsorted(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() , intersection()或&運算符，以及symmetric_difference()或者^運算符。這些操作都能使算法更加優雅。
10.素數數組（Prime Numbers Array）
# Given k numbers which are less thann, return the set of prime number among them # Note: The task isto write a program to print all Prime numbers in an Interval. # Definition: Aprime number is a natural number greater than 1 that has no positive divisors otherthan 1 and itself. n =35 defsolution(n): prime_nums = [] for num inrange(n): if num >1: # all prime numbers are greater than 1 for i inrange(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_nums solution(n) Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]這也是一個經典問題。使用range(n)進行循環可以讓解法十分便捷，如果你熟悉素數定義和取模運算的話。
圖源：unsplash
如果正在準備知名科技公司的面試，這篇文章將幫助你開始熟悉一些常見的算法模式。請注意，本文中的練習（以及解決方案）只是Leetcode和GeekForGeeks網站上問題的簡化版本，僅供參考。了解這些基礎之後，你就可以逐漸轉向更複雜的問題啦。
留言點贊關注
我們一起分享AI學習與發展的乾貨
如轉載，請後台留言，遵守轉載規範