# 面試題整理

## 群聯 PCIE SSD 韌體開發工程師 08 台南
### 01 指標

#include <stdio.h>
int main() {
	short str[] ={0x2,0x4,6,8,0xA, 0xC};
    // 0002|0004|0006|0008|000a|000c
	printf("1.%d\r\n", sizeof(str)); // 12
	printf("2.%d\r\n", *(str+1));    // 4
	printf("3.%d\r\n", (str+1)[1]);  // 6
	
	int *ptr = str;
	printf("4.0x%x\r\n", *(ptr+2)); //0xc000a
	
	return 0;
}

要特別注意 [位元組順序(Endianness)](https://blog.gtwang.org/programming/difference-between-big-endian-and-little-endian-implementation-in-c/)
本題假設為 Little-Endian，也就是==最高位的位元組放在最高的記憶體位址==

### 02 Linear Search

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int> num, int target);
int left_search(vector<int> num, int target);
int right_search(vector<int> num, int target);
vector<int> lin_search(vector<int> num, int target);

int main() {
    vector<int> num = {1,2,2,2,2,7,9,10};
    // vector<int> num = {1,2,2,3,7,9,10};
    int target = 2;
    
    // Sol. 1: Binary Search (left right search)
    int left = left_search(num, target);
    int right = right_search(num, target);
    printf("Sol.1: %d %d\n", left, right);
    
    // Sol. 2: Bidirectional Linear Search
    vector<int> res = lin_search(num, target);
    printf("Sol.2: %d %d\n", res[0], res[1]);

    return 0;
}

int binarySearch(vector<int> num, int target)
{
    int left = 0;
    int right = num.size() - 1;
    
    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (num[mid] == target)
            return mid;
        else if (num[mid] < target)
            left = mid + 1;
        else if (num[mid] > target)
            right = mid - 1;
    }
    return -1;
}

int left_search(vector<int> num, int target)
{
    int left = 0;
    int right = num.size() - 1;
    
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (num[mid] == target)
            right = mid - 1;
        else if (num[mid] < target)
            left = mid + 1;
        else if (num[mid] > target)
            right = mid - 1;
    }

    if (left >= num.size() || num[left] != target)
        return -1;
    return left;
}

int right_search(vector<int> num, int target)
{
    int left = 0;
    int right = num.size();
    
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (num[mid] == target)
            left = mid + 1;
        else if (num[mid] < target)
            left = mid + 1;
        else if (num[mid] > target)
            right = mid - 1;
    }

    if (right < 0 || num[right] != target)
        return -1;
    return right;
}

vector<int> lin_search(vector<int> num, int target)
{
    int left = 0;
    int right = num.size() - 1;

    while (left <= right)
    {
        if (num[left] != target)
            left++;
        if (num[right] != target)
            right--;
        if (num[left] == target && num[right] == target)
            break;
        printf("l = %d, r = %d\n", left, right);
    }

    if (left > right)
        left = right = -1;

    return vector<int> {left, right};
}

### 03 最大差值問題
> 給定一個sorted array, 回出特定值在這個array 的範圍 [左邊界, 右邊界], 若不存在回傳[-1, -1]
eg. [1, 2, 2, 2, 2, 3, 4, 5], input : 2 output :[1, 4]
解釋: 在這個array中 2的範圍是從idx 1 – idx 4
一array [X0, X1,……Xm,…Xn,…]，Xn - Xm = Y，求Y最大值且n > m
→int max_diff(int* nums, int nums_size)
ex :
[7, 1, 5, 3, 6, 4] : 6 – 1 = 5

#include <iostream>
#include <climits>
#include <vector>

using namespace std;

int max_diff(vector<int> a);
int max_diff2(vector<int> a);

int main() {
    vector<int> a = {7, 1, 5, 3, 6, 4};
    int res = max_diff2(a);
    printf("%d\n", res);
    return 0;
}

int max_diff2(vector<int> a)
{
    int cur_min = INT_MAX;
    int max_diff = INT_MIN;
    for (int i = 0; i < a.size(); ++i)
    {
        if (cur_min > a[i])
            cur_min = a[i];
        if (max_diff < a[i] - cur_min)
            max_diff = a[i] - cur_min;
        printf("%d %d\n", cur_min, max_diff);
    }
    return max_diff;
}

// Brutal Force
int max_diff(vector<int> a)
{
    int max = INT_MIN;
    
    for (int i = 0; i < a.size() - 1; ++i)
    {
        for (int j = i + 1; j < a.size(); ++j)
        {
            if (a[j] - a[i] > max)
                max = a[j] - a[i];
        }
    }
    return max;
}

## 群聯 韌體工程師0106
### 一面

/* Q2. Write a function GetBitValue(unsigned char * bitmap, int A) to get Ath bit value in bitmap, each byte starts from bit0:
 * unsigned char bitmap[10] = {0x00, 0x80, 0x00, 0x00, 0xAB, 0x00, 0xD2, 0x2D, 0x3C, 0xAB};
 * GetBitValue(bitmap, 15) will return 1;
 * GetBitValue(bitmap, 8) will return 0;
 */

#include <stdio.h>

int GetBitValue(unsigned char * bitmap, int A)
{
    // (1) Get the index: A/8 (equal A >> 3)
    // (2) Get the bit: right shift (A % 8)
    // (3) Bit Mask
    return (bitmap[A >> 3] >> (A % 8)) & 0x1;
}

int main()
{
    unsigned char bitmap[10] = {0x00, 0x80, 0x00, 0x00, 0xAB, 0x00, 0xD2, 0x2D, 0x3C, 0xAB};
    
    printf("GetBitValue(bitmap, 15) = %d\n", GetBitValue(bitmap, 15));
    printf("GetBitValue(bitmap,  8) = %d\n", GetBitValue(bitmap, 8));
}

### 二面
#### 資料蒐集整理
* 給一份美光的 NAND Flash Datasheet
* 回答以下問題，可以查詢網路，在一小時內做成PPT後報告給面試主管：
> Q1. 什麼是read ID?
> Q2. 如何發送read ID?
> Q3. 為何要使用read ID?
> Q4. 加分補充資料

#### 修改程式使其正常運作
* 給你5個程式檔`main.c`、`a.h`、`a.c`、`b.h`、`b.c`
* 修改程式使其正常運作
* 回答 `main.c` 會 print 出什麼結果

// main.c
#include <stdio.h>

/* Answer
 * #include "a.h"
 * #include "b.h"
 */

int main() {
    aaa(0x12);
    printf("%d\n", counter);

    printf("%d\n", bbb(13));
    printf("%x\n", bbb(10));
}

// a.h
/* Answer
 * #ifndef A_H
 * #define A_H
 * 
 * extern int counter; // declare variable as extern (make another file visible)
 * void aaa(int a); // function declaration
 * #endif // A_H
 */

// a.c
/* Answer
 * #include "a.h"
 */

int counter = 0; // definition

void aaa(int a) {
    counter += a;
    return counter;
}

// b.h
/* Answer
 * #ifndef B_H
 * #define B_H
 * 
 * void bbb(int b); // function declaration
 * #endif // B_H
 */

// b.c
/* Answer
 * #include "b.h"
 */
int bbb(int b) {
    return counter + b;
}

* 觀念
* Function Declaration
* `#include "a.h"`
* b.c 要怎麼調用到 a.c 當中的`int counter`變數
* `extern`

#### 解釋code的功能以及問答C觀念題
* 面試官會給你看公司內部的code，並請你講解程式的功能
* 考到的觀念包含
* 指標
* 強制轉型 `(void *)`
* `#define`
* `typedef`
* `static` [(1)] [(2)]
* `volitile`

[(1)]: https://stellvia7.pixnet.net/blog/post/95393590
[(2)]: https://stackoverflow.com/questions/1856599/when-to-use-static-keyword-before-global-variables