量化投资与机器学习微信公众号,是业内垂直于量化投资、对冲基金、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
面试系列汇
继续阅读
阅读原文