在本文中，我提出并分享了 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 上可用問題的輕微重新解釋。我遠非該領域的專家，因此我提出的解決方案只是指示性的。