参加顶级科技公司面试前需要掌握的10个基本算法|顶级科技公司|算法|字符串

图源：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.24.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:22002200

　　我认为两种方法都很不错：第一种十分简洁，并且灵活使用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) # #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:121###121

　　这个例子中也提供了两个可行的算法。如果你刚刚接触算法，第一种方式看起来应该比较熟悉，它使用一个空字典创建了计数器。

　　然而，理解第二种算法将更加长远地帮助读者，因为它仅仅使用了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] all(nums[i] >= nums[i +1] for i inrange(len(nums) -1))) print(solution(A)) print(solution(B)) print(solution(C))

　　Output:TrueFalseTrue

　　这也是一个常见的问题，此处提供的算法十分优雅，只用一行就可以写完。一个数组是单调的，当且仅当它单调增加或单调减少。为了判断数组是否单调，这个算法利用了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)进行循环可以让解法十分便捷，如果你熟悉素数定义和取模运算的话。