量化投资与机器学习微信公众号，是业内垂直于
量化投资、对冲基金、
Fintech、人工智能、大数据
等
领域的
主流自媒体
。
公众号拥有来自
公
募
、私募、券商、期货、银行、保险、高校
等行业
30W+
关注者，荣获2021年度AMMA优秀品牌力、优秀洞察力大奖，连续2
年被腾讯云+社区评选为“年度最佳作者”。
上一起，QIML为大家分享几道有关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)) / 2
QIML解答过程
# 不转换为字符串
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 length += 1
length -= 1
while x != 0:
if x//(10 ** length) == x %10:
x = x % 10**length // 10
length -=2
else:
return False
return True
QIML解答过程
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
def _divide(a, b)
:
if (areturn 0
cnt = 1
tb = b
while (tb+tb) 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 merged
QIML解答过程
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 == numCourses
QIML解答过程
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
