2023 年「資訊科技產業專案設計」作業 1

Contributor: 六六 Leo

977. Squares of a Sorted Array

video
Google Docs

面試過程

Repeat

• Interviewer: Hi, I'm today's interviewer. If you are ready. let's get started. Suppose we have an integer array nums sorted in non-decreasing order, please write a function that returns an array of the squares of each number sorted in non-decreasing order.
• Interviewee: Let me make sure I understand the problem correctly. What is the range of the element of input array?
• Interviewer: The element of the input array is between 10,000 and negative 10,000.
• Interviewee: How many elements at most in the input array?
• Interviewer: 10,000 elements
• Interviewee: Can the input array be empty?
• Interviewer: No, you can assume the input array has at least one element.
• Interviewee: Should I sort the array in-place or out-of-place?
• Interviewer: You should not modify the input array. Please use an out-of-place appoarch.

Examples

• Interviewee: No problem. So if I have an array [1, 2, 3] then I should returns [1, 4, 9] right?
• Interviewer: Yes.
• Interviewee: If a have an array [-2, -1, 0, 1, 2], then I should returns [0, 1, 1, 4, 4].
• Interviewer: Yes.

Approach

• Interviewee: Thanks for clarifying. In this problem. I would first allocate a memory space for the output array, which has the same length as the input array. Its element is the squares of each element of input array with the same index. Finally, sort the output array.
• Interviewer: Good. Can you write down the code?

Code

• Interviewee: Sure.

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int* sortedSquares(int* nums, int size, int* retSize) {
    *retSize = size;
    int* ret = malloc(size * sizeof(int));

    // square the elements
    for (int i = 0; i < size; i++) {
        ret[i] = nums[i] * nums[i];
    }

    // sort the array
    qsort(ret, size, sizeof(int), cmp);

    return ret;
}

Optimization

• Interviewer: It looks no problem. But if the length of input array grows, what does the execution time be affected?
• Interviewee: As the length of input array grows, the execution time will grows in an
  $O(nlog(n))$ level.
• Interviewer: Is there a better way?
• Interviewee: Yes, we can use the techniques of two pointers to optimize the execution time to
  $O(n)$.
• Interviewer: Can you explain the

int *sortedSquares(int *nums, int size, int *retSize) {
    *retSize = size;
    int *ret = malloc(size * sizeof(int));

    int *l = nums, r = nums + size - 1;
    for (int i = size - 1; i >= 0; i--) {
        int ls = *l * *l, rs = *r * *r;
        if (ls > rs) {
            ret[i] = ls;
            l++;
        } else {
            ret[i] = rs;
            r--;
        }
    }

    return ret;
}

• Interviewer: We don't have much time left. I think this is good enough. So That's the interview for today. Thank you for your time.

231. Power of Two

video
Google Docs

面試過程

Repeat

• Interviewer: Given an integer
  $n$, check if it is a power of 2.
• Interviewee: So if the number
  $n$ is power of 2, then returns true. Ohterwise returns false, right?
• Interviewer: Yes.
• Interviewee: What is the range of the input number
  $n$?
• Interviewer:
  $n$ is between negative 2 to the power of 31 and 2 to the power of 31 minus 1 (
  $-2^{31}<=n<=2^{31}-1$).

Examples

• Interviewee: So if
  $n$ is negative or 0, then I should return false, right?
• Interviewer: Yes.

Approach

• Intervieree: I would use the recursive method. If n is not divisible by 2, it is definitely not a power of 2, then return false. If n is divisible by 2, then continue to check if n/2 is a power of 2 until n/2 equals 2.
• Intervieree: And before entering the recusive function, I would first check if
  $n$ is positive

Code

bool _isPowerOfTwo(int n) {
    if (n == 2) return true;
    if (n % 2) return false;
    return _isPowerOfTwo(n / 2);
}

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    if (n == 1) return true;
    return _isPowerOfTwo(n);
}

Optimization

• Interviewer: Well, it looks no problem. Can you figure out another method that execute in constant time?
• Interviewee: OK, let me give it a try. I would like to observe the binary representation of the power of two by writing it down. And then we can find it that if a number
  $n$ is the power of 2, then its binary representation would be a 1 followed by several or no 0s. Otherwise,
  $n$ would not be power of 2. Therefore, we can check if
  $n$ is power of 2 by masking
  $n$ with

/*
     1 => 0b1
     2 => 0b10
     4 => 0b100
     8 => 0b1000
    16 => 0b10000
    ...
 */

bool isPowerOfTwo(int n) {
    if (n < 1) return false;
    return !(n & (n - 1));
}

451. Sort Characters By Frequency

video
Google Docs

面試過程

Repeat

Interviewer: 同學你好，我是今天的面試官，讓我們開始今天的面試。首先給定一個字串 s，請你依照裡面每個字元出現的頻率做遞減排序，也就是出現次出越高的字元排在前面，出現次數越少的字元排在後面，最後將排序好的字串回傳，如果有多種可能的排法，則回傳其中一種即可。

Examples

Interviewee: 好的，所以說我要針對一個字串中的字元頻率做排序，也就是如果 s 是 "tree"，那我得回傳 "eert"，如果 s 是 "cccaaa"，那回傳 "cccaaa" 或 "aaaccc" 都可以，對嗎？
Interviewer: 對，你理解得沒錯

s = "tree" => "eert"
s = “cccaaa” => “cccaaa” or “aaaccc”

Approach

Interviewee: 針對這題我會使用 hash map 的方式，先計算字串中每個字元出現的次數，然後對次數做排序，最後產生要回傳的字串
Interviewer: 好的，請你將程式碼實作出來

1. count the frequency of characters
2. sort by frequency
3. generate output string

Code

typedef struct Pair {
    char ch;
    uint32_t freq;
} Pair;

enum {
    FORMER = -1,
    LATTER = 1,
    EQUAL = 0,
};

int32_t cmp(const void* a, const void* b) {
    Pair pa = *(const Pair*)a;
    Pair pb = *(const Pair*)b;
    if (pa.freq > pb.freq) return FORMER;
    if (pa.freq < pb.freq) return LATTER;
    if (pa.ch < pb.ch) return FORMER;
    if (pa.ch > pb.ch) return LATTER;
    return EQUAL;
}

#define CHAR_BIT_SIZE 256U

char* frequencySort(char* str) {
    Pair* map = calloc(CHAR_BIT_SIZE, sizeof(Pair));
    for (char* ch = str; *ch; ch++) {
        map[*ch].ch = *ch;
        map[*ch].freq++;
    }
    
    qsort(map, CHAR_BIT_SIZE, sizeof(Pair), cmp);
    
    uint32_t c = 0;
    for (uint32_t i = 0; i < CHAR_BIT_SIZE; i++) {
        if (!map[i].freq) break;
        for (uint32_t j = 0; j < map[i].freq; j++) {
            str[c++] = map[i].ch;
        }
    }
    str[c] = '\0';
    return str;
}

Interviewer: 好的程式碼看起來沒什麼問題，那我們時間差不多了，今天的面試就先告一段落，謝謝

初步檢討

1. REACTO 的 Test 並沒有確實執行
2. 第三題 (451. Sort Characters By Frequency) 的程式實作中，map 的記憶體用完應該要記得用 free 釋放掉

---

第二次作業 - 他評 01

Interviewer

• 優點
• 對答還蠻自然的，而且講話也很清楚。
• 可改進部分
• 面試官跟面試者雖然看的出來是用全螢幕區分，但應該要再區分明確一點，比如說用不同帽子之類的。

Interviewee

• 優點
• 在對答和改善程式碼的時候，有把例子跟條件都打上去，讓面試官可以更了解想法和改進方式。
• 可改進部分
• 語速很ok，但是語助詞(痾)有點多。

第二次作業 - 他評 02

Interviewer

• 優點

• 口條清晰。

• 可改進部分

• 題目部分，不要直接給定 Leetcode 題號，容易讓受訪者背誦題目。
• 跟interviewee沒有太多互動，像是在考試一樣。

Interviewee

• 優點

• 舉例清楚，撰寫程式時的註解也有幫助理解的功用
• A 的部分一條條列出來，對理解想法上有幫助。

• [ ]可改進部分

• R 的部分跳過了，直接快進到了 E 的部分。
• 知道自己在講什麼，實作上的細節都有講到，但可以稍微放慢速度，略顯緊張

第二次作業 - 他評 03

Interviewer

• 優點

• 講話簡短扼要

• 可改進部分

• (第一題) 06:27: "Can you come up with a better way?" 可以改成更明確的說法，像是 "How can you improve the time complexity?"，可以讓 interviewer 不需要揣測要做什麼。

Interviewee

• 優點

• 有把題目輸入的條件紀錄在文件上
• 有適當的寫註解

• 可改進部分

• 在寫程式的時候，filler （如 uh） 有點多。可以稍微有點沉默，等確定想好以後再一次把句子講完。
• (第一題) 07:07: 講解比較大小的條件時，可以把條件和要做的事情寫成 pseudo code，會比直接聽更好懂。
• (第二題) 06:20: 「因為使用遞迴，所以時間複雜度是
  $O(\log n$)」，應該可以改成說「如果 n 為二的 k 次方，則需要呼叫遞迴函式 k 次，也就是
  $lo{g}_2^n$ 次，因此時間複雜度為
  $O(\log n)$」，會解釋得比較清楚。

第二次作業 - 他評 04

Interviewer

• 優點

• 口齒清晰

Interviewee

• 優點

• 英文講得很好
• 打字速度很快，排版整齊
• 對問題的提問很全面
• 寫程式時會一邊寫一邊解釋程式，很棒
• 第一題 two pointer 講解很清楚，用 ^ 在 array 的下一行代表pointer是個好方法
• 第三題寫程式前先用註解寫大綱很清楚的表達了程式內容

第二次作業 - 他評 05

Interviewer

• 優點

• 咬字清楚，語速與音量適當

• 可改進部分

• 避免自稱 interviewer
• 0:00：除了口頭帶過題目，也在螢幕上顯示題目
• 避免使用 LeetCode 原題，建議適度做更改，或結合實例

Interviewee

• 優點

• 咬字清楚，語速與音量適當
• Repeat 及 Example 部分 解釋得非常清楚，非常棒
• Coding 部分有做到邊寫程式邊做講解，令人刮目相看
• 1:22：向面試官詢問能否進行 in-place 排序，展現自己的細心

• 可改進部分

• 因為使用 Word，可以嘗試將重點用紅字標示