精选微软等公司数据结构+算法面试100题
前40道,第1题-40题,
[Quote=引用楼主 v_july_v 的回复:]
算法面试:精选微软等公司经典的算法面试100题 第1-40题
i am back,after one day。July、2010/10/23。
引用楼主 v_july_v 的回复:
算法面试:精选微软经典的算法面试100题
--------------
个人认为,算法永远是王道。
特此,精选微软等公司经典的算法面试100题,以飨各位。
希望,能有……
[/Quote]
前40道,第1题-40题,见下帖:
[推荐] [整理]算法面试:精选微软经典的算法面试100题[前40题]
http://topic.csdn.net/u/20101023/20/5652ccd7-d510-4c10-9671-307a56006e6d.html
贴一下上帖的,第36题-40题:
[Quote=引用 424 楼 v_july_v 的回复:]
引用 385 楼 v_july_v 的回复:
接下来,请看第36题-39题:
C/C++ code
36.引用自网友:longzuo
谷歌笔试:
n支队伍比赛,分别编号为0,1,2。。。。n-1,已知它们之间的实力对比关系,
存储在一个二维数组w[n][n]中,w[i][j] 的值代表编号为i,j的队伍中更强的一支。
所以w[i][j]=i 或者j,现在给出它们的出场顺序,并存储在数组order[n]中,
比如order[n] = {4,3,5,8,1......},那么第一轮比赛就是 4对3, 5对8。.......
胜者晋级,败者淘汰,同一轮淘汰的所有队伍排名不再细分,即可以随便排,
下一轮由上一轮的胜者按照顺序,再依次两两比,比如可能是4对5,直至出现第一名
编程实现,给出二维数组w,一维数组order 和 用于输出比赛名次的数组result[n],求出result。
37.
有n个长为m+1的字符串,
如果某个字符串的最后m个字符与某个字符串的前m个字符匹配,则两个字符串可以联接,
问这n个字符串最多可以连成一个多长的字符串,如果出现循环,则返回错误。
38.
百度面试:
1.用天平(只能比较,不能称重)从一堆小球中找出其中唯一一个较轻的,使用x次天平,
最多可以从y个小球中找出较轻的那个,求y与x的关系式
2.有一个很大很大的输入流,大到没有存储器可以将其存储下来,而且只输入一次,如何从这个输入
流中随机取得m个记录
3.大量的URL字符串,如何从中去除重复的,优化时间空间复杂度
39.
网易有道笔试:
(1).
求一个二叉树中任意两个节点间的最大距离,
两个节点的距离的定义是 这两个节点间边的个数,
比如某个孩子节点和父节点间的距离是1,和相邻兄弟节点间的距离是2,优化时间空间复杂度。
(2).
求一个有向连通图的割点,割点的定义是,如果除去此节点和与其相关的边,
有向图不再连通,描述算法。
40.百度研发笔试题
引用自:zp155334877
1)设计一个栈结构,满足一下条件:min,push,pop操作的时间复杂度为O(1)。
2)一串首尾相连的珠子(m个),有N种颜色(N<=10),
设计一个算法,取出其中一段,要求包含所有N中颜色,并使长度最短。
并分析时间复杂度与空间复杂度。
3)设计一个系统处理词语搭配问题,比如说 中国 和人民可以搭配,
则中国人民 人民中国都有效。要求:
*系统每秒的查询数量可能上千次;
*词语的数量级为10W;
*每个词至多可以与1W个词搭配
当用户输入中国人民的时候,要求返回与这个搭配词组相关的信息。
............
[/Quote]
--------------------------------------------------
后20道,第41题-60题,如下:
41.求固晶机的晶元查找程序
晶元盘由数目不详的大小一样的晶元组成,晶元并不一定全布满晶元盘,
照相机每次这能匹配一个晶元,如匹配过,则拾取该晶元,
若匹配不过,照相机则按测好的晶元间距移到下一个位置。
求遍历晶元盘的算法 求思路。
42.请修改append函数,利用这个函数实现:
两个非降序链表的并集,1->2->3 和 2->3->5 并为 1->2->3->5
另外只能输出结果,不能修改两个链表的数据。
43.递归和非递归俩种方法实现二叉树的前序遍历。
44.腾讯面试题:
1.设计一个魔方(六面)的程序。
2.有一千万条短信,有重复,以文本文件的形式保存,一行一条,有重复。
请用5分钟时间,找出重复出现最多的前10条。
3.收藏了1万条url,现在给你一条url,如何找出相似的url。(面试官不解释何为相似)
45.雅虎:
1.对于一个整数矩阵,存在一种运算,对矩阵中任意元素加一时,需要其相邻(上下左右)某一个元素也加一,
现给出一正数矩阵,判断其是否能够由一个全零矩阵经过上述运算得到。
2.一个整数数组,长度为n,将其分为m份,使各份的和相等,求m的最大值
比如{3,2,4,3,6} 可以分成{3,2,4,3,6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3
46.搜狐:
四对括号可以有多少种匹配排列方式?比如两对括号可以有两种:()()和(())
47.创新工场:
求一个数组的最长递减子序列 比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,4,3,2}
48.微软:
一个数组是由一个递减数列左移若干位形成的,比如{4,3,2,1,6,5}
是由{6,5,4,3,2,1}左移两位形成的,在这种数组中查找某一个数。
49.一道看上去很吓人的算法面试题:
如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)
50.网易有道笔试:
1.求一个二叉树中任意两个节点间的最大距离,两个节点的距离的定义是 这两个节点间边的个
数,
比如某个孩子节点和父节点间的距离是1,和相邻兄弟节点间的距离是2,优化时间空间复杂度。
2.求一个有向连通图的割点,割点的定义是,
如果除去此节点和与其相关的边,有向图不再连通,描述算法。
51.和为n连续正数序列。
题目:输入一个正数n,输出所有和为n连续正数序列。
例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5、4-6和7-8。
分析:这是网易的一道面试题。
52.二元树的深度。
题目:输入一棵二元树的根结点,求该树的深度。
从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的
深度。
例如:输入二元树:
10
/ \
6 14
/ / \
4 12 16
输出该树的深度3。
二元树的结点定义如下:
struct SBinaryTreeNode // a node of the binary tree
{
int m_nValue; // value of node
SBinaryTreeNode *m_pLeft; // left child of node
SBinaryTreeNode *m_pRight; // right child of node
};
分析:这道题本质上还是考查二元树的遍历。
53.字符串的排列。
题目:输入一个字符串,打印出该字符串中字符的所有排列。
例如输入字符串abc,则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
分析:这是一道很好的考查对递归理解的编程题,
因此在过去一年中频繁出现在各大公司的面试、笔试题中。
54.调整数组顺序使奇数位于偶数前面。
题目:输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,
所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
55.
题目:类CMyString的声明如下:
class CMyString
{
public:
CMyString(char* pData = NULL);
CMyString(const CMyString& str);
~CMyString(void);
CMyString& operator = (const CMyString& str);
private:
char* m_pData;
};
请实现其赋值运算符的重载函数,要求异常安全,即当对一个对象进行赋值时发生异常,
对象的状态不能改变。
56.最长公共字串。
题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,
则字符串一称之为字符串二的子串。
注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。
请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。
例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,
则输出它们的长度4,并打印任意一个子串。
分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,
因此一些重视算法的公司像MicroStrategy都把它当作面试题。
July声明:17:02:53 2010-11-09
57.用俩个栈实现队列。
题目:某队列的声明如下:
template<typename T> class CQueue
{
public:
CQueue() {}
~CQueue() {}
void appendTail(const T& node); // append a element to tail
void deleteHead(); // remove a element from head
private:
T> m_stack1;
T> m_stack2;
};
分析:从上面的类的声明中,我们发现在队列中有两个栈。
因此这道题实质上是要求我们用两个栈来实现一个队列。
相信大家对栈和队列的基本性质都非常了解了:栈是一种后入先出的数据容器,
因此对队列进行的插入和删除操作都是在栈顶上进行;队列是一种先入先出的数据容器,
我们总是把新元素插入到队列的尾部,而从队列的头部删除元素。
58.从尾到头输出链表。
题目:输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析:这是一道很有意思的面试题。
该题以及它的变体经常出现在各大公司的面试、笔试题中。
59.不能被继承的类。
题目:用C++设计一个不能被继承的类。
分析:这是Adobe公司2007年校园招聘的最新笔试题。
这道题除了考察应聘者的C++基本功底外,还能考察反应能力,是一道很好的题目。
60.在O(1)时间内删除链表结点。
题目:给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函数的声明如下:
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
分析:这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应
速度,更重要的是,还能考察我们对时间复杂度的理解。
-----------------------------------
整理资源,下载地址:
[第1题-60题汇总]微软等数据结构+算法面试100题
http://download.csdn.net/source/2826690
[答案V0.2版]精选微软数据结构+算法面试100题[前20题]--答案修正
http://download.csdn.net/source/2813890
//此份答案是针对最初的V0.1版本,进行的校正与修正。
[答案V0.1版]精选微软数据结构+算法面试100题[前25题]
http://download.csdn.net/source/2796735
[第二部分]精选微软等公司结构+算法面试100题[前41-60题]:
http://download.csdn.net/source/2811703
[第一部分]精选微软等公司数据结构+算法经典面试100题[1-40题]
http://download.csdn.net/source/2778852
更多资源,下载地址:
http://v_july_v.download.csdn.net/