`
v_JULY_v
  • 浏览: 69356 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
文章分类
社区版块
存档分类
最新评论

[整理II]精选微软等公司数据结构+算法面试100题 [第41-60题]

阅读更多

精选微软等公司数据结构+算法,经典面试100题 [第1题-第60题]

-------- 首次公布

July声明:首次发布。请尊重作者。

20:38:53 2010-10-29

----------------------------------------------------

前40题:

[整理I]精选微软等公司数据结构+算法面试100题 [第1-40题]
http://blog.csdn.net/v_JULY_v/archive/2010/10/27/5968678.aspx

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-54-67-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,则输出由字符abc所能排列出来的所有字符串abcacbbacbcacabcba

分析:这是一道很好的考查对递归理解的编程题,

因此在过去一年中频繁出现在各大公司的面试、笔试题中。

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.最长公共字串。

题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,

则字符串一称之为字符串二的子串。

注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。

请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。

例如:输入两个字符串BDCABAABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,

则输出它们的长度4,并打印任意一个子串。

分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,

因此一些重视算法的公司像MicroStrategy都把它当作面试题。

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.由于其中有些题目搜集于网络。有的流传甚广,个别题,我也无法考究究竟最初源自哪里。

但,所有资料如此精选整理,的确是出自于我手。且题目的答案由我个人和一些网友完成。

如此,我自称为作者,我想并不过分。

2.作者本人July对以上所有任何资料享有版权。转载请注明出处。谢谢。July。

分享到:
评论

相关推荐

    [最新答案V0.4版]微软等数据结构+算法面试100题[第41-60题答案]

    微软等公司数据结构+算法面试100题之第41-60题答案 --- 答案V0.4版 My Blog:http://blog.csdn.net/v_JULY_v 微软等100题系列,整理资源下载地址:题目系列: 1.[最新整理公布][汇总II]微软等数据结构+算法面试100...

    [最新整理]微软等公司数据结构+算法面试100题[第1-80题

    - **描述**:“[汇总II][最新整理]微软等公司数据结构+算法面试100题[第1-80题,值得珍藏]” **解读**:标题和描述都提到了这是针对微软等公司面试时常见的数据结构与算法问题的汇总,特别标注了“最新整理”和...

    [最新整理公布][汇总II]微软等数据结构+算法面试100题[第1-80题]

    以上四个知识点覆盖了从二叉树转换到双向链表、特殊栈的设计、求解最大子数组和、以及在二叉树中寻找特定路径等问题,这些问题是数据结构与算法面试中的常见题型,对于理解基本的数据结构原理及其应用有着重要的意义...

    [汇总II][最新整理]微软等公司数据结构%2B算法面试100题[第1-80题].pdf

    【知识点详解】 1. **二元查找树转换成排序双向链表** 二元查找树(Binary Search Tree,BST)是一种特殊的树结构,每个节点的左子树...同时,提供的资源链接可以帮助深入学习和实践这些面试题,提高解决问题的能力。

    Routing+TCP+IP+Volume+II--英文.rar

    Routing+TCP+IP+Volume+II--英文.rar

    leetCode 面试高频算法整理-2020

    2020高频面试算法整理 leetcode ,18个大类,80+到常见算法题。 1.热身题|1)查找唯一数字|2)查找N/2数字|3)判断数字是否存在|4)合并二叉树|5)泡鸡蛋问题|2.互联网公司最常见的面试算法题有哪些?|3.TOP INTERVIEW ...

    2008-数据结构与算法-期末试题B1

    【数据结构与算法期末试题解析】 1. 对称矩阵压缩存储:在10阶对称矩阵中,元素85a位于第8行第5列,由于是对称矩阵,所以存储时只需要存储下三角或上三角部分,对于主序存储,地址计算公式通常为(行下标-1)*阶数+列...

    面试知识点总结--java笔试算法题及答案.pdf

    在 Java 中,字符串分割算法是非常常见的面试题之一。本文中提供了一个使用 StringTokenizer 类实现字符串分割的示例代码,然而,该方法已不再被推荐使用,取而代之的是使用 String 类的 split 方法,该方法更简洁、...

    无人机四轴项项目源码+项目说明,stm32主控,固件库编程,移植ucos ii 操作系统,最终实现飞机可以起飞的完整项目.zip

    这是一个无人机四轴项项目,使用stm32 作为主控,使用固件库编程,移植ucos ii 操作系统,最终实现飞机可以起飞的完整项目 ## 所使用的硬件: 1. STM32 f401 开发版 2. ESP8266-01s wifi 模块 3. OLED ssd1305 4....

    CANalyst-II+用户手册

    CANalyst-II+是一款高性能的CAN-bus总线分析仪,能够对CAN总线进行实时监控、数据记录、分析和调试。该设备采用先进的硬件架构和软件平台,能够满足多种应用场景下的需求。 1.2 功能特点 CANalyst-II+拥有以下功能...

    【驱动程序】USBCAN-I_I+_II_II+_2A_I-MINI驱动安装.zip

    USBCAN-I/I+ II/II+ 2A I-MINI是一款由周立功公司研发的专业CAN总线接口设备,它通过USB接口与计算机连接,提供对CAN(Controller Area Network)网络的访问。该设备广泛应用于汽车电子、工业自动化、楼宇自动化等...

    数据结构和算法试题-总共1000多页带目录

    这本1000多页的PDF文档是关于数据结构和算法题解的集合,它涵盖了计算机科学与技术领域的核心内容。文档分为多个章节,每个章节专注于不同算法或数据结构的详细解析和应用实例。以下将详细介绍文档中提到的知识点。 ...

    【驱动程序】USBCAN-I_I+_II_II+_2A_I windows-all驱动安装.zip

    【驱动程序】USBCAN-I/I+/II/II+/2A_I windows-all驱动安装.zip是一个包含周立功CAN盒子驱动的压缩包文件,主要用于解决USBCAN系列接口设备在Windows操作系统上的连接和通信问题。该驱动程序适用于多种Windows版本,...

    数据结构与算法分析(Java版)

    ### 数据结构与算法分析(Java版)核心知识点详解 #### 一、概述 《数据结构与算法分析(Java版)》是一本针对Java语言的数据结构和算法的经典教材,由Robert Lafore编写,出版于1998年。本书旨在帮助读者理解和...

    遗传算法代码(NSGA-II)

    在众多的遗传算法变种中,非支配排序遗传算法第二代(Nondominated Sorting Genetic Algorithm II, NSGA-II)是目前最常用且最有效的之一。本篇将详细介绍NSGA-II的基本原理及其在VC++6.0环境下的实现。 **一、NSGA...

    算法笔试题:(Python实现)—— 算法面试题汇总

    算法笔试题:(Python实现)—— 算法面试题汇总算法笔试题:(Python实现)—— 算法面试题汇总开始之前Python实现只出现一次的数字多数元素搜索二维矩阵 II合并两个有序数组鸡蛋掉落字符串Python实现验证回文串...

Global site tag (gtag.js) - Google Analytics