学长最近完成了一份到 台積電OA （TSMC）的線上測驗（OA）真題，发出来分享一下~
台積電OA題目一
對於字串s和整數k，如果滿足以下條件，則子字串的選擇是有效的：
– 每個子字串的長度大於或等於k。
– 每個子字串都是回文。
– 沒有兩個子字串重疊。
– 確定s可以形成的有效子字串的最大數量。
筆記
子字串是字串中一組相鄰的字元。
回文是一個向後和向前讀相同的字串。
示例：
text复制编辑s = "aababaabce"
k = 3
對於這個例子，長度至少為k的非重疊回文子串的一些可能選擇是：“ababa”和“abce”，“aba”和“baab”，此類有效子字串的最大數量是2
功能說明
使用以下參數完成函數getMaxSubstring：
– string s：給定的字串。
– int k：有效子字串的最小長度。
返回值
– int：可以形成的最大有效子字串數。
Python Code
def getMaxSubstrings(s, k):
n = len(s)
# 步驟1：使用DP識別所有回文子串
dp = [[False] * n for _ in range(n)]
# 每個字元都是回文
for i in range(n):
dp[i][i] = True
# 檢查長度為2的回文
for i in range(n - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
# 檢查長度大於2的回文
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
# 步驟2：按長度過濾子字串
palindromic_substrings = []
for i in range(n):
for j in range(i + k - 1, n):
if dp[i][j]:
palindromic_substrings.append((i, j))
# 步驟3：選擇非重疊回文子串
palindromic_substrings.sort(key=lambda x: x[1]) # Sort by the end index
max_count = 0
last_end = -1
for start, end in palindromic_substrings:
if start > last_end:
max_count += 1
last_end = end
return max_count
# 示例用法
s = "aababaabce"
k = 3
print(getMaxSubstrings(s, k)) # Output: 2
台積電OA題目二
In a coding competition organized to hire software developers, there is an interesting problem involving the Bitwise-OR operation.
The goodness of a sequence is defined as the bitwise OR of its elements. Given an array arr of length n, you are required to find all possible distinct values of goodness that can be obtained by choosing any strictly increasing subsequence of the array. Thereturn array should be sorted in non-decreasing order.
筆記
- A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.
- A strictly increasing subsequence is a subsequence where each element is greater than the previous one.
- The goodness of a sequence is defined as the bitwise OR of all its elements.
例子
Consider n = 4 and arr = [4, 2, 4, 1].
The strictly increasing subsequences which can be chosen to have distinct goodness values are:
- Empty subsequence; goodness = 0
[1]; goodness = 1[2]; goodness = 2[4]; goodness = 4[2,4]; goodness = 6
There are no other strictly increasing subsequences that yield a different goodness value. Thus, the answer is [0, 1, 2, 4, 6].
Python Code
def findDistinctGoodnessValues(arr):
n = len(arr)
# goodness_values：一個存儲所有不同善良值的集合。
goodness_values = set()
dp = [set() for _ in range(n)]
# 對於每個元素arr[i]，反覆運算所有前面的元素arr[j]，其中arr[j]<arr[i]
# 對於dp[j]中的每個優度值，通過用arr[i]執行按比特OR來計算新的優度值並將其添加到new_values中
# 將arr[i]本身添加到new_values中，以解釋僅由arr[i]組成的子序列
for i in range(n):
new_values = set()
for j in range(i):
if arr[j] < arr[i]:
for val in dp[j]:
new_values.add(val | arr[i])
new_values.add(arr[i])
dp[i] = new_values
# 更新dp[i]後，將new_values中的所有值添加到goodness_values集合中
for val in new_values:
goodness_values.add(val)
# 將0添加到集合中，以包含空子序列的優度值
goodness_values.add(0)
return sorted(goodness_values)
# 示例用法
arr = [4, 2, 4, 1]
result = findDistinctGoodnessValues(arr)
print(result) # Output: [0, 1, 2, 4, 6]
Learn More
联系我们
最後，經過我們的强力面試輔助和台積電hackerrank作弊，候選人通過這些面試題的解析和溝通，面試官不僅瞭解了候選人的程式設計能力，也看到了我在解决問題過程中清晰的思路和有效的溝通技巧。 這些不僅有助於應對台積電的面試，同時也能提升我們解决實際程式設計問題的能力。 祝大家面試順利！
With our strong interview assistance and OA ghostwriting, the candidate not only understood their programming skills through the analysis andcommunication of these interview questions, but also saw my clear thinking and effective communication skills in problem-solving. These not only helpus cope with TSMC interviews, but also enhance our ability to solve practical programming problems.
如果你也需要我們的台積電hackerrank作弊服務和面試輔助服務，請立即聯繫我們。
