Pramp 練習

「真希望 Google 能成功的收到更多台灣人。進去的條件就像聯考。不知為何，明明台灣人考試不弱，但會這種制式面試的卻相對少… 面試以外的能力固然重要，可是你的競爭者就是除了面試比你強外，其他也很強啊。光是母語不同、開發專案的知名度不同、待過的學校不同等，就狠耍一條街了。相較之下面試題真的是最容易準備的了」 – from a Googler

video: How to Get a Job at the Big 4 - Amazon, Facebook, Google & Microsoft

貢獻者: 林克-Link

Array Index & Element Equality

時間軸: 00:02:08-00:26:47

Question description

Given a sorted array arr of distinct integers, write a function indexEqualsValueSearch that returns the lowest index i for which arr[i] == i. Return -1 if there is no such index. Analyze the time and space complexities of your solution and explain its correctness.

Examples:

input: arr = [-8,0,2,5]
output: 2 // since arr[2] == 2
input: arr = [-1,0,3,6]
output: -1 // since no index in arr satisfies arr[i] == i.

Constraints:

• [time limit] 5000ms
• [input]
  • array.integer arr
  • 1 ≤ arr.length ≤ 100
• [output] integer

Solution

Approach 1: Brute force

Since input is at most contain 100 element. Use for loop to iterate all index. If find the element equal to index return index. Otherwise return -1.

int indexEqualsValueSearch(const vector<int> &arr) {
    for (int i = 0; i < arr.size(); i++)
        if (arr[i] == i) return i;
    return -1;
}

Time complexity: 疊代所有 index，直到 arr[i] == i 或 arr 中最後一個元素，複雜度為

$O(N)$。
Space complexity: 沒有使用額外的空間，複雜度為

$O(1)$。

Approach 2 Binary search

因為 arr 已排序過，所以我們可使用 binary search 這類策略或技巧，一開始宣告兩個變數 lo 和 hi，用來記錄搜索範圍。每輪搜索中確認 arr 中索引值為 mid 的 element ， 分成兩個狀況:

1. mid <= arr[mid] 代表 feasible region 小於等於 mid ，將搜索區間的上界設為 mid
2. 否則 feasible region 大於 mid，下界調整為 mid + 1

結束 while 迴圈時 lo == hi，若此時答案不存在 arr[lo] != lo，回傳 -1。

int indexEqualsValueSearch(vector<int> arr) {
    int lo = 0, hi = arr.size() - 1;
    while (lo < hi) {
        // avoid overflow
        int mid = (hi - lo) / 2 + lo;
        if (mid > arr[mid])
            lo = mid + 1;
        else
            hi = mid;
    }
    return (lo == arr[lo]) ? lo : -1;
}

Time complexity: 起出搜索空間為 0 到 N - 1 ， 每一輪都將搜索空間縮小一半，因此經過 lgN 輪後便能找到 the lowest index，時間複雜度為 O(logN) 。
Space complexity: 僅宣告 lo, hi, mid 等變數，複雜度為

$O(1)$。

Self-Criticism

REACTO

• Repeat: 重複提問，確認自己理解原本的要求
  • 聽不懂 interviewer 問題，應加強英文聽力不要依賴題目敘述
• Examples: 針對題目條件，舉出符合的案例，不限於特例
  • 沒有注意到題目限制舉了錯誤的案例
• Approach: 說明自己打算採用的方案
  • 45 秒內給出一個直覺的做法 (Naive Approach)，並進一步提出更加的解法。
  • 講解思路過程中，與 interviewer 溝通確認解題方向正確。
  • 等待 interviewer 訊號才開始撰寫程式碼。
• Code: 撰寫程式
  • 應注意變數名稱及排版風格
• Test: 若不能實際測試，那說明驗證程式的方案
  • 使用題目案例驗證及說明程式碼運作

程式碼改進與討論

• 第一版程式碼正確性無法涵蓋所有測資，未達題目要求找出最小的 index ，改善原本方法。
  • 應該想清楚題目限制在開始實作
• mid 判斷與搜索範圍有誤更正後通過所有測資。
  • Test (驗證)時沒有完全照著所寫程式碼執行因此沒發現錯誤。
• 分析時間及空間複雜度時不夠嚴謹，為何為 Time complexity 是 logN 僅粗略帶過。

---

Award Budget Cuts

from TechZoo
時間軸: 00:26:47-1:14:36

Question description

The awards committee of your alma mater (i.e. your college/university) asked for your assistance with a budget allocation problem they're facing. Originally, the committee planned to give N research grants this year. However, due to spending cutbacks, the budget was reduced to newBudget dollars and now they need to reallocate the grants. The committee made a decision that they’d like to impact as few grant recipients as possible by applying a maximum cap on all grants. Every grant initially planned to be higher than cap will now be exactly cap dollars. Grants less or equal to cap, obviously, won’t be impacted.

Given an array grantsArray of the original grants and the reduced budget newBudget, write a function findGrantsCap that finds in the most efficient manner a cap such that the least number of recipients is impacted and that the new budget constraint is met (i.e. sum of the N reallocated grants equals to newBudget).

Analyze the time and space complexities of your solution.

Example:

input:  grantsArray = [2, 100, 50, 120, 1000]
        newBudget = 190
output: 47 // and given this cap the new grants array would be
           // [2, 47, 47, 47, 47]. Notice that the sum of the
           // new grants is indeed 190

Constraints:

• [time limit] 5000ms
• [input] array.double grantsArray
  • 0 ≤ grantsArray.length ≤ 20
  • 0 ≤ grantsArray[i]
• [input] double newBudget
• [output] double

Solution

Approach 1: Binary search

double findGrantsCap(vector<int> grantsArray, double newBudget ) 
{
    double lo = 1, hi = newBudget;
    int sum_of_grant = accumulate(grantsArray.begin(), grantsArray.end(), 0);
    if (sum_of_grant < newBudget)
        return newBudget;
    while (lo < hi) {
        double mid = (lo + hi) / 2;
        double cur = 0.0;
        for (auto grant:grantsArray) {
            if (grant > mid)
                cur += mid;
            else
                cur += grant;
        }
        if (cur == newBudget)
            return mid;
        if (cur > newBudget)
            hi = mid;
        else
            lo = mid;
    }
}

Time complexity: 算出 arr 的合需要

$O(N)$ ，while 迴圈中每輪會花

$O(N)$ 的時間執行，需要執行

$O(logP)$ 其中 P 為 double 的 precision， 因爲搜索空間為浮點數，而非整數。
Space complexity: 僅有一些變數宣告，因此空間複雜度為常數，也就是 O(1)。

Approach 2: Sorting

double findGrantsCap(vector<int> grantsArray, double newBudget) 
{
    sort(grantsArray.begin(), grantsArray.end(), greater<int>());
    grantsArray.push_back(0);
    int sum_of_grants = accumulate(grantsArray.begin(),grantsArray.end(),0);
    int surplus = sum_of_grants - newBudget;
    if (surplus <= 0) return grantsArray[0];
    int i;
    for (i = 0; i < grantsArray.size(); i++){
        surplus -= (i + 1) * (grantsArray[i] - grantsArray[i + 1]);
        if (surplus <= 0) break;
    }
    return grantsArray[i + 1] + (-surplus / float(i + 1));
}

Time complexity:
Space complexity:

Approach 3: Approximate

double findGrantsCap(vector<int> grantsArray, int newBudget) {                                       
    int len = grantsArray.size();
    double mean = newBudget / len;
    int count, rem_sum, max_min;
    do {
        count = 0, rem_sum = 0, max_min = newBudget;
        for (auto e : grantsArray) {
            if (e >= mean) {
                max_min = min(max_min, e);
                continue;
            }
            count++;
            rem_sum += e;
        }
        mean = (newBudget - rem_sum) / double(len - count);
    } while (max_min < mean);
    return mean;
}

檢討

• 解釋 Int to Float to Int conversion precision loss

Peer FeedBack_

2021/12/30