職缺介紹

#

詳見 Github 連結－[徵才] 美國IMSLP-Petrucci / Backend / Fullstack（200-280萬/年）open_in_new

第一輪線上技術測驗

#

僅一題白板題如下：

Given a string S and a string T, find the minimum window in S which will contain all the characters in T.

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

面試官聽口音是中國人，表情全程看起來十分嚴肅，討論實作思路時面無表情，整場面試沒有提供任何提示，但有特別要求思考完想法以後再實作。我實作到一半時，面試官表示有另一場面試而先離開，並請我完成後再寄信提交。

面試結果及時程

#

• 2021/10/22 寄信投履歷
• 2021/10/25 第一輪線上技術測驗（參與人：Edward Guo）
• 2021/10/27 第一輪回答點評回信
• 此後無任何通知

附錄：第一輪線上技術測驗題目參考解答

#

本命題與 Leetcode 76. Minimum Window Substringopen_in_new 相同

以下解法為面試當下所寫，並非最優解。

def str_to_count_map(s):
    count_map = {}
    for c in s:
        if c not in count_map:
            count_map[c] = 0
        count_map[c] += 1
    return count_map

def contains_t(current_count_map, t_count_map):
    return all([
        c in current_count_map and current_count_map[c] >= t_count_map[c]
        for c in t_count_map.keys()
    ])

def find_min_str(s, t):
    s_len = len(s)
    left = 0
    right = 1
    t_chars = set(t)
    t_count_map = str_to_count_map(t)

    ans_left = 0
    ans_right = len(s) - 1
    find_at_least_one_answer = False

    while (right < s_len) and (left < right):
        current_count_map = str_to_count_map(s[left:right+1])
        if contains_t(current_count_map, t_count_map):
            if right - left < ans_right - ans_left:
                find_at_least_one_answer = True
                ans_left, ans_right = left, right
            # move left pointer
            left += 1
            while s[left] not in t_chars:
                left += 1
        else:
            # move right pointer
            right += 1
            if right >= s_len - 1:
                break
            c = s[right]
            if c not in current_count_map:
                current_count_map[c] = 0
            current_count_map[c] += 1
            while (right < s_len - 1) and (s[right] not in t_chars or not contains_t(current_count_map, t_count_map)):
                right += 1
                c = s[right]
                if c not in current_count_map:
                    current_count_map[c] = 0
                current_count_map[c] += 1

    if find_at_least_one_answer:
        return s[ans_left:ans_right+1]
    else:
        return ''

print(find_min_str('ADOBECODEBANC', 'ABC'))

附錄：第一輪線上技術測驗題目相似題

#

2022/12/17 筆者閱讀 Hacker News 電子報時看到一個相似題，且作者巧妙地運用 XOR 實作了最佳演算法：A Neat XOR Trickopen_in_new