Data Scientist Python Coding 题整理（持续更新

.1point3acres
这几年看了不少DS相关复习资料（地里面筋和其他网上资料），也参加了一些面试，积累了一点General Data Scientist岗位的Python Coding题目。目前看来General DS岗位的Python Coding题目分为以下五类

1. Leetcode easy难度的题目，主要考察Array，String，Hashtable，Searching & Sorting，和简单DP。Tree，Linked List和Graph我从来没见过。

2. Simulation，比如抽样

3. Scripting，比如读取一个文件，存成dictionary或者list of list，再进行相关操作

4. 一些机器学习算法实现

5. 统计计算类编程

注意如果是面MLE的话，对coding的要求就是SDE的要求了，General Data Scientist的Coding要求不适用

每一题会给出题目简单描述和相关代码（我不保证自己的代码一定对），此贴会一直慢慢更新，也欢迎其他同学提出意见和贡献题目。

1. Weighted Sampling

You are given n numbers as well as probabilities p_0, p_1, ... , p_{n - 1}, which sum up to 1, how would you generate one of the n numbers according to the specified probabilities?

For example, if the numbers are 3, 5, 7, 11, and the probabilities are 9/18, 6/18, 2/18, 1/18, then 100000 calls to your program, 3 should appear roughly 500000 times,
5 should appear roughly 333333 times, 7 should appear roughly 111111 times, and 11 should appear roughly 55555 times.

1. import itertools, bisect, random
   
2. 
   
3. def weighted_sample(values, probs):
   
4.     cumulative_probs = [0.0] + list(itertools.accumulate(probs))
   
5.     interval_idx = bisect.bisect(cumulative_probs, random.random()) - 1
   
6.     return values[interval_idx]

复制代码

1. values = [3, 5, 7, 11]
   
2. probs = [9/18, 6/18, 2/18, 1/18]
   
3. 
   
4. result = {}
   
5. 
   
6. for _ in range(1000000):
   
7.     value = weighted_sample(values, probs)
   
8.     result[value] = result.get(value, 0) + 1
   
9.    
   
10. print(result)
    
11. 
    
12. # {3: 500175, 5: 333546, 7: 110936, 11: 55343}

复制代码

补充内容 (2021-2-3 04:30):
"then 100000 calls" 更正到 "then 1000000 calls", 感谢Jack2020u同学提醒

18. Implement the K-means algorithm

一些比较简单但是重要的机器学习算法需要会描述算法并且写出代码，K-means算法是常考题

K-means算法简介：
https://jakevdp.github.io/Python ... /05.11-k-means.html

Elbow method:
https://en.wikipedia.org/wiki/Elbow_method_(clustering)

Silhouette analysis:
https://scikit-learn.org/stable/ ... uette_analysis.html

K-means ++:
https://en.wikipedia.org/wiki/K-means%2B%2B

Feature scaling:
https://datascience.stackexchang ... -stage#:~:text=Yes.,KGs%20before%20calculating%20the%20distance.

1. import random
   
2. import numpy as np
   
3. from collections import defaultdict
   
4. 
   
5. def k_means(X, k=5, max_iter=1000):
   
6.     """
   
7.     Args:
   
8.     - X - data matrix
   
9.     - k - number of clusters
   
10.     - max_iter - maximum iteratations
    
11. 
    
12.     Returns:
    
13.     - clusters - dict mapping cluster centers (tuples) to
    
14.                  observations (list of datapoints, each datapoint is a numpy array)
    
15.     """
    
16.     # initialize cluster centers by random sample k rows of X
    
17.     # random.seed(42)
    
18.     centers = [tuple(pt) for pt in random.sample(list(X), k)]
    
19.    
    
20.     # begin iterations
    
21.     for i in range(max_iter):
    
22.         clusters = defaultdict(list)
    
23.         
    
24.         # E-Step: assign points to the nearest cluster center
    
25.         for datapoint in X:
    
26.             dists = [np.linalg.norm(datapoint - center) for center in centers]
    
27.             center = centers[np.argmin(dists)]
    
28.             clusters[center].append(datapoint)
    
29.         
    
30.         # M-Step: average the cluster datapoints to calculate the new centers
    
31.         new_centers = []
    
32.         for center, datapoints in clusters.items():
    
33.             new_center = np.mean(datapoints, axis=0)
    
34.             new_centers.append(tuple(new_center))
    
35.         
    
36.         # stop iteration if the centers stop changing
    
37.         if set(new_centers) == set(centers):
    
38.             break
    
39. 
    
40.         # update centers
    
41.         centers = new_centers
    
42. 
    
43.     return clusters
    
44. 
    
45. 
    
46. # use the iris dataset as example
    
47. from sklearn import datasets
    
48. iris = datasets.load_iris()
    
49. X = iris.data
    
50. 
    
51. X_clustered = k_means(X, k=5, max_iter=1000)
    
52. X_clustered
    
53. 
    
54. 
    
55. # Output:
    
56. # defaultdict(list,
    
57. #             {(5.242857142857143,
    
58. #               3.6678571428571423,
    
59. #               1.5,
    
60. #               0.28214285714285714): [array([5.1, 3.5, 1.4, 0.2]),
    
61. #               array([5. , 3.6, 1.4, 0.2]),
    
62. #               array([5.4, 3.9, 1.7, 0.4]),
    
63. #               array([5. , 3.4, 1.5, 0.2]),
    
64. #               array([5.4, 3.7, 1.5, 0.2]),
    
65. #               array([5.8, 4. , 1.2, 0.2]),
    
66. #               array([5.7, 4.4, 1.5, 0.4]),
    
67. #               array([5.4, 3.9, 1.3, 0.4]),
    
68. #               array([5.1, 3.5, 1.4, 0.3]),
    
69. #               array([5.7, 3.8, 1.7, 0.3]),
    
70. #               array([5.1, 3.8, 1.5, 0.3]),
    
71. #               array([5.4, 3.4, 1.7, 0.2]),
    
72. #               array([5.1, 3.7, 1.5, 0.4]),
    
73. #               array([5.1, 3.3, 1.7, 0.5]),
    
74. #               array([5. , 3.4, 1.6, 0.4]),
    
75. #               array([5.2, 3.5, 1.5, 0.2]),
    
76. #               array([5.2, 3.4, 1.4, 0.2]),
    
77. #               array([5.4, 3.4, 1.5, 0.4]),
    
78. #               array([5.2, 4.1, 1.5, 0.1]),
    
79. #               array([5.5, 4.2, 1.4, 0.2]),
    
80. #               array([5.5, 3.5, 1.3, 0.2]),
    
81. #               array([4.9, 3.6, 1.4, 0.1]),
    
82. #               array([5.1, 3.4, 1.5, 0.2]),
    
83. #               array([5. , 3.5, 1.3, 0.3]),
    
84. #               array([5. , 3.5, 1.6, 0.6]),
    
85. #               array([5.1, 3.8, 1.9, 0.4]),
    
86. #               array([5.1, 3.8, 1.6, 0.2]),
    
87. #               array([5.3, 3.7, 1.5, 0.2])],
    
88. #              (4.704545454545454,
    
89. #               3.122727272727273,
    
90. #               1.4136363636363638,
    
91. #               0.2000000000000001): [array([4.9, 3. , 1.4, 0.2]),
    
92. #               array([4.7, 3.2, 1.3, 0.2]),
    
93. #               array([4.6, 3.1, 1.5, 0.2]),
    
94. #               array([4.6, 3.4, 1.4, 0.3]),
    
95. #               array([4.4, 2.9, 1.4, 0.2]),
    
96. #               array([4.9, 3.1, 1.5, 0.1]),
    
97. #               array([4.8, 3.4, 1.6, 0.2]),
    
98. #               array([4.8, 3. , 1.4, 0.1]),
    
99. #               array([4.3, 3. , 1.1, 0.1]),
    
100. #               array([4.6, 3.6, 1. , 0.2]),
     
101. #               array([4.8, 3.4, 1.9, 0.2]),
     
102. #               array([5. , 3. , 1.6, 0.2]),
     
103. #               array([4.7, 3.2, 1.6, 0.2]),
     
104. #               array([4.8, 3.1, 1.6, 0.2]),
     
105. #               array([4.9, 3.1, 1.5, 0.2]),
     
106. #               array([5. , 3.2, 1.2, 0.2]),
     
107. #               array([4.4, 3. , 1.3, 0.2]),
     
108. #               array([4.5, 2.3, 1.3, 0.3]),
     
109. #               array([4.4, 3.2, 1.3, 0.2]),
     
110. #               array([4.8, 3. , 1.4, 0.3]),
     
111. #               array([4.6, 3.2, 1.4, 0.2]),
     
112. #               array([5. , 3.3, 1.4, 0.2])],
     
113. #              (6.23658536585366,
     
114. #               2.8585365853658535,
     
115. #               4.807317073170731,
     
116. #               1.6219512195121943): [array([7. , 3.2, 4.7, 1.4]),
     
117. #               array([6.4, 3.2, 4.5, 1.5]),
     
118. #               array([6.9, 3.1, 4.9, 1.5]),
     
119. #               array([6.5, 2.8, 4.6, 1.5]),
     
120. #               array([6.3, 3.3, 4.7, 1.6]),
     
121. #               array([6.6, 2.9, 4.6, 1.3]),
     
122. #               array([6.1, 2.9, 4.7, 1.4]),
     
123. #               array([6.7, 3.1, 4.4, 1.4]),
     
124. #               array([5.6, 3. , 4.5, 1.5]),
     
125. #               array([6.2, 2.2, 4.5, 1.5]),
     
126. #               array([5.9, 3.2, 4.8, 1.8]),
     . 1point 3acres
127. #               array([6.3, 2.5, 4.9, 1.5]),
     
128. #               array([6.1, 2.8, 4.7, 1.2]),
     
129. #               array([6.4, 2.9, 4.3, 1.3]),
     
130. #               array([6.6, 3. , 4.4, 1.4]),
     
131. #               array([6.8, 2.8, 4.8, 1.4]),
     . 1point 3 acres
132. #               array([6.7, 3. , 5. , 1.7]),
     
133. #               array([6. , 2.9, 4.5, 1.5]),
     
134. #               array([6. , 2.7, 5.1, 1.6]),
     
135. #               array([6. , 3.4, 4.5, 1.6]),
     
136. #               array([6.7, 3.1, 4.7, 1.5]),
     
137. #               array([6.3, 2.3, 4.4, 1.3]),
     
138. #               array([6.1, 3. , 4.6, 1.4]),
     
139. #               array([6.2, 2.9, 4.3, 1.3]),
     
140. #               array([5.8, 2.7, 5.1, 1.9]),
     
141. #               array([6.5, 3.2, 5.1, 2. ]),
     
142. #               array([6.4, 2.7, 5.3, 1.9]),
     
143. #               array([5.7, 2.5, 5. , 2. ]),
     
144. #               array([5.8, 2.8, 5.1, 2.4]),
     
145. #               array([6. , 2.2, 5. , 1.5]),
     
146. #               array([5.6, 2.8, 4.9, 2. ]),
     
147. #               array([6.3, 2.7, 4.9, 1.8]),
     
148. #               array([6.2, 2.8, 4.8, 1.8]),
     
149. #               array([6.1, 3. , 4.9, 1.8]),
     
150. #               array([6.3, 2.8, 5.1, 1.5]),
     
151. #               array([6.1, 2.6, 5.6, 1.4]),
     
152. #               array([6. , 3. , 4.8, 1.8]),
     
153. #               array([5.8, 2.7, 5.1, 1.9]),
     
154. #               array([6.3, 2.5, 5. , 1.9]),
     
155. #               array([6.5, 3. , 5.2, 2. ]),
     
156. #               array([5.9, 3. , 5.1, 1.8])],
     
157. #              (5.529629629629629,
     
158. #               2.6222222222222222,
     
159. #               3.940740740740741,
     
160. #               1.2185185185185188): [array([5.5, 2.3, 4. , 1.3]),
     
161. #               array([5.7, 2.8, 4.5, 1.3]),
     
162. #               array([4.9, 2.4, 3.3, 1. ]),
     
163. #               array([5.2, 2.7, 3.9, 1.4]),
     
164. #               array([5. , 2. , 3.5, 1. ]),
     
165. #               array([5.9, 3. , 4.2, 1.5]),
     
166. #               array([6. , 2.2, 4. , 1. ]),
     
167. #               array([5.6, 2.9, 3.6, 1.3]),
     
168. #               array([5.8, 2.7, 4.1, 1. ]),
     
169. #               array([5.6, 2.5, 3.9, 1.1]),
     
170. #               array([6.1, 2.8, 4. , 1.3]),
     
171. #               array([5.7, 2.6, 3.5, 1. ]),
     
172. #               array([5.5, 2.4, 3.8, 1.1]),
     
173. #               array([5.5, 2.4, 3.7, 1. ]),
     
174. #               array([5.8, 2.7, 3.9, 1.2]),
     
175. #               array([5.4, 3. , 4.5, 1.5]),
     
176. #               array([5.6, 3. , 4.1, 1.3]),
     
177. #               array([5.5, 2.5, 4. , 1.3]),
     
178. #               array([5.5, 2.6, 4.4, 1.2]),
     
179. #               array([5.8, 2.6, 4. , 1.2]),
     
180. #               array([5. , 2.3, 3.3, 1. ]),
     
181. #               array([5.6, 2.7, 4.2, 1.3]),
     
182. #               array([5.7, 3. , 4.2, 1.2]),
     
183. #               array([5.7, 2.9, 4.2, 1.3]),
     
184. #               array([5.1, 2.5, 3. , 1.1]),
     
185. #               array([5.7, 2.8, 4.1, 1.3]),
     
186. #               array([4.9, 2.5, 4.5, 1.7])],
     
187. #              (6.9125000000000005,
     
188. #               3.099999999999999,
     
189. #               5.846874999999999,
     
190. #               2.1312499999999996): [array([6.3, 3.3, 6. , 2.5]),
     
191. #               array([7.1, 3. , 5.9, 2.1]),
     
192. #               array([6.3, 2.9, 5.6, 1.8]),
     
193. #               array([6.5, 3. , 5.8, 2.2]),
     
194. #               array([7.6, 3. , 6.6, 2.1]),
     
195. #               array([7.3, 2.9, 6.3, 1.8]),
     
196. #               array([6.7, 2.5, 5.8, 1.8]),
     
197. #               array([7.2, 3.6, 6.1, 2.5]),
     
198. #               array([6.8, 3. , 5.5, 2.1]),
     
199. #               array([6.4, 3.2, 5.3, 2.3]),
     
200. #               array([6.5, 3. , 5.5, 1.8]),
     
201. #               array([7.7, 3.8, 6.7, 2.2]),
     
202. #               array([7.7, 2.6, 6.9, 2.3]),
     
203. #               array([6.9, 3.2, 5.7, 2.3]),
     
204. #               array([7.7, 2.8, 6.7, 2. ]),
     
205. #               array([6.7, 3.3, 5.7, 2.1]),
     
206. #               array([7.2, 3.2, 6. , 1.8]),
     
207. #               array([6.4, 2.8, 5.6, 2.1]),
     
208. #               array([7.2, 3. , 5.8, 1.6]),
     
209. #               array([7.4, 2.8, 6.1, 1.9]),
     
210. #               array([7.9, 3.8, 6.4, 2. ]),
     
211. #               array([6.4, 2.8, 5.6, 2.2]),
     
212. #               array([7.7, 3. , 6.1, 2.3]),
     
213. #               array([6.3, 3.4, 5.6, 2.4]),
     
214. #               array([6.4, 3.1, 5.5, 1.8]),
     
215. #               array([6.9, 3.1, 5.4, 2.1]),
     
216. #               array([6.7, 3.1, 5.6, 2.4]),
     
217. #               array([6.9, 3.1, 5.1, 2.3]),
     
218. #               array([6.8, 3.2, 5.9, 2.3]),
     
219. #               array([6.7, 3.3, 5.7, 2.5]),
     
220. #               array([6.7, 3. , 5.2, 2.3]),
     
221. #               array([6.2, 3.4, 5.4, 2.3])]})

复制代码

31. Merge k sorted arraysGiven k sorted arrays, create a combined list while maintaining sorted order.(这道题和leetcode 23其实是一道题，不过leetcod里面是list of linkedLists)

Example:
Input: arrs = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]

1. # Use Python heapq module
   
2. # T: O(nlogk)
   
3. # S: O(n)
   
4. 
   
5. import heapq
   
6. 
   
7. class Solution:
   
8.     def merge_k_arrays(self, arrs):
   
9.         if not arrs or len(arrs) == 0:
   
10.             return []
    
11. 
    
12.         result = []
    
13.         min_heap = []
    
14. 
    
15.         for arr in arrs:
    
16.             i = 0
    
17.             while i < len(arr):
    
18.                 heapq.heappush(min_heap, arr[i])
    
19.                 i += 1
    
20. 
    
21.         while min_heap:
    
22.             result.append(heapq.heappop(min_heap))
    
23. 
    
24.         return result
    
25.    
    
26. 
    
27. if __name__ == '__main__':
    
28.     Solution().merge_k_arrays([[1, 4, 5], [1, 3, 4], [2, 6]]) == \
    
29.                                [1, 1, 2, 3, 4, 4, 5, 6]
    
30.     Solution().merge_k_arrays([[1, 3, 5, 7], [2, 4, 6, 8], [0, 9, 10, 11]]) == \
    
31.                                [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]
    .1point3acres
32.     Solution().merge_k_arrays([]) == []
    
33.     Solution().merge_k_arrays([[]]) == []

复制代码

[/i]

感谢分享,
请问第一句话是这么断句么:
Leetcode easy难度的题目，主要考察Array，String，Hashtable，Searching和简单DP. Tree，Linked List和Graph我从来没见过。

123小液泡 发表于 2021-2-2 13:12
感谢分享,
请问第一句话是这么断句么:
Leetcode easy难度的题目，主要考察Array，String，Hashtable，S ...

对的，sorry写得有点confusing，已经更正

2. String Compression

Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccddd would become a2b1c5d3. If the "compressed" string would not become smaller than the original string, your method should return the original string.

You can assume the string has only lowercase letters. (a-z)

1. def string_compress(s):
   
2.     result = ""
   
3.     cnt = 1
   
4.    
   
5.     for i in range(len(s) - 1):
   
6.         if s[i] == s[i + 1]:
   
7.             cnt += 1
   
8.         else:
   
9.             result += s[i] + str(cnt)
   
10.             cnt = 1
    
11.             
    
12.     result += s[i] + str(cnt)
    
13.    
    
14.     if len(result) >= len(s):
    
15.         return s
    
16.     return result
    
17. 
    
18. if __name__ == "__main__":
    
19.     assert string_compress("aabcccccddd") == "a2b1c5d3"
    
20.     assert string_compress("abcde") == "abcde"

复制代码

3. Rotate matrix

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise and anticlockwise).

. 1point3acres.com You have to rotate the image in-place.

1. def rotate_clock(matrix):
   
2.     n = len(matrix)
   
3.     for i in range(n):
   
4.         for j in range(i):
   
5.             matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
   
6.             
   
7.     for i in range(n):
   
8.         for j in range(n//2):
   
9.             matrix[i][j], matrix[i][n - 1 - j] = matrix[i][n - 1 - j], matrix[i][j]
   
10.     return matrix
    
11. 
    
12. if __name__ == "__main__":
    
13.     assert rotate_clock([[1, 2, 3],
    
14.                          [4, 5, 6],
    
15.                          [7, 8, 9]]) == [[7, 4, 1],
    
16.                                          [8, 5, 2],
    
17.                                          [9, 6, 3]]

复制代码

1. def rotate_anticlock(matrix):
   
2.     n = len(matrix)
   
3.     for i in range(n):
   
4.         for j in range(i):
   
5.             matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
   
6.             
   
7.     for i in range(n//2):
   
8.         for j in range(n):
   
9.             matrix[i][j], matrix[n - 1 - i][j] = \
   
10.             matrix[n - 1 - i][j], matrix[i][j]
    
11.     return matrix
    
12. 
    
13. if __name__ == "__main__":
    
14.     assert rotate_anticlock([[1, 2, 3],
    
15.                              [4, 5, 6],
    
16.                              [7, 8, 9]]) == [[3, 6, 9],
    
17.                                              [2, 5, 8],
    
18.                                              [1, 4, 7]]
    

复制代码

. check 1point3acres for more.

4. Largest sum subarry

Given an array of integers, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

[i][i][i][i]

1. def max_subarray(nums):
   
2.     # T: O(n), S: O(n)
   
3.     if len(nums) == 0:
   
4.         return 0
   
5.    
   
6.     dp = [0]*len(nums)
   
7.     dp[0] = nums[0]
   
8.     result = dp[0]
   
9.    
   
10.     for i in range(1, len(nums)):
    
11.         if dp[i - 1] < 0:
    
12.             dp[i] = nums[i]
    
13.         else:
    
14.             dp[i] = nums[i] + dp[i - 1]
    . 1point3acres
15.         result = max(result, dp[i])
    
16.         
    
17.     return result
    
18. 
    
19. if __name__ == "__main__":
    
20.     assert max_subarray([-2,1,-3,4,-1,2,1,-5,4]) == 6

复制代码

[/i][/i][/i][/i]

5. Reservoir sampling （有名的蓄水池抽样）

Reservoir sampling is a family of randomized algorithms for randomly choosing a sample of k items from a list S containing n items, where n is either a very large or unknown number. Typically, n is too large to fit the whole list into main memory.

算法：

1. '''  S has items to sample, R will contain the result
   
2. 
   
3. ReservoirSample(S[1..n], R[1..k])
   
4.   // fill the reservoir array
   
5.   for i = 1 to k
   
6.       R[i] := S[i]
   
7. 
   
8.   // replace elements with gradually decreasing probability
   
9.   for i = k+1 to n
   
10.     j := random(1, i) // important: inclusive range
    
11.     if j <= k
    
12.         R[j] := S[i]
    
13. '''

复制代码

Code:

1. import random
   
2. 
   
3. def reservoir_sample(iterable, k):
   
4.     """
   
5.     Returns @param n random items from @param iterable.
   
6.     """
   
7.     reservoir = []
   
8.     for i, item in enumerate(iterable):
   
9.         if i < k:
   
10.             reservoir.append(item)
    
11.         else:
    
12.             j = random.randint(0, i)
    
13.             if j < k:
    
14.                 reservoir[j] = item
    
15.     return reservoir
    
16. 
    
17. 
    
18. reservoir_sample(range(1000000), 10)
    
19. # [973801, 423005, 360287, 932539, 372598, 139061, 147183, 44640, 686224, 165398]

复制代码

[/i][/i][/i]

谢谢分享🦀～～

YZDH 发表于 2021-2-2 00:12
1. Weighted Sampling

You are given n numbers as well as probabilities p_0, p_1, ... , p_{n - 1},  ...

多谢分享，前面的表述里面100000 call是不是应该是1 million call（少了一个0）？