

/////////////////////////  排序 ///////////////////////////



49.一道看上去很吓人的算法面试题：

如何对n个数进行排序，要求时间复杂度O(n)，空间复杂度O(1)

 
3.快速排序（东软喜欢考类似的算法填空题，又如堆排序的算法等）




1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？
   






3.收藏了1万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似）

四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））

 
要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。


给你5个球，每个球被抽到的可能性为30、50、20、40、10，设计一个随机算法，该算法的输出结果为本次执行的结果。输出A，B，C，D，E即可。


2.已知一随机发生器，产生0的概率是p，产生1的概率是1-p，现在要你构造一个发生器，
使得它构造0和1的概率均为1/2；构造一个发生器，使得它构造1、2、3的概率均为1/3；...，
构造一个发生器，使得它构造1、2、3、...n的概率均为1/n，要求复杂度最低。







3.请编写能直接实现strstr()函数功能的代码。


请编写实现malloc()内存分配函数功能一样的代码。 


25、用C语言实现函数void * memmove(void *dest, const void *src, size_t n)。memmove
函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。

分析：由于可以把任何类型的指针赋给void类型的指针，这个函数主要是实现各种数据类型的拷贝。



8、请编写能直接实现int atoi(const char * pstr)函数功能的代码。







int i=(j=4,k=8,l=16,m=32); printf(“%d”, i); 输出是多少？

逗号运算符
(表达式1，表达式2，...，表达式n) 分别计算每个表达式，，最后表达式的值做为整个表达式的值
所以输出是32





42、两个圆相交，交点是A1，A2。现在过A1点做一直线与两个圆分别相交另外一点B1，B2。

B1B2可以绕着A1点旋转。问在什么情况下，B1B2最长




题目：输入四个点的坐标，求证四个点是不是一个矩形
关键点：
1.相邻两边斜率之积等于-1，
2.矩形边与坐标系平行的情况下，斜率无穷大不能用积判断。
3.输入四点可能不按顺序，需要对四点排序。


51、矩阵式螺旋输出

    





///////////////  系统设计  ///////////////////////////////


一、系统有很多任务，任务之间有依赖，比如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(int timeout);返回运行完成的任务id，如果没有则返回-1；
    bool killTask(int taskID);杀死进程



2.设计一种内存管理算法。 




1.有不同的手机终端，如iphone，安卓，Symbian，不同的终端处理不一样，设计一种服务器和算法实现对不同的终端的处理。



3.A向B发邮件，B收到后读取并发送收到，但是中间可能丢失了该邮件，怎么设计一种最节省的方法，来处理丢失问题。 

4.设计一种算法求出算法复杂度 。



















