# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/)」課程第 2 次作業
> 乙二 - Two
> 👒: interviewer
> ◼️: interviewee
>
> 影片中戴帽子的是面試官，沒戴的是面試者

## 影片

- [第一題](https://youtu.be/KOVfvmkCNWE)

## [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/)

👒: 乙二先生你好，歡迎來到本公司的面試。本公司主打的產品是音樂播放器，在年度回顧的時候會需要知道使用者今年第一次聽，以及最近一次聽某一首歌的時間。假設我們已經從資料庫中取出某位使用者今年的所有聽歌紀錄，你會怎麼找出這兩個時間？
◼️: 我想確認一下，我需要在某個使用者的所有聽歌紀錄中，找到第一次聽這首歌，以及最後一次聽的時間，對嗎？
👒: 是的。
◼️: 好，那麼聽歌紀錄的 schema 會有哪些欄位？
👒: 聽歌紀錄的 schema 會有使用者 ID、歌曲 ID、時間這三個欄位。
◼️: 那麼時間是使用 unix timestamp 儲存的嗎？
👒: 是的，你可以將它當作整數處理。
👒: 請問使用者與歌曲 ID 都是 serial int 嗎，我能不能將它們當成整數處理？
◼️: 是的，可以。
◼️: 請問資料會不會依照任何欄位排序過？
👒: 紀錄會根據時間，從小到大排序，但歌曲 ID 沒有排序。
◼️: 好，那請讓我舉個範例：如果使用者聽歌的 ID 順序分別為 `[1,2,3,1,2`]，那麼尋找第一次聽的紀錄是在 index=0，最後一次聽是在 index=3，之後再取出時間就好，請問我理解的正確嗎？
👒: 是的，這樣沒有錯。
◼️: 好，那我的方法會是這樣：寫一個回傳 int vector 的函式，接收 records 和 songId 兩個參數。使用兩個變數儲存第一次和最後一次聽那首歌的 index，分別從開始與結束向中間搜尋，如果找到了歌曲就紀錄並停止搜尋，最後回傳這兩個 index。
👒: 好，你可以開始實作了

vector<int> findFirstAndLastListenIndexes(vector<Record>records, int songId){
    int firstIndex=-1;
    int lastIndex=-1;
    int currentIndex=0;
    while(currentIndex<records.size()){
        if(records[currentIndex].songId==songId){
            firstIndex=currentIndex;
            break;
        }
        currentIndex++;
    }
    
    currentIndex=records.size()-1;
    while(currentIndex>=0){
        if(records[currentIndex].songId==songId){
            lastIndex=currentIndex;
            break;
        }
        currentIndex--;
    }
    
    return  {firstIndex,lastIndex};
}

👒: 好，請你舉出一些範例來驗證這個演算法。
◼️: 如同我一開始舉的範例，如果聽歌的順序是 `[1,2,3,1,2]`，找歌曲編號 1，last 在第一個迴圈變成 0，而 lastIndex 則會變成 3。
◼️: 而如果是極端情況，例如空陣列，則會直接不進入迴圈；而找不到的情況則是迴圈完全跑完，但不改變 first 和 last index，都會回傳 -1。
👒: 好，這樣看起來每一種情況都有考慮到。
👒: 但是我注意到一個問題，在第一個迴圈找不到值的時候，這個演算法在第二個迴圈可能會做不必要的檢查，造成效能的浪費，你能修正這個問題嗎？
◼️: 當我們找不到第一個 index 的時候，就代表這首歌不存在於紀錄之中，如果是這樣的話，就不需要找最後一個 index，直接用 -1 就可以了。

vector<int> findFirstAndLastIndexes(vector<Record>records, int songId){
    int firstIndex=-1;
    int lastIndex=-1;
    int currentIndex=0;
    while(currentIndex<records.size()){
        if(records[currentIndex].songId==songId){
            firstIndex=currentIndex;
            break;
        }
        currentIndex++;
    }
    
+   if(firstIndex==-1){
+       return {-1,-1};
+   }
    
    currentIndex=records.size()-1;
    while(currentIndex>=0){
        if(records[currentIndex].songId==songId){
            lastIndex=currentIndex;
            break;
        }
        currentIndex--;
    }
    
    return  {firstIndex,lastIndex};
}

👒: 好，那麼可以請你分析這個演算法的時間複雜度嗎？
◼️: 這個演算法在 worst case 會需要搜索整個陣列一輪，所以時間複雜度是 O(n)。
👒: 那接下來的題目是假設聽歌紀錄已經根據歌曲 ID 排序過的情況，你會怎麼修改這個演算法來改善時間複雜度？
◼️: 請問除了依照歌曲 ID 排序，還會跟原本一樣保持以時間排序嗎？
👒: 是的，會和原本一樣升冪排序。
◼️: 好，那舉例來說，陣列的歌曲 ID 可能是 `[1,1,2,3,3]`，但不可能是`[1,3,2,2,1]`，請問這樣對嗎？
👒: 對。
◼️: 那舉例來說，如果歌曲 ID 是 `[1,1,2,3,3]` 找 1，那就應該回傳 0 和 1，對嗎？
👒: 對
◼️: 好，那麼我認為這題可以使用 binary search，因為陣列是升冪排序的。而在找到了目標以後，再從那個地方往前後找尋第一個與最後一個 index。
👒: 好，你可以開始實作了。

vector<int> findIndexes(vector<Record> records, int songId)
{
  int left = 0;
  int right = records.size() - 1;

  int first = -1;
  int last = -1;

  // O(log n)
  while (left <= right)
  {
    int mid = left + (right - left) / 2; // prevent overflow
    if (records[mid].songId == songId)
    {
      first = mid;
      last = mid;

      // worst case: loop every element O(n)
      while (first - 1 >= 0 && records[first - 1].songId == songId)
      {
        first--;
      }

      while (last + 1 < records.size() && records[last + 1].songId == songId)
      {
        last++;
      }
      break;
    }
    else if (records[mid].songId > songId)
    {
      right = mid - 1;
    }
    else
    {
      left = mid + 1;
    }
  }
  return {first, last}; // 0, 1
}
}

👒: 看起來沒有問題，你能舉出一些例子來證明演算法的正確性嗎？同時考慮極端情況。
◼️: 好，極端情況可能是空陣列或是找不到值，如果是空陣列，會直接不進入迴圈。
◼️: 而如果是找 5，會因為 `left > right` 而跳出迴圈，就會回傳 {-1,-1}。
◼️: 而如果沒有 overflow，則任何長度的陣列都是使用 binary search 找出值，並且向兩邊尋找。例如 `[1,1,2,3,3]` 找 1，mid=2、太大所以right=1, mid=0，找到，然後向左右找，找到 index 0 和 1。

👒: 好，這樣看起來程式是正確的。你能分析一下這個演算法的時間複雜度嗎？
◼️: 這個演算法使用了 binary search，在找到值的時候會花 $O(logn)$ 的時間，而向兩邊尋找的時間複雜度則是 O(n)，因為有可能整個陣列都是同一個值。所以整個演算法的時間複雜度是 O(n)。
👒: 沒錯。我還有一個問題，有一些情況下，你可以利用歌曲 ID 升冪排序的特性，在binary search 以前就知道歌曲是否可能存在在陣列中，請問你知道應該怎麼實作嗎？
◼️: 如果歌曲 ID 是升冪的，那最小的值就是第一個，而最大的就是最後一個，我可以檢查目標是否超出了範圍，如果是的話，就可以直接回傳 {-1,-1}。
👒: 很好，請你替演算法加上這個功能。

vector<int> findIndexes(vector<Record> records, int songId){
+   if (records.size() > 0 && (records[0].songId > songId || records[records.size() - 1].songId < songId))
+   {
+     return {-1, -1};
+   }


    int firstIndex=-1;
    int lastIndex=-1;
    
    int left=0;
    int right=records.size()-1;
    ...

◼️: 我們一開始需要檢查 `records` 的長度，確保我們的 index 不會超出去，而如果要找的 songId 超出了最大與最小的範圍，我們就不需要檢查，可以直接回傳找不到。
👒: 好，我們今天的面試到此結束，謝謝你今天的參與。

## 初步檢討

### interviewer

- 優點
- 有多個 follow up、提出能讓 interviewee 改進的地方
- 可改進的地方
- 詢問的問題不夠多種，基本上都是時間複雜度／快速處理特殊情況／驗證正確性

### interviewee

- 優點
- 有對於 database 的 schema 對題目做出變化（例如：比較紀錄的 songId）
- 有問清楚各種細節
- 可改進的地方
- 應該主動測試演算法的正確性（主動帶入範例）
- 有些口頭解釋太過繁雜，應該變得和 hackmd 上寫得一樣簡潔

## 對其他同學的批評

- 哈囉-Hi
有把範例用註解寫下來很好，但是寫程式的時候可能要注意 coding style 一致，學到自己可以先把範例寫在註解。
- 肥俠-Billy
英文單字發音需要加強，但是範例的寫法很清楚、有連續的 follow up，更能看出面試者的實力。
- 六六-Leo
面試者有把題目輸入的條件也記在文件上很好，但面試官問問題、面試者回答問題有一點太快跳到結論、filler word 有點太多了，我自己也可以注意這件事。
- 瑪奇朵-Macchiato
面試官問的問題很好，包含面試者為什麼要用某個方法、不同情況對於時間複雜度的影響等。
- 抹茶-Matcha
leetcode 原題直接寫在 Google Docs 上，可能會讓 interviewee 直接背題目通過，而面試者的舉例和分析都很詳細。

## 第四次作業

### 盲狗

- interviewer
- 有適當引導面試者應該朝哪個方向優化
- interviewee
- 要重複問題的時候，不需要說自己要重複一次，說自己要確認會比較自然
- 在講解自己的方法時，有寫出遞迴關係式，能展現自己有理解這個題目，不過可以另外寫下 n=1 時，S(n)=1, n=2, S(n)=2，讓面試官知道自己也有考慮到 edge case

### 節瓜

- interviewer
- 變化後的題目好像要素有點太多，可以去除一些資訊，變成：「有一場藝術品拍賣會，拍賣會上多出了很多複製品，而這些畫作的拍賣編號都相同，請問你應該如何找出哪些拍賣品有複製品。」
- interviewee
- 確認問題條件時，可以問是否會有多個拍賣品同時有複製品（陣列中有多個重複）