1. 寻找两个有序数组的中位数
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
double ret = -1;
vector<double> buff;
//合并两个数组
for (auto e : nums1)
buff.push_back(e);
for (auto a : nums2)
buff.push_back(a);
//将合并后的结果进行排序
sort(buff.begin(), buff.end());
int size3 = buff.size();
//获取中位数
if (size3 % 2 == 0)
{
ret = ((buff[size3 / 2] + buff[size3 / 2 - 1]) / 2);
}
else
{
ret = buff[size3 / 2];
}
return ret;
}
2. C++实现线程安全的单例模式
懒汉模式：
class singleton
{
protected:
singleton()
{
pthread_mutex_init(&mutex);
}
private:
static singleton* p;
public:
static pthread_mutex_t mutex;
static singleton* initance();
};
pthread_mutex_t singleton::mutex;
singleton* singleton::p = NULL;
singleton* singleton::initance()
{
if (p == NULL)
{
pthread_mutex_lock(&mutex);
if (p == NULL)
p = new singleton();
pthread_mutex_unlock(&mutex);
}
return p;
}
3. kmp算法next数组求解过程
KMP算法是用来求一个较长字符串是否包含另一个较短字符串的算法。
int *next = new int[length];
//这里的str是被包含的较短字符串，length是这个字符串的长度。
void next(char *str, int *next, int length)
{
next[0] = -1;
int k = -1;
for (int q = 1; q <= length-1; q++)
{
while (k > -1 && str[k + 1] != str[q])
{
k = next[k];//往前回溯
}
if (str[k + 1] == str[q])//如果相同，k++
{
k = k + 1;
}
next[q] = k;
}
}
理解
这里是用被包含的较短字符串，自己与自己匹配，求得next数组，然后再进行算法的后续步骤。
next数组中储存的是这个字符串前缀和后缀中相同字符串的最长长度。比如abcdefgabc，前缀和后缀相同的是abc，长度是3。
next[i]储存的是string中前i+1位字符串前缀和后缀的最长长度。如abadefg，next[2]存的是aba这个字符串前缀和后缀的最长长度。
但是这里为了和代码相对应，将-1定义为相同长度为0，0定义为相同长度为1，……依次类推
这里用一个比较明显的字符串abababac来做例子，先创建一个和字符串长度相同的数组next。第一位设为-1。
所以向后移一位开始比较
a和b不同，next第二位写-1
再向后移一位
a和a相同，next数组存前一个k=-1加1等于0.
再比较下一位，相同就比前一个加一。
到第7位时，c和b不再相等，这时就用到了回溯！！！先看下一次比较时，应该移动到哪里。
原因要再回来看上一次比较，上一次比较相同长度为5。
看这5个字符串相同的前后缀的长度，即next[4]中储存的值：2再加1，因为这5个字符串就是str的前五个字符串！
所以k先回溯到2，再比较下一个字符是否相同，这里是比较c和b，不同，再回溯，这次前面剩下aba三个字符，k=next[2]=0，即前后缀还有一个字符相同，所以应该后移到下图位置。
再比较c和b，还不同，再回溯，k=next[0]=-1，然后next[7]=-1，这样就求出了next数组了。
4. 使用“反向代理服务器”的优点是什么?
（1）提高访问速度
由于目标主机返回的数据会存在代理服务器的硬盘中，因此下一次客户再访问相同的站 点数据时，会直接从代理服务器的硬盘中读取，起到了缓存的作用，尤其对于热门站点 能明显提高请求速度。
（2）防火墙作用
由于所有的客户机请求都必须通过代理服务器访问远程站点，因此可在代理服务器上设 限，过滤某些不安全信息。
（3）通过代理服务器访问不能访问的目标站点
互联网上有许多开发的代理服务器，客户机可访问受限时，可通过不受限的代理服务器 访问目标站点，通俗说，我们使用的***浏览器就是利用了代理服务器，可直接访问外 网。
5. kafka的生产者和消费者的理解
生产者:
Producer将消息发布到指定的Topic中,同时Producer也能决定将此消息归属于哪个 partition;比如基于"round-robin"方式或者通过其他的一些算法等.
消费者:
本质上kafka只支持Topic.每个consumer属于一个consumer group;反过来说,每个 group中可以有多个consumer.发送到Topic的消息,只会被订阅此Topic的每个group 中的一个consumer消费.
如果所有的consumer都具有相同的group,这种情况和queue模式很像;消息将会在 consumers之间负载均衡.
如果所有的consumer都具有不同的group,那这就是"发布-订阅";消息将会广播给所有 的消费者.
在kafka中,一个partition中的消息只会被group中的一个consumer消费;每个group 中consumer消息消费互相独立;我们可以认为一个group是一个"订阅"者,一个Topic 中的每个partions,只会被一个"订阅者"中的一个consumer消费,不过一个consumer 可以消费多个partitions中的消息.kafka只能保证一个partition中的消息被某个 consumer消费时,消息是顺序的.事实上,从Topic角度来说,消息仍不是有序的.
6. kafka中partition的工作原理?
Kafka集群partition replication默认自动分配分析
下面以Kafka集群中4个Broker举例，创建1个topic包含4个Partition，2 Replication；数据Producer流动如图所示：
当集群中新增2节点，Partition增加到6个时分布情况如下：
副本分配逻辑规则如下：
在Kafka集群中，每个Broker都有均等分配Partition的Leader机会。
上述图Broker Partition中，箭头指向为副本，以Partition-0为例:broker1中 parition-0为Leader，Broker2中Partition-0为副本。
上述图种每个Broker(按照BrokerId有序)依次分配主Partition,下一个Broker为副 本，如此循环迭代分配，多副本都遵循此规则。
副本分配算法如下：
将所有N Broker和待分配的i个Partition排序.
将第i个Partition分配到第(i mod n)个Broker上.
将第i个Partition的第j个副本分配到第((i + j) mod n)个Broker上.
7. redis的对象类型有哪些，底层的数据结构。（主要是有序列表的底层实现）
Redis的五大数据类型也称五大数据对象；前面介绍过6大数据结构，Redis并没有直 接使用这些结构来实现键值对数据库，而是使用这些结构构建了一个对象系统 redisObject；这个对象系统包含了五大数据对象，字符串对象（string）、列表对象 （list）、哈希对象（hash）、集合（set）对象和有序集合对象（zset）；而这五大 对象的底层数据编码可以用命令OBJECT ENCODING来进行查看。
1.字符串对象(string):字符串对象底层数据结构实现为简单动态字符串（SDS）和直接 存储，但其编码方式 可以是int、raw或者embstr，区别在于内存结构的不同。
2.列表对象(list):列表对象的编码可以是ziplist和linkedlist。
3.哈希对象(hash):哈希对象的编码可以是ziplist和hashtable。
4.集合对象(set):集合对象的编码可以是intset和hashtable。
5.有序集合对象(zset):有序集合的编码可以是ziplist和skiplist。
（1）ziplist编码
ziplist编码的有序集合对象底层实现是压缩列表，其结构与哈希对象类似，不同的是 两个紧密相连的压缩列表节点，第一个保存元素的成员，第二个保存元素的分值，而且 分值小的靠近表头，大的靠近表尾。
（2）skiplist编码
skiplist编码的有序集合对象底层实现是跳跃表和字典两种；
每个跳跃表节点都保存一个集合元素，并按分值从小到大排列；节点的object属性保 存了元素的成员，score属性保存分值；
字典的每个键值对保存一个集合元素，字典的键保存元素的成员，字典的值保存分值。
skiplist编码同时使用跳跃表和字典实现的原因
跳跃表优点是有序，但是查询分值复杂度为O(logn)；字典查询分值复杂度为O(1) ， 但是无序，所以结合连个结构的有点进行实现。
虽然采用两个结构但是集合的元素成员和分值是共享的，两种结构通过指针指向同一地 址，不会浪费内存。
有序集合编码转换：
有序集合对象使用ziplist编码需要满足两个条件：一是所有元素长度小于64字节； 二是元素个数小于128个；不满足任意一条件将使用skiplist编码。
8. Epoll在LT和ET模式下的区别以及注意事项
1.ET模式：
因为ET模式只有从unavailable到available才会触发，所以
1)、读事件：需要使用while循环读取完，一般是读到EAGAIN，也可以读到返回值小 于缓冲区大小；
如果应用层读缓冲区满：那就需要应用层自行标记，解决OS不再通知可读的问题
2)、写事件：需要使用while循环写到EAGAIN，也可以写到返回值小于缓冲区大小
如果应用层写缓冲区空（无内容可写）：那就需要应用层自行标记，解决OS不再通知 可写的问题。
3).正确的accept，accept 要考虑 2 个问题
(1) 阻塞模式 accept 存在的问题
考虑这种情况：TCP连接被客户端夭折，即在服务器调用accept之前，客户端主动发 送RST终止连接，导致刚刚建立的连接从就绪队列中移出，如果套接口被设置成阻 塞模式，服务器就会一直阻塞在accept调用上，直到其他某个客户建立一个新的连接 为止。但是在此期间，服务器单纯地阻塞在accept调用上，就绪队列中的其他描述符 都得不到处理。
解决办法是把监听套接口设置为非阻塞，当客户在服务器调用accept之前中止某个连 接时，accept调用可以立即返回-1，这时源自Berkeley的实现会在内核中处理该 事 件，并不会将该事件通知给epool，而其他实现把errno设置为ECONNABORTED或者 EPROTO错误，我们应该忽略这两个错误。
(2)ET模式下accept存在的问题
考虑这种情况：多个连接同时到达，服务器的TCP就绪队列瞬间积累多个就绪连接，由 于是边缘触发模式，epoll只会通知一次，accept只处理一个连接，导致TCP就绪队列 中剩下的连接都得不到处理。
解决办法是用while循环抱住accept调用，处理完TCP就绪队列中的所有连接后再退 出循环。如何知道是否处理完就绪队列中的所有连接呢？accept返回-1并且errno 设置为EAGAIN就表示所有连接都处理完。
综合以上两种情况，服务器应该使用非阻塞地accept，accept在ET模式下的正确使用 方式为：
while ((conn_sock = accept(listenfd,(struct sockaddr *) &remote,
(size_t *)&addrlen)) > 0) {
handle_client(conn_sock);
}
if (conn_sock == -1) {
if (errno != EAGAIN && errno != ECONNABORTED &&
errno != EPROTO && errno != EINTR)
perror("accept");
}
2.LT模式：
因为LT模式只要available就会触发，所以：
1)、读事件：因为一般应用层的逻辑是“来了就能读”，所以一般没有问题，无需while 循环读取到EAGAIN；
如果应用层读缓冲区满：就会经常触发，解决方式如下；
2)、写事件：如果没有内容要写，就会经常触发，解决方式如下。
LT经常触发读写事件的解决办法：修改fd的注册事件，或者把fd移出epollfd。
总结：
LT模式的优点在于：事件循环处理比较简单，无需关注应用层是否有缓冲或缓冲区是 否满，只管上报事件。缺点是：可能经常上报，可能影响性能。
9. 线程池的原理及实现
多线程技术主要解决处理器单元内多个线程执行的问题，它可以显著减少处理器单元 的闲置时间，增加处理器单元的吞吐能力。
假设一个服务器完成一项任务所需时间为：
T1 创建线程时间，
T2 在线程中执行任务的时间，
T3 销毁线程时间。
如果：T1 + T3 远大于 T2，则可以采用线程池，以提高服务器性能。
一个线程池包括以下四个基本组成部分：
1、线程池管理器（ThreadPool）：用于创建并管理线程池，包括 创建线程池，销毁线 程池，添加新任务；
2、工作线程（PoolWorker）：线程池中线程，在没有任务时处于等待状态，可以循环 的执行任务；
3、任务接口（Task）：每个任务必须实现的接口，以供工作线程调度任务的执行，它 主要规定了任务的入口，任务执行完后的收尾工作，任务的执行状态等；
4、任务队列（taskQueue）：用于存放没有处理的任务。提供一种缓冲机制。
线程池技术正是关注如何缩短或调整T1,T3时间的技术，从而提高服务器程序性能的。 它把T1，T3分别安排在服务器程序的启动和结束的时间段或者一些空闲的时间段，这 样在服务器程序处理客户请求时，不会有T1，T3的开销了。
线程池不仅调整T1,T3产生的时间段，而且它还显著减少了创建线程的数目。
代码实现:
condition.h
#ifndef _CONDITION_H_
#define _CONDITION_H_
#include <pthread.h>
//封装一个互斥量和条件变量作为状态
typedef struct condition
{
pthread_mutex_t pmutex;
pthread_cond_t pcond;
}condition_t;
//对状态的操作函数
int condition_init(condition_t *cond);
int condition_lock(condition_t *cond);
int condition_unlock(condition_t *cond);
int condition_wait(condition_t *cond);
int condition_timedwait(condition_t *cond, const struct timespec *abstime);
int condition_signal(condition_t* cond);
int condition_broadcast(condition_t *cond);
int condition_destroy(condition_t *cond);
#endif
condition.c
#include "condition.h"
//初始化
int condition_init(condition_t *cond)
{
int status;
if((status = pthread_mutex_init(&cond->pmutex, NULL)))
return status;
if((status = pthread_cond_init(&cond->pcond, NULL)))
return status;
return 0;
}
//加锁
int condition_lock(condition_t *cond)
{
return pthread_mutex_lock(&cond->pmutex);
}
//解锁
int condition_unlock(condition_t *cond)
{
return pthread_mutex_unlock(&cond->pmutex);
}
//等待
int condition_wait(condition_t *cond)
{
return pthread_cond_wait(&cond->pcond, &cond->pmutex);
}
//固定时间等待
int condition_timedwait(condition_t *cond, const struct timespec *abstime)
{
return pthread_cond_timedwait(&cond->pcond, &cond->pmutex, abstime);
}
//唤醒一个睡眠线程
int condition_signal(condition_t* cond)
{
return pthread_cond_signal(&cond->pcond);
}
//唤醒所有睡眠线程
int condition_broadcast(condition_t *cond)
{
return pthread_cond_broadcast(&cond->pcond);
}
//释放
int condition_destroy(condition_t *cond)
{
int status;
if((status = pthread_mutex_destroy(&cond->pmutex)))
return status;
if((status = pthread_cond_destroy(&cond->pcond)))
return status;
return 0;
}
threadpool.h
#ifndef _THREAD_POOL_H_
#define _THREAD_POOL_H_
//线程池头文件
#include "condition.h"
//封装线程池中的对象需要执行的任务对象
typedef struct task
{
void *(*run)(void *args); //函数指针，需要执行的任务
void *arg; //参数
struct task *next; //任务队列中下一个任务
}task_t;
//下面是线程池结构体
typedef struct threadpool
{
condition_t ready; //状态量
task_t *first; //任务队列中第一个任务
task_t *last; //任务队列中最后一个任务
int counter; //线程池中已有线程数
int idle; //线程池中kongxi线程数
int max_threads; //线程池最大线程数
int quit; //是否退出标志
}threadpool_t;
//线程池初始化
void threadpool_init(threadpool_t *pool, int threads);
//往线程池中加入任务
void threadpool_add_task(threadpool_t *pool, void *(*run)(void *arg), void *arg);
//摧毁线程池
void threadpool_destroy(threadpool_t *pool);
#endif
threadpool.c
#include "threadpool.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <time.h>
//创建的线程执行
void *thread_routine(void *arg)
{
struct timespec abstime;
int timeout;
printf("thread %d is starting\n", (int)pthread_self());
threadpool_t *pool = (threadpool_t *)arg;
while(1)
{
timeout = 0;
//访问线程池之前需要加锁
condition_lock(&pool->ready);
//空闲
pool->idle++;
//等待队列有任务到来 或者 收到线程池销毁通知
while(pool->first == NULL && !pool->quit)
{
//否则线程阻塞等待
printf("thread %d is waiting\n", (int)pthread_self());
//获取从当前时间，并加上等待时间， 设置进程的超时睡眠时间
clock_gettime(CLOCK_REALTIME, &abstime);
abstime.tv_sec += 2;
int status;
//该函数会解锁，允许其他线程访问，当被唤醒时，加锁
status = condition_timedwait(&pool->ready, &abstime);
if(status == ETIMEDOUT)
{
printf("thread %d wait timed out\n", (int)pthread_self());
timeout = 1;
break;
}
}
pool->idle--;
if(pool->first != NULL)
{
//取出等待队列最前的任务，移除任务，并执行任务
task_t *t = pool->first;
pool->first = t->next;
//由于任务执行需要消耗时间，先解锁让其他线程访问线程池
condition_unlock(&pool->ready);
//执行任务
t->run(t->arg);
//执行完任务释放内存
free(t);
//重新加锁
condition_lock(&pool->ready);
}
//退出线程池
if(pool->quit && pool->first == NULL)
{
pool->counter--;//当前工作的线程数-1
//若线程池中没有线程，通知等待线程（主线程）全部任务已经完成
if(pool->counter == 0)
{
condition_signal(&pool->ready);
}
condition_unlock(&pool->ready);
break;
}
//超时，跳出销毁线程
if(timeout == 1)
{
pool->counter--;//当前工作的线程数-1
condition_unlock(&pool->ready);
break;
}
condition_unlock(&pool->ready);
}
printf("thread %d is exiting\n", (int)pthread_self());
return NULL;
}
//线程池初始化
void threadpool_init(threadpool_t *pool, int threads)
{
condition_init(&pool->ready);
pool->first = NULL;
pool->last =NULL;
pool->counter =0;
pool->idle =0;
pool->max_threads = threads;
pool->quit =0;
}
//增加一个任务到线程池
void threadpool_add_task(threadpool_t *pool, void *(*run)(void *arg), void *arg)
{
//产生一个新的任务
task_t *newtask = (task_t *)malloc(sizeof(task_t));
newtask->run = run;
newtask->arg = arg;
newtask->next=NULL;//新加的任务放在队列尾端
//线程池的状态被多个线程共享，操作前需要加锁
condition_lock(&pool->ready);
if(pool->first == NULL)//第一个任务加入
{
pool->first = newtask;
}
else
{
pool->last->next = newtask;
}
pool->last = newtask; //队列尾指向新加入的线程
//线程池中有线程空闲，唤醒
if(pool->idle > 0)
{
condition_signal(&pool->ready);
}
//当前线程池中线程个数没有达到设定的最大值，创建一个新的线性
else if(pool->counter < pool->max_threads)
{
pthread_t tid;
pthread_create(&tid, NULL, thread_routine, pool);
pool->counter++;
}
//结束，访问
condition_unlock(&pool->ready);
}
//线程池销毁
void threadpool_destroy(threadpool_t *pool)
{
//如果已经调用销毁，直接返回
if(pool->quit)
{
return;
}
//加锁
condition_lock(&pool->ready);
//设置销毁标记为1
pool->quit = 1;
//线程池中线程个数大于0
if(pool->counter > 0)
{
//对于等待的线程，发送信号唤醒
if(pool->idle > 0)
{
condition_broadcast(&pool->ready);
}
//正在执行任务的线程，等待他们结束任务
while(pool->counter)
{
condition_wait(&pool->ready);
}
}
condition_unlock(&pool->ready);
condition_destroy(&pool->ready);
}
全部评论
(0) 回帖