Here is the generated study plan from GitHub Copilot: | Day | Night (2 hours) | Midnight (1.5 hours) | | --- | --------------------------------- | ----------------------------------- | | 1 | SadServers (Disk, Processes) | SadServers (Services, Networking) | | 2 | SadServers (Permissions, Logs) | Linux command drills | | 3 | LeetCode 15, 11, 3 (Two Pointers) | LeetCode 33, 34, 74 (Binary Search) | | 4 | LeetCode 200, 133, 207 (Graphs) | LeetCode 994, 102, 236 (BFS/DFS) | | 5 | LeetCode 322, 198, 300 (DP) | LeetCode 46, 78 (Backtracking) | It also comes with a check-list: - Can write BFS/DFS templates from memory - Can implement binary search without off-by-one errors - Know `systemctl`, `journalctl`, `df`, `du`, `netstat` commands - Completed at least 5 SadServers scenarios successfully - Did 2 full medium problems timed, within 25 minutes each ## SadServers I tested the following commands using a Docker container with the `ubuntu:22.04` image. Some tools require additional installation: ```shell docker run \ --rm --interactive --tty \ --privileged \ ubuntu:22.04 bash -c " apt-get update && apt-get install --yes sysstat nmap && exec bash" ``` ### System Monitoring | Command | Description | | ----------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | `uptime` | Total load average over **1/5/15** minutes | | `dmesg \| tail` | Watch for the error messages. Always check this since the messages are clear indicators | | `vmstat 1` | Watch **r** for running processes and **us** for user CPU usage | | `mpstat -P ALL 1` | List CPU usage per processor | | `pidstat 1` | List CPU usage per process. A 1600 **%CPU** means the process takes 16 cores fully loaded | | `iostat -xz 1` | Watch too-high **r/s**, **w/s**, **await** for excessive load, >1 **avgqu-sz** for being saturated, >60% **%util** for being too busy. This is not a strong indication as many techniques perform I/S asynchronously | | `free -m` | RAM. Safe as long as they are non-zero, which can lead to higher disk I/O (confirm using `iostat -xz 1`). Free memory can include buffers/cache which can be reclaimed quickly when needed | | `ps auxf` | Display running processes. `a` shows processes for all users, `u` displays the process's user/owner, `x` shows processes not attached to a terminal, and `f` displays a tree view of processes | ### Network Diagnostics | Command | Description | | ------------------------ | ------------------------------------------------------------------------------------------------------------------------------------------------------ | | `ping -W 1 -c 1 8.8.8.8` | Test network connectivity by sending a request to Google's DNS server. Fail if no response (`-c`) is received within 1 second (`-W`) | | `sar -n DEV 1` | Network interface throughput. Watch **rxkB/s** (received KB/s) and **txkB/s** (transmitted KB/s) especially | | `sar -n TCP,ETCP 1` | TCP metrics. See **active/s** for locally initialized connections, **passive/s** for remote connections, **retrans/s** for retransmissions | | `netstat -tulpn` | Show active listening ports and associated programs. `-t` for TCP, `-u` for UDP, `-l` for listening, `-p` for program name, `-n` for numeric addresses | | `nc -zv -` | Scan open ports in a given range. `-z` for scanning without sending data, `-v` for verbose output | | `nmap -p - localhost` | Scan all 65535 TCP ports on localhost, where `-` represents the full range of ports (1-65535) | ### Text Processing | Command | Description | | --------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------- | | `awk '{print $1}' ` | Extract the first column from a file or command output, separating fields by whitespace (use `-F` for a different delimiter) | | `awk -F "" -v OFS="" '{print $1, $2}' ` | `-v` to specify variables, such as `OFS` to set output field separator, `ORS` to set output record separator | | `uniq -c` | Count unique occurrences of lines in a file | | `sort -nr` | Sort lines of text files. `-n` sorts numerically, `-r` reverses the order (descending) | | `head -n 1`/`tail -n 1` | Display the first or last line of a file or output | | `head -c -1` | Display all but the last character of a file | | `head -n 173 \| tail -n 1` | Display only the 173rd line of a file | | `grep ` | `-i` for case-insensitive search, `-w` for whole word match, `-r` for recursive search, `-c` for count of matches, `-n` to show line numbers | | `grep -A 3 -B 2 ` | Show 3 lines after and 2 lines before each match of the pattern in a file | | `grep -C 4 ` | Show 4 lines of context (before and after) for each match of the pattern in a file | | `grep -c " " ` | Count non-empty lines in a file (lines containing at least one space character) | | `echo -n ` | Print a string without a trailing newline | ### Service Management | Command | Description | | ------------------------------- | ------------------------------------------------------------------------------------------------------------------------------ | | `systemctl ` | Manage system services. Common commands include `start`/`stop`, `restart`, `status`, and `enable`/`disable` (to start on boot) | | `systemctl list-units --failed` | List all failed services | | `journalctl -u -f` | View logs for a specific service managed by systemd, `-f` to follow | ### Database Management Most of the databases need to load their configuration files by `systemctl restart `. #### PostgreSQL | Command | Description | | ------------------------------------------------------ | --------------------------------------------------------------------------------------- | | `PASSWORD="" psql -U -d -c '\q'` | Connect to a PostgreSQL database as a specific user and execute a command. `\q` to quit | | `cat /etc/postgresql/$version/main/pg_hba.conf` | View PostgreSQL authentication configuration file | ### Kubernetes Management | Command | Description | | ---------------------------- | ---------------------------------------------- | | `kubectl get pods` | List all pods in the current namespace | | `kubectl get services` | List all services in the current namespace | | `kubectl describe pod ` | Show detailed information about a specific pod | ## LeetCode I only focus on problems that can be solved with specific techniques. ### Two Pointers This is often used in problems involving arrays or strings, where we need to find pairs or triplets that satisfy certain conditions. The idea is to use two pointers that move towards each other or in the same direction to reduce the time complexity. Sometimes, it can be three pointers. #### 15. 3 Sum > See [LeetCode 15. 3Sum](https://leetcode.com/problems/3sum/). - Sort the given array if possible to create a predictable order - Skip duplicates by comparing with the previous/next element when entering a loop - The outer loop doesn't have to be the left or right pointer, it can be a fixed pointer with the other two moving towards each other ```python {1,4-5,17-20} nums.sort() result = [] for i in range(0, len(nums) - 1): if i > 0 and nums[i] == nums[i - 1]: continue target = -nums[i] j = i + 1 k = len(nums) - 1 while j < k: two_sum = nums[j] + nums[k] if two_sum == target: result.append((nums[i], nums[j], nums[k])) j += 1 k -= 1 while j < k and nums[j] == nums[j - 1]: j += 1 while j < k and nums[k] == nums[k + 1]: k -= 1 elif two_sum < target: j += 1 else: k -= 1 return result ``` #### 11. Container With Most Water > See [LeetCode 11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/). - Can move both pointers accordingly ```python {9-12} def get_area(left, right): return (right - left) * min(height[left], height[right]) result = 0 left, right = 0, len(height) - 1 while left < right: result = max(result, get_area(left, right)) if height[right] < height[left]: right -= 1 else: left += 1 return result ``` #### 3. Longest Substring Without Repeating Characters > See [LeetCode 3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/). - Store pointer positions in a hash map for quick lookup ```python {5-6,8} result = 0 left = 0 seen = {} for right in range(0, len(s)): if s[right] in seen and left <= seen[s[right]]: left = seen[s[right]] + 1 seen[s[right]] = right result = max(result, right - left + 1) return result ``` ### Sliding Window A window is a subset of contiguous elements in an array that is defined by two pointers. We focus on expanding and contracting the window for the certain value across the window to find the answer. #### 424. Longest Repeating Character Replacement > See [LeetCode 424. Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/). - Think if the most common/rare value can be compared and stored with `max`/`min` to avoid recalculating ```python {8} result = 0 left = 0 window = Counter() most = 0 for right in range(0, len(s)): window[s[right]] += 1 most = max(most, window[s[right]]) while (right - left + 1) - most > k: window[s[left]] -= 1 left += 1 result = max(result, right - left + 1) return result ``` ### Binary Search When the given array is sorted or has a certain order, and the problem requires a `O(log n)` solution, binary search is often a good choice. #### 33. Search in Rotated Sorted Array > See [LeetCode 33. Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/). - Use normal binary search in the correct half, go the other half otherwise ```python {11-14,16-19} left = 0 right = len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid if nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 else: if nums[right] >= target > nums[mid]: left = mid + 1 else: right = mid - 1 return -1 ``` #### 34. Find First and Last Position of Element in Sorted Array > See [LeetCode 34. Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/). - Can use binary search multiple times to find boundaries - When middle equals left or right - When there is no more similar element on one side ```python {6-9,22-25} def findLeftBound(left, right): while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: if mid == left or nums[mid - 1] != nums[mid]: return mid else: right = mid - 1 elif nums[mid] > target: right = mid - 1 else: left = mid + 1 return -1 def findRightBound(left, right): while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: if mid == right or nums[mid + 1] != nums[mid]: return mid else: left = mid + 1 elif nums[mid] > target: right = mid - 1 else: left = mid + 1 return -1 left = 0 right = len(nums) - 1 mid = left + (right - left) // 2 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: break elif nums[mid] > target: right = mid - 1 else: left = mid + 1 left = findLeftBound(left, mid) if left == -1: return [-1, -1] return left, findRightBound(mid, right) ``` #### 74. Search a 2D Matrix > See [LeetCode 74. Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/). - Indices can be virtualized by `m * n`, where `m` is the number of rows and `n` is the number of columns - Current row is `index // n` - Current column in the row is `index % n` ```python {6,8-9} m = len(matrix) n = len(matrix[0]) if m == 0: return False left, right = 0, m * n - 1 while left <= right: pivot = (left + right) // 2 pivot_value = matrix[pivot // n][pivot % n] if target == pivot_value: return True elif target < pivot_value: right = pivot - 1 else: left = pivot + 1 return False ``` - Binary search can be done vertically ```python {8} def findRow(): top = 0 bottom = len(matrix) - 1 while top <= bottom: mid = top + (bottom - top) // 2 if matrix[mid][0] <= target <= matrix[mid][len(matrix[mid]) - 1]: return mid elif matrix[mid][0] < target: top = mid + 1 else: bottom = mid - 1 return False row = findRow() if row == -1: return False left = 0 right = len(matrix[row]) - 1 while left <= right: mid = left + (right - left) // 2 if matrix[row][mid] == target: return True elif matrix[row][mid] > target: right = mid - 1 else: left = mid + 1 return False ``` ### Graphs I guess most of the problems can be solved with DFS or BFS. #### 200. Number of Islands > See [LeetCode 200. Number of Islands](https://leetcode.com/problems/number-of-islands/). - DFS can be more efficient than BFS due to less overhead from queueing - Mark visited nodes by modifying the original grid to avoid using extra space (LeetCode only. I don't think it is a good practice) ```python def search(row, col): if row == -1 or row >= len(grid): return if col == -1 or col >= len(grid[row]): return if grid[row][col] == "0": return grid[row][col] = "0" search(row + 1, col) search(row - 1, col) search(row, col + 1) search(row, col -1) result = 0 for row in range(0, len(grid)): for col in range(0, len(grid[row])): if grid[row][col] == "1": search(row, col) result += 1 return result ``` - Queueing can be a TLE factor in BFS ```python {5-6} def search(row, col): queue = deque([(row, col)]) while queue: next_row, next_col = queue.popleft() # Unnecessary queueing and dequeuing grid[next_row][next_col] = "0" ``` ```python {3} def search(row, col): queue = deque([(row, col)]) grid[row][col] = "0" while queue: next_row, next_col = queue.popleft() for direction in ((1, 0), (-1, 0), (0, -1), (0, 1)): nr = next_row + direction[0] nc = next_col + direction[1] if nr >= 0 and nr < len(grid) and \ nc >= 0 and nc < len(grid[nr]) and \ grid[nr][nc] == "1": grid[nr][nc] = "0" queue.append((nr, nc)) result = 0 for row in range(0, len(grid)): for col in range(0, len(grid[row])): if grid[row][col] == "1": search(row, col) result += 1 return result ``` #### 133. Clone Graph > See [LeetCode 133. Clone Graph](https://leetcode.com/problems/clone-graph/). - The visited condition can be whether the node is cloned or not - Use original nodes to loop through neighbors to the visited map, then map cloned ones to the clones' neighbors ```python {7,14} visited = {} if node is None: return None visited = {} def visit(current): if current.val in visited: return visited[current.val] clone = Node(current.val, []) visited[current.val] = clone for neighbor in current.neighbors: clone.neighbors.append(visit(neighbor)) return clone return visit(node) ``` #### 207. Course Schedule > See [LeetCode 207. Course Schedule](https://leetcode.com/problems/course-schedule/). - A visited map can have multiple states, such as **taking**, **taken**, and `None` ```python {7,14} if numCourses <= 1: return True to_take = defaultdict(list) for course, pre in prerequisites: to_take[course].append(pre) study = {} def take(course): if course in study: if study[course] == "taking": return False if study[course] == "taken": return True study[course] = "taking" for pre in to_take[course]: is_able = take(pre) if not is_able: return False study[course] = "taken" return True for course in range(0, numCourses): if not take(course): return False return True ``` #### 994. Rotting Oranges > See [LeetCode 994. Rotting Oranges](https://leetcode.com/problems/rotting-oranges/). - Set a delimiter like `(-1, -1)` to indicate the end of a round in BFS - Append a new delimiter right after encountering one (only when the queue is not empty) ```python {15,20-24} queue = deque([]) freshes = 0 for row in range(len(grid)): for col in range(len(grid[row])): if grid[row][col] == 1: freshes += 1 if grid[row][col] == 2: queue.append((row, col)) if freshes == 0: return 0 if len(queue) == 0: return -1 queue.append((-1, -1)) days = -1 rottens = 0 while queue: row, col = queue.popleft() if row == -1: days += 1 if queue: queue.append((-1, -1)) continue for direction in DIRECTIONS: next_row = row + direction[0] if next_row < 0 or next_row == len(grid): continue next_col = col + direction[1] if next_col < 0 or next_col == len(grid[next_row]): continue if grid[next_row][next_col] == 0: continue if grid[next_row][next_col] == 2: continue queue.append((next_row, next_col)) grid[next_row][next_col] = 2 rottens += 1 return days if rottens == freshes else -1 ``` #### 102. Binary Tree Level Order Traversal > See [LeetCode 102. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/). - Same technique as [994. Rotting Oranges](#994-rotting-oranges) with a delimiter to separate levels ```python {5,11-16} if root is None: return [] queue = deque([root]) queue.append(None) result = [] current = [] while queue: item = queue.popleft() if item is None: result.append(current) current = [] if queue: queue.append(None) continue current.append(item.val) if item.left: queue.append(item.left) if item.right: queue.append(item.right) return result ``` #### 236. Lowest Common Ancestor of a Binary Tree > See [LeetCode 236. Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/). - Don't get confused with `p` and `q`, they are not necessarily the left and right nodes - Lowest common ancestor is the first node can reach both `p` and `q` ```python {4,10} def search(current): if current is None: return None if current is p or current is q: return current left = search(current.left) right = search(current.right) if left and right: return current else: return left if left else right ``` ### Dynamic Programming When it comes to finding the maximum/minimum value with previous computations, dynamic programming is often a good choice. #### 322. Coin Change > See [LeetCode 322. Coin Change](https://leetcode.com/problems/coin-change/). ##### Top-Down Memoization - Initialize the DP array with `amount + 1` to make `cache[amount]` more intuitive - Always cache the minimum value at each step - The return value can be different from the first time and subsequent times ```python {6-7,15} def toss(reminder, cache): if reminder < 0: return -1 if reminder == 0: return 0 if cache[reminder] != float("inf"): return cache[reminder] min_cost = float("inf") for coin in coins: tryout = toss(reminder - coin, cache) if tryout != -1: min_cost = min(min_cost, tryout + 1) cache[reminder] = -1 if min_cost == float("inf") else min_cost return cache[reminder] cache = [float("inf")] * (amount + 1) return toss(amount, cache) ``` ##### Bottom-Up Tabulation - Increase cost by 1 when needing one or more coins ```python {6-7} dp = [float("inf")] * (amount + 1) dp[0] = 0 for current in range(1, amount + 1): for coin in coins: if current >= coin: dp[current] = min(dp[current], dp[current - coin] + 1) return dp[amount] if dp[amount] != float("inf") else -1 ``` #### 198. House Robber > See [LeetCode 198. House Robber](https://leetcode.com/problems/house-robber/). - Same as [322. Coin Change](#322-coin-change) but taking care of the initial and jump conditions - Be careful with the indices and the offset between `nums` and `dp` ```python {2-4,8} dp = [None] * (last_house + 1) dp[0] = 0 dp[1] = nums[0] dp[2] = max(dp[1], nums[1]) for i in range(3, last_house + 1): current_money = nums[i - 1] dp[i] = max(dp[i - 1], current_money + dp[i - 2]) return dp[last_house] ``` #### 300. Longest Increasing Subsequence > See [LeetCode 300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/). - Even with dynamic programming, the time complexity of a valid solution can be `O(n^2)` ```python {7} dp = [None] * len(nums) max_count = float("-inf") for i in range(0, len(nums)): current = nums[i] dp[i] = 1 for j in range(0, i): previous = nums[j] if previous < current: dp[i] = max(dp[i], 1 + dp[j]) max_count = max(max_count, dp[i]) return max_count ``` ### Backtracking Most backtracking problems can be solved with a very similar template, which is defining a recursive function with a base case and a recursive step iterating choices. In the recursive step, we sometimes need to verify if the current choice is valid or not, and we may need to undo the choice after the recursive backtracking call. #### 46. Permutations > See [LeetCode 46. Permutations](https://leetcode.com/problems/permutations/). - Choices' status can be used as an end condition - Backtrack (`current.append()` then `current.pop()`) is not always needed if we handle `remaining` properly ```python {4} result = [] def backtrack(current, remaining): if not remaining: result.append(current) return for i in range(0, len(remaining)): backtrack(current + [remaining[i]], remaining[:i] + remaining[i + 1:]) backtrack([], nums) return result ``` #### 78. Subsets > See [LeetCode 78. Subsets](https://leetcode.com/problems/subsets/). - Can append the current combination at each step without waiting for the end condition - Keep in mind that `choices` is changing at each step, hence careful using it as a base case condition ```python {4,6-7,9-12} result = [] def backtrack(current, choices): result.append(current[:]) if len(current) > len(nums): return for i in range(0, len(choices)): current.append(choices[i]) backtrack(current, choices[i + 1:]) current.pop() backtrack([], nums) return result ```