Interview-250212

Interview
  1. 判断一个unsigned char有多少个bit为1；
1
2
3
4
5
6
7
8
9
int count_set_bits(unsigned char byte)
{
	int count = 0;
	while(byte){
		count += byte & 1；
		byte >>= 1;
	}
	return count;
}
  1. 在一个字符串中查找匹配的子串，返回匹配到位置；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int find_sub_string(const char *str, const char *sub)
{
	int str_len = strlen(str);
	int sub_str_len = strlen(sub);

	for(int i = 0;  i <= str_len - sub_str_len; ++i)
	{
		int j;
		for(j = 0; j < sub_str_len; ++j)
		{
			if(str[i + j] != substr[j])
			{
				break;
			}
		}
		if(j == sub_str_len)
		{
			return i;
		}
	}
	return -1;
}
  1. 双向链表删除节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdlib.h>
#include <stdio.h>
struct Node
{
    int data;
    struct Node *prev;
    struct Node *next;
};

typedef struct Node Node;

void delete_node(Node **head, int val)
{
    if(*head == NULL)
    {
        printf("empty\n");
        return;
    }

    Node* current = *head;

    while(current != NULL && current->data != val)
    {
        current = current->next;
    }
    if (current == NULL) {
        printf("未找到值为 %d 的节点。\n", val);
        return;
    }

    // 如果删除的是头节点
    if (current->prev == NULL) {
        *head = current->next;  // 更新头节点
    } else {
        current->prev->next = current->next;  // 更新前一个节点的 next 指针
    }

    // 如果删除的不是尾节点
    if (current->next != NULL) {
        current->next->prev = current->prev;  // 更新后一个节点的 prev 指针
    }

    free(current);  // 释放内存
    printf("成功删除值为 %d 的节点。\n", val);
}

4.hash表的常见应用
字典
缓存
数据库索引
唯一性检查

hash冲突的解决方法:

  1. 链地址法（Chaining）
  2. 开放地址法（Open Addressing）
  3. 再哈希法（Rehashing）

tips:作缓存时，发生冲突直接覆盖即可

5.MYSQL的CAPI
mysql_init()初始化连接
mysql_real_connect()简历连接
mysql_query() 执行SQL语句
mysql_store_result() 和 mysql_fetch_row() 等函数来处理结果

5.Redis的常用数据结构
STRING，LIST，ZSET，SET，HASH