面试10大算法汇总+常见题目解答

标签: 面试 算法 常见 | 发表时间:2013-12-16 18:03 | 作者:iwindyforest
出处:http://www.iteye.com

面试10大算法汇总+常见题目解答

 
 

最近更新: 2013年12月15日 持续更新…

英文版的 “面试10大算法汇总”日最高访问量已高达4,318次。这说明总结程序员面试算法有实际意义,比读算法书更有效。下面是中文版的10大算法汇总+有代表性的题目汇总。这些概念是专门为面试准备的,因为日常编程中我们很少会自己去写一个链表或者做一个图,也不会经常使用没有效率的递归。

以下用Java角度解释面试常见的算法和数据结构:字符串,链表,树,图,排序,递归 vs. 迭代,动态规划,位操作,概率问题,排列组合,以及一些需要寻找规律的题目。

1. 字符串和数组

首先需要注意的是和C++不同,Java字符串不是char数组。没有IDE代码自动补全功能,应该记住下面的这些常用的方法。

toCharArray() //获得字符串对应的char数组
Arrays.sort()  //数组排序
Arrays.toString(char[] a) //数组转成字符串
charAt(int x) //获得某个索引处的字符
length() //字符串长度
length //数组大小
substring(int beginIndex) 
substring(int beginIndex, int endIndex)
Integer.valueOf() //string to integer
String.valueOf() /integer to string

字符串和数组本身很简单,但是相关的题目需要更复杂的算法来解决。比如说动态规划,搜索,等等。

经典题目: Evaluate Reverse Polish Notation, Longest Palindromic Substring, Word Break, Word Ladder.

2. 链表

在Java中,链表的实现非常简单,每个节点Node都有一个值val和指向下个节点的链接next。

class Node {
	int val;
	Node next;
 
	Node(int x) {
		val = x;
		next = null;
	}
}

链表两个著名的应用是栈Stack和队列Queue。在Java标准库都都有实现,一个是Stack,另一个是LinkedList(Queue是它实现的接口)。

经典题目: Add Two Numbers, Reorder List, Linked List Cycle, Copy List with Random Pointer.

3. 树

这里的树通常是指二叉树,每个节点都包含一个左孩子节点和右孩子节点,像下面这样:

class TreeNode{
	int value;
	TreeNode left;
	TreeNode right;
}

下面是与树相关的一些概念:
二叉搜索树:左结点 <= 中结点 <= 右结点
平衡 vs. 非平衡:平衡二叉树中,每个节点的左右子树的深度相差至多为1(1或0)。
满二叉树(Full Binary Tree):除叶子节点以为的每个节点都有两个孩子。
完美二叉树(Perfect Binary Tree):是具有下列性质的满二叉树:所有的叶子节点都有相同的深度或处在同一层次,且每个父节点都必须有两个孩子。
完全二叉树(Complete Binary Tree):二叉树中,可能除了最后一个,每一层都被完全填满,且所有节点都必须尽可能想左靠。

经典题目: Binary Tree Preorder Traversal , Binary Tree Inorder Traversal, Binary Tree Postorder Traversal, Word Ladder.

4. 图

图相关的问题主要集中在深度优先搜索(depth first search)和广度优先搜索(breath first search)。深度优先搜索很简单,广度优先要注意使用queue. 下面是一个简单的用队列Queue实现广度优先搜索。

public class GraphTest {
	public static void breathFirstSearch(GraphNode root, int x){
		if(root.val == x)
			System.out.println("find in root");
 
		Queue queue = new Queue();
		root.visited = true;
		queue.enqueue(root);
 
		while(queue.first != null){
			GraphNode c = (GraphNode) queue.dequeue();
			for(GraphNode n: c.neighbors){
 
				if(!n.visited){
					System.out.print(n + " ");
					n.visited = true;
					if(n.val == x)
						System.out.println("Find "+n);
					queue.enqueue(n);
				}
			}
		}
	}
}

经典题目: 复制图(Clone Graph)

5. 排序

下面是不同排序算法的时间复杂度,你可以去wiki看一下这些算法的基本思想。

Algorithm Average Time Worst Time Space
冒泡排序(Bubble sort) n^2 n^2 1
选择排序(Selection sort) n^2 n^2 1
插入排序(Insertion sort) n^2 n^2  
快速排序(Quick sort) n log(n) n^2  
归并排序(Merge sort) n log(n) n log(n) depends

* 另外还有BinSort, RadixSort和CountSort 三种比较特殊的排序。

经典题目: Mergesort, Quicksort, InsertionSort.

6. 递归 vs. 迭代

对程序员来说,递归应该是一个与生俱来的思想(a built-in thought),可以通过一个简单的例子来说明。

问题:

有n步台阶,一次只能上1步或2步,共有多少种走法。

步骤1:找到走完前n步台阶和前n-1步台阶之间的关系。

为了走完n步台阶,只有两种方法:从n-1步台阶爬1步走到或从n-2步台阶处爬2步走到。如果f(n)是爬到第n步台阶的方法数,那么f(n) = f(n-1) + f(n-2)。

步骤2: 确保开始条件是正确的。

f(0) = 0;
f(1) = 1;

public static int f(int n){
	if(n <= 2) return n;
	int x = f(n-1) + f(n-2);
	return x;
}

递归方法的时间复杂度是指数级,因为有很多冗余的计算:

f(5)
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)

直接的想法是将递归转换为迭代:

public static int f(int n) {
	if (n <= 2){
		return n;
	}
 
	int first = 1, second = 2;
	int third = 0;
	for (int i = 3; i <= n; i++) {
		third = first + second;
		first = second;
		second = third;
	}
	return third;
}

这个例子迭代花费的时间更少,你可能复习一个两者的区别 Recursion vs Iteration

7. 动态规划

动态规划是解决下面这些性质类问题的技术:

  1. 一个问题可以通过更小子问题的解决方法来解决,或者说问题的最优解包含了其子问题的最优解
  2. 有些子问题的解可能需要计算多次
  3. 子问题的解存储在一张表格里,这样每个子问题只用计算一次
  4. 需要额外的空间以节省时间

爬台阶问题完全符合上面的四条性质,因此可以用动态规划法来解决。

public static int[] A = new int[100];
 
public static int f3(int n) {
	if (n <= 2)
		A[n]= n;
 
	if(A[n] > 0)
		return A[n];
	else
		A[n] = f3(n-1) + f3(n-2);//store results so only calculate once!
	return A[n];
}

8. 位操作

常用位操作符:

OR (|) AND (&) XOR (^) Left Shift (<<) Right Shift (>>) Not (~)
1|0=1 1&0=0 1^0=1 0010<<2=1000 1100>>2=0011 ~1=0

用一个题目来理解这些操作 -

获得给定数字n的第i位:(i从0计数并从右边开始)

public static boolean getBit(int num, int i){
	int result = num & (1<<i);
 
	if(result == 0){
		return false;
	}else{
		return true;
}

例如,获得数字10的第2位:

i=1, n=10
1<<1= 10
1010&10=10
10 is not 0, so return true;

9. 概率问题

解决概率相关的问题通常需要先分析问题,下面是一个这类问题的简单例子:

一个房间里有50个人,那么至少有两个人生日相同的概率是多少?(忽略闰年的事实,也就是一年365天)

计算某些事情的概率很多时候都可以转换成先计算其相对面。在这个例子里,我们可以计算所有人生日都互不相同的概率,也就是:365/365 * 364/365 * 363/365 * … * (365-49)/365,这样至少两个人生日相同的概率就是1 – 这个值。

public static double caculateProbability(int n){
	double x = 1; 
 
	for(int i=0; i<n; i++){
		x *=  (365.0-i)/365.0;
	}
 
	double pro = Math.round((1-x) * 100);
	return pro/100;
}
calculateProbability(50) = 0.97

10. 排列组合

组合和排列的区别在于次序是否关键。

11. 其他类型的题目

主要是不能归到上面10大类的。需要寻找规律,然后解决问题的。

经典题目: Reverse Integer

更新记录

算法汇总会不算更新,同时偶尔我会面试Google, Facebook, Amazon, Microsoft等等比较有名的公司,面经也会分享在这里。欢迎收藏本页。

微博: http://www.weibo.com/programcreek

12/06/2013 – 添加 “Add Two Numbers”, “Binary Tree Traversal(pre/in/post-order)”, “Find Single Number”,”Word Break”,”Reorder List”,”Edit Distance”, ” Reverse Integer”
12/14/2013 – 添加 “Copy List with Random Pointer”, “Evaluate Reverse Polish Notation”, “Word Ladder”.

引用:
1. Binary tree
2. Introduction to Dynamic Programming
3. UTSA Dynamic Programming slides
4. Birthday paradox
5. Cracking the Coding Interview: 150 Programming InterviewQuestions and Solutions, Gayle Laakmann McDowell
5. Counting sort
6. 感谢伯乐在线- 敏敏翻译
7. Top 10 Algorithms for Coding Interview

 

Related posts:

  1. Leetcode Solution of Iterative Binary Tree Postorder Traversal in Java
  2. Leetcode Solution of Binary Tree Inorder Traversal in Java
  3. Top 10 Algorithms for Coding Interview
  4. Leetcode Solution for Binary Tree Preorder Traversal in Java


已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [面试 算法 常见] 推荐:

面试10大算法汇总+常见题目解答

- - Java - 编程语言 - ITeye博客
面试10大算法汇总+常见题目解答. 最近更新: 2013年12月15日 持续更新…. 英文版的 “面试10大算法汇总”日最高访问量已高达4,318次. 这说明总结程序员面试算法有实际意义,比读算法书更有效. 下面是中文版的10大算法汇总+有代表性的题目汇总. 这些概念是专门为面试准备的,因为日常编程中我们很少会自己去写一个链表或者做一个图,也不会经常使用没有效率的递归.

面试常见十大类算法汇总

- - ITeye博客
在Java中,String是一个包含char数组和其它字段、方法的类. 如果没有IDE自动完成代码,下面这个方法大家应该记住: . String/arrays很容易理解,但与它们有关的问题常常需要高级的算法去解决,例如动态编程、递归等. 下面列出一些需要高级算法才能解决的经典问题:. 在Java中实现链表是非常简单的,每个节点都有一个值,然后把它链接到下一个节点.

我的Sql常见面试题(总结)

- - CSDN博客推荐文章
我开的  DBA群:225982985. 1.用一条SQL语句 查询出每门课都大于80分的学生姓名. 姓名 课程编号课程名称 分数. 1        2005001  张三 0001      数学    69. 2        2005002  李四 0001      数学    89. 3        2005001  张三 0001      数学    69.

10个常见的Redis面试

- -
导读:在程序员面试过程中Redis相关的知识是常被问到的话题. 作为一名在互联网技术行业打击过成百上千名的资深技术面试官,本文作者总结了面试过程中经常问到的问题. 作者简介:钱文品(老钱),互联网分布式高并发技术十年老兵,目前任掌阅科技资深后端工程师. 熟练使用 Java、Python、Golang 等多种计算机语言,开发过游戏,制作过网站,写过消息推送系统和MySQL 中间件,实现过开源的 ORM 框架、Web 框架、RPC 框架等.

常见 SQL 面试题:经典 50 例

- - SegmentFault 最新的文章
-- 含义是跳过2条取出1条数据,limit后面是从第2条开始读,读取1条信息,即读取第3条数据 select * from table limit 2 offset 1;. -- 含义是从第1条(不包括)数据开始取出2条数据,limit后面跟的是2条数据,offset后面是从第1条开始读取,即读取第2,3条.

常见程式算法推演

- hl - 博客园-首页原创精华区
 主要收集一些常见程序的练习题目,您可以借这些题目培养. 一些程序设计逻辑的感觉,对题目的分类只是个大概,方便索引而已,用 C  C#  Java    Python    Scala实现. 背包问题(Knapsack Problem). Eratosthenes筛选求质数. 最大公因数、最小公倍数、因式分解.

Javascript常见加密算法库

- - 脚本爱好者
CryptoJS (crypto.js) 为 JavaScript 提供了各种各样的加密算法. CryptoJS在Google Code上的主页是: http://code.google.com/p/crypto-js/.

面试失败之24点算法

- UnderSn0w - 博客园-首页原创精华区
  周一风尘仆仆(上午6点抵达成都)的去参加了凡客成都研发中心的面试,虽然经历一夜的折腾让我感觉头脑很不清醒,不过这种面试状态也不错,能让我深刻体验一下在不清醒状态下进行的思考和回答问题. 午饭过后便出了门,习惯了不堵车,突然觉得成都的交通真的很拥堵. 到达凡客成都研发中心填完表后等了大概10多分钟,面试官把我带进会议室,开始了面试.

我看面试时出(纯)算法题

- - 老赵点滴 - 追求编程之美
今天早上一边出门一边在平板上读了 左耳朵耗子的新文章《 为什么我反对纯算法面试题》,略有想法. 正逢外面暴雨如注,我就又回屋打开笔记本发了一些回复,特此整理一下. 为了避免有人扭曲我的看法,我先声明我并不是反对这篇文章,相反我是基本同意其中的观点,只不过会加以一些补充,把其中一些我认为有些过头的地方按一按.

大数据量的算法面试题

- - 编程 - 编程语言 - ITeye博客
作者:July、youwang、yanxionglu. 时间:二零一一年三月二十六日. 说明:本文分为俩部分,第一部分为10道海量数据处理的面试题,第二部分为10个海量数据处理的方法总结. 出处:http://blog.csdn.net/v_JULY_v. 第一部分、十道海量数据处理面试题. 1、海量日志数据,提取出某日访问百度次数最多的那个IP.