在本文中，我提出并分享了 FAANG 訪談中經(jīng)常出現(xiàn)的一些基本算法的解決方案

為什么實(shí)踐算法是關(guān)鍵？

如果你是 Python 的新手，并且計(jì)劃開始面試頂級公司(包括 FAANG) ，聽聽這個(gè): 你現(xiàn)在就需要開始練習(xí)算法。

不要像我剛開始解決這些問題時(shí)那樣天真。盡管我認(rèn)為時(shí)不時(shí)破解幾個(gè)算法很有趣，但我從來沒有花太多時(shí)間練習(xí)，花更少的時(shí)間來實(shí)現(xiàn)一個(gè)更快或更高效的解決方案。就我個(gè)人而言，我在想，在一天結(jié)束的時(shí)候，整天解決算法有點(diǎn)太書呆子氣了，它在實(shí)際的日常工作環(huán)境中并沒有真正的實(shí)際用途，而且從長遠(yuǎn)來看，它也不會(huì)給我?guī)矶嗌偈杖搿?/p>

“知道如何解決算法將給你在求職過程中帶來競爭優(yōu)勢”

好吧... 我錯(cuò)了(至少部分錯(cuò)了) : 我仍然認(rèn)為，在算法上花費(fèi)太多時(shí)間而不關(guān)注其他技能，并不足以讓你找到理想的工作，但我明白，既然復(fù)雜的問題出現(xiàn)在日常工作中，作為一名程序員，大公司必須找到一個(gè)標(biāo)準(zhǔn)化的流程，以收集求職者解決問題的見解和對細(xì)節(jié)技能的關(guān)注。這意味著，知道如何解決算法將使你在求職過程中具有競爭優(yōu)勢，因?yàn)榧词共荒敲闯雒墓疽矁A向于采用類似的評估方法。

外面有一個(gè)完整的世界

在我開始更加一致地解決算法后不久，我發(fā)現(xiàn)有大量的資源可以用來練習(xí)，學(xué)習(xí)最有效的策略來解決它們，并為面試做好心理準(zhǔn)備(hackerank、 LeetCode、 CodingBat 和 GeeksForGeeks 只是其中的幾個(gè)例子)。

這些網(wǎng)站通常會(huì)按照公司對算法進(jìn)行分組，在活躍的博客中分享他們面試經(jīng)驗(yàn)的詳細(xì)總結(jié)，有時(shí)甚至?xí)峁┠M面試問題作為高級計(jì)劃的一部分。

例如，LeetCode 可以讓你根據(jù)特定的公司和頻率篩選出最重要的面試問題。你也可以選擇你感覺舒服的難度級別(簡單、中等和難度) :

現(xiàn)在有成百上千種不同的算法問題，這意味著要在不到10分鐘的時(shí)間內(nèi)識別出通用模式并編寫出一個(gè)有效的解決方案，需要花費(fèi)大量的時(shí)間和精力。

“如果一開始你真的很難解決這些問題，不要失望，這是完全正常的”

如果一開始你真的很難解決這些問題，不要失望，這是完全正常的。即使是更有經(jīng)驗(yàn)的 Python 程序員也會(huì)發(fā)現(xiàn)，如果沒有足夠的培訓(xùn)，許多算法在短時(shí)間內(nèi)就難以解決。

如果你的面試沒有按照你預(yù)期的那樣進(jìn)行，而你剛剛開始解決算法問題，也不要失望。有些人為每天解決一些問題準(zhǔn)備了好幾個(gè)月，并且在能夠搞定面試之前定期進(jìn)行排練。

為了幫助您在您的培訓(xùn)過程中，下面我選擇了10個(gè)算法(主要圍繞字符串操作和數(shù)組) ，我已經(jīng)看到一次又一次出現(xiàn)在電話編碼采訪。這些問題的層次主要是容易的，所以把它們當(dāng)作一個(gè)好的起點(diǎn)。

請注意，我分享的每個(gè)問題的解決方案只是許多可以實(shí)現(xiàn)的潛在解決方案之一，通常是 BF (“蠻力”)解決方案。因此，您可以自由地編寫自己版本的算法，嘗試在運(yùn)行時(shí)和使用內(nèi)存之間找到正確的平衡。

操縱字符串

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))

view rawreverse_int.py hosted with ? by GitHub

Output:
-132
543

一個(gè)熱身運(yùn)算法則，可以幫助你練習(xí)切片技巧。實(shí)際上，唯一棘手的問題是確保考慮到整數(shù)為負(fù)的情況。我見過這個(gè)問題以許多不同的方式出現(xiàn)，但它通常是更復(fù)雜的請求的起點(diǎn)。

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

我發(fā)現(xiàn)這兩種方法同樣有效: 第一種方法簡潔，直觀地使用 eval ()方法動(dòng)態(tài)評估基于字符串的輸入; 第二種方法聰明地使用 ord ()函數(shù)通過字符的 Unicode 代碼點(diǎn)將兩個(gè)字符串重新構(gòu)建為實(shí)際數(shù)字。如果我真的必須在兩者之間做出選擇，我可能會(huì)選擇第二種方法，因?yàn)樗鸪蹩雌饋砀鼜?fù)雜，但在解決需要更高級的字符串處理和計(jì)算的“中等”和“硬”算法時(shí)，這種方法通常很方便。

4. 第一個(gè)獨(dú)特的角色

# 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

在這種情況下，還提供了兩種可能的解決方案，我猜想，如果您對算法還很陌生，那么第一種方法看起來有點(diǎn)熟悉，因?yàn)樗鼜囊粋€(gè)空字典開始構(gòu)建為簡單的計(jì)數(shù)器。

然而，從長遠(yuǎn)來看，理解第二種方法將對您有更大的幫助，這是因?yàn)樵谶@個(gè)算法中，我只是使用了集合。計(jì)數(shù)器不是自己構(gòu)建一個(gè)字符計(jì)數(shù)器，而是用枚舉值替換范圍(len (s)) ，這個(gè)函數(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

“有效回文”問題是一個(gè)真正的經(jīng)典，你可能會(huì)發(fā)現(xiàn)它在許多不同的口味反復(fù)。在這種情況下，任務(wù)是通過刪除最多一個(gè)字符來檢查天氣情況，字符串與相反的對應(yīng)字符匹配。當(dāng) s = ‘ radkar’函數(shù)通過排除‘ k’返回 Trueas 時(shí)，我們得到了單詞‘ 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è)經(jīng)常被問到的問題，上面提供的解決方案非常優(yōu)雅，因?yàn)樗梢詫懗梢恍谐绦?。一個(gè)數(shù)組是單調(diào)的當(dāng)且僅當(dāng)它是單調(diào)增加的或單調(diào)減少的，為了對它進(jìn)行評估，上面的算法利用了返回 Trueif 一個(gè)迭代中的所有項(xiàng)都為真的 all ()函數(shù)，否則返回 False。如果可迭代對象為空，則 all ()函數(shù)也返回 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]

當(dāng)您使用數(shù)組時(shí),。移走()及。Append ()方法是寶貴的盟友。在這個(gè)問題中，我使用它們首先刪除屬于原始數(shù)組的每個(gè)零，然后將它們附加到同一個(gè)數(shù)組的末尾。

8. 填補(bǔ)空白

# 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è)問題好幾次，兩次的解決方案都必須包括邊緣案例(為了簡單起見，我在這里略去了)。理論上，這是一個(gè)很容易構(gòu)建的算法，但是您需要清楚地知道您想用 for 循環(huán)實(shí)現(xiàn)什么，以及 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'])

這個(gè)問題相當(dāng)直觀，但是這個(gè)算法利用了一些非常常見的集合運(yùn)算，比如 set ()、 intersection ()或 & 和對稱差分()或 ^ ，這些運(yùn)算非常有用，可以使你的解決方案更加優(yōu)雅。如果這是你第一次遇到他們，一定要檢查這個(gè)頁面。

10. 素?cái)?shù)數(shù)組

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é)束這一部分。如果你同時(shí)熟悉素?cái)?shù)定義和模運(yùn)算，可以很容易地找到一個(gè)解決方案，即循環(huán)槽范圍(n)。

總結(jié)

在這篇文章中，我分享了10個(gè) Python 算法的解決方案，這些算法在編寫面試流程時(shí)經(jīng)常遇到問題。如果你正在準(zhǔn)備與一家知名科技公司的面試，這篇文章是一個(gè)很好的起點(diǎn)，可以幫助你熟悉常見的算法模式，然后轉(zhuǎn)向更復(fù)雜的問題。同時(shí)請注意，本文中的練習(xí)(以及他們的解決方案)是對 Leetcode 和 GeekForGeeks 上可用問題的輕微重新解釋。我遠(yuǎn)非該領(lǐng)域的專家，因此我提出的解決方案只是指示性的。