常见算法面试题及答案

A. 面试算法题：你的任务就是计算出长度为n的字符串(只包含‘A’、‘B’和‘C’)，有多少个是暗黑字符串。

程序肯定不是判断一个字符串是纯洁的还是黑暗的。从现有的题目描述看，程序和题目没有关系。

题目是否不全？

B. 面试官常问十大经典算法排序（用python实现）

算法是一种与语言无关的东西，更确切地说就算解决问题的思路，就是一个通用的思想的问题。代码本身不重要，算法思想才是重中之重

我们在面试的时候总会被问到一下算法，虽然算法是一些基础知识，但是难起来也会让人非常头疼。

排序算法应该算是一些简单且基础的算法，但是我们可以从简单的算法排序锻炼我们的算法思维。这里我就介绍经典十大算法用python是怎么实现的。

十大经典算法可以分为两大类：

比较排序： 通过对数组中的元素进行比较来实现排序。

非比较排序： 不通过比较来决定元素间的相对次序。

算法复杂度

冒泡排序比较简单，几乎所有语言算法都会涉及的冒泡算法。

基本原理是两两比较待排序数据的大小 ，当两个数据的次序不满足顺序条件时即进行交换，反之，则保持不变。

每次选择一个最小（大）的，直到所有元素都被输出。

将第一个元素逐个插入到前面的有序数中，直到插完所有元素为止。

从大范围到小范围进行比较-交换，是插入排序的一种，它是针对直接插入排序算法的改进。先对数据进行预处理，使其基本有序，然后再用直接插入的排序算法排序。

该算法是采用 分治法 对集合进行排序。

把长度为n的输入序列分成两个长度为n/2的子序列，对这两个子序列分别采用归并排序，最终合并成序列。

选取一个基准值，小数在左大数在在右。

利用堆这种数据结构所设计的一种排序算法。

堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。利用最大堆和最小堆的特性。

采用字典计数-还原的方法，找出待排序的数组中最大和最小的元素，统计数组中每个值为i的元素出现的次数，对所有的计数累加，将每个元素放在新数组依次排序。

设置一个定量的数组当作空桶；遍历输入数据，并且把数据一个一个放到对应的桶里去；对每个不是空的桶进行排序；从不是空的桶里把排好序的数据拼接起来。

元素分布在桶中：

然后，元素在每个桶中排序：

取得数组中的最大数，并取得位数；从最低位开始取每个位组成新的数组；然后进行计数排序。

上面就是我整理的十大排序算法，希望能帮助大家在算法方面知识的提升。看懂之后可以去试着自己到电脑上运行一遍。最后说一下每个排序是没有调用数据的，大家记得实操的时候要调用。

参考地址：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

C. 经典C语言面试算法题

经典C语言面试算法题

1.写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)

功能：

在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数outputstr所指内存。例如："abcd12345ed125ss123456789"的首地址传给intputstr后，函数将返回

9，outputstr所指的值为123456789。

#include

#include

#include

int FindMax_NumStr(char *outputstr,char *inputstr)

{

char *in = inputstr,*out = outputstr,*temp;

char *final;

int count = 0;

int maxlen = 0;

int i;

while(*in!='')

{

if(*in > 47 && *in < 58)

{

for(temp = in;*in> 47 && *in <58;in++)

count++;

}

else

in++;

if(maxlen < count)

{

maxlen = count;

count = 0;

final = temp;

}

}

for(i =0;i

{

*out = *final;

out++;

final++;

}

*out = '';

return maxlen;

}

void main(void)

{

char input[]="abc123def123456eec123456789dd";

char output[50] = {0};

int maxlen;

maxlen = FindMax_NumStr(output,input);

printf("the str %s ",output);

printf("the maxlen is %d ",maxlen);

}

2.求1000!的未尾有几个0;

求出1->1000里,能被5整除的数的个数n1,能被25整除的数的个数n2,能被125整除的'数的个数n3,能被625整除的数的个数n4.1000!末尾的零的个数=n1+n2+n3+n4;

只要是末尾是5的数它乘以一个偶数就会出现一个0，而末尾是0的数乘以任何数也都会出现0

而末尾是0的如果是一个0肯定能被5整除，两个0肯定能被25整数，以此类推3个0就能被5的三次方整除，也就是125

1000!就是1-1000数的相乘，能被5整除的所有数分别乘以一个偶数就会出现这些个的0，而例如100，既能被5整除，也能被25整除，所以就是两个0

1000，既能被5，25，也能被125整除，所以算三个0

例如是10!=1*2*3*4*5*6*7*8*9*10，里面有两个数能被5整除，就是10和5，而

5随便乘以一个偶数就出现一个0，而10乘以其它数也会出现一个0，所以10!会有两个0

#include

#define NUM 1000

int find5(int num)

{

int ret = 0;

while(num%5==0)

{

num/=5;

ret++;

}

return ret;

}

int main(void)

{

int result = 0;

int i;

for(i=5;i<=NUM;i+=5)

result +=find5(i);

printf("the total zero number is %d ",result);

return 0;

}

3。编写一个 C 函数，该函数在一个字符串中找到可能的最长的子字符串，且该字符串是由同一字符组成的。

char * search(char *cpSource, char ch)

{

char *cpTemp=NULL, *cpDest=NULL;

int iTemp, iCount=0;

while(*cpSource)

{

if(*cpSource == ch)

{

iTemp = 0;

cpTemp = cpSource;

while(*cpSource == ch)

++iTemp, ++cpSource;

if(iTemp > iCount)

iCount = iTemp, cpDest = cpTemp;

if(!*cpSource)

break;

}

++cpSource;

}

return cpDest;

}

;

D. java编程常见面试题目,要求正确答案

第一，谈谈final, finally, finalize的区别。

final?修饰符（关键字）如果一个类被声明为final，意味着它不能再派生出新的子类，不能作为父类被继承。因此一个类不能既被声明为 abstract的，又被声明为final的。将变量或方法声明为final，可以保证它们在使用中不被改变。被声明为final的变量必须在声明时给定初值，而在以后的引用中只能读取，不可修改。被声明为final的方法也同样只能使用，不能重载finally?再异常处理时提供 finally 块来执行任何清除操作。如果抛出一个异常，那么相匹配的 catch 子句就会执行，然后控制就会进入 finally 块（如果有的话）。

finalize?方法名。Java 技术允许使用 finalize() 方法在垃圾收集器将对象从内存中清除出去之前做必要的清理工作。这个方法是由垃圾收集器在确定这个对象没有被引用时对这个对象调用的。它是在 Object 类中定义的，因此所有的类都继承了它。子类覆盖 finalize() 方法以整理系统资源或者执行其他清理工作。finalize() 方法是在垃圾收集器删除对象之前对这个对象调用的。

第二，Anonymous Inner Class (匿名内部类) 是否可以extends(继承)其它类，是否可以implements(实现)interface(接口)?

匿名的内部类是没有名字的内部类。不能extends(继承) 其它类，但一个内部类可以作为一个接口，由另一个内部类实现。

第三，Static Nested Class 和 Inner Class的不同，说得越多越好(面试题有的很笼统)。

Nested Class （一般是C++的说法），Inner Class (一般是JAVA的说法)。Java内部类与C++嵌套类最大的不同就在于是否有指向外部的引用上。具体可见http: //www.frontfree.net/articles/services/view.ASP?id=704&page=1

注： 静态内部类（Inner Class）意味着1创建一个static内部类的对象，不需要一个外部类对象，2不能从一个static内部类的一个对象访问一个外部类对象

第四，&和&&的区别。

&是位运算符。&&是布尔逻辑运算符。

第五，HashMap和Hashtable的区别。

都属于Map接口的类，实现了将惟一键映射到特定的值上。

HashMap 类没有分类或者排序。它允许一个 null 键和多个 null 值。

Hashtable 类似于 HashMap，但是不允许 null 键和 null 值。它也比 HashMap 慢，因为它是同步的。

第六，Collection 和 Collections的区别。

Collections是个java.util下的类，它包含有各种有关集合操作的静态方法。
Collection是个java.util下的接口，它是各种集合结构的父接口。

第七，什么时候用assert。

断言是一个包含布尔表达式的语句，在执行这个语句时假定该表达式为 true。如果表达式计算为 false，那么系统会报告一个 AssertionError。它用于调试目的：

assert(a > 0); // throws an AssertionError if a <= 0

断言可以有两种形式：

assert Expression1 ;
assert Expression1 : Expression2 ;

Expression1 应该总是产生一个布尔值。
Expression2 可以是得出一个值的任意表达式。这个值用于生成显示更多调试信息的 String 消息。
断言在默认情况下是禁用的。要在编译时启用断言，需要使用 source 1.4 标记：

Javac -source 1.4 Test.java

要在运行时启用断言，可使用 -enableassertions 或者 -ea 标记。
要在运行时选择禁用断言，可使用 -da 或者 -disableassertions 标记。
要系统类中启用断言，可使用 -esa 或者 -dsa 标记。还可以在包的基础上启用或者禁用断言。

可以在预计正常情况下不会到达的任何位置上放置断言。断言可以用于验证传递给私有方法的参数。不过，断言不应该用于验证传递给公有方法的参数，因为不管是否启用了断言，公有方法都必须检查其参数。不过，既可以在公有方法中，也可以在非公有方法中利用断言测试后置条件。另外，断言不应该以任何方式改变程序的状态。

第八，GC是什么? 为什么要有GC? (基础)。

GC是垃圾收集器。Java 程序员不用担心内存管理，因为垃圾收集器会自动进行管理。要请求垃圾收集，可以调用下面的方法之一：

System.gc()
Runtime.getRuntime().gc()

第九，String s = new String("xyz");创建了几个String Object?

两个对象，一个是“xyx”,一个是指向“xyx”的引用对象s。

第十，Math.round(11.5)等于多少? Math.round(-11.5)等于多少?

Math.round(11.5)返回（long）12，Math.round(-11.5)返回（long）-11;

第十一，short s1 = 1; s1 = s1 + 1;有什么错? short s1 = 1; s1 += 1;有什么错?

short s1 = 1; s1 = s1 + 1;有错，s1是short型，s1+1是int型,不能显式转化为short型。可修改为s1 =(short)(s1 + 1) 。short s1 = 1; s1 += 1正确。

第十二，sleep() 和 wait() 有什么区别? 搞线程的最爱

sleep()方法是使线程停止一段时间的方法。在sleep 时间间隔期满后，线程不一定立即恢复执行。这是因为在那个时刻，其它线程可能正在运行而且没有被调度为放弃执行，除非(a)“醒来”的线程具有更高的优先级，(b)正在运行的线程因为其它原因而阻塞。

wait()是线程交互时，如果线程对一个同步对象x 发出一个wait()调用，该线程会暂停执行，被调对象进入等待状态，直到被唤醒或等待时间到。

第十三，Java有没有goto?

Goto?java中的保留字，现在没有在java中使用。

第十四，数组有没有length()这个方法? String有没有length()这个方法？

数组没有length()这个方法，有length的属性。
String有有length()这个方法。

第十五，Overload和Override的区别。Overloaded的方法是否可以改变返回值的类型?

方法的重写Overriding和重载Overloading是Java多态性的不同表现。重写Overriding是父类与子类之间多态性的一种表现，重载Overloading是一个类中多态性的一种表现。如果在子类中定义某方法与其父类有相同的名称和参数，我们说该方法被重写 (Overriding)。子类的对象使用这个方法时，将调用子类中的定义，对它而言，父类中的定义如同被“屏蔽”了。如果在一个类中定义了多个同名的方法，它们或有不同的参数个数或有不同的参数类型，则称为方法的重载(Overloading)。Overloaded的方法是可以改变返回值的类型。

第十六，Set里的元素是不能重复的，那么用什么方法来区分重复与否呢? 是用==还是equals()? 它们有何区别?

Set里的元素是不能重复的，那么用iterator()方法来区分重复与否。equals()是判读两个Set是否相等。

equals()和==方法决定引用值是否指向同一对象equals()在类中被覆盖，为的是当两个分离的对象的内容和类型相配的话，返回真值。

第十七，给我一个你最常见到的runtime exception。

ArithmeticException, ArrayStoreException, BufferOverflowException, BufferUnderflowException, CannotRedoException, CannotUndoException, ClassCastException, CMMException, , DOMException, EmptyStackException, IllegalArgumentException, IllegalMonitorStateException, IllegalPathStateException, IllegalStateException,
ImagingOpException, IndexOutOfBoundsException, MissingResourceException, NegativeArraySizeException, NoSuchElementException, NullPointerException, ProfileDataException, ProviderException, RasterFormatException, SecurityException, SystemException, UndeclaredThrowableException, UnmodifiableSetException, UnsupportedOperationException

第十八，error和exception有什么区别?

error 表示恢复不是不可能但很困难的情况下的一种严重问题。比如说内存溢出。不可能指望程序能处理这样的情况。

exception 表示一种设计或实现问题。也就是说，它表示如果程序运行正常，从不会发生的情况。

第十九，List, Set, Map是否继承自Collection接口?

List，Set是

Map不是。

第二十，abstract class和interface有什么区别?

声明方法的存在而不去实现它的类被叫做抽象类（abstract class），它用于要创建一个体现某些基本行为的类，并为该类声明方法，但不能在该类中实现该类的情况。不能创建abstract 类的实例。然而可以创建一个变量，其类型是一个抽象类，并让它指向具体子类的一个实例。不能有抽象构造函数或抽象静态方法。Abstract 类的子类为它们父类中的所有抽象方法提供实现，否则它们也是抽象类为。取而代之，在子类中实现该方法。知道其行为的其它类可以在类中实现这些方法。

接口（interface）是抽象类的变体。在接口中，所有方法都是抽象的。多继承性可通过实现这样的接口而获得。接口中的所有方法都是抽象的，没有一个有程序体。接口只可以定义static final成员变量。接口的实现与子类相似，除了该实现类不能从接口定义中继承行为。当类实现特殊接口时，它定义（即将程序体给予）所有这种接口的方法。然后，它可以在实现了该接口的类的任何对象上调用接口的方法。由于有抽象类，它允许使用接口名作为引用变量的类型。通常的动态联编将生效。引用可以转换到接口类型或从接口类型转换，instanceof 运算符可以用来决定某对象的类是否实现了接口。

第二十一，abstract的method是否可同时是static,是否可同时是native，是否可同时是synchronized?

都不能

第二十二，接口是否可继承接口? 抽象类是否可实现(implements)接口? 抽象类是否可继承实体类(concrete class)?

接口可以继承接口。抽象类可以实现(implements)接口，抽象类是否可继承实体类，但前提是实体类必须有明确的构造函数。

第二十三，启动一个线程是用run()还是start()?

启动一个线程是调用start()方法，使线程所代表的虚拟处理机处于可运行状态，这意味着它可以由JVM调度并执行。这并不意味着线程就会立即运行。run()方法可以产生必须退出的标志来停止一个线程。

第二十四，构造器Constructor是否可被override?

构造器Constructor不能被继承，因此不能重写Overriding，但可以被重载Overloading。

第二十五，是否可以继承String类?

String类是final类故不可以继承。

第二十六，当一个线程进入一个对象的一个synchronized方法后，其它线程是否可进入此对象的其它方法?

不能，一个对象的一个synchronized方法只能由一个线程访问。

第二十七，try {}里有一个return语句，那么紧跟在这个try后的finally {}里的code会不会被执行，什么时候被执行，在return前还是后?

会执行，在return前执行。

第二十八，编程题: 用最有效率的方法算出2乘以8等于几?

有C背景的程序员特别喜欢问这种问题。

2 << 3

第二十九，两个对象值相同(x.equals(y) == true)，但却可有不同的hash code，这句话对不对?

不对，有相同的hash code。

第三十，当一个对象被当作参数传递到一个方法后，此方法可改变这个对象的属性，并可返回变化后的结果，那么这里到底是值传递还是引用传递?

是值传递。Java 编程语言只由值传递参数。当一个对象实例作为一个参数被传递到方法中时，参数的值就是对该对象的引用。对象的内容可以在被调用的方法中改变，但对象的引用是永远不会改变的。

第三十一，swtich是否能作用在byte上，是否能作用在long上，是否能作用在String上?

switch（expr1）中，expr1是一个整数表达式。因此传递给 switch 和 case 语句的参数应该是 int、 short、 char 或者 byte。long,string 都不能作用于swtich。

第三十二，编程题: 写一个Singleton出来。

Singleton模式主要作用是保证在Java应用程序中，一个类Class只有一个实例存在。

一般Singleton模式通常有几种种形式:

第一种形式: 定义一个类，它的构造函数为private的，它有一个static的private的该类变量，在类初始化时实例话，通过一个public的getInstance方法获取对它的引用,继而调用其中的方法。

public class Singleton {
private Singleton(){}
//在自己内部定义自己一个实例，是不是很奇怪？
//注意这是private 只供内部调用
private static Singleton instance = new Singleton();
//这里提供了一个供外部访问本class的静态方法，可以直接访问
public static Singleton getInstance() {
return instance;
}
}

第二种形式:

public class Singleton {
private static Singleton instance = null;
public static synchronized Singleton getInstance() {
//这个方法比上面有所改进，不用每次都进行生成对象，只是第一次
//使用时生成实例，提高了效率！
if (instance==null)
instance＝new Singleton();
return instance; }
}

其他形式:

定义一个类，它的构造函数为private的，所有方法为static的。

一般认为第一种形式要更加安全些

第三十三 Hashtable和HashMap

Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现

HashMap允许将null作为一个entry的key或者value，而Hashtable不允许

还有就是，HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解。

最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap就必须为之提供外同步。

Hashtable和HashMap采用的hash/rehash算法都大概一样，所以性能不会有很大的差异。

E. 经典C语言面试算法题

1.写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)

功能：

在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数outputstr所指内存。例如："abcd12345ed125ss123456789"的首地址传给intputstr后，函数将返回

9，outputstr所指的值为123456789。

#include

#include

#include

int FindMax_NumStr(char *outputstr,char *inputstr)

{

char *in = inputstr,*out = outputstr,*temp;

char *final;

int count = 0;

int maxlen = 0;

int i;

while(*in!='')

{

if(*in > 47 && *in < 58)

{

for(temp = in;*in> 47 && *in <58;in++)

count++;

}

else

in++;

if(maxlen < count)

{

maxlen = count;

count = 0;

final = temp;

}

}

for(i =0;i

{

*out = *final;

out++;

final++;

}

*out = '';

return maxlen;

}

void main(void)

{

char input[]="abc123def123456eec123456789dd";

char output[50] = {0};

int maxlen;

maxlen = FindMax_NumStr(output,input);

printf("the str %s ",output);

printf("the maxlen is %d ",maxlen);

}

2.求1000!的'未尾有几个0;

求出1->1000里,能被5整除的数的个数n1,能被25整除的数的个数n2,能被125整除的数的个数n3,能被625整除的数的个数n4.1000!末尾的零的个数=n1+n2+n3+n4;

只要是末尾是5的数它乘以一个偶数就会出现一个0，而末尾是0的数乘以任何数也都会出现0

而末尾是0的如果是一个0肯定能被5整除，两个0肯定能被25整数，以此类推3个0就能被5的三次方整除，也就是125

1000!就是1-1000数的相乘，能被5整除的所有数分别乘以一个偶数就会出现这些个的0，而例如100，既能被5整除，也能被25整除，所以就是两个0

1000，既能被5，25，也能被125整除，所以算三个0

例如是10!=1*2*3*4*5*6*7*8*9*10，里面有两个数能被5整除，就是10和5，而

5随便乘以一个偶数就出现一个0，而10乘以其它数也会出现一个0，所以10!会有两个0

#include

#define NUM 1000

int find5(int num)

{

int ret = 0;

while(num%5==0)

{

num/=5;

ret++;

}

return ret;

}

int main(void)

{

int result = 0;

int i;

for(i=5;i<=NUM;i+=5)

result +=find5(i);

printf("the total zero number is %d ",result);

return 0;

}

3。编写一个 C 函数，该函数在一个字符串中找到可能的最长的子字符串，且该字符串是由同一字符组成的。

char * search(char *cpSource, char ch)

{

char *cpTemp=NULL, *cpDest=NULL;

int iTemp, iCount=0;

while(*cpSource)

{

if(*cpSource == ch)

{

iTemp = 0;

cpTemp = cpSource;

while(*cpSource == ch)

++iTemp, ++cpSource;

if(iTemp > iCount)

iCount = iTemp, cpDest = cpTemp;

if(!*cpSource)

break;

}

++cpSource;

}

return cpDest;

}

F. java算法面试题

三个for循环，第一个和第二个有啥区别?去掉一个吧
可以用迭代器remove方法，在移除的同时添加。

不知道是你记错了还是题本身就这样，我只想说：
写这代码的是二货么？
1、每个循环的索引都是从0开始，这是什么遍历方式？
2、看这题的目的是想把用户添加到相应的组里，这我就不明白了，新建一个用户的时候就没分配组么？那用户的GroupId哪来的？

3、这是一个操作，难道就不会根据GroupId直接查出用户或者组么？

这哪是优化代码？分明是挖坑。

G. c++经典面试题及答案

1. C++的类和C里面的struct有什么区别?

struct成员默认访问权限为public，而class成员默认访问权限为private

2. 析构函数和虚函数的用法和作用

析构函数是在对象生存期结束时自动调用的函数，用来释放在构造函数分配的内存。

虚函数是指被关键字virtual说明的函数，作用是使用C++语言的多态特性

3. 全局变量和局部变量有什么区别?是怎么实现的?操作系统和编译器是怎么知道的?

1) 全局变量的作用用这个程序块,而局部变量作用于当前函数

2) 前者在内存中分配在全局数据区,后者分配在栈区

3) 生命周期不同：全局变量随主程序创建和创建，随主程序销毁而销毁，局部变量在局部函数内部，甚至局部循环体等内部存在，退出就不存在

4) 使用方式不同：通过声明后全局变量程序的各个部分都可以用到，局部变量只能在局部使用

4. 有N个大小不等的自然数(1–N)，请将它们由小到大排序.要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。

void sort(int e[], int n)

{

int i;

int t;

for (i=1; i {

t = e[e[i]];

e[e[i]] = e[i];

e[i] = t;

}

}

5. 堆与栈的去区别

A. 申请方式不同

Stack由系统自动分配，而heap需要程序员自己申请，并指明大小。

B. 申请后系统的响应不同

Stack：只要栈的剩余空间大于申请空间，系统就为程序提供内存，否则将抛出栈溢出异常

Heap：当系统收到程序申请时，先遍历操作系统中记录空闲内存地址的链表，寻找第一个大于所申请空间的堆结点，然后将该结点从空间结点链表中删 除，并将该结点的空间分配给程序。另外，大多数系统还会在这块内存空间中的首地址处记录本次分配的大小，以便于delete语句正确释放空间。而且，由于 找到的堆结点的大小不一定正好等于申请的大小，系统会自动将多余的那部分重新放入空闲链表。

C. 申请大小限制的不同

Stack：在windows下，栈的大小是2M(也可能是1M它是一个编译时就确定的常数)，如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。

Heap：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。

D. 申请效率的比较：

栈由系统自动分配，速度较快。但程序员是无法控制的。

堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便。

另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈是直接在进程的地址空间中保留一快内存，虽然用起来最不方便。但是速度快，也最灵活。

E. 堆和栈中的存储内容

栈：在函数调用时，第一个进栈的是主函数中后的下一条指令(函数调用语句的下一条可执行语句)的地址，然后是函数的各个参数，在大多数的C编译器 中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开 始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。

堆：一般是在堆的.头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。

6. 含参数的宏与函数的优缺点

宏： 优点：在预处理阶段完成，不占用编译时间，同时，省去了函数调用的开销，运行效率高

缺点：不进行类型检查，多次宏替换会导致代码体积变大，而且由于宏本质上是字符串替换，故可能会由于一些参数的副作用导致得出错误的结果。

函数： 优点：没有带参数宏可能导致的副作用，进行类型检查，计算的正确性更有保证。

缺点：函数调用需要参数、返回地址等的入栈、出栈开销，效率没有带参数宏高

PS：宏与内联函数的区别

内联函数和宏都是在程序出现的地方展开，内联函数不是通过函数调用实现的，是在调用该函数的程序处将它展开(在编译期间完成的);宏同样是;

不同的是：内联函数可以在编译期间完成诸如类型检测，语句是否正确等编译功能;宏就不具有这样的功能，而且宏展开的时间和内联函数也是不同的(在运行期间展开)

7. Windows程序的入口是哪里?写出Windows消息机制的流程

Windows程序的入口是WinMain()函数。

Windows应用程序消息处理机制：

A. 操作系统接收应用程序的窗口消息，将消息投递到该应用程序的消息队列中

B. 应用程序在消息循环中调用GetMessage函数从消息队列中取出一条一条的消息，取出消息后，应用程序可以对消息进行一些预处理。

C. 应用程序调用DispatchMessage，将消息回传给操作系统。

D. 系统利用WNDCLASS结构体的lpfnWndProc成员保存的窗口过程函数的指针调用窗口过程，对消息进行处理。

8. 如何定义和实现一个类的成员函数为回调函数

A.什么是回调函数?

简而言之，回调函数就是被调用者回头调用调用者的函数。

使用回调函数实际上就是在调用某个函数(通常是API函数)时，将自己的一个函数(这个函数为回调函数)的地址作为参数传递给那个被调用函数。而该被调用函数在需要的时候，利用传递的地址调用回调函数。

回调函数，就是由你自己写的，你需要调用另外一个函数，而这个函数的其中一个参数，就是你的这个回调函数名。这样，系统在必要的时候，就会调用你写的回调函数，这样你就可以在回调函数里完成你要做的事。

B.如何定义和实现一个类的成员函数为回调函数

要定义和实现一个类的成员函数为回调函数需要做三件事：

a.声明;

b.定义;

c.设置触发条件，就是在你的函数中把你的回调函数名作为一个参数，以便系统调用

如：

一、声明回调函数类型

typedef void (*FunPtr)(void);

二、定义回调函数

class A

{

public:

A();

static void callBackFun(void) //回调函数，必须声明为static

{

cout<<"callBackFun"<

}

virtual ~A();

};

三、设置触发条件

void Funtype(FunPtr p)

{

p();

}

void main(void)

{

Funtype(A::callBackFun);

}

C. 回调函数与API函数

回调和API非常接近，他们的共性都是跨层调用的函数。但区别是API是低层提供给高层的调用，一般这个函数对高层都是已知的;而回调正好相反， 他是高层提供给底层的调用，对于低层他是未知的，必须由高层进行安装，这个安装函数其实就是一个低层提供的API，安装后低层不知道这个回调的名字，但它 通过一个函数指针来保存这个回调函数，在需要调用时，只需引用这个函数指针和相关的参数指针。

其实：回调就是该函数写在高层，低层通过一个函数指针保存这个函数，在某个事件的触发下，低层通过该函数指针调用高层那个函数。

H. 如何准备算法面试

主要介绍算法面试的一些问题、以及如何准备算法面试

!--more--

算法面试不仅仅是正确的回答问题

对于面试中遇到的大多数问题，都能有一个合理的思考路径

让大家在面对面试中的算法问题时，有一个合理的思考路径:

不代表能够“正确”回答每一个算法问题，但是合理的思考方向其实更重要，也是正确完成算法面试问题的前提

算法面试优秀不意味着技术面试优秀

技术面试优秀不意味着能够拿到Offer

算法面试的目的不是给出一个“正确”答案，

而是展示给面试官你思考问题的方式。

算法面试不是高考。

把这个过程看作是和面试官一起探讨一个问题的解决方案。

对于问题的细节和应用环境，可以和面试官沟通。

这种沟通本身很重要，它暗示着你思考问题的方式。

我们需要对一组数据进行排序

设计排序接口，标准库的设计，业务中排序算法。

排序是基础操作，很重要。

解决

快速排序算法：O(nlogn)

忽略了算法使用的基础环境。要动态选择。

(向面试官提问):这组数据有什么样的特征?

有没有可能包含有大量重复的元素?

如果有这种可能的话，三路快排是更好地选择。

普通数据：普通快速排序就行了;java语言标准库排序使用的三路快排。

是否大部分数据距离它正确的位置很近?是否近乎有序?

如果是这样的话，插入排序是更好地选择。

按照业务发生顺序,先发生先完成,几乎有序，插入排序是更好的选择。

是否数据的取值范围非常有限?比如对学生成绩排序。

如果是这样的话，计数排序是更好地选择。高考成绩取值范围有限：计数排序更好。

(向面试官提问):对排序有什么额外的要求?

是否需要稳定排序?

如果是的话，归并排序是更好地选择。

(向面试官提问):数据的存储状况是怎样的?

是否是使用链表存储的?

如果是的话，归并排序是更好地选择。

快排依赖于数组的随机存取。

(向面试官提问):数据的存储状况是怎样的?

数据的大小是否可以装载在内存里?

数据量很大，或者内存很小，不足以装载在内存里，需要使用外排序算法。

有没有可能包含有大量重复的元素?

是否大部分数据距离它正确的位置很近?是否近乎有序?

是否数据的取值范围非常有限?比如对学生成绩排序。

是否需要稳定排序?

是否是使用链表存储的?

数据的大小是否可以装载在内存里?

正确除了你能把代码编出来运行出正确的结果。正确还包含对问题的独到见解;优化;代码规范;容错性;

o 不仅仅是给出解决算法问题的代码,还要把上面因素包括。

o 如果是非常难的问题，对你的竞争对手来说，也是难的。

关键在于你所表达出的解决问题的思路。

甚至通过表达解题思路的方向，得出结论：这个问题的解决方案，应该在哪一个领域，我可以通过查阅或者进一步学习解决问题。

算法面试只是面试的一部分

算法面试只是技术面试的一部分。

根据你的简历和应聘职位的不同，势必要考察其他技术方面。

项目经历和项目中遇到的实际问题

o 解决能力，是否参与

o 深入思考

o 技术态度

面试前梳理自己简历上所写到的项目：整理一下可能会问到的。

你遇到的印象最深的bug是什么?

面向对象

设计模式

网络相关;安全相关;内存相关;并发相关;…

系统设计;scalability(大规模)

技术面试只是面试的一部分。面试不仅仅是考察你的技术水平，还是了解你的过去以及形成的思考行为方式。

关于过去：参与项目至关重要

工作人士

研究生

本科生

o 毕业设计

o 其他课程设计(大作业)

实习

创建自己的项目

o 自己做小应用：计划表;备忘录;播放器…

o 自己解决小问题：爬虫;数据分析;词频统计...

o “不是项目”的项目：一本优秀的技术书籍的代码整理等…(github)

o 分享：自己的技术博客;github等等

通过过去了解你的思考行为方式：

遇到的最大的挑战?

犯过的错误?

遭遇的失败?

最享受的工作内容?

遇到冲突的处理方式?

做的最与众不同的事儿?

具体阐述：我在某某项目中遇到一个怎样的算法问题：这个问题是怎样的。它是我遇到的最大的挑战,我是如何克服解决的。

整个小组的大概运行模式是怎样的?

整个项目的后续规划是如何的?

这个产品中的某个问题是如何解决的?

为什么会选择某些技术?标准?

我对某个技术很感兴趣，在你的小组中我会有怎样的机会深入这种技术?

算法面试仍然是非常重要的一部分

如何准备算法面试

准备面试和准备算法面试是两个概念

算法面试，只是面试中的一个环节。

远远不需要啃完一本《算法导论》

o 强调理论证明

o 第一遍读不需要弄懂证明

o 前几遍阅读应该记住结论就行了，不需要弄懂证明。把更多的精力放在算法思想上。

针对算法面试，算法导论里面的理论推导和证明不是很重要的方面。

选择合适的oj

leetcode

o Online Portal for IT Interview

o 真实的面试问题

o http://www.leetcode.com

HankeRank

o 特点是对于问题的分类很详细。偏难，不过可以对某一类细分问题解决。

o http://www.hackerrank.com

在学习和实践做题之间，要掌握平衡

基础算法实现与算法思想

如何回答算法面试问题

注意题目中的条件

o 给定一个有序数组...(二分法)

有一些题目中的条件本质是暗示

o 设计一个O(nlogn)的算法(分治：在一颗搜索树中完成任务，对于数据排序)

o 无需考虑额外的空间(用空间换时间上的优化)

o 数据规模大概是10000(O(n^2)就可以)

当没有思路的时候

自己给自己几个简单的测试用例，试验一下

不要忽视暴力解法。暴力解法通常是思考的起点。

例子

LeetCode 3 LongestSubstringWithout Repeating Characters

在一个字符串中寻找没有重复字母的最长子串

如”abcabcbb”，则结果为”abc”

如”bbbbb”，则结果为”b”

对于字符串s的子串s[i...j]

使用O(n^2)的算法遍历i,j，可以得到所有的子串s[i...j]

使用O(length(s[i...j]))的算法判断s[i...j]中是否含有重复字母

三重循环：复杂度O(n^3)，对于n=100的数据，可行

遍历常见的算法思路

遍历常见的数据结构

空间和时间的交换(哈希表)

预处理信息(排序)

在瓶颈处寻找答案：O(nlogn)+ O(n^2); O(n^3)

o O(n^2)能否优化。

什么样的问题使用什么样的思路和数据结构。

极端条件的判断

o 数组为空?

o 字符串为空?

o 数量为0?

o 指针为NULL?

代码规范:

o 变量名

o 模块化

o 复用性

I. 面试算法知识梳理(14) - 数字算法

面试算法知识梳理(1) - 排序算法
面试算法知识梳理(2) - 字符串算法第一部分
面试算法知识梳理(3) - 字符串算法第二部分
面试算法知识梳理(4) - 数组第一部分
面试算法知识梳理(5) - 数组第二部分
面试算法知识梳理(6) - 数组第三部分
面试算法知识梳理(7) - 数组第四部分
面试算法知识梳理(8) - 二分查找算法及其变型
面试算法知识梳理(9) - 链表算法第一部分
面试算法知识梳理(10) - 二叉查找树
面试算法知识梳理(11) - 二叉树算法第一部分
面试算法知识梳理(12) - 二叉树算法第二部分
面试算法知识梳理(13) - 二叉树算法第三部分

斐波那契数列 满足下面的通项公式，要求给出 N ，输出第 N 项的 F(N)

这里介绍两种解决办法， 循环算法 和 矩阵算法 。循环算法比较容易理解，就是从 F(0) 开始，根据通项公式，得到下一个斐波那契数列中的数字即可。

对于上面的通项公式，可以用下面的矩阵乘法的形式来表示

一个台阶总共有 n 级，如果一次可以跳 1 级，也可以跳 2 级，求总共有多少总跳法。

由于有两种跳台阶方式，因此跳 n 级台阶可以转换为下面两个问题之和：

这就和之前的斐波那契数列的通项公式相同。

这个问题，需要先总结一下规律，我们根据数字 N 的 位数 来进行分析：

那么 N>=1 时才会出现 1 ，并且出现 1 的次数为 1 次

在这种情况下，出现 1 的次数等于个位上出现 1 的次数加上十位上出现 1 的个数。

例如，如果要计算百位上 1 出现的次数，它要受到三方面的影响：百位上的数字，百位以下的数字，百位以上的数字。

对于一个二进制数，例如 1010 ，将其减 1 后得到的结果是 1001 ，也就是将最后一个 1 （倒数第二位）及其之后的 0 变成 1 ， 1 变成 0 ，再将该结果与原二进制数相与，也就是 1010 & 1001 = 1000 ，那么就可以去掉最后一个 1 。

因此，如果需要计算两个数的二进制表示中有多少位是不同的，可以 先将这两个数异或 ，那么不相同的位数就会变成 1 ，之后利用上面的技巧，通过每次去掉最后一个 1 ，来 统计该结果中 1 的个数 ，就可以知道两个数的二进制表示中有多少是不同的了。

N! 的含义为 1*2*3*...*(N-1)*N ，计算 N! 的十进制表示中，末尾有多少个 0 。

N! 中能产生末尾是 0 的质数组合是 2*5 ，所以 N! 末尾的 0 的个数取决了 2 的个数和 5 的个数的最小值，有因为被 2 整除的数出现的概率大于 5 ，因此 5 出现的次数就是 N! 末尾 0 的个数。因此，该问题就转换成为计算从 1~N ，每个数可以贡献 5 的个数，也就是每个数除以 5 的值。

上面的解法需要从 1 到 N 遍历每一个数，当然还有更加简便的方法。以 26! 为例，贡献 5 的数有 5、10、15、20、25 ，一共贡献了 6 个 5 ，可以理解为 5 的倍数 5、10、15、20、25 贡献了一个 5 ，而 25 的倍数又贡献了一个 5 ，得到下面的公式：

首先，让我们换一个角度考虑，其实这个问题就是求解二进制表示中从最低位开始 0 的个数，因为二进制最低位为 0 代表的是偶数，能够被 2 整除，所以质因数 2 的个数就是二进制表示中最低位 1 后面的 0 的个数。

因此，我们的实现这就和上面 2.7 中求解质因数 5 的个数是一样的。

最大公约数 的定义为 两个或多个整数的共有约数中最大的一个 。这里采用的是 更相止损法 ，其操作步骤为：

则第一步中约掉的若干个 2 与第二步中等数的乘积就是所求的最大公约数。

有限小数或者无限循环小数都可以转化为分数，例如：

在 http://blog.csdn.net/flyfish1986/article/details/47783545 这边文章中，详细地描述了该题的解决思路，核心思想就是将原小数分为 有限部分 和 无限循环小数 部分，对于这两部分别进行处理。

J. 大公司笔试面试有哪些经典算法题目

1、二维数组中的查找

具体例题：如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：{1, 2, 1}, {15, 78, 78, 15} , {112} 是回文序列, {1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是回文序列。现在给出一个数字序列，允许使用一种转换操作：选择任意两个相邻的数，然后从序列移除这两个数，并用这两个数字的和插入到这两个数之前的位置(只插入一个和)。现在对于所给序列要求出最少需要多少次操作可以将其变成回文序列？