2023/03/01~2023/03/14【Product Developer (私有雲端溝通平台開發)】未錄取
C/C++
JavaScript
OS
請比較 Process 及 Thread
有哪些方式可以跨 Process 進行通訊?
file lock, domain socket
題目為 LeetCode 279. Perfect Squaresopen_in_new。
此職缺會負責開發 NAS 中的 App,包括但不限於 Email, Calendar, Contact 等 Apps。這是一個全端的工作,後端主要使用 C/C++,前端使用 Vue。工作上的挑戰主要來自硬體的資源限制,以及可能要做 NAS Cluster,會需要實作分散式系統的架構。
題目的範例輸入輸出及限制為:
input: 12output: 3explanation: 12 = 4 + 4 + 4
input: 13output: 2explanation: 13 = 4 + 9
1 <= n <= 100,000
當下第一個想嘗試的方法是 Greedy:
def solove(n): count = 0 while n > 0: p = sqrt(n) n -= p * p count += 1 return count
但第一個 Test Case 就會 WA,因此嘗試使用 Backtracking 窮舉所有組合來求解:
import math
def solve(n): min_count = float('inf')
def backtracking(currents, candidates): # 尚未平方的 current, candidate sum_of_current_square = sum([c * c for c in currents]) if sum_of_current_square == n: min_count = min(min_count, len(currents)) return for candidate in candidates: # [1], [1,2,3] # -> ... # [2], [1,2] # -> [2, 1], [1, 2] # -> ... # -> [2, 2], [1, 2] # -> [2, 2, 1], [1] # -> [2, 2, 2], [] # [3], [1] if sum_of_current_square <= n: backtracking([*currents, candidate], [i for i in range(1, math.ceil(math.sqrt(n - sum_of_current_square)))])
backtracking([], [i for i in range(1, math.ceil(math.sqrt(n)))]) # [], [1, 2, 3] return min_count
後來看 LeetCode 的標準解法有兩個流派,一個是 DP,另一個是數學公式解,但無論是哪一種,都超出我的腦袋容量了。