Two Sigma:面试真题——编程(下)
平均阅读时长为 139分钟
量化投资与机器学习微信公众号,是业内垂直于量化投资、对冲基金、Fintech、人工智能、大数据等领域的主流自媒体。公众号拥有来自公募、私募、券商、期货、银行、保险、高校等行业30W+关注者,荣获2021年度AMMA优秀品牌力、优秀洞察力大奖,连续2年被腾讯云+社区评选为“年度最佳作者”。
上一起,QIML为大家分享几道有关Two Sigma面试的计算真题。今天,我们主要为大家分享几道编程真题。
量化对冲基金技术面试中一般都会有pair coding的部分,主要是测试候选人代码的能力。远程面试时,一般会选取如hackerrank的在线编程平台进行面试。
在回顾Two Sigma以往的面试题,我们发现大部分题目来自leetcode的原题,主要涉及到的知识点有:动态规划、回溯算法、深度优先搜索及递归等。
在搜集了各大论坛中的面试经验分享帖子后,对于其中比较高频的面试题,公众号做了整理,并给出了代码答案,供大家参考,其中编号就是leetcode题号。
大家可以先自己解答一下,不要急着看答案,测试一下自己的真实水平!
4寻找两个有序数组中位数
QIML解答过程
classSolution:
deffindMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
defgetKthElement(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
whileTrue:
# 特殊情况
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
9回文数
QIML解答过程
# 不转换为字符串
classSolution:
defisPalindrome(self, x: int) -> bool:
if x < 0 :
returnFalse
elif x == 0: #防止求log时,底数为0
returnTrue
else:
length = 1
while10**length<x:
length += 1
length -= 1
while x != 0:
if x//(10 ** length) == x %10:
x = x % 10**length // 10
length -=2
else:
returnFalse
returnTrue
29两数相除,不能使用乘法/除法
QIML解答过程
classSolution:
defdivide(self, dividend: int, divisor: int) -> int:
def_divide(a, b):
if (a<b): return0
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>0and divisor<0) or (dividend<0and 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)
43字符串相乘multiply-strings
QIML解答过程
# 出现频率较高
classSolution:
defmultiply(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
defaddStrings(self, num1: str, num2: str) -> str:
i, j = len(num1) - 1, len(num2) - 1
add = 0
ans = list()
while i >= 0or j >= 0or add != 0:
x = int(num1[i]) if i >= 0else0
y = int(num2[j]) if j >= 0else0
result = x + y + add
ans.append(str(result % 10))
add = result // 10
i -= 1
j -= 1
return"".join(ans[::-1])
56合并区间
QIML解答过程
# 出现频率很高的一道题
classSolution:
defmerge(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
123买卖股票的最佳时机III
QIML解答过程
from typing import List
# 初始化确定的逻辑还不是很明白
classSolution:
defmaxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return0
dp = [[0]*5for _ 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]
207课程表
QIML解答过程
import collections
classSolution:
defcanFinish(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
289生命游戏
QIML解答过程
classSolution:
defgameOfLife(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] == 1and (live_neighbors < 2or live_neighbors > 3):
# -1 代表这个细胞过去是活的现在死了
board[row][col] = -1
# 规则 4
if board[row][col] == 0and 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] = 0
415字符串相加
QIML解答过程
classSolution:
defaddStrings(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>=0or j>=0or last_sum>0:
_num1 = int(num1[i]) if i>=0else0
_num2 = int(num2[j]) if j>=0else0
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])
443压缩字符串
QIML解答过程
from typing import List
classSolution:
defcompress(self, chars: List[str]) -> int:
n = len(chars)
if n<2: return1
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_used
547省份数量
QIML解答过程
classSolution:
deffindCircleNum(self, isConnected: List[List[int]]) -> int:
defdfs(i):
for j in range(n):
if isConnected[i][j] == 1and j notin visited:
visited.add(j)
dfs(j)
visited = set()
n = len(isConnected)
ans = 0
for i in range(n):
if i notin visited:
dfs(i)
ans += 1
return ans
564寻找最近的回文数
QIML解答过程
classSolution:
defnearestPalindromic(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 == 0else 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 == -1or \
abs(candidate - selfNumber) < abs(ans - selfNumber) or \
abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:
ans = candidate
return str(ans)
606根据二叉树创建字符串
QIML解答过程
classSolution:
deftree2str(self, root: Optional[TreeNode]) -> str:
if root isNone:
return""
if root.left isNoneand root.right isNone:
return str(root.val)
# if root.left is None:
# return f"{root.val}()({self.tree2str(root.left)})"
if root.right isNone:
returnf"{root.val}({self.tree2str(root.left)})"
returnf"{root.val}({self.tree2str(root.left)})({self.tree2str(root.right)})"
698划分为k个相等的子集
QIML解答过程
classSolution:
defcanPartitionKSubsets(self, nums: List[int], k: int) -> bool:
# 特殊情况处理
if k==1:
returnTrue# 特殊情况1
target, resid = sum(nums)//k, sum(nums)%k
if resid!=0:
returnFalse# 特殊情况2
nums=sorted(nums, reverse=True)
if nums[-1]>target:
returnFalse# 特殊情况3
# 预处理
while nums and nums[0]==target:
nums.pop(0)
k-=1# 如果有等于target的数字 则先弹出
ifnot nums:
returnTrue# 特殊情况4
# 递归判断 (回溯法)
defdfs(groups, nums):
ifnot nums: returnTrue
v=nums[0]
for i in range(k):
if groups[i]+v<=target:
# 向下递归
groups[i]+=v
if dfs(groups, nums[1:]):
returnTrue
# 回置状态
groups[i]-=v
if groups[i]==0: break# 避免重复搜索
returnFalse
return dfs([0]*k, nums)
1048最长字符串链
QIML解答过程
classSolution:
deflongestStrChain(self, words: List[str]) -> int:
defcheck_words(x, y):
x_len, y_len = len(x), len(y)
if x_len+1 != y_len:
returnFalse
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 res
1779找到最近的有相同 X 或 Y 坐标的点
QIML解答过程
classSolution:
defnearestValidPoint(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
面试系列汇总
往期推荐
Quant面试『真题』系列:第三期
Quant面试『真题』系列:第二期
Quant面试『真题』系列:第一期
干翻机器学习面试!
全程干货!Citadel在职Quant求职经验分享
G-Research量化面试『真题』答案出炉!
G-Research:量化研究员面试『真题』
独家!中国量化私募面试Q&A系列——鸣石投资
独家!中国量化私募面试Q&A系列——白鹭资管
Jane Street烧脑Puzzle(2019-2020)
Two Sigma:面试还是挺难(附面经)!
你能做几道?Jane Street烧脑面试题!
独家!全球顶尖对冲基金LeetCode面试题汇总
关键词
代码
答案
最新评论
推荐文章
作者最新文章
你可能感兴趣的文章
Copyright Disclaimer: The copyright of contents (including texts, images, videos and audios) posted above belong to the User who shared or the third-party website which the User shared from. If you found your copyright have been infringed, please send a DMCA takedown notice to [email protected]. For more detail of the source, please click on the button "Read Original Post" below. For other communications, please send to [email protected].
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。