文章目录

1. 1. 1,用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。
2. 2. dest, const void *src, size_t n)。
3. 3. 3,有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间.
4. 4. 4,给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。
5. 5. 5,在一维坐标轴上有n个区间段，求重合区间最长的两个区间段。
6. 6. 6,系统有很多任务，任务之间有依赖，比如B依赖于A，则A执行完后B才能执行
7. 7. 7,解释下面ptr含义和不同
8. 8. 8,去掉const属性。
9. 9. 10,现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来。
10. 10. 11,SSH的原理
11. 11. 12,利用互斥量和条件变量设计一个消息队列，具有以下功能：
12. 12. 13,对已排好序的数组A，一般来说可用二分查找可以很快找到。现有一特殊数组A[]，它是循环递增的，如A[]={ 17 19 20 25 1 4 7 9}，试在这样的数组中找一元素x，看看是否存在。
13. 13. 14,动态链接库与静态链接库的区别
14. 14. 15,指针与引用的区别
15. 15. 16,进程与线程的区别
16. 16. 17,函数调用入栈出栈的过程。
17. 17. 18,c++对象模型与虚表。
18. 18. 19,海量数据处理，以及如何解决Hash冲突等问题。
19. 19. 20,判断一个数的所有因数的个数是偶数还是奇数.
20. 20. 21,指针数组和数组指针的区别。
21. 21. 22,查找单链表的中间结点。
22. 22. 23,sizeof和strlen的区别。
23. 23. 24,malloc-free和new-delete的区别
24. 24. 25,vector的实现机制.
25. 25.
26. 26. 27,设rand（s，t）返回[s,t]之间的随机小数，利用该函数在一个半径为R的圆内找随机n个点，并给出时间复杂度分析。
27. 27. 28,求全排列
28. 28. 29,求一个组合函数： 如p([1,2,3]) ，输出：[1],[2],[3],[1,2],[2,3],[1,3],[1,2,3]

1,用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。

char *revert(char *str){
    int n = strlen(str);
    int i = 0;
    for(int i = 0; i <= n /2; i++){
        char ch = str[i];
        str[i] = str[n - i - 1];
        str[n - i - 1] = ch;
    }
    return str;
}

2,用C语言实现函数void memmove(void dest, const void *src, size_t n)。

void * memmove(void *dest, const void *src, size_t n){
    char *pbTo = (char *)dest;
    char *pbFrom = (char *)src;
    assert(dest != NULL && src != NULL);
    if(dest <= src || pbTo >= pbFrom + n){
        while(n-- > 0){
            *pbTo++ = *pbFrom++;
        }
    }
    else{
        pbTo = pbTo + n - 1;
        pbFrom = pbFrom +n - 1;
        while(n-- > 0){
            *pbTo-- = *pbFrom--;
        }
    }
    return dest;
}

3,有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间.

4,给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。

要求：空间复杂度O(1)，时间复杂度为O（n）。

void func(int *arr, int len){
    int begin = 0;
    int end = len - 1;
    while(begin < end){
        while((arr[begin] % 2 == 1) && end > begin) ++begin;
        while((arr[end] % 2 == 1) && end > begin) --end;
        swap(arr[begin], arr[end]);
    }
}

5,在一维坐标轴上有n个区间段，求重合区间最长的两个区间段。

算法

// 算法实现
struct postion{
    int x;
    int y;
}a[5];

int cmp(position a, position b){
    if(a.x == b.x){
        return a.y < b.y;
    }
    else{
        return a.x < b.x;
    }
}

int maxShareLen(position *a, int n){
    assert(a != NULL && n > 0);
    position pivot = a[0];
    int maxLen = 0;
    for(int i = 1; i < n; i++){
        if(a[i].x >= pivot.y){
            pivot = a[i];
        }
        else{
            if(a[i].y > pivot.y){
                maxLen = max(maxLen, (pivot.y - a[i].x));
                pivot = a[i];
            }
            else{
                maxLen = max(maxLen, (a[i].y - a[i].x));
            }
        }
    }
    return maxLen;
}

int main(){
    for(int i = 0; i < 5; i++){
        cin>>a[i].x>>a[i].y;
        sort(a, a + 5, cmp);
        int max = maxShareLen(a, 5);
    }
}

6,系统有很多任务，任务之间有依赖，比如B依赖于A，则A执行完后B才能执行

   1.不考虑系统并行性，设计一个函数（Task *Ptask,int Task_num），用最快的方法完成任务。
   2.考虑并行度，怎么设计。
   typedef struct{
        int ID;
        int * child;
        int child_num;
   }Task;
   提供的函数：
   bool doTask(int taskID);无阻塞的运行一个任务；
   int waitTask(inttimeout);返回运行完成的任务id，如果没有则返回-1；
   bool killTask(int taskID);杀死进程

7,解释下面ptr含义和不同

double* ptr = &value;
//ptr是一个指向double类型的指针，ptr的值可以改变，ptr所指向的value的值也可以改变 
const double *ptr = &value; double const *ptr = &value;
//ptr是一个指向constd ouble类型的指针，ptr的值可以改变，ptr所指向的value的值不可以改变
double * const ptr = &value;
//ptr是一个指向double类型的指针，ptr的值不可以改变，ptr所指向的value的值可以改变
const double * const ptr = &value;
//ptr是一个指向const double类型的指针，ptr的值不可以改变，ptr所指向的value的值也不可以

8,去掉const属性。

const double value = 0.0f;
double *ptr = NULL;
//强制类型转换
ptr = <const_cast double *>(&value);

10,现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来。

//bitmap
void bitmap(){
    int int_len = sizeof(int) * 8;
    int bit_len = 0xffffffff / int_len;
    int *bit = new int[bit_len];
    int v;
    while(scanf("%d", &v) != EOF){
        bit[v/int_len] |= (1 << v % int_len);
    }
    for(int i = 0; i < bit_len; i++){
        for(int j = 0; j < int_len; j++){
            if(bit[j] && (1 << j) == 0){
                printf("%d\n", i * int_len + j);
            }
        }
    }
}

11,SSH的原理

12,利用互斥量和条件变量设计一个消息队列，具有以下功能：

1. 创建消息队列（消息中所含的元素）
2. 消息队列中插入消息
3. 取出一个消息（阻塞方式）
4. 取出第一消息（非阻塞方式）

queue<msg> msgs;
pthread_mutex_t qready = PTHREAD_MUTEX_INITIALIZER;
ptrhead_cond_t qlock = PTHREAD_COND_INITIALIZER;

void process_msg(void){//4
    pthread_mutex_lock(&qlock);
    while(msgs.size() == 0){
        pthread_cond_wait(&qready, &lock);
    }
    msg = msgs.top();
    msg.pop();
    pthread_mutex_unlock(&qlock);
}

void enqueue_msg(msg m){//2
    pthread_mutex_lock(&qlock);
    msgs.push(m);
    pthread_mutex_unlock(&qlock);
    pthread_cond_signal(&qready);
}

13,对已排好序的数组A，一般来说可用二分查找可以很快找到。现有一特殊数组A[]，它是循环递增的，如A[]={ 17 19 20 25 1 4 7 9}，试在这样的数组中找一元素x，看看是否存在。

//leetcode Search in Rotated Sorted Array 
//https://leetcode.com/problems/search-in-rotated-sorted-array/
//space O(1), time O(lgn)
int search(int A[], int n, int target){
    int l = 0;
    int r = n - 1;
    if(n == 1){
        return (A[0] == target) ? 0 : -1;
    }
    
    while(l <= r){
        if(A[l] <= A[r] && (target > A[r] || A[l] > target)){
            return -1;
        }
        
        int mid = (l + r) / 2;
        if(A[mid] == target) return mid;
        
        if(A[l] < A[mid] && target >= A[l] && target < A[mid])
            r = mid - 1;
        else if(A[r] > A[mid] && target >= A[mid] && target <= A[r])
            l = mid + 1;
        else if(A[l] > A[mid])
            r = mid - 1;
        else if(A[r] < A[mid])
            l = mid + 1;
    }
    
    return -1;
}

14,动态链接库与静态链接库的区别

静态链接库是.lib格式的文件，一般在工程的设置界面加入工程中，程序编译时会把
lib文件的代码加入你的程序中因此会增加代码大小，你的程序一运行lib代码强制被
装入你程序的运行空间，不能手动移除lib代码.动态链接库是程序运行时动态装入内存
的模块，格式*.dll，在程序运行时可以随意加载和移除，节省内存空间。在大型的软
件项目中一般要实现很多功能，如果把所有单独的功能写成一个个lib文件的话，程序
运行的时候要占用很大的内存空间，导致运行缓慢；但是如果将功能写成dll文件，就
可以在用到该功能的时候调用功能对应的dll文件，不用这个功能时将dll文件移除内
存，这样可以节省内存空间。）

15,指针与引用的区别

相同点：1. 都是地址的概念；
指针指向一块内存，它的内容是所指内存的地址；引用是某块内存的别名。
区别：
1). 指针是一个实体，而引用仅是个别名；
2). 引用使用时无需解引用(*)，指针需要解引用；
3). 引用只能在定义时被初始化一次，之后不可变；指针可变；
4). 引用没有 const，指针有 const；
5). 引用不能为空，指针可以为空；
6). “sizeof 引用”得到的是所指向的变量(对象)的大小，而“sizeof 指针”得到的是指针本身(所指向的变量或对象的地址)的大小；
7). 指针和引用的自增(++)运算意义不一样；
8).从内存分配上看：程序为指针变量分配内存区域，而引用不需要分配内存区域。）

16,进程与线程的区别

①从概念上：
进程：一个程序对一个数据集的动态执行过程，是分配资源的基本单位。
线程：一个进程内的基本调度单位。
线程的划分尺度小于进程，一个进程包含一个或者更多的线程。
②从执行过程中来看：
进程：拥有独立的内存单元，而多个线程共享内存，从而提高了应用程序的运行效率。
线程：每一个独立的线程，都有一个程序运行的入口、顺序执行序列、和程序的出口。但是线程不能够独立的执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。
③从逻辑角度来看：（重要区别）
多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但是，操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理及资源分配。）

17,函数调用入栈出栈的过程。

//http://www.cnblogs.com/biyeymyhjob/archive/2012/07/20/2601204.html
1,堆栈中变量的分布是从高地址到低地址的分布。
2,指向栈底，ESP指向栈顶
具体的过程：
1,函数参数从右向左压入栈中。
2,返回地址入栈。
3,函数地址入栈后，EBP入栈，然后把当前的ESP值给EBP。
4,执行函数，局部变量入栈，完毕后，局部变量出栈。
5,EBP回复原值，返回地址出栈，执行原执行地址，参数出栈，调用完毕。

18,c++对象模型与虚表。

19,海量数据处理，以及如何解决Hash冲突等问题。

20,判断一个数的所有因数的个数是偶数还是奇数.

如果一个数是平方数，因数是奇数个；
如果不是平方数，因数是偶数个 
比如24这个数，可以把因子配对(1,24),(2,12),(3,8),(4,6)
而对于36，因子配对(1,36),(2,18),(3,12),(4,9),(6,6),因为是平方数，有一组中的数重复了，所以因子数为奇数。

21,指针数组和数组指针的区别。

int *ptr[10];//指针数组
int (*ptr)[10];//数组指针

22,查找单链表的中间结点。

node * midlist(node *head){
    if(head == NULL || head->next == NULL) return head;
    
    node *p = head;
    node *q = head->next;
    while(q != NULL && q->next != NULL){
        p = p->next;
        q = q->next->next;
    }
    
    return p;
}

23,sizeof和strlen的区别。

24,malloc-free和new-delete的区别

25,vector的实现机制.

1,当调用push_back成员函数时，怎么实现？
   内存足则直接 placement new 构造对象，否则扩充内存,
   转移对象，新对象placement new上去
2,当调用clear成员函数时，做什么操作，如果要释放内存该怎么做.
   调用析构函数，内存不释放。clear没有释放内存，只是将数  
   组中的元素置为空了，此时size=0，释放内存需要delete。
   v.swap(vector<T>());//清空数据

26,设子数组A[0:k]和A[k+1:N-1]已排好序(0≤K≤N-1)。试设计一个合并这2个子数组为排好序的数组A[0:N-1]的算法。要求算法在最坏情况下所用的计算时间为O(N)，只用到O(1)的辅助空间。

27,设rand（s，t）返回[s,t]之间的随机小数，利用该函数在一个半径为R的圆内找随机n个点，并给出时间复杂度分析。

int count = 0;
int x = 0, y = 0;
while(count < n){
    x = rand(-r, r);
    y = rand(-sqrt(r * r - x * x), sqrt(r * r - x * x));
    
    if(x * x + y * y != r * r){
        ++count;
    }
}

28,求全排列

bool isSwap(string str, int l, int r){
    for(int i = l; l < r; l++){
        if(str[i] == str[r])
            return false;
    }
    return ture;
}

void cur(string &str, int l, int r, vector<string> &svec){
    if(l == r){
        string s(str);
        svec.push_back(s);
    }
    else{
        for(int i = l; i <= r; i++){
            if(isSwap(str, l, i)){
                swap(str[l], str[i]);
                cur(str, l + 1, r, svec);
                swap(str[l], str[i]);
            }
        }
    }
}

29,求一个组合函数： 如p([1,2,3]) ，输出：[1],[2],[3],[1,2],[2,3],[1,3],[1,2,3]

stack<int> istack;
vector<string> istr;
void print_stack(){
	if(istack.empty()) return;
	vector<int> ivec;
	string s = "";
	while (!istack.empty()){
		int c = istack.top();
		s += c;
		ivec.push_back(c);
		istack.pop();
	}
	//cout<<s<<endl;
	if(find(istr.begin(), istr.end(), s) == istr.end()){
		cout<<s<<endl;
		istr.push_back(s);
	}
	for(vector<int>::reverse_iterator iter = ivec.rbegin(); 
	                iter != ivec.rend(); iter++){
		istack.push(*iter);
	}
	ivec.clear();
}
void enum_array(char *p, int n){
	if(n < 0) return;
	print_stack();
	istack.push(p[n - 1]);
	enum_array(p, n - 1);
	istack.pop();
	enum_array(p, n - 1);
}