2024 年「資訊科技產業專案設計」課程作業 4

# 2024 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2024/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FH1-4KbanC)」課程第 4 次作業 > 貢獻者: 爛咖Weak、哈哈球Hahaball > 影片連結: [Interviewer](https://youtu.be/IJ3067ORLr4)、[Interviewee](https://youtu.be/d3BYMy5SOhA) + 作業要求觀摩「[學員作業清單](https://hackmd.io/@sysprog/rJmM-nhbkx)」，挑出你認為表現優異的學員數明，利用該 LeetCode 題目設計延伸問題 (follow-up)，比照 Meta 和 Google 公司面試風格和難度，準備你作為 interviewer 所擬定的題目 --- ## [704. Binary Search](https://leetcode.com/problems/binary-search/) > :man: interviewer : Hahaball > :baby: interviewee : Weak :man: interviewer: welcome to our interview. We're excited to have you here today. Let’s start with something basic. Write a function to search for a target value in an array, assume the array is sorted in ascending order :baby: intervwee: To clarify, is the input array contains only integers? and should I handle cases where the target doesn’t exist in the array? :man: interviewer: Yes, the array contains integers, and you only need to return the index of the first occurrence of the target. If the target doesn’t exist, you should return -1. :baby: interviewee: Got it, so I will use binary search to find the target. First I will define head and tail. And binary search compares the target value to the middle element of the array, ```c int mid = head + (tail - head) / 2; if (nums[mid] == target) return mid; ``` If unequal, eliminate the half where the target can't be and continue searching in the remaining half. ```c if (nums[mid] > target) tail = mid - 1; else head = mid + 1; ``` Again compare the middle element with the target, repeating until the target is found or the search ends with an empty half, that's mean the target is not in the array. ```c while(head <= tail) { ... } return -1; ``` :baby: interviewee: Here’s the solution: ```c int search(int* nums, int numsSize, int target) { int head = 0; int tail = numsSize - 1; while (head <= tail) { int mid = head + (tail - head) / 2; if (nums[mid] == target) return mid; if (nums[mid] > target) tail = mid - 1; else head = mid + 1; } return -1; } ``` If the array is sorted, we can use binary search to improve efficiency, which results in a time complexity of $O(log(n))$. :man: interviewer: Ok. Now imagine the sorted array is part of a pre-processing step for another problem. You need to determine whether the array has more positive numbers or negative numbers. Maybe you can use binary search to improve the solution about this problem. :baby: interviewee: Is zero belong postive or negative? :man: interviewer: 0 is neither positive nor negative. :baby: interviewee: So, my task is to write a program that can deal with this problem by binary search. First, identify the position of the last negative number and the first positive number. ```c int negEnd = -1; int posStart = numsSize; ``` And perform a binary search to locate the last negative number by checking for numbers less than 0. ```c while (low <= high) { int mid = low + (high - low) / 2; } ``` If the middle element is negative, update the position and shift the search range to the right. ```c if (nums[mid] < 0) { negEnd = mid; low = mid + 1; } ``` else if the middle element is not negative, shift the search range to the left. ```c else { high = mid - 1; } ``` Next, perform another binary search to find the first positive number using a similar approach. ```c // Find the first posi number ``` :man: interviewer: Finally, I'll compare the two counts and return the greater one. ```clike int negCount = negEnd + 1; int posCount = numsSize - posStart; return negCount > posCount ? negCount : posCount; ``` Here’s the solution: ```c int maximumCount(int* nums, int numsSize) { int negEnd = -1; int posStart = numsSize; // Find the last neg number int low = 0, high = numsSize - 1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] < 0) { negEnd = mid; low = mid + 1; } else { high = mid - 1; } } // Find the first posi number low = 0, high = numsSize - 1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] > 0) { posStart = mid; high = mid - 1; } else { low = mid + 1; } } int negCount = negEnd + 1; int posCount = numsSize - posStart; return negCount > posCount ? negCount : posCount; } ``` The overall time complexity is dominated by the binary searches, is O(log n). :man: interviewer: Good explanation. Why are you initializing negEnd and posStart to -1 and numsSize? :baby: interviewee: I use first one is -1 because if there are no negative numbers in the array, the count of negatives should be 0. Similarly, posStart is numsSize ensures that if there are no positive numbers. :man: interviewer: That's a solid approach. Well done, thank you for your participation today. ## [647. Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/description/) > :man: interviewer : Weak > :baby: interviewee : Hahaball :man: Hi Hahaball, welcome to our interview. Our company is currently developing a validation program for an encryption protocol. The goal is to identify and count certain symmetrical structures within a dataset. For example, palindromes are one such structure that holds significant importance. Could you design and implement a program to accomplish this task? ### (Repeat) :baby: Sure. So, my task is to write a program that takes a dataset as input, which could be a string or a sequence of integers, and returns the total number of palindromic structures within the dataset. Is my understanding correct? :man: Your understanding is correct, but to simplify the task, you can assume the dataset is a string containing only lowercase English letters. ### (Example) :baby: Ok, for example, if I input the string "abc", the program should return 3, because each character in the string, "a", "b", and "c", is a palindrome. :man: Yes. ### (Approach) :baby: Ok, so my approach is to first write a boolean function that checks if a string is a palindrome, then apply this function to all possible substrings, and finally sum up the number of palindromes. :man: Sounds good. Please go ahead and start implementing. ### (Code) ```c== bool IsPal(char* s, int left, int right){ while(left < right){ if(s[left++] != s[right--]) return 0; } return 1; } int countSubstrings(char* s) { int len = strlen(s); int ans = len; for(int i = 2; i <= len; i++){ for(int j = 0; j < len-i+1; j++){ int k = j+i-1; if(IsPal(s, j, k)) ans++; } } return ans; } ``` ### (Test) Use input: `s = "aaa"` to test the code. ### (Optimization) :man: Your code uses two for loops to check all possible substrings, which results in a time complexity of $O(n^2)$. This can be inefficient for very long input strings. Do you have any ideas on how to optimize the code to reduce its time complexity? :baby: Sure, another approach I can use is to treat each character as the center of a palindrome, then expand outwards to both sides while checking if it still forms a palindrome. Finally, I would sum up all the possible palindromes, which would reduce the time complexity to $O(n)$. ```c== int countSubstrings(char* s) { int len = strlen(s); int ans = 0; for(int i = 0; i < 2*len-1; i++){ int left = i/2; int right = left+i%2; while((left >= 0) && (right < len) && (s[left] == s[right])){ ans++; left--; right++; } } return ans; } ``` :man: Great, thank you for your participation today.