推荐算法面试题

① java算法面试题：排序都有哪几种方法

一、冒泡排序
[java] view plain
package sort.bubble;
import java.util.Random;
/**
* 依次比较相邻的两个数，将小数放在前面，大数放在后面
* 冒泡排序，具有稳定性
* 时间复杂度为O（n^2）
* 不及堆排序，快速排序O（nlogn，底数为2）
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for(int i = 0 ; i < 10 ; i++){
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的数组为");
for(int i : sort){
System.out.print(i+" ");
}
buddleSort(sort);
System.out.println();
System.out.print("排序后的数组为");
for(int i : sort){
System.out.print(i+" ");
}
}
/**
* 冒泡排序
* @param sort
*/
private static void buddleSort(int[] sort){
for(int i=1;i<sort.length;i++){
for(int j=0;j<sort.length-i;j++){
if(sort[j]>sort[j+1]){
int temp = sort[j+1];
sort[j+1] = sort[j];
sort[j] = temp;
}
}
}
}
}
二、选择排序
[java] view plain
package sort.select;
import java.util.Random;
/**
* 选择排序
* 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，
* 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
* 选择排序是不稳定的排序方法。
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0; i < 10; i++) {
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
selectSort(sort);
System.out.println();
System.out.print("排序后的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
}
/**
* 选择排序
* @param sort
*/
private static void selectSort(int[] sort){
for(int i =0;i<sort.length-1;i++){
for(int j = i+1;j<sort.length;j++){
if(sort[j]<sort[i]){
int temp = sort[j];
sort[j] = sort[i];
sort[i] = temp;
}
}
}
}
}
三、快速排序
[java] view plain
package sort.quick;
/**
* 快速排序 通过一趟排序将要排序的数据分割成独立的两部分， 其中一部分的所有数据都比另外一部分的所有数据都要小，
* 然后再按此方法对这两部分数据分别进行快速排序， 整个排序过程可以递归进行，以此达到整个数据变成有序序列。
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
int[] sort = { 54, 31, 89, 33, 66, 12, 68, 20 };
System.out.print("排序前的数组为：");
for (int data : sort) {
System.out.print(data + " ");
}
System.out.println();
quickSort(sort, 0, sort.length - 1);
System.out.print("排序后的数组为：");
for (int data : sort) {
System.out.print(data + " ");
}
}
/**
* 快速排序
* @param sort 要排序的数组
* @param start 排序的开始座标
* @param end 排序的结束座标
*/
public static void quickSort(int[] sort, int start, int end) {
// 设置关键数据key为要排序数组的第一个元素，
// 即第一趟排序后，key右边的数全部比key大，key左边的数全部比key小
int key = sort[start];
// 设置数组左边的索引，往右移动判断比key大的数
int i = start;
// 设置数组右边的索引，往左移动判断比key小的数
int j = end;
// 如果左边索引比右边索引小，则还有数据没有排序
while (i < j) {
while (sort[j] > key && j > start) {
j--;
}
while (sort[i] < key && i < end) {
i++;
}
if (i < j) {
int temp = sort[i];
sort[i] = sort[j];
sort[j] = temp;
}
}
// 如果左边索引比右边索引要大，说明第一次排序完成，将sort[j]与key对换，
// 即保持了key左边的数比key小，key右边的数比key大
if (i > j) {
int temp = sort[j];
sort[j] = sort[start];
sort[start] = temp;
}
//递归调用
if (j > start && j < end) {
quickSort(sort, start, j - 1);
quickSort(sort, j + 1, end);
}
}
}
[java] view plain
/**
* 快速排序
*
* @param a
* @param low
* @param high
* voidTest
*/
public static void kuaisuSort(int[] a, int low, int high)
{
if (low >= high)
{
return;
}
if ((high - low) == 1)
{
if (a[low] > a[high])
{
swap(a, low, high);
return;
}
}
int key = a[low];
int left = low + 1;
int right = high;
while (left < right)
{
while (left < right && left <= high)// 左边向右
{
if (a[left] >= key)
{
break;
}
left++;
}
while (right >= left && right > low)
{
if (a[right] <= key)
{
break;
}
right--;
}
if (left < right)
{
swap(a, left, right);
}
}
swap(a, low, right);
kuaisuSort(a, low, right);
kuaisuSort(a, right + 1, high);
}
四、插入排序
[java] view plain
package sort.insert;
/**
* 直接插入排序
* 将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据
* 算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
*/
import java.util.Random;
public class DirectMain {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0; i < 10; i++) {
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
directInsertSort(sort);
System.out.println();
System.out.print("排序后的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
}
/**
* 直接插入排序
*
* @param sort
*/
private static void directInsertSort(int[] sort) {
for (int i = 1; i < sort.length; i++) {
int index = i - 1;
int temp = sort[i];
while (index >= 0 && sort[index] > temp) {
sort[index + 1] = sort[index];
index--;
}
sort[index + 1] = temp;
}
}
}
顺便添加一份，差不多的
[java] view plain
public static void charuSort(int[] a)
{
int len = a.length;
for (int i = 1; i < len; i++)
{
int j;
int temp = a[i];
for (j = i; j > 0; j--)//遍历i之前的数字
{
//如果之前的数字大于后面的数字，则把大的值赋到后面
if (a[j - 1] > temp)
{
a[j] = a[j - 1];
} else
{
break;
}
}
a[j] = temp;
}
}
把上面整合起来的一份写法：
[java] view plain
/**
* 插入排序:
*
*/
public class InsertSort {
public void sort(int[] data) {
for (int i = 1; i < data.length; i++) {
for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
swap(data, j, j - 1);
}
}
}
private void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
五、顺便贴个二分搜索法
[java] view plain
package search.binary;
public class Main {
public static void main(String[] args) {
int[] sort = {1,2,3,4,5,6,7,8,9,10};
int mask = binarySearch(sort,6);
System.out.println(mask);
}
/**
* 二分搜索法，返回座标，不存在返回-1
* @param sort
* @return
*/
private static int binarySearch(int[] sort,int data){
if(data<sort[0] || data>sort[sort.length-1]){
return -1;
}
int begin = 0;
int end = sort.length;
int mid = (begin+end)/2;
while(begin <= end){
mid = (begin+end)/2;
if(data > sort[mid]){
begin = mid + 1;
}else if(data < sort[mid]){
end = mid - 1;
}else{
return mid;
}
}
return -1;
}
}

② Java面试算法题求解

看了两行看不下去了，吐槽一下。
现在某些小公司的面试官，面试题花式秀智商，一副全世界都求着他赐予工作的样子。

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

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

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

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

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

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

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

算法复杂度

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

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

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

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

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

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

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

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

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

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

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

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

元素分布在桶中：

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

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

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

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

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

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

题目是否不全？

⑤ 面试算法知识梳理(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 这边文章中，详细地描述了该题的解决思路，核心思想就是将原小数分为 有限部分 和 无限循环小数 部分，对于这两部分别进行处理。

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

大公司的笔试面试一般是针对你所面试的岗位进行一些专业知识的考核，不会出现想考公员里面的行测似得，当然也有哪些逆向思维的计算题。

⑦ A/B Test基本原理

一、引入

ABTest，就是做一个测试，在产品设计场景中，为同一个产品目标制定两个方案（比如两个页面一个用这个文案另一个用那个文案，一个用红色的按钮、另一个用蓝色），让一部分用户使用A方案，另一部分用户使用B方案，然后利用埋点可以对用户点击行为数据进行采集，并通过统计引擎分析结构化的日志数据，计算相关指标，一般是点击率、转化率、CTR（点击次数/展示量）等，进行假设检验，从而得出那个方案更好

ABtest原理很简单。ABtest的难度主要在开发上：开发新版本、进行测试、测试数据回传保存

二、AB Test步骤

ABtest本质上是一个两总体假设检验问题，要检验A、B两个版本是否有显着区别。

两总体假设检验步骤：

第一步：确定对象和指标。明确要检验的A、B两个对象，版本。以及要检验的指标，是CTR，还是客单价，ARPU

第二步：给出原假设/备择假设

第三步：选择检验统计量，t 还是F？（t是总体方差未知或小样本，用样本方差代替总体方差。F是总体方差或大样本）

第四步：埋点，获取数据。计算统计量，明确A,B版本是否有显着区别。p值小于显着性水平0.05则推翻原假设

确定目标 --> 确定最小样本量 --> 确认流量分割方案 --> 实验上线 --> 规则校验 --> 数据收集 --> 效果检验

三、AB Test例子

某电商平台，想提升用户客单价，运营部门做了两套A、B激励方案，想将流量分成相同的两批测试下效果。已选出两组各12名用户，测试用户客单价如下

H0：方案A客单价均值=方案B客单价均值

H1：两者不相等

解读结论

既然方案A与方案B不同，A的均值又高于B，那么就认为A更好

三、AB Test的局限性

AB Test要求数据充足、开发资源充足的时候，才能完美落地

且AB测试得到的结果是更优的方案，而不是最优，所以只能作为一种验证性的工具和方法，要得到最优，不可能通过做很多次AB Test，这样成本太大

A/B测试只有在 你要测的KPI指标 可以被电脑量化 时适用，对于声誉，公关等不适用

四、面试题

Q1：什么场景可以做AB测试？

产品迭代场景：界面优化、增加功能

策略优化场景：运营策略优化，算法策略优化（推荐算法）

检验场景：新功能推出，30天内的DAU增加了，那么要通过假设检验来测试这个结果是否显着

Q2：为什么要进行ABtest

APP想要存活及增长，精细化运营就变成了必须。往往产品的认知并不是用户的认知，所以我们需要去测试，去实验。类似于医学中的“双盲实验”

Q3：AB Test需要多大的样本？AB Test需要做多久是如何确定的？如果计划做20天，第10天时感觉结果显着，能不能停止测试？

样本量        计算公式： 

Q4：做AB实验的时候，数据对比上涨25%，判定为效果显着，但上线后效果不好，为什么？

样本量不足，结果是随机波动导致

实验时间太短，用户由于新鲜感表现出不可持续的行为

实验人群不等于上线人群

外部环境变化，比如打车场景下，下雨和下雪会导致订单量激增

Q5：谈谈第一类错误，第二类错误

互联网产品案例中，第一类错误（拒真错误）：本来是一个好的产品，它本来可以给我们带来收益，但是由于我们统计的误差，导致我们误认为它并不能给我们带来收益。

第二类错误代表的是一个功能改动，本来不能给我们带来任何收益，但是我们却误认为它能够给我们带来收益。

Q6：流量分割有哪两种方式？

Q7：假设检验如何选取统计量？

Q7：ABTest有哪些注意事项？

一些效应

① 网络效应：

主要是因为对照组和实验组在一个社交网络导致。如果微信改动了某一个功能，这个功能让实验组用户更加活跃，发更多朋友圈。但是实验组用户的好友可能在对照组，实验组发的多，对照组用户可能就刷朋友圈刷的多，所以本质上对照组用户也受到了新功能的影响，那么ABTest就不再能很好的检测出相应的效果

解决办法：从地理上隔绝用户

② 学习效应：

主要是用户的好奇心理导致。比如产品将某个按钮从暗色调成亮色。很多用户刚刚看到，会有个新奇心里，去点击该按钮，导致按钮点击率在一段时间内上涨，但是长时间来看，点击率可能又会恢复到原有水平

解决方法：一是把时间拉长。二是只看新用户的数据

Q7：如果样本量不足该怎么办

只能通过拉长时间周期，通过累计样本量来进行比较

Q8：是否需要上线第一天就开始看效果？

在做AB测试时，尽量设定一个测试生效期，这一般是用户的一个活跃周期。如用户活跃间隔是7天，那么生效期为7天，如果是一个机酒app，用户活跃间隔是30天，那生效期为30天

BOUNUS:

ABtest实验可以分成两种，客户端client实验和服务端server实验

客户端实验一般来说只是UI上的实验，纯粹是展示端的策略；

而服务端的实验是返回给client数据的内容做实验，比如推荐的策略，算法策略等

⑧ 经典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;

}

⑨ 如何准备算法面试

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

!--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 复用性

⑩ 经典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;

}