資訊科技產業專案設計作業4

268. Missing Number

😈interviewer: 潔西卡
😬interviewee: 魏昇芷

題目敘述

• 😈: There is an issue in the company. We store every employee's information in dataBase and every employee has unique ID. This ID is an integer. Because the number of employee is n + 1, so the range of ID is from 0 to n. The issue is that we lost one employee's information in database, we want to find out which employee's information is lost.
• 😈: I further simplize the issue. These employees' ID store in an array. For example, if the array is [0, 1, 2, 3, 4, 6], you should tell me the missing employee's information whose ID is 5. The range of number in this array is from 0 to size of the array and all the number is integer. So, if this issue is dispatched to you, what is your solution?

參考解答

• 😬: Ok, I double-check the issue. So, all the employees' ID are stored in the given array, and all ID are in the range from 0 to size of array. What I need to do is finding out an employee's ID, which is not in the given array, but in range from 0 to size of array.
• 😈: That's right。
• 😬: Is the given array sorted.
• 😈: No.
• 😬: emmm ~ I think I will use a set to record all the number in the given array first. Then, I will iterate the number from 0 to size of array. If the number does not exist in set, it means that the number is missing employee's ID.
• 😈: Sounds feasible. But this way you need to allocate more memory space, right?
• 😬: Yes, I need to allocate the extra space for set.
• 😈: Can you think of any other method that no needs to allocate more memory space?
• 😬: emmm ~ I think I can use trapezoid formula to calculate the sum of 0 to size of array first. Then, I iterate the array and subtract all the elements in given array from sum we calculated before。
• 😈: Okay, try to code it down.
• 😬:

int findMissingNumber(vector<int> *nums) {
    int sum = 0;
    int size = nums.size();
    sum = (1 + size) * size / 2 ;
    for(int i = 0; i < size; i++){
        sum -= nums[i];
    }
    return sum;
}

• 😈: Seems good! Then do you think of any solution to solve this problem without allocating memory space and any mathematical operation?
• 😬: I think I can use the property of xor operation to solve this problem. When x ^ x, we can get the result 0, so we can calculate the result of 0 ^ 1 ^ 2 ^ … ^ n, then use this result to xor all elements in the given array. After all operation done, the remaining value is the missing number.
• 😬:

Ex: [0, 1, 3]

• initial:
  • res = 0 ^ 1 ^ 2 ^ 3
• iterate array
  • i = 0: 0 ^ 1 ^ 2 ^ 3 ^ 1 = 1 ^ 2 ^ 3 ^ 0 ^ 0
  • i = 1: 1 ^ 2 ^ 3 ^ 1 = 2 ^ 3 ^ 1 ^ 1
  • i = 2: 2 ^ 3 ^ 3 = 2
    Remaining value 2 is missing number

😈: Great!

242. Valid Anagram

😈interviewer: 潔西卡
😬interviewee: 魏昇芷

題目敘述

• 😈: There is an issue in the company. When we store a string data in database, we will mess up the order of character in this string. For example, if the original string is abc，it might become bac or cba … and so on when it is stored to DB. The issue is that we need to design an algorithm to compare the data in DB with original string. If we can reorder the character to make string in DB equal to original string, then return true. Otherwise, return false. All charachter in string data is lowercase letter.

參考解答

• 😬: Ok, so you will give me two strings, if I can get one string from reordering the character in another string, then return true.
• 😈: That's right!
• 😬: emmm ~ the first slution come to my mind is sorting these two strings, if two sorted strings are equal, return true, if not, return false.
• 😈: Got it, then code it down.

bool checkTwoStr(string str1, string str2)
{
    sort(str1.begin(), str1.end());
    sort(str2.begin(), str2.end());
    if (str1 == str2)
        return true;
    return false;
}

• 😬: Because the time complexity of native sorting funciton in C++ is O(
  $NlogN$), the time complexity of this function is O(
  $NlogN$)
• 😈: Can you solve it without sorting?
• 😬: emmm~ I think I will create two array and their size are 26. they are used to record the number of these 26 different lowercase letters in the string. if all the elements in these two array are equal, return true.
• 😈: Good, now code it down.

    int arr[26] = {0}; 
    int arr2[26] = {0}; 
    // record the number this character appear to the coressponding element
    for(int i = 0; i < str1.length(); i++){
        arr[str1[i] - 'a'] += 1;
    } 
    for(int i = 0; i < str2.length(); i++){
        arr2[str2[i] - 'a'] += 1;
    }
    for(int i = 0; i < 26; i++) {
        if(arr[i] != arr2[i])
            return false;
    }
    return true;

• 😬: Because I use O(1) operation in 3 for loop, so the time complexity is linear time .

121. Best Time to Buy and Sell Stock

😈interviewer: 魏昇芷
😬interviewee: 潔西卡

題目敘述

• 😈: Here is a basic optimization problem. An array prices records the pirce of a given stock on the day. Try to maximize the profit by choosing a single day to buy one stock and selling it on a later different day.
• 😈: For example, given the prices [7, 1, 5, 3, 6, 4], buy on day 2 and sell on day 5 will get the maximum prize 5. If you cannot achieve any maximum profit, just return 0.

參考解答

• 😬: Em… so selling before buying is not allowed, right?
• 😈: That's right. You must buy before you sell.
• 😬: And correct me if I'm wrong. Given an integer array, The maximum profit will be obtained from the lowest price to buy and the highest price to sell, and each action will only do once.
• 😈: Yes, and every price is a positive integer.
• 😬: Thanks, I think the naive method is to use two forloops, try to buy and sell for everyday to get the maximum profit.
• 😈: Okay, just type it.

public int maxProfit(int prices[]) {
    int max_profit = 0;
    for(int i = 0; i < prices.length; i++){
        for(int j = i+1; j < prices.length; j++){
            if(prices[j] - prices[i] > max_profit){
                max_profit = prices[j] - prices[i];
            }
        }
    }
    return max_profit;
}

• 😬: The time complexity is O(n^2)
• 😈: Can you try to solve this problem with O(n)?
• 😬: Okay, because I can get the price each iteration, I think just add a variable to store the minimum price and check the profit each iteration. can decrese the time complexity to O(n).
• 😈: Sounds good. Try it!

publiv int maxProfit(int prices[]){
 int max_profit = 0;
 int min_price = 9999;
 for(int i = 0; i < prices.length; i++) {
     if(prices[i] < min_price) {
         min_price = prices[i];        // buy
     } else if(prices[i] - min_price > max_profit) {
         max_profit = prices[i] - min_price;   // sell
     }
     return max_profit;
 }
}