面试算法机器学习July西电华为创新俱乐部2014-9-3,晚7:00~9:？2本次讲座大纲•第一部分、面试–笔试面试考什么–解决笔试面试题的常用算法–常用算法的时间复杂度–O(N)时间复杂度内能解决的问题•第二部分、算法–如何学习算法•循序渐进（KMP）•相互串联（以Trie树、后缀树，贪心、动态规划为例）•追本溯源（二叉树、红黑树、2-3-4树、B树为例）–海量数据处理面试题•十种解决之道•第三部分、机器学习–SVM的简单介绍，与SMO的简单推导3以前的不足•对着PPT一本正经念到底•堆砌知识、没有要害•100页PPT•PPT上字多、不够一目了然•体力不支、互动太少4第一部分、面试5笔试面试考什么6笔试偏基础•语言基础inthope;int*hope;double(*p)[3];void(*func)();•操作系统–线程与进程的区别–产生死锁的条件•如何规避死锁–C++内存分配•堆、栈、自由存储区、全局/静态存储区，常量存储区•网络协议–TCP建立连接的三次握手•数据库•概率论与数理统计–推荐《数理统计学简史》7面试偏算法•数据结构上的增删改查–查找、遍历、排序•算法–分治、递归、回溯–贪心、动态规划•海量数据处理8基于各个数据结构上的增删改查•字符串–字符串库函数的编写，例如atoi等–字符串查找、翻转、匹配•数组–查找（如二分查找、杨氏矩阵查找）•链表–翻转、遍历、查找、删除、合并•Hash表–查找•树–遍历（前序、中序、后序）–set、map–高级树的查找（红黑树、B树、R树）•图–遍历–查找（DFS、BFS）–最短路径算法9知道了考什么，怎么破10笔试面试常用算法•穷举（递归回溯）——“万能的”–求n个数的全排列&8皇后（N皇后问题）•分治–分而治之，然后归并•递归回溯–DFS•空间换时间–hashtable•巧用数据结构–堆•能排序，考虑排序–前后两个指针往中间扫–若已经排好序，想想有无必要二分•不能排序–贪心•最小生成树Prim,Krusal•最短路dijkstra–动态规划•如01背包问题，每一步都在决策•细节处理–注意边界条件11各类算法的时间复杂度12O(1)到O(nlogn)•O(1)–基本运算，＋，－，＊，／，%，寻址–Hash表的期望复杂度•O(logn)–二分查找•O(n1/2)–枚举约数•O(n)–线性查找–建立堆•O(nlogn)–归并排序–快速排序的期望复杂度–基于比较排序的算法下界13O(n2)到O(nn)•O(n2)–集合里枚举所有二元组、朴素最近点对•O(n3)–集合里枚举三元组、Floyd最短路、普通矩阵乘法•O(2n)–枚举全部的子集•O（2nn)–TSP的动态规划算法•O(n!)–枚举全排列•O(nn)–枚举[1..n]的n维数组的全部元素……•总结–O(1)defabc）•X：abc，Y：def；•X->X^T，得：abc->cba；Y->Y^T，得：def->fed•X^TY^T，得到：cbafed->defabc，即(X^TY^T)^T=YX18寻找最小的k个数•输入1，2，3，4，5，6，7和8这8个数字•请输出其中最小的4个数字：1，2，3和419寻找和为定值的两个数•输入数组1、2、4、7、11、15和数字15•由于4+11=15，因此输出4和11•解答：–百试不厌：暴力穷举–如果无序，先排序，排完序后，ij前后两个指针往中间扫20编程艺术github21第二部分、算法22如何学习算法？23算法学习方法论•基础很重要•学习什么，心中有大纲•算法解决什么问题，解决策略是什么–广搜•一层一层往外遍历，寻找最短路径•策略：队列–最小生成树•最小代价连接所有点•策略：贪心（Prim：贪心+权重队列）–Dijkstra•寻找单源最短路径•策略：贪心+非负权重队列–Floyd•多结点对的最短路...
VIP
