# 面試考題
### 觀念
* 指標++ & ++指標
* 韌體ISR的問題
* cache
* semaphore
* context switch
* deadlock
* inline function
### [Dcard`1`](https://www.dcard.tw/f/tech_job/p/238404188)
#### **leetcode.283**
Given an integer array `nums`, move all `0`'s to the end of it while maintaining the relative order of the non-zero elements.
**Note** that you must do this in-place without making a copy of the array.
Example 1:
> Input: nums = [0,1,0,3,12]
> Output: [1,3,12,0,0]
```c
void swap(int *a, int *b){
if(*a != *b){
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
}
void moveZeroes(int* nums, int numsSize){
int i = 0;
int j = 0;
while(i < numsSize){
if(nums[i] == 0)
i++;
else{
swap(&nums[j], &nums[i]);
i++;
j++;
}
}
}
```
#### **leetcode.56**
Given an array of `intervals` where `intervals[i] = [starti, endi]`, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
>Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
```c
int cmp(const void *a, const void *b)
{
int **a1 = (int **)a;
int **b1 = (int **)b;
if (a1[0][0] != b1[0][0]) {
return a1[0][0] - b1[0][0];
} else {
return a1[0][1] - b1[0][1];
}
}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){
qsort(intervals,intervalsSize,sizeof(intervals[0]),cmp);
int **ret = (int **)malloc(sizeof(int *) * intervalsSize);
int start = intervals[0][0];
int end = intervals[0][1];
int count = 0;
int idx = 1;
while(idx < intervalsSize){
if(intervals[idx][0] < start)
start = intervals[idx][0];
if(end < intervals[idx][0]){
ret[count] = (int *)malloc(sizeof(int) * 2);
ret[count][0] = start;
ret[count][1] = end;
start = intervals[idx][0];
end = intervals[idx][1];
count++;
}
else if(end < intervals[idx][1]){
end = intervals[idx][1];
}
idx++;
}
ret[count]=malloc(sizeof(int)*2);
ret[count][0]=start;
ret[count][1]=end;
count++;
*returnSize=count;
*returnColumnSizes = malloc(count * sizeof(int));
for (int i = 0; i < count; i++)
(*returnColumnSizes)[i] = 2;
return ret;
}
```
### [Dcard`2`](https://www.dcard.tw/f/tech_job/p/238148424)
#### **strlen**
```c
#define DETECT_NULL(x) (((x) -0x01010101) & ~(x) & 0x80808080)
void strlen_fast(char *src){
int count = 0;
unsigned long *src_l = (unsigned long *)src;
while(!DETECT_NULL(*src_l)){
count+=4;
src_l++;
}
src = (unsigned char *)src_l;
while(*src != '\0'){
src++;
count++;
}
printf("%d",count);
}
void strlen_slow(char *src){
int count = 0;
while(*src != '\0'){
count++;
src++;
}
printf("%d",count);
}
```
#### **strcpy**
```c=
#define DETECT_NULL(x) (((x) -0x01010101) & ~(x) & 0x80808080)
void strcpy_fast(const char *src, char *dest){
char *res = dest;
long *src_l = (long *)src;
long *dest_l = (long *)dest;
while(!DETECT_NULL(*src_l)){
*dest_l = *src_l;
dest_l++;
src_l++;
}
src = (char *)src_l;
dest = (char *)dest_l;
while(*src != '\0'){
*dest = *src;
dest++;
src++;
}
*dest = '\0';
printf("%s\n",res);
}
void strcpy_slow(const char *src, char *dest){
char *res = dest;
while(*src != '\0'){
*dest = *src;
dest++;
src++;
}
*dest = '\0';
printf("%s\n",res);
}
```
#### **shuffle the array**
```c
void swap(int *a, int *b){
int tmp = *a;
*a = *b;
*b = tmp;
}
void yates_shuffle(int *a, int length){
int last_pos = length - 1;
while(last_pos > 0){
int pick_index = rand() % last_pos;
swap(&a[pick_index],&a[last_pos]);
last_pos--;
}
}
```
#### **array reverse**
```c
void swap(int *a, int *b){
int tmp = *a;
*a = *b;
*b = tmp;
}
void array_reverse(int *a, int length){
int high = length - 1;
int low = 0;
while(low < high){
swap(&a[low], &a[high]);
low++;
high--;
}
}
```
#### **linklist insert**
```c
void insert_node(node **head_href,int index,int val){
node *n = (node *)malloc(sizeof(node));
node *target = *head_href;
node *prev = NULL;
n->val = val;
if(index == 0){
n->next = *head_href;
*head_href = n;
return;
}
while(index){
index--;
prev = target;
target = target->next;
}
prev->next = n;
n->next = target;
}
```
#### **leetcode 20 Valid Parentheses**
```c
bool isValid(char * s){
int length = strlen(s);
char *stack = (char *)malloc(sizeof(char) * length);
int idx = -1;
while(*s != '\0'){
if(*s == '(' || *s == '[' || *s == '{'){
idx++;
stack[idx] = *s;
s++;
}
else if(*s == ')'){
if(idx == -1 || stack[idx] != '('){
return false;
}
else{
idx--;
s++;
}
}
else if(*s == ']'){
if(idx == -1 || stack[idx] != '['){
return false;
}
else{
idx--;
s++;
}
}
else if(*s == '}'){
if(idx == -1 || stack[idx] != '{'){
return false;
}
else{
idx--;
s++;
}
}
}
if(idx != -1)
return false;
return true;
}
```
### [Dcard`3`](https://www.dcard.tw/f/tech_job/p/238411372)
#### **88. Merge Sorted Array**
```c
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int n_1 = m - 1;
int n_2 = n - 1;
int last_pos = nums1Size - 1;
while(n_1 >= 0 && n_2 >= 0 && last_pos >= 0){
if(nums1[n_1] >= nums2[n_2]){
nums1[last_pos] = nums1[n_1];
last_pos--;
n_1--;
}
else{
nums1[last_pos] = nums2[n_2];
last_pos--;
n_2--;
}
}
while(n_1 >= 0){
nums1[last_pos] = nums1[n_1];
last_pos--;
n_1--;
}
while(n_2 >= 0){
nums1[last_pos] = nums2[n_2];
last_pos--;
n_2--;
}
}
```
### [Dcard`4`](https://www.dcard.tw/f/tech_job/p/237433913)
#### **reverse list**
```c
void reverse_list(node **head_href){
node *prev = NULL;
node *cur = *head_href;
node *next;
while(cur != NULL){
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
*head_href = prev;
}
```
#### **merge sort**
```c
void merge(int *a, int low, int middle, int high){
int l_l = middle - low + 1;
int r_l = high - middle;
int arr1[l_l];
int arr2[r_l];
for(int i = 0; i < l_l; i++){
arr1[i] = a[low + i];
}
for(int i = 0; i < r_l; i++){
arr2[i] = a[middle + 1 +i];
}
int idx = low;
int i = 0;
int j = 0;
while(i < l_l && j < r_l){
if(arr1[i] <= arr2[j]){
a[idx] = arr1[i];
i++;
}
else{
a[idx] = arr2[j];
j++;
}
idx++;
}
while(i < l_l){
a[idx] = arr1[i];
i++;
idx++;
}
while(j < r_l){
a[idx] = arr2[j];
j++;
idx++;
}
}
void merge_sort(int *a, int low, int high){
if(low < high){
int middle = (high >> 1) + (low >> 1) + (high & low & 1);
merge_sort(a, low, middle);
merge_sort(a, middle + 1, high);
merge(a, low, middle, high);
}
}
```
#### **check big/little endian**
```c
short int a = 0x1234;
char *b = (char *) &a;
if(*b == 0x34)
printf("little");
else
printf("big");
```
### [Dcard`5`](https://www.dcard.tw/f/tech_job/p/237790033)
#### **驗證x是不是2的冪**
```c
bool isPowerOfTwo(int n){
return (n > 0) && !(n & (n-1));
}
```
#### **驗證x是不是平方數**
```c
bool isPerfectSquare(int num){
int left = 1;
int right = num;
while(left <= right){
int mid = left + (right - left) / 2;
long mid_sqr = (long) mid * (long) mid;
if(mid_sqr == num)
return true;
else if(mid_sqr < num)
left = mid + 1;
else
right = mid - 1;
}
return false;
}
```
#### **x的絕對值**
```c
int abs(int a){
int mask = a >> 31;
return (a + mask) ^ mask;
}
```
#### **x換成2進位有幾個1**
```c
void count_1_bit(unsigned int a){
int count = 0;
while(a){
count++;
a &= (a-1);
}
printf("%d",count);
}
```
### [Dcard`6`](https://www.dcard.tw/f/tech_job/p/237422517)
#### **160. Intersection of Two Linked Lists**
```c
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *a = headA;
struct ListNode *b = headB;
while(a || b){
if(a == b){
return a;
}
if(a)
a = a->next;
else
a = headB;
if(b)
b = b->next;
else
b = headA;
}
return a;
}
```
#### **linklist 中間node**
```c
node *middle_node(node *head){
node *slow = head;
node *fast = head;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
}
printf("%d\n",slow->val);
return slow;
}
```
#### **linklist delete node**
```c
void delete_node(node **head, node *target){
node **indirect = head;
while(*indirect != target){
indirect = &(*indirect)->next;
}
*indirect = target->next;
}
```
### [面試考題 - C語言](http://paicc.github.io/2018/09/29/%E9%9D%A2%E8%A9%A6%E8%80%83%E9%A1%8C-C%E8%AA%9E%E8%A8%80/)
#### **給一個連續數列，找出連續最長的1bit**
```c
#define MAX(X,Y) ((X) > (Y)) ? (X) : (Y)
int findMaxConsecutiveOnes(int* nums, int numsSize){
int ans = 0;
int cur = 0;
for(int i = 0; i < numsSize; i++){
if(nums[i] == 1){
cur++;
ans = MAX(ans,cur);
}
else{
cur = 0;
}
}
return ans;
}
```
#### **將一個字串reverse**
```c
void swap(char *a, char *b){
if(*a != *b){
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
}
void reverse_string(char *c){
int low = 0;
int high = strlen(c) - 1;
while(low < high){
swap(&c[low], &c[high]);
low++;
high--;
}
}
```
#### **將一個數值的奇偶bit互換**
```c
unsigned int odd_even_change(unsigned int a){
return ((a & 0xAAAAAAAA) >> 1) | ((a & 0x55555555) << 1);
}
```
#### **quick sort**
```c
void swap(int *a, int *b){
int tmp = *a;
*a = *b;
*b = tmp;
}
int parition(int *arr, int low, int high){
int pk = arr[high];
int j = low - 1;
for(int i = low; i < high; i++){
if(arr[i] < pk){
j++;
swap(&arr[j],&arr[i]);
}
}
swap(&arr[j + 1], &arr[high]);
return j + 1;
}
void quick_sort(int *arr, int low, int high){
if(low < high){
int p = parition(arr,low,high);
quick_sort(arr,low,p - 1);
quick_sort(arr,p + 1,high);
}
}
```
#### **寫一個string compare的function。相同return 0，不同return 1**
```c
int string_compare(char *a, char *b){
while(*a != '\0' && *b != '\0'){
if(*a != *b)
return 0;
else
a++;
b++;
}
if(*a != *b)
return 0;
else
return 1;
}
```
#### **The content of array a?**
```c
int a[ ]={6,7,8,9,10};
int *p= a;
*(p++) +=123;
*(++p) +=123;
/* a[] = {129,7,131,9,10} */
```
#### **請問輸出為何?**
```c
char i[ ] = "Hello";
char *p = 1;
int n = 10;
printf("%d %d %d", sizeof(i), sizeof(p), sizeof(n));
/* 6 8 4 */
```
#### **請問輸出為何?**
```c
int main(){
int arr[] = {10,20,30,40,50};
int *ptr1 = arr;
int *ptr2 = arr + 5;
printf("%d", (ptr2-ptr1));
printf("%d", (char*)ptr2 - (char*)ptr1);
}
/* 5 20 */
```
#### **請問輸出為何?**
```c
int main(){
int a[] ={1,2,3,4,5,6};
int *ptr = (int*) (&a+1);
printf("%d", *(ptr-1));
}
/* 6 */
```
#### **請問輸出為何?**
```c
int main(){
int arr1[] = {10,20};
int arr2[] = {10,20};
int arr3[] = {10,20};
int *p = arr1;
int *q = arr2;
int *r = arr3;
++*p;
*q++;
*++r;
printf("%d %d %d", arr1[0], arr1[1], *p);
printf("%d %d %d", arr2[0], arr2[1], *q);
printf("%d %d %d", arr3[0], arr3[1], *r);
}
/* 11 20 11
* 10 20 20
* 10 20 20
*/
```
#### **請問輸出為何?**
```c
void f(int *p, int *q){
p = q;
*p = 2;
}
int i=0, j=1;
int main(){
f(&i, &j);
printf("%d %d\n", i, j);
}
/* 0 2 */
```
#### **請問輸出為何?**
```c
int main(){
char s[ ]="0113256";
char *p = s;
printf("%c", *p++); //0
printf("%c", *(p++)); //1
printf("%c", (*p)++); //1
printf("%c", *++p); //3
printf("%c", *(++p)); //2
printf("%c", ++*p); //3
printf("%c", ++(*p)); //4
printf("\n");
printf("%s",s); //0123456
}
```
#### **請問輸出為何?**
```c
int main(){
int ref[]={8,4,0,2};
int *ptr;
int index;
for(index=0, ptr=ref; index<2; index++,ptr++)
printf("%d %d\n", ref[index], *ptr);
(*ptr++);
printf("%d %d\n", ref[index], *ptr);
}
/*
* 8 8
* 4 4
* 0 2
*/
```
#### **請問輸出為何?**
```c
ine main() {
char *str[ ][2] =
{ "professor", "Justin" ,
"teacher", "Momor" ,
"student", "Caterpillar"};
char str2[3][10] = {"professor", "Justin", "etc"};
printf("%s\n", str[1][1]); // Momor
printf("%c\n",str2[1][1]); // u
}
```
#### **what is final value of cnt?**
```c
int cnt = 10;
const char *pc = "welcome";
while(*pc++)
cnt++;
/* 17 */
```
#### **請問輸出為何?**
```c
#include <stdio.h>
union StateMachine {
char character;
int number;
char *str;};
int main(void) {
union StateMachine machine;
machine.number = 1;
printf("sizeof: %lu\n", sizeof(machine)); // 8
printf("number: %d\n", machine.number); // 1
}
```
### [ICL實驗室面試考古題](https://hackmd.io/uhQN-foHQCmP_vVaW-vlDg?fbclid=IwAR2vNa3fSHIqUbLNDlaR-8OLoQHGeSbatA_-A-o4elffty4Rw87-SfnpB-4)
#### **Please write the following print**
```c
union AA
{
char a[2];
int s;
};
int main()
{
AA aa = { 0 };
aa.a[0] = 12;
aa.a[1] = 1;
printf("%x\n", aa.s); // 10c
printf("%d\n", sizeof(aa)); // 4
getchar();
return 0;
}
```
#### **Please write the following print**
```c
#define XPROC(X) X*X
int main()
{
int n = XPROC(2 + 3);
cout << n << endl; // 11
}
```
#### **Reverse_string**
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
>Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
```c
void swap(char *a, int low, int high){
while(low < high){
char tmp = a[low];
a[low] = a[high];
a[high] = tmp;
low++;
high--;
}
}
void resver_string(char *a){
int i = 0;
int j = 0;
while(a[i] != '\0'){
if(a[i] == ' '){
swap(a, j, i-1);
j = i + 1;
}
i++;
}
swap(a, j, i-1);
}
```
#### **寫function return這個整數是不是2的次方**
看Dcard 5
#### **考 little/big endian 變數值怎麼存放**
看Dcard 4
#### **寫function 把某個數的第n+1個bit改成1或0**
* Set bit
```c
x = x | (1 << n);
```
* clear bit
```c
x = x & ~(1 << n);
```
* Get bit
```c
(x >> n) & 1;
```
* Inverse bit
```c
x = x ^ (1 << n);
```
* Reverse bit
```c
uint32_t reverseBits(uint32_t n) {
n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16);
n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
return n;
}
```
#### **struct的size、memory alignment問題**
#### **一個non-empty linked-list找middle node的值**
看Dcard 6
#### **實作 Binary search，找到回true，反之回false**
```c
int binary_search(int *arr, int target, int size){
int low = 0;
int high = size - 1;
int middle;
while(low <= high){
middle = (low >> 1) + (high >> 1) + (low & high & 1);
if(arr[middle] == target)
return 1;
else if(target < arr[middle])
high = middle - 1;
else
low = middle + 1;
}
return 0;
}
```
#### **Sorting**
quick_sort 看 面試考題 - C語言
```c
void bubble_sort(int *arr, int low, int high){
int swapped;
int last = high;
do{
swapped = 0;
for(int i = 0; i < last; i++){
if(arr[i] > arr[i+1]){
swap(&arr[i],&arr[i+1]);
swapped = 1;
}
}
last--;
}
while(swapped);
}
```
#### **0~500個數字每次隨機取一個數字出來，但下次在抽出時不可以出現已經抽過的數字，問你如何時實現**
```c
void swap(int *a, int *b){
int tmp = *a;
*a = *b;
*b = tmp;
}
int main()
{
int arr[501];
for(int i = 0; i < 501; i++){
arr[i] = i;
}
int final_idx = 500;
int choose_idx;
while(1){
choose_idx = rand() % (final_idx + 1);
printf("%d\n",arr[choose_idx]);
if(final_idx == 0)
break;
swap(&arr[choose_idx],&arr[final_idx]);
final_idx--;
}
}
```
#### **給8-bit size的值，求最高位元是在第幾個bit**
```c
void msb(unsigned int x){
int ret = x > 0;
int m = (x > 0xf) << 2;
x = x >> m;
ret = ret + m;
m = (x > 0x3) << 1;
x = x >> m;
ret = ret + m;
m = (x > 0x1);
ret = ret + m;
printf("%d",ret);
}
```
#### **輸入一unsigned int n，當輸入0則輸出0，輸入1-32為輸出32，33-64輸出64，65-96輸出96 (32進位)**
```c=
int mul_32(unsigned int x){
x = x + 31;
x = x & ~31;
return x;
}
```
#### **預測以下output**
```c
void little_endian(){
char c[] = { '\x01', '\x23', '\x45', '\x67', '\x89', '\xab', '\xcd', '\xef' };
int *p = (int *)c;
printf("%x ",*p); //0x67452301
*p += 1;
printf("%x ",*p); //0x67452302
printf("%x ",*(++p)); //0xefcdab89
}
// little-endian跟big endian結果不一樣，沒明確講要先問
```
#### **假設說我有一個unsigned short，檢查每四個位元是否相同，例如：0xaaaa就return true,0x1121因為二跟其他四個bit不同所以return false**
```c=
unsigned short x = 0xabab;
int m1 = x >> 8;
int m2 = x & 0x00ff;
int m3 = x >> 12;
int m4 = (x & 0x000f);
printf("%d",(m1 == m2) & (m3 == m4));
```
### 個人筆記
#### **Find First and Last Position of Element in Sorted Array**
```c
void binary_search(int *arr,int length,int target){
int low = 0;
int high = length - 1;
int left = 0;
int right = 0;
//find most left
while(low <= high){
int mid = low + (high - low) / 2;
if(arr[mid] == target){
left = mid;
high = mid - 1;
}
else if(target < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
low = 0;
high = length - 1;
//find most right
while(low <= high){
int mid = low + (high - low) / 2;
if(arr[mid] == target){
right = mid;
low = mid + 1;
}
else if(target < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
printf("%d\n",left);
printf("%d\n",right);
}
```
#### **linked list delete node**
```c
void delete_node(node **head_href, node *target){
node *cur = *head_href;
node *prev = NULL;
while(cur != target){
prev = cur;
cur = cur->next;
}
if(prev == NULL){
*head_href = cur->next;
free(cur);
}
else{
prev->next = cur->next;
free(cur);
}
}
```
#### **linked list merge sort**
```c
node *sorted_merge(node *a, node *b){
node *result = NULL;
if(a == NULL)
return b;
else if(b == NULL)
return a;
if(a->val <= b->val){
result = a;
result->next = sorted_merge(a->next , b);
}
else{
result = b;
result->next = sorted_merge(a, b->next);
}
return result;
}
node *halve_split(node *head){
node *slow = head;
node *fast = head->next;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
void merge_sort(node **head_href){
node *head = *head_href;
node *a;
node *b;
if((head == NULL) || (head->next == NULL))
return;
node *mid = halve_split(head);
a = head;
b = mid->next;
mid->next = NULL;
merge_sort(&a);
merge_sort(&b);
*head_href = sorted_merge(a,b);
}
```
#### **檢查質數**
```c
int count_prime(int n){
int *arr = malloc(sizeof(int) * n);
for(int i = 0; i < n; i++){
arr[i] = 1;
}
int ans = 1;
for(int i = 3; i < n; i = i + 2){
if(arr[i] == 1){
ans++;
for(int j = i; j < n; j = j + i){
arr[j] = 0;
}
}
}
return ans;
}
```
#### **設定一個絕對位置為0x67a9的整數型變數的值為0xaa55**
```c
int *ptr;
ptr = (int *)0x67a9;
*ptr = 0xaa55;
```
#### **53. Maximum Subarray**
```c
int maxSubArray(int* nums, int numsSize){
int ans=-999999;
int prev=0;
int cur=0;
for(int i = 0; i < numsSize; i++){
if(prev < 0){
cur = nums[i] + 0;
}
else{
cur = nums[i] + prev;
}
prev = cur;
if(cur > ans)
ans = cur;
}
return ans;
}
```
#### **linked list找最大值，找到最大值在前面加new node**
```c
void insert_node(node **head_href, int target){
node *cur = *head_href;
node *prev = NULL;
node *max_cur;
node *max_prev;
int max = -1;
while(cur != NULL){
if(cur->val > max){
max_cur = cur;
max_prev = prev;
max = cur->val;
}
prev = cur;
cur = cur->next;
}
node *n = (node *)malloc(sizeof(node));
n->val = target;
if(prev == *head_href){
n->next = prev;
*head_href = n;
return;
}
max_prev->next = n;
n->next = max_cur;
}
```
#### **swap node**
```c
void swap(node **head_href, int x, int y){
node *cur_x = *head_href;
node *prev_x = NULL;
node *cur_y = *head_href;
node *prev_y = NULL;
node *cur = *head_href;
node *prev = NULL;
while(cur != NULL){
if(cur->val == x){
cur_x = cur;
prev_x = prev;
}
if(cur->val == y){
cur_y = cur;
prev_y = prev;
}
prev = cur;
cur = cur->next;
}
if(prev_x != NULL)
prev_x->next = cur_y;
else
*head_href = cur_y;
if(prev_y != NULL)
prev_y->next = cur_x;
else
*head_href = cur_x;
node *tmp = cur_x->next ;
cur_x->next = cur_y->next;
cur_y->next = tmp;
}
```
#### **linked list binary search**
```c
node *find_middle(node *low, node *high){
if(low == NULL)
return NULL;
node *slow = low;
node *fast = low->fast;
while(fast != high && fast->next != high){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
node *binary_search(node *head,int target){
node *low = head;
node *high = NULL;
do{
node *middle = find_middle(low,high);
if(middle == NULL){
return NULL;
}
if(middle->val == target){
return middle;
}
else if(target < middle->val)
high = middle;
else
low = middle->next;
}
while(high == NULL || high != low);
return NULL;
```
#### **double linked list (array to link list)**
```c
struct node{
int data;
struct node* next;
struct node* prev;
};
typedef struct Node node;
void append(struct Node **head_href,int *arr){
node *cur;
for(int i = 0; i < 5; i++){
node *n = (node *)malloc(sizeof(node));
n->val = arr[i];
n->next = NULL;
if(i == 0){
n->prev = NULL;
*head_href= n;
}
else{
n->prev = cur;
cur->next = n;
}
cur = n;
}
}
```
#### **link list two sum**
```c
void two_sum(node *head, int target){
node *low = head;
node *tail = head;
while(tail->next != NULL)
tail = tail->next;
while(low != tail){
if(low->val + tail->val == target){
printf("%d\n",low->val);
printf("%d\n",tail->val);
return;
}
else if(low->val + tail->val < target)
low = low->next;
else
tail = tail->prev;
}
printf("no find");
}
```
#### **memory check**
```c=
/*
* char b[]={0x10,0x12,0x13,0x14,0x11,0x12,0x13,0x14,0x16};
* char a[]={0x11,0x12,0x13,0x14,0x11,0x12,0x13,0x14,0x16};
*/
int memory_check(char *a, char *b, int length){
long *a_l = (long *) a;
long *b_l = (long *) b;
while(length >= sizeof(long)){
if(!(*a_l ^ *b_l)){
a_l++;
b_l++;
length -= sizeof(long);
}
else
return 0;
}
a = (char *)a_l;
b = (char *)b_l;
while(length > 0){
if(*a != *b)
return 0;
else{
a++;
b++;
length--;
}
}
return 1;
}
```
#### **Maximum Subarray(return start/end index)**
```c
int maxSubArray(int* nums, int numsSize){
int global_max = -99999;
int cur_max = 0;
int start = 0;
int end = 0;
int s = 0;
for(int i = 0; i < numsSize; i++){
cur_max += nums[i];
if(cur_max > global_max){
global_max = cur_max;
start = s;
end = i;
}
if(cur_max < 0){
cur_max = 0;
s = i + 1;
}
}
return global_max;
}
```
#### **transpose matrix**
```c
void transpose(int **arr, int n, int m){
int *t = (int *)malloc(sizeof(int) * n * m);
int index = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
t[index] = arr[i][j];
printf("%d ",t[index]);
index++;
}
printf("\n");
}
printf("\n");
int **ans = (int **)malloc(sizeof(int *) * m);
for(int i = 0; i < m; i++){
ans[i] = malloc(sizeof(int) * n);
}
index = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
ans[j][i] = t[index];
index++;
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
printf("%d ",ans[i][j]);
}
printf("\n");
}
}
```
### 宗翰考古題
#### **Assuming that we are using 32-bit compiler, pointer in 4 bytes.**
```c
int ints[20] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200};
int *ip = ints + 3;
//&ints = 100
ints[4] = 50
ints + 4 = 116
*ints + 4 = 14
*(ints +4) = 50
ints[-2] = undefined
&ints = 100
&ints[4] = 116
&ints + 4 = 420
&ints[-2] = 92
ip = 112
ip[4] = 80
ip + 4 = 128
*ip + 4 = 44
*(ip + 4) = 80
ip[-2] = 20
&ip = undefined
&ip[4] = 128
&ip + 4 = undefined
&ip[-2] = 104
```
#### **In the end, flag.All should be?**
```c
struct BYTE_struct
{
unsigned char BYTE4;
unsigned char BYTE3;
unsigned char BYTE2;
unsigned char BYTE1;
};
union LongFlag
{
unsigned long All;
struct BYTE_struct BYTEMODE;
};
int main(){
union LongFlag flag;
flag.All = 0x01234567;
flag.BYTEMODE.BYTE4 = 0x11;
flag.BYTEMODE.BYTE1 = 0xFA;
flag.BYTEMODE.BYTE3 &= 0x55;
flag.BYTEMODE.BYTE2 &= 0xAA;
}
/*
* little endian : 0xfa224511
* big endian : 0x110100fa
*/
```
## **純軟面試考題**：
1. **KKcompany** (考 codility)
題目* 4
中級以上的題目
```
you are given an array A consisting of N positive integers. Consider subarrays of A, with at least two elements, whoose first and last elements have the same value. Your tasks is to find the largest possible sum of such a subarray
For example for array A = [1,3,6,1,6,6,9,9]
the subarray with the largest sum is [6,1,6,6] and its sum is 19
```
第二題有難度
```
There is an array A consisting of N integers. Divide them into three non-empty groups. In each group we calculate the differece between the largest and smallest integer. Our goal is to make the maximum of these differences as small as possible. For example,
give A=[11,5,3,12,6,8,1,7,4] we can divide the elements into three groups: 1. [3,1,4] the difference between elements is 3; 2. [5,6,8,7] the difference is also3;
```
Sign in with Wallet
Connect another wallet