Auto Byte

Science AI

AnBento作者陈丹校对陈超翻译

# 在Python编程面试前需要学会的10个算法（附代码）

“知道如何解决算法问题将会成为你在找工作过程中极有竞争力的优势”

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

“如果你一开始感觉到解决这些算法问题很困难千万不要灰心丧气，这是很正常的事。”

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

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."

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

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

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 1
def 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('crunchy'))

print('###')

#Approach 2
import 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('crunchy'))

Output:

1

2

1

###

1

2

1

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.

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

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

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]

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]

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:

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 = 35
def 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_nums
solution(n)

Output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

10 Algorithms To Solve Before your Python Coding Interview

https://towardsdatascience.com/10-algorithms-to-solve-before-your-python-coding-interview-feb74fb9bc27

THU数据派

THU数据派"基于清华，放眼世界"，以扎实的理工功底闯荡“数据江湖”。发布全球大数据资讯，定期组织线下活动，分享前沿产业动态。了解清华大数据，敬请关注姐妹号“数据派THU”。