ByteDance
[心得] 新鮮人面試心得(ByteDance/Qualcomm)
給予A和B兩個sorted array找出交集，限制用in-place的方式解題
Intersection of Two Sorted Arrays using In Place Approach
要在原地（in-place）解決這個問題，可以使用雙指針的方法。假設給定的兩個數組分別為A和B，它們已經按升序排序。
首先，我們可以初始化兩個指針i和j分別指向A和B的起始位置，然後開始進行比較。如果A[i]小於B[j]，則移動指針i向後移動一位；如果A[i]大於B[j]，則移動指針j向後移動一位；如果A[i]等於B[j]，則將該值添加到結果中，並將兩個指針都向後移動一位。
重複上述步驟，直到其中一個數組的指針達到數組末尾為止。最終，得到的結果就是兩個數組的交集。
package intersection
func FindIntersection(A, B []int) []int {
var i, j int = 0, 0
result := []int{}
for i < len(A) && j < len(B) {
if A[i] < B[j] {
i++
} else if A[i] > B[j] {
j++
} else {
result = append(result, A[i])
i++
j++
}
}
return result
}
func TestFindIntersection(t *testing.T) {
var tests = []struct {
arg1 []int
arg2 []int
want []int
}{
{
arg1: []int{1, 3, 4, 6, 7},
arg2: []int{2, 4, 6, 8, 9},
want: []int{4, 6},
},
}
for _, tt := range tests {
if got := FindIntersection(tt.arg1, tt.arg2); !reflect.DeepEqual(got, tt.want) {
t.Errorf("got = %v, want = %v", got, tt.want)
}
}
}
TODO: 延伸
TODO:LeetCode 103. Binary Tree Zigzag Level Order Traversal (medium)
Leetcode 103. Binary Tree Zigzag Level Order Traversal (二叉樹的之字形層序遍歷) 難易度: Medium
- 題目描述: 給定一個二叉樹，返回其節點值的之字形層序遍歷（即從左到右，然後從右到左進行下一層遍歷，以此類推）。
- 解題思路: 使用BFS進行層序遍歷，並使用一個變數來記錄當前層的遍歷方向。根據遍歷方向，將節點值存入相應的層級列表中，最後返回結果。
- 連結: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal
TODO: LeetCode 60. Permutation Sequence (hard)
Leetcode 60. Permutation Sequence (排列序列) 難易度: Hard
- 題目描述:給定一個正整數 n 和 k，找出由 1 到 n 組成的順序的第 k 個排列。
- 解題思路:可以使用回溯法來生成所有的排列，並找到第 k 個排列。使用一個計數器來跟踪已生成的排列數量，當計數器等於 k 時，返回當前的排列。
- 連結: https://leetcode.com/problems/permutation-sequence
巨集和函式的差別，各自的優缺點
巨集(Macro)
是一系列指令的集合，可以在程式中被重複使用和展開。 巨集是在編譯時展開的，通常由預處理器負責處理。
優點：
- 彈性：巨集可以根據需要展開，提供了更大的彈性和動態性。
- 強大的功能：巨集可以執行複雜的指令序列，甚至可以擁有條件判斷和迴圈等控制結構。
- 增加程式碼的可讀性：通過使用巨集，可以將重複的程式碼片段抽象為一個可讀性較高的巨集，從而提高程式碼的可讀性和維護性。
缺點：
- 可能產生代碼膨脹：巨集在展開時會直接將巨集內容複製到展開的位置，這可能導致代碼膨脹，增加可執行文件的大小。
- 可能產生難以追蹤的錯誤：巨集的展開可能會使得代碼變得複雜，並且在巨集被多次展開的情況下，錯誤的追蹤和調試可能變得困難。
函式(Function)
是一段可重複使用的程式碼，具有特定的輸入和輸出。它可以在程式中進行調用和執行。
優點：
- 可重用性：函式可以在程式中被重複使用，提供了程式碼的模組化和可重用性。
- 代碼的結構化：函式可以幫助將程式分解為更小的功能塊，從而提高程式的可讀性和可維護性。
- 容易追蹤和調試：函式的呼叫和執行通常比較清晰，因此在出現錯誤時容易追蹤和調試。
缺點：
- 限制：函式只能執行預先定義的操作，功能較巨集有所限制。
- 執行開銷：函式的
double pointer的用法
雙指針（double pointer）是指一個指針的指針，也被稱為指向指針的指針。 它在程式設計中常用於需要修改指針本身或指向的內容的情況。 這種技巧通常用於傳遞指標的引用，以便在函式中能夠修改指標的值。
下面是使用雙指針的一些常見用法：
動態分配記憶體：當需要在函式中動態分配記憶體並將其返回時，可以使用雙指針。函式內部可以使用一個指針來分配記憶體，並將其分配的記憶體的地址保存在雙指針中，這樣在函式外部可以獲得新分配記憶體的地址。
修改指標的值：有時需要在函式內部修改指針本身的值。這時可以將指針作為參數傳遞給函式，並使用雙指針在函式內部修改指針的值。
下面是一個使用雙指針的例子：
#include <stdio.h>
// 通過雙指針修改指標的值
void modifyPointer(int** ptr) {
int* newPtr = (int*)malloc(sizeof(int));
*newPtr = 10;
*ptr = newPtr;
}
int main() {
int* ptr = NULL;
modifyPointer(&ptr);
printf("Value: %d\n", *ptr); // 輸出：Value: 10
free(ptr); // 釋放動態分配的記憶體
return 0;
}
在上面的例子中，modifyPointer 函式使用了雙指針 ptr，它接收一個指向指針的指針作為參數。函式內部分配了一個整數的記憶體並將其值設為 10，然後將分配的記憶體的地址存儲在 *ptr 中。在 main 函式中，我們可以看到指針 ptr 的值已經被修改為分配記憶體的地址，並且可以正確地訪問和使用這個記憶體。
是要確保在使用動態分配的記憶體後適時地釋放它，以避免記憶體洩漏。
C語言main function的參數(int argc, char *argv[])是什麼
在C語言中，main 函式的參數是 int argc 和 char *argv[]。這些參數用於接收命令行傳遞的參數。
argc（argument count）是一個整數，代表命令行參數的數量，包括程式本身的名稱。argv（argument vector）是一個指向指針的陣列，每個指針指向一個命令行參數的字串。這些字串以 C 字串的形式存儲，並按照它們在命令行上出現的順序進行排列。
以下是一個使用 argc 和 argv 的簡單範例：
#include <stdio.h>
int main(int argc, char *argv[]) {
printf("Number of arguments: %d\n", argc);
for (int i = 0; i < argc; i++) {
printf("Argument %d: %s\n", i, argv[i]);
}
return 0;
}
在這個範例中，main 函式接受了 argc 和 argv 這兩個參數。printf 函式用來顯示命令行參數的數量和每個參數的值。程式執行時，命令行上輸入的參數會被傳遞給 main 函式。例如，執行以下命令：
./program arg1 arg2 arg3
則會輸出：
Number of arguments: 4
Argument 0: ./program
Argument 1: arg1
Argument 2: arg2
Argument 3: arg3
其中 ./program 是程式的名稱，arg1、arg2 和 arg3 是命令行傳遞的參數。
藉由 argc 和 argv 可以讓程式根據不同的命令行參數執行不同的邏輯，例如讀取檔案、設定選項等。
給予一個情境，講出如何發現bug及debug的過程
TODO: 還沒好
[心得] 新加坡 Bytedance NLP Scientist 面試
top-k element 的題目
Top-k元素問題是一個經典的算法問題，它要求從給定的集合中找出前k個最大（或最小）的元素。 以下是一種常見的解決方案，使用最小堆（Min Heap）數據結構： 創建一個最小堆，用於存儲當前的前k個最大元素。最小堆的大小限制為k。 遍歷給定的集合，對於每個元素，執行以下操作： 如果最小堆的大小小於k，將當前元素添加到最小堆中。 如果最小堆的大小已達到k，則比較當前元素與堆頂元素的大小。 如果當前元素大於堆頂元素，則將堆頂元素替換為當前元素，並對最小堆進行堆化（維護最小堆的性質）。 遍歷完整個集合後，最小堆中的k個元素即為前k個最大元素。
container/heap包可以用来構造優先級Queue。 Heap(堆積)其實是一個Complete Binary Tree(完全二元樹). Go的Heap特性是 各個節點都自己是其子樹的根, 且值是最小的(index = 0 的值是最小的). 同個根節點的左子樹的值會小於右子樹
package main
import (
"container/heap"
"fmt"
)
// 自定義最小 Heap 結構體
type MinHeap []int
func (h MinHeap) Len() int {
return len(h)
}
func (h MinHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h MinHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
// Push 和 Pop 方法需要使用指針，因為它們會修改 slice 的長度，而不僅僅只內容。
func (h *MinHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func findTopK(nums []int, k int) []int {
if k <= 0 || k > len(nums) {
return nil
}
// 初始化最小堆
h := &MinHeap{}
heap.Init(h)
// 遍歷集合
for _, num := range nums {
if h.Len() < k {
heap.Push(h, num)
} else if num > (*h)[0] {
heap.Pop(h)
heap.Push(h, num)
}
}
result := make([]int, k)
for i := k - 1; i >= 0; i-- {
result[i] = heap.Pop(h).(int)
}
return result
}
func main() {
nums := []int{3, 1, 5, 2, 8, 4}
k := 3
result := findTopK(nums, k)
fmt.Println(result) // Output: [8 5 4]
}
Edit distance 的 weighted 版本
速速寫了二維 DP
`WeightedEditDistance` 是一個計算帶有權重的編輯距離的函式。編輯距離是衡量兩個字串之間的相似度的指標，表示將一個字串轉換為另一個字串所需的最小操作數量。
在標準的編輯距離算法中，操作包括插入、刪除和替換字符。每個操作都被認為具有相同的代價。然而，在 `WeightedEditDistance` 中，每個字符的操作代價可以不同，並由一個權重映射表指定。
函式 `WeightedEditDistance` 接受兩個字符串 `word1` 和 `word2`，以及一個權重映射表 `weights`。該映射表將每個字符映射到其相應的權重值，用於計算操作的代價。
該函式使用動態規劃的方法計算編輯距離。它創建一個二維矩陣 `dp`，其中 `dp[i][j]` 表示將 `word1[:i]` 轉換為 `word2[:j]` 的最小操作代價。
算法的核心是遍歷 `dp` 矩陣並計算每個單元格的值。如果 `word1[i-1]` 等於 `word2[j-1]`，則表示兩個字符相等，不需要進行操作，所以 `dp[i][j]` 等於 `dp[i-1][j-1]`。否則，需要考慮插入、刪除和替換操作的代價，並取其中最小的作為 `dp[i][j]` 的值。
最終，函式返回 `dp[m][n]`，其中 `m` 和 `n` 分別為 `word1` 和 `word2` 的長度，表示將整個字串 `word1` 轉換為 `word2` 的最小操作代價。
使用 `WeightedEditDistance` 函式，您可以根據字符的權重值計算帶有自定義操作代價的編輯距離，以更好地反映兩個字串之間的相似性。
package weightededitdistance
import "fmt"
func WeightedEditDistance(word1, word2 string, weights map[rune]int) int {
m, n := len(word1), len(word2)
// 創建二維矩陣用於保存編輯距離
// dp，其中 dp[i][j] 表示將 word1[:i] 轉換為 word2[:j] 的最小操作代價
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}
// 初始化第一列, base case
for i := 1; i <= m; i++ {
dp[i][0] = dp[i-1][0] + weights[rune(word1[i-1])]
}
// 初始化第一行
for j := 1; j <= n; j++ {
dp[0][j] = dp[0][j-1] + weights[rune(word2[j-1])]
}
// fmt.Println(dp)
// 填充編輯距離矩陣
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
// 計算插入、刪除和替換操作的代價
// insert: 直接在 word1[i]中插入一個和word2[j]一樣的字符, 那麼word2[j]就被匹配了,往前j, 繼續和i對比, 操作次數+1
insertCost := dp[i][j-1] + weights[rune(word2[j-1])]
deleteCost := dp[i-1][j] + weights[rune(word1[i-1])]
replaceCost := dp[i-1][j-1] + weights[rune(word1[i-1])] + weights[rune(word2[j-1])]
// 取最小的代價作為當前操作的編輯距離
dp[i][j] = min(insertCost, deleteCost, replaceCost)
}
}
}
fmt.Println(dp)
return dp[m][n]
}
// 輔助函式，返回三個數字中的最小值
func min(a, b, c int) int {
if a <= b && a <= c {
return a
} else if b <= a && b <= c {
return b
} else {
return c
}
}
func TestWeightedEditDistance(t *testing.T) {
tests := []struct {
word1 string
word2 string
weights map[rune]int
expected int
}{
{"abc", "", map[rune]int{'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6}, 6},
{"abc", "def", map[rune]int{'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6}, 21},
{"kitten", "sitting", map[rune]int{'k': 1, 'i': 2, 't': 3, 'e': 4, 'n': 5, 's': 6, 'g': 7}, 20},
}
for _, test := range tests {
actual := WeightedEditDistance(test.word1, test.word2, test.weights)
if actual != test.expected {
t.Errorf("WeightedEditDistance(%s, %s, %v) = %d, expected %d", test.word1, test.word2, test.weights, actual, test.expected)
}
}
}
[心得] 日本轉職面試 bytedance/paypay/amazon
先問如果有個EC網站，客戶抱怨很慢，要怎麼除錯？
- 網站效能測試：使用效能測試工具（例如Google PageSpeed Insights、GTmetrix或WebPagetest）來評估網站的加載速度和效能。這些工具可以提供關於網站性能的詳細報告，包括可能導致緩慢加載的問題。
- 檢查伺服器效能：確保你的伺服器能夠處理網站流量。檢查伺服器的資源使用情況，包括處理器、記憶體和網路帶寬。如果伺服器資源不足，可能需要升級伺服器或考慮使用負載平衡技術。
- 檢查程式碼優化：檢查網站的程式碼，尤其是後端程式碼，確保它們被適當地優化和效能良好。優化程式碼可以包括減少資料庫查詢次數、避免重複計算和最佳化迴圈等。
- 瀏覽器相容性：確認網站在不同瀏覽器中的相容性。有時網站可能在某些瀏覽器上較慢，因此測試並修復瀏覽器相容性問題可能會改善網站的加載速度。
- 圖片和檔案壓縮：確保圖片和其他靜態檔案被壓縮以減少檔案大小。大型圖片和檔案可能會導致網站加載緩慢，因此使用壓縮工具（例如ImageOptim或TinyPNG）可以幫助改善網站效能。
- 快取和緩存：使用快取和緩存技術來儲存網站資源，以減少每次請求的伺服器負擔。這可以通過設定HTTP快取標頭、使用快取外掛程式或通過Content Delivery Network（CDN）來實現。
- 監控和日誌分析：使用監控工具和日誌分析來追蹤網站的效能問題。這些工具可以提供關於網站流量
如果慢的是place order，而這是一個行銷活動, 期望會有大量user，該怎麼設計架構？
pub/sub message queue
TODO: BFS找有幾塊1的經典題目
以下是幾個與BFS在矩陣中尋找1塊數量相關的經典LeetCode題目：
LeetCode 200. Number of Islands (島嶼的數量) 難易度: Medium
- 題目描述：給定一個由 '1'（陸地）和 '0'（水域）組成的二維矩陣，計算矩陣中有多少個相互連接的陸地區域。
- 解題思路：使用BFS或DFS遍歷矩陣，將相鄰的陸地標記為已訪問，並計算有多少個相互連接的陸地區域。
- 連結：https://leetcode.com/problems/number-of-islands
- 分類:
- Data Structure: Array & String, Matrix
- Algorithm: DFS & BFS
LeetCode 695. Max Area of Island (島嶼的最大面積) 難易度: Medium
- 題目描述：給定一個由 '1'（陸地）和 '0'（水域）組成的二維矩陣，計算矩陣中連續的1所組成的最大區域的面積。
- 解題思路：使用BFS或DFS遍歷矩陣，計算每個島嶼的面積，並找到最大的面積值。
- 連結：https://leetcode.com/problems/max-area-of-island
- 分類:
- Data Structure: Array & String, Matrix
- Algorithm: DFS & BFS
LeetCode 733. Flood Fill (區域填充) 難易度: Easy
- 題目描述：給定一個起始位置和目標顏色，將起始位置和與其相鄰的具有相同顏色的區域都填充為目標顏色。
- 解題思路：使用BFS或DFS遍歷矩陣，將具有相同顏色且與起始位置相鄰的區域標記為目標顏色。
- 時間複雜度: O(N), 其中 N 是圖像的像素數量
- 空間複雜度: O(N), 使用遞迴或佇列時需要額外的空間存儲遍歷的位置
- 連結：https://leetcode.com/problems/flood-fill
- 分類:
- Data Structure: Array & String, Matrix
- Algorithm: DFS & BFS
- Solution :
[請益] (ByteDance 面試) 兩種不同寫法的複雜度分析
leetcode 3. Longest Substring Without Repeating Characters (Medium)
My solution: 0003.Longest-Substring-Without-Repeating-Characters
func LengthOfLongestSubstringBit(s string) int {
slength := len(s)
if slength == 0 || slength == 1 {
return slength
}
// ASCII 0~255
charMap := [256]bool{}
maxLen, left, right := 0, 0, 0
for left < slength {
if ok := charMap[s[right]]; ok {
// 有找到
charMap[s[left]] = false
left++
} else {
charMap[s[right]] = true
right++
}
if maxLen < right-left {
maxLen = right - left
}
if left+maxLen >= slength || right >= len(s) {
break
}
}
return maxLen
}