folder_open

arrow_right
article

# 面試心得–IMSLP-Petrucci

2021/10/22~【Backend】無聲卡

# 第一輪線上技術測驗#

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 第一輪回答點評回信
• 此後無任何通知

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

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