Two Sigma：面试真题 - 编程（下）
量化投资与机器学习
发表于
量化投资与机器学习微信公众号，是业内垂直于量化投资、对冲基金、Fintech、人工智能、大数据等领域的主流自媒体。公众号拥有来自公募、私募、券商、期货、银行、保险、高校等行业30W+关注者，荣获2021年度AMMA优秀品牌力、优秀洞察力大奖，连续2年被腾讯云+社区评选为“年度最佳作者”。
上一起，QIML为大家分享几道有关Two Sigma面试的计算真题。今天，我们主要为大家分享几道编程真题。
Two Sigma：面试真题（上）
量化对冲基金技术面试中一般都会有pair coding的部分，主要是测试候选人代码的能力。远程面试时，一般会选取如hackerrank的在线编程平台进行面试。
在回顾Two Sigma以往的面试题，我们发现大部分题目来自leetcode的原题，主要涉及到的知识点有：动态规划、回溯算法、深度优先搜索及递归等。
在搜集了各大论坛中的面试经验分享帖子后，对于其中比较高频的面试题，公众号做了整理，并给出了代码答案，供大家参考，其中编号就是leetcode题号。
4 寻找两个有序数组中位数
QIML解答过程
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def getKthElement(k):
"""
- 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
- 这里的 "/" 表示整除
- nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
- nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
- 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
- 这样 pivot 本身最大也只能是第 k-1 小的元素
- 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
- 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
- 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
"""
index1, index2 = 0, 0
while True:
# 特殊情况
if index1 == m:
return nums2[index2 + k - 1]
if index2 == n:
return nums1[index1 + k - 1]
if k == 1:
return min(nums1[index1], nums2[index2])
# 正常情况
newIndex1 = min(index1 + k // 2 - 1, m - 1)
newIndex2 = min(index2 + k // 2 - 1, n - 1)
pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
if pivot1 <= pivot2:
k -= newIndex1 - index1 + 1
index1 = newIndex1 + 1
else:
k -= newIndex2 - index2 + 1
index2 = newIndex2 + 1
m, n = len(nums1), len(nums2)
totalLength = m + n
if totalLength % 2 == 1:
return getKthElement((totalLength + 1) // 2)
else:
return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2QIML解答过程
# 不转换为字符串
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0 :
return False
elif x == 0: #防止求log时，底数为0
return True
else:
length = 1
while 10**length<x:
length += 1
length -= 1
while x != 0:
if x//(10 ** length) == x %10:
x = x % 10**length // 10
length -=2
else:
return False
return TrueQIML解答过程
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
def _divide(a, b):
if (a<b): return 0
cnt = 1
tb = b
while (tb+tb)<a:
cnt += cnt
tb += tb
return cnt + _divide(a-tb, b)
INT_MIN, INT_MAX = -2**31, 2**31 - 1
# if dividend == 0: return 0
# if divisor == 1: return dividend
# if divisor == -1:
# if dividend>INT_MIN:
# return -dividend
# return INT_MAX
sign = 1
if (dividend>0 and divisor<0) or (dividend<0 and divisor>0):
sign = -1
dividend, divisor = abs(dividend), abs(divisor)
res = _divide(dividend, divisor)
if sign>0:
return min(INT_MAX, res)
return max(INT_MIN, -res)QIML解答过程
# 出现频率较高
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
ans = "0"
m, n = len(num1), len(num2)
for i in range(n - 1, -1, -1):
add = 0
y = int(num2[i])
curr = ["0"] * (n - i - 1)
for j in range(m - 1, -1, -1):
product = int(num1[j]) * y + add
curr.append(str(product % 10))
add = product // 10
if add > 0:
curr.append(str(add))
curr = "".join(curr[::-1])
ans = self.addStrings(ans, curr)
return ans
def addStrings(self, num1: str, num2: str) -> str:
i, j = len(num1) - 1, len(num2) - 1
add = 0
ans = list()
while i >= 0 or j >= 0 or add != 0:
x = int(num1[i]) if i >= 0 else 0
y = int(num2[j]) if j >= 0 else 0
result = x + y + add
ans.append(str(result % 10))
add = result // 10
i -= 1
j -= 1
return "".join(ans[::-1])QIML解答过程
# 出现频率很高的一道题
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if len(intervals) == 1:
return intervals
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
left = merged[-1]
for right in intervals[1:]:
if right[0]<=left[1]:
left[1] = max(right[1], left[1])
else:
merged.append(right)
left = merged[-1]
return mergedQIML解答过程
from typing import List
# 初始化确定的逻辑还不是很明白
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
dp = [[0]*5 for _ in range(len(prices))]
dp[0][1] = -prices[0]
dp[0][3] = -prices[0]
for i in range(1, len(prices)):
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1])
dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2])
dp[i][3] = max(dp[i-1][2] - prices[i], dp[i-1][3])
dp[i][4] = max(dp[i-1][3] + prices[i], dp[i-1][4])
return dp[-1][4]QIML解答过程
import collections
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
#存储有向图
edges = collections.defaultdict(list) #{k: [v1, v2]} 以k为先导课程的课有[v1, v2]
# 存储每个节点的入度
in_degree = [0]*numCourses
result = 0
for info in prerequisites:
edges[info[1]].append(info[0])
in_degree[info[0]] += 1
q = collections.deque([u for u in range(numCourses) if in_degree[u]==0])
while q:
u = q.popleft()
result += 1
for v in edges[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
q.append(v)
return result == numCoursesQIML解答过程
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
neighbors = [(1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1)]
rows = len(board)
cols = len(board[0])
# 遍历面板每一个格子里的细胞
for row in range(rows):
for col in range(cols):
# 对于每一个细胞统计其八个相邻位置里的活细胞数量
live_neighbors = 0
for neighbor in neighbors:
# 相邻位置的坐标
r = (row + neighbor[0])
c = (col + neighbor[1])
# 查看相邻的细胞是否是活细胞
if (r < rows and r >= 0) and (c < cols and c >= 0) and abs(board[r][c]) == 1:
live_neighbors += 1
# 规则 1 或规则 3
if board[row][col] == 1 and (live_neighbors < 2 or live_neighbors > 3):
# -1 代表这个细胞过去是活的现在死了
board[row][col] = -1
# 规则 4
if board[row][col] == 0 and live_neighbors == 3:
# 2 代表这个细胞过去是死的现在活了
board[row][col] = 2
# 遍历 board 得到一次更新后的状态
for row in range(rows):
for col in range(cols):
if board[row][col] > 0:
board[row][col] = 1
else:
board[row][col] = 0QIML解答过程
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
num1_len, num2_len = len(num1), len(num2)
i, j = num1_len-1, num2_len-1
last_sum = 0
ans = []
while i>=0 or j>=0 or last_sum>0:
_num1 = int(num1[i]) if i>=0 else 0
_num2 = int(num2[j]) if j>=0 else 0
temp_sum = _num1 + _num2 + last_sum
ans.append(str(temp_sum%10))
last_sum = temp_sum//10
i -= 1
j -= 1
return ''.join(ans[::-1])QIML解答过程
from typing import List
class Solution:
def compress(self, chars: List[str]) -> int:
n = len(chars)
if n<2: return 1
chars.append(None)
n += 1
cnt = 1
left = 0
right = 1
tot_used = 0
while right<n:
if chars[left] != chars[right]:
if cnt == 1:
temp_char = chars[left]
else:
temp_char = list(chars[left]) + list(str(cnt))
chars[tot_used: tot_used+len(temp_char)] = temp_char
tot_used += len(temp_char)
cnt = 1
else:
cnt += 1
left += 1
right += 1
return tot_usedQIML解答过程
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
def dfs(i):
for j in range(n):
if isConnected[i][j] == 1 and j not in visited:
visited.add(j)
dfs(j)
visited = set()
n = len(isConnected)
ans = 0
for i in range(n):
if i not in visited:
dfs(i)
ans += 1
return ansQIML解答过程
class Solution:
def nearestPalindromic(self, n: str) -> str:
m = len(n)
candidates = [10 ** (m - 1) - 1, 10 ** m + 1]
selfPrefix = int(n[:(m + 1) // 2])
for x in range(selfPrefix - 1, selfPrefix + 2):
y = x if m % 2 == 0 else x // 10
while y:
x = x * 10 + y % 10
y //= 10
candidates.append(x)
ans = -1
selfNumber = int(n)
for candidate in candidates:
if candidate != selfNumber:
if ans == -1 or \
abs(candidate - selfNumber) < abs(ans - selfNumber) or \
abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:
ans = candidate
return str(ans)QIML解答过程
class Solution:
def tree2str(self, root: Optional[TreeNode]) -> str:
if root is None:
return ""
if root.left is None and root.right is None:
return str(root.val)
# if root.left is None:
# return f"{root.val}()({self.tree2str(root.left)})"
if root.right is None:
return f"{root.val}({self.tree2str(root.left)})"
return f"{root.val}({self.tree2str(root.left)})({self.tree2str(root.right)})"QIML解答过程
class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
# 特殊情况处理
if k==1:
return True # 特殊情况1
target, resid = sum(nums)//k, sum(nums)%k
if resid!=0:
return False # 特殊情况2
nums=sorted(nums, reverse=True)
if nums[-1]>target:
return False # 特殊情况3
# 预处理
while nums and nums[0]==target:
nums.pop(0)
k-=1 # 如果有等于target的数字 则先弹出
if not nums:
return True # 特殊情况4
# 递归判断 （回溯法）
def dfs(groups, nums):
if not nums: return True
v=nums[0]
for i in range(k):
if groups[i]+v<=target:
# 向下递归
groups[i]+=v
if dfs(groups, nums[1:]):
return True
# 回置状态
groups[i]-=v
if groups[i]==0: break # 避免重复搜索
return False
return dfs([0]*k, nums)QIML解答过程
class Solution:
def longestStrChain(self, words: List[str]) -> int:
def check_words(x, y):
x_len, y_len = len(x), len(y)
if x_len+1 != y_len:
return False
i,j = 0, 0
while i<x_len and j<y_len:
if x[i] == y[j]:
i += 1
j += 1
return i == x_len
words.sort(key=lambda x : len(x))
n = len(words)
dp = [1] * n
res = 0
for i in range(n):
for j in range(i):
if check_words(words[j], words[i]):
dp[i] = max(dp[i], dp[j]+1)
res = max(res, dp[i])
return resQIML解答过程
class Solution:
def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
min_dist = float('inf')
min_point = None
res = -1
idx = 0
for i,j in points:
if i == x or j==y:
dist = abs(i-x) + abs(j-y)
# print(dist)
if dist < min_dist:
min_dist = dist
min_point = [i, j]
res = idx
idx += 1
return res往期推荐