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

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

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

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

字符串處理

1. 整數(shù)逆位輸出

# 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

這是一個(gè)預(yù)熱算法，將幫助您練習(xí)切片技巧。實(shí)際上，唯一棘手的問題是確保您考慮整數(shù)為負(fù)數(shù)的情況。我已經(jīng)看到此問題以許多不同的方式呈現(xiàn)，但這通常有更復(fù)雜的要求。

2. 平均單詞長(zhǎng)度

# 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

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

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 我發(fā)現(xiàn)兩種方法同樣好用：第一種勝在簡(jiǎn)潔和直觀地使用eval()方法對(duì)基于字符串的輸入進(jìn)行動(dòng)態(tài)評(píng)估，而第二種勝在ord()功能的巧妙使用，來通過其字符的Unicode編碼將兩個(gè)字符串重構(gòu)成實(shí)際的數(shù)字。如果你真的要選擇其中的一種，我傾向于選擇第二種，因?yàn)樗谝谎劭瓷先ジ鼜?fù)雜，但是通常在解決需要更高級(jí)的字符串處理和計(jì)算的“中等”和“困難”算法問題當(dāng)中非常好用。 4. 第一個(gè)不同的字母

# 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 在這種情況下，也是有兩種潛在的解決方法，我猜測(cè)如果你是算法小白，第一種看起來更熟悉，因?yàn)樗菑目兆值溟_始構(gòu)建的簡(jiǎn)單計(jì)數(shù)器。 然而理解第二種方法將會(huì)從長(zhǎng)期來看幫助你更多，這是因?yàn)樵谶@個(gè)算法當(dāng)中我簡(jiǎn)單地使用了collection.Counter(s)代替創(chuàng)建字符計(jì)數(shù)器，并且用enumerate(s)代替了range(len(s))，enumerate(s)是一個(gè)可以幫助你更好地識(shí)別索引地址的函數(shù)。 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 “回文數(shù)列”問題是一個(gè)經(jīng)典問題，你可能會(huì)在很多不同場(chǎng)景都見到它。任務(wù)是檢查通過移除最多一個(gè)字符之后，字符串是否與它的逆向字符串相匹配。當(dāng)s=’radkar’時(shí)，函數(shù)返回True，因?yàn)槌ァ痥’之后，我們獲得單詞’radar’是一個(gè)回文序列。 數(shù)組6. 單調(diào)數(shù)組

# 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 這是另外一個(gè)常見的問題，以上提供的解決方法也是非常漂亮的，因?yàn)榭梢杂靡恍薪鉀Q。當(dāng)且僅當(dāng)某一數(shù)組單調(diào)遞增或單調(diào)遞減時(shí)才被稱為單調(diào)數(shù)組，為了評(píng)估它，以上算法利用了all()函數(shù)，當(dāng)所有可迭代項(xiàng)為真，則返回True，否則返回FALSE。如果迭代對(duì)象是空，all()函數(shù)也會(huì)返回True。 7. 移動(dòng)零

#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] 當(dāng)你在處理數(shù)組的時(shí)候，.remove()和.append()的方法是“黃金組合”。在這個(gè)問題當(dāng)中，我用他們首先將屬于原始數(shù)組的零移除，然后把移出的零填到同一個(gè)數(shù)組的末尾。 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] 在真實(shí)面試過程中，我有兩次都被問到這個(gè)問題。這兩次都需要包括邊界情況（我在這里為了簡(jiǎn)化省略了）。在論文當(dāng)中，這是一個(gè)易于創(chuàng)建的算法，但是你需要在腦海中有一個(gè)清晰的概念，你到底希望通過這個(gè)for循環(huán)和if語句實(shí)現(xiàn)什么，并且可以輕松地使用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']) 這個(gè)問題非常直觀，但是該算法利用了一些非常常見的set操作，例如set(), intersection() or &以及symmetric_difference() or ^這些方法都會(huì)讓你的解題過程更漂亮。如果你是第一次見到它們，請(qǐng)查看一下這個(gè)網(wǎng)址：https://www.programiz.com/python-programming/set 10. 質(zhì)數(shù)數(shù)據(jù)

# 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] 我想用另外一個(gè)經(jīng)典問題來結(jié)束這一部分。如果你熟悉質(zhì)數(shù)的定義和模運(yùn)算，就可以輕而易舉地找到遍歷range(n)的解法。 結(jié)論 本文當(dāng)中我分享了10個(gè)在編程面試當(dāng)中常被問到的Python算法。如果你正在準(zhǔn)備一家知名技術(shù)公司的面試，這篇文章對(duì)你熟悉常見算法模式并且循序漸進(jìn)到更復(fù)雜問題來說，是一個(gè)好的開始。順便請(qǐng)注意本文當(dāng)中的練習(xí)（及其解決方案）只是針對(duì)Leetcode和GeekforGeeks上存在的問題稍微做了重新解釋。在這個(gè)領(lǐng)域我還遠(yuǎn)非達(dá)得到一個(gè)專家的水平，因此我呈現(xiàn)的解決方法僅僅是指示性的。

責(zé)任編輯：xj

原文標(biāo)題：在Python編程面試前需要學(xué)會(huì)的10個(gè)算法

文章出處：【微信公眾號(hào)：數(shù)據(jù)分析與開發(fā)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。